リンク先は各 Award の受賞者一覧ページ, Project Euler サイトにログインした状態で閲覧可能です. 進行状況確認ページ(Progress)で表示されている表に準じています。統計ページ(Statistics)に表示される表とは並びが異なるのでご注意下さい。↑

Problem Solving Awards †

(* difficulty explorer, coquering difficultiesが増えている)

Forum Post Awards

• この "Forum" とは正答後に閲覧, 投稿することができる問題, 解法, プログラミング議論用フォーラムのことです. Project Euler のサイトフォーラム, にはがありますが, これとは異なるので注意.

• 問題発表後, 冒頭100件の投稿が自動的に永久保存ポスト (permanent post) にされ, その後は最新100件の投稿より古い投稿は, 管理者が手動で永久保存ポストにしない限り, 自動的に削除されます.

• "kudo" とはいわゆる投稿評価ポイントです. 投稿者には問題毎に5個の kudo 投票権が与えられ, ためになる, 熟慮されていると思う投稿に投票することができます.

Project Eulerとは何ですか？

Project Eulerとは挑戦しがいのある数学/コンピュータプログラミングの問題集で、単なる数学的洞察だけではこれを解くことはできません。数学の知識があれば簡潔かつ効率的に問題を解くことができますが、多くの場合はコンピュータとプログラムの技能が必要です。

Project Eulerを開始し、また継続している動機は、未知の分野を探索し、愉快で楽しいコンテキストから新しい概念を学ぼうという探究心のためのプラットホームを提供することです。

どの問題から始めるべきですか？

それはあなたのもつ背景知識によります。問題の一覧表が２つあります。最近の問題リスト(Recent)には、最近公表された最新10問があります。あなたがProject Euler初心者なら、ここの問題の様々な問題の種類や難易度の感じをつかむために、アーカイブ(Archive)から始めるのがよいでしょう。

初めの100問あたりは、おおむねそれ以降の問題より易しいと考えられます。アーカイブの問題の一覧表には、それぞれの問題を解いた人数を示しています。一般的に、問題を解いた人数が多いほど、その問題は易しいと言えるでしょう。さらに、難易度評価システムもどこから手を付けるかの目安になるでしょう。アーカイブの表は番号(ID)、解いた人数(Solved By)、難易度(Difficulty)順に並べ替えることができます。

プログラムを書いたのですが、計算が終わるのに何日もかかってしまいます。

そんなはずはありません。それぞれの問題は「1分ルール」に基づいて作られています。つまり、難しい問題の場合、正しいアルゴリズムを考えるのには何時間もかかるかもしれませんが、どんなに難しい問題であっても、効率的な実装ができれば、そこそこの性能のコンピュータでも1分以内に答えを算出できるようにしています。

計算時間が1分以上かかってしまうのはダメですか？

それは気にしなくてかまいませんが、問題に立ち戻ってアプローチを改善させる動機になります。問題を解くとその問題に関連する掲示板にアクセスできるようになるので、そこで他の人のやり方をみることができるということを覚えておいて下さい。

検索エンジンを使って問題を解いてもよいですか？

インターネットを使って検索することは奨励されています。それによって多くの問題の下に隠された数学的な宝物が見つかることがあるからです。しかし、アイデアを検索することと、他所のウェブサイトで見つけた答えをただ使うことは紙一重です。クロスワードの答えをコピー機で複写したならば、あなたは何も達成していません。

自分のプログラムを10回見直したのですが、それでも答えが間違っていると言われてしまいます。問題が間違っているのでは？

新しく発表された問題では小さな間違いが入り込むことが十分ありえます。あるいは言葉遣いが曖昧であったり、説明が十分でないのかもしれません。しかし, 多くの人が問題を解いている中でただ一人10回間違いに突き当たるのは、あなたが間違っているのにもかかわらず、何か他のことのせいにしている可能性が高いでしょう。

問題を解く上で何かヒントはありますか？

問題の細部を注意深く読み、与えられた例を心にとどめて下さい。問題の裏に潜むアイデアに触れるために紙とペンで実験をおこなってください。もしも問題のアイデアがあなたにとって初めてのものだったら、インターネットや本で背景知識を得て下さい。問題には何を参照すべきかのヒントが載っているはずです。簡単な場合のプログラムを書き、例に示されている結果と一致することを確認してください。問題を正確に理解し、正しい方向に向かっていることが確認できるでしょう。このような試行から、最終結果を計算するのにかかる時間を推定してください。もし, その時間が1分を大きく上回るようであるのならば、もう一度戦略を練り直して下さい。

レベルとアワードとは何ですか？

25問解答するごとにレベルが1つ上がっていき、これを短期間の目標にすることで励みとすることができます。アワードは様々な条件により獲得できます。獲得する方法を知りたければ、のページに行くと現在用意されているアワードの完全なリストを見ることができます。レベル、アワードともに、統計ページの画像をクリックすればレベル別、あるいは特定のアワードを獲得したメンバーを確認することができます。

それぞれの問題には掲示板があるとのことですが、なぜ私はアクセスできないのでしょう？

問題の掲示板は正答しないとアクセスできません。アクセスすれば、他のメンバーがどのように問題を解いたか、手法に対する議論を見ることができ、あなたの考えを共有することができます。

名声(Kudos)とは何ですか？

名声の目的は、役に立つ、有用で、よく練られた投稿を見つけたことを投稿者や他のメンバーに知らせることです。各問題の掲示板につき5まで名声ポイントを付与することができます。ですので本当に価値があると思う投稿にのみ使用してください。

議論スレッドにはなぜ消滅する投稿があるのですか?

最初の100件の投稿のみが自動的に永続化されます. その後は最新の100個の投稿のみが保持されます; 古い投稿は自動的に削除されます. ただし, もし素晴らしい投稿がされた場合は管理者がそれを永続化することがあるかもしれません. Kudosはメンバーが有益な投稿を見つけ, 保存すべきであると管理者に知らせることのできる便利な方法です.

他に議論できる場所はないですか?

ありますよ! 一般的な議論に参加したり, 問題の解法やプログラミングのアイデアを共有したり, ウェブサイトについての提案をしたり, 問題の大まかなヒントや解説について聞くために, メンバーが投稿できる設定になっている代わりのphpBBフォーラムがあります. フォーラムへのリンクは下記に, しかしProject Eulerのサイトのアカウントから自動的にフォーラムのアカウントが移行して作られるわけではないので, フォーラムでアカウントを作成する必要があることに注意してください.

フォーラムウェブアドレス :

このフォーラムでのあなたの投稿はすべてのメンバーに見えています, ですので問題の解き方を明確に暴露してしまうことが無いようよく考えて投稿する必要があることに注意してください.

問題XXXの解き方を十分会得しました, なので私の解き方をどこかに発表してもよいですか?

あなたはすでに自分の質問に答えているように思います. しばらくの間取り組んだ問題を解き明かした時のなるほど!という瞬間より素晴らしいものはありません. 他の人にもこの瞬間を楽しんでもらうために私たちの考えを共有したいという善意であることも多いでしょう. しかし残念ながら, それは読者のためにはなりません. 真の学習とは積極的なプロセスであり, また発見のひらめきを経験するまでの長い道のりが一体どのようなものであるかを垣間見ることでもあります. あなたの高じた自尊心によって他の方からその経験を奪ったりしないようお願いします.

どのようにProject Eulerと連絡を取ったらよいですか?

Project Eulerのチームメンバーと連絡を取るには上記のphpBBフォーラムを用いるのが望ましい方法です. チームは定期的にフォーラムを確認しており, 大抵の問題であれば素早く効果的に対処できます. 代わりに, kevinsogo氏に新しい問題のアイデアを送る, あるいはeuler氏に緊急の技術的な問題について連絡できるページを使うことができます. 上記2つのカテゴリー以外のメッセージは無視されます.

このプロジェクトが始まったきっかけは何ですか?

Project EulerはColin Hughes(別名 euler)によりのサブセクションとして始められました. 当時, この手の問題にこれほどの人気がでるとは誰も思いませんでした. 開始以来, プロジェクトを発展させるためのメンバーの交流は続いています. Project Eulerは2006年に独自ドメインに移行しました.

Project Eulerは誰が運営していますか?

新しい問題のアイデアはメンバーで出しあっています. そのアイデアは有能な数学者やプログラマーによって煮詰められます. 端的に言えば, これらの人々がProject Eulerの運営者です.

Project Eulerに寄付することはできますか?

もちろんできます! Project Eulerはメンバーの持ち出しで運営されています. もしあなたが問題を楽しんで, 何か恩返しがしたいと思ったら, 寄付して頂けるのは大歓迎です.

(公式のaboutページにPaypal寄付ボタンが置かれています)

免責事項

創設以来, 多くの人たちの協力により, ここ数年Project Eulerの人気が非常に高まっています.

参加者はたいてい自分の成績を自慢したがるものです. 問題ページに設置されている掲示板はその最適の場所になっています. しかしその一方で, 人気の高まりは, 別の目的を持った人たちを惹きつけています. 多くのサイトが上記掲示板の代わりにProject Eulerの問題に対する解答を発表しており, どういうわけかそれらの解答を収集し提出して成績を自慢している人がいるようです.

こうした人たちを, 独力でProject Eulerを解いている参加者と確実に区別することは不可能です. Project Eulerのランキングは, こういうものだと解釈すべきです: その問題にメンバーが解答を提出し, 解答チェックで確認された正答数を表示したもの. 自力で達成したんだ, ということはメンバー自分自身が一番よくわかっています. 競争することにあまり重点を置き過ぎてしまうと, Project Eulerの目的の1つである問題を解くという楽しみを台無しにしてしまいます. そしてまた, 実績に対するメンバーからのいかなるクレームに対しても, Project Eulerが信用性を立証することはできません. 仮に重要だとしても, そうしたクレームを立証するには第三者による別の手段が必要になるでしょう.

少数の参加者の意図にかかわらず, 愉しみや教育のために質の高い問題を提供し続けることがProject Eulerの最大の目的です.

ログイン時に問題一覧下部に表示される注意事項

注記: この問題が解けないんだけど、とProject Eulerに連絡してこないでください。「解けない」ということは、つまり「解けていない」ということです!

Project Euler 有志による和訳Wiki をGitBookに写しているだけです。

ライセンス

CC BY-NC-SA 4.0です。

2020-7-29 GitBookからOpenSource活動として承認されました！

2020-7-16 和訳Wikiが消失していたことから、からサルベージする事業を始めました。

で公開しています。

単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.

1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1

0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある.

d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ.

正の整数を順に連結して得られる以下の10進の無理数を考える:

0.123456789101112131415161718192021...

(1文字おおきくして赤くする)

小数第12位は1である.

$d_n$で小数第$n$位の数を表す. $d_1 × d_{10} × d_{100} × d_{1000} × d_{10000} × d_{100000} × d_{1000000}$ を求めよ.

三角数の第$n$項は $t_n = n(n+1)/2$で与えられる. 最初の10項は

$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$

である.

単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は $19 + 11 + 25 = 55 = t_{10}$である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ.

16Kのテキストファイル words.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか?

$n$枚のコインを異なった方法で山に分ける場合の数を$p(n)$と表す。例えば5枚のコインを山に分ける異なったやり方は７通りなので$p(5)=7$となる。

OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

$p(n)$が100万で割り切れるような最小の$n$を求めよ。

左右どちらから読んでも同じ値になる数を回文数という。2桁の数の積で表される回文数のうち最大のものは 9009 = 91 × 99 である。

では、3桁の数の積で表される回文数の最大値を求めよ。

2520 は 1 から 10 の数字の全ての整数で割り切れる数であり、そのような数の中では最小の値である。

では、1 から 20 までの整数全てで割り切れる数の中で最小の正の数はいくらになるか。

最初の10個の自然数について、その二乗の和は

$1^2 + 2^2 + \dots + 10^2 = 385$

最初の10個の自然数について、その和の二乗は

$(1 + 2 + \dots + 10)^2 = 3025$

これらの数の差は $3025 - 385 = 2640$ となる。

同様にして、最初の100個の自然数について二乗の和と和の二乗の差を求めよ。

10未満の自然数のうち、3もしくは5の倍数であるものは3, 5, 6, 9の4つであり、これらの合計は23である。

同じようにして、1000未満の3か5の倍数である数の合計を求めよ。

13195の素因数は5, 7, 13, 29である。

600851475143 の素因数のうち最大のものを求めよ。

フィボナッチ数列の項は前の2つの項の和である。最初の2項を1, 2とすれば、最初の10項は以下の通りである。

$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$

数列の項の値が400万以下の、偶数値の項の総和を求めよ。

ピタゴラス数（ピタゴラスの定理を満たす自然数）とは、 $a < b < c$ で以下の式を満たす数の組である。

$a^2 + b^2 = c^2$

例えば $3^2 + 4^2 = 9 + 16 = 25 = 5^2$ である。

$a + b + c = 1000$ となるピタゴラスの三つ組が一つだけ存在する。 これらの積 $abc$ を答えよ。

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。

10 001 番目の素数を求めよ。

10以下の素数の和は $2 + 3 + 5 + 7 = 17$ である。

200万以下の全ての素数の和を求めよ。

であり, 各位の数字の和は となる.

同様にして, の各位の数字の和を求めよ.

注: も各位の数字の和に関する問題です。解いていない方は解いてみてください。

の格子のうち, 斜めに並んだ4つの数字が赤くマークされている.

(7行めの26から右下に63,78,14を赤くしたい)

それらの数字の積は となる.

上の の格子のうち, 上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものはいくつか?

以下の50桁の数字100個の合計の上から10桁を求めなさい。

正の整数に以下の式で繰り返し生成する数列を定義する.

n → n/2 (n が偶数)

n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

$13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1$

13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)

さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.

注意: 数列の途中で100万以上になってもよい

1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で $3 + 3 + 5 + 4 + 4 = 19$ の文字が使われている.

では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.

注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

次の1000桁の数字のうち、隣接する4つの数字の総乗の中で最大となる値は$9 \times 9 \times 8 \times 9 = 5832$である。

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

この1000桁の数字から13個の連続する数字を取り出して、それらの総乗を計算する。では、それら総乗のうち最大となる値はいくらか。

例：6桁の数123789から5個の連続する数字を取り出す場合、 $1 \times 2 \times 3 \times 7 \times 8$と$2 \times 3 \times 7 \times 8 \times 9$の二通りとなり、後者の$2 \times 3 \times 7 \times 8 \times 9=3024$が最大の総乗となる。

以下の三角形の頂点から下の行の隣接する数字を通って下まで移動するとき, その数値の和の最大値は23になる.

   3
  7 4
 2 4 6
8 5 9 3

(3,7,4,9という経路を赤くしめしたい）

この例では $3 + 7 + 4 + 9 = 23$.

以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.

              75
             95 64
            17 47 82
           18 35 87 10
          20 04 82 47 65
         19 01 23 75 03 34
        88 02 77 73 07 63 67
       99 65 04 28 06 16 70 92
      41 41 26 56 83 40 80 70 33
     41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
   70 11 33 28 77 73 17 78 39 68 17 57
  91 71 52 38 17 14 91 43 58 50 27 29 48
 63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.

(他ページへのリンク)

$2×2$ のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

では, $20×20$ のマス目ではいくつのルートがあるか.

次の情報が与えられている.

• 1900年1月1日は月曜日である.

• 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.

• 2月は28日まであるが, うるう年のときは29日である.

5000個以上の名前が書かれている46Kのテキストファイルnames.txtを用いる. まずアルファベット順にソートせよ.

のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.

たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは 3 + 15 + 12 + 9 + 14 = 53 という値を持つ. よってCOLINは 938 × 53 = 49714 というスコアを持つ.

ファイル中の全名前のスコアの合計を求めよ.

$n × (n - 1) × ... × 3 × 2 × 1$ を $n!$ と表す.

例えば, $10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800$ となる. この数の各桁の合計は $3 + 6 + 2 + 8 + 8 + 0 + 0 = 27$ である.

では, $100!$ の各位の数字の和を求めよ.

注: 問題16も各位の数字の和に関する問題です。解いていない方は解いてみてください。

$d(n)$ を $n$ の真の約数の和と定義する. (真の約数とは $n$ 以外の約数のことである. ) もし, $d(a) = b$ かつ $d(b) = a$ $(a ≠ b のとき)$ を満たすとき, $a$ と $b$ は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので $d(220) = 284$ である. また, 284 の約数は 1, 2, 4, 71, 142 なので $d(284) = 220$ である.

それでは10000未満の友愛数の和を求めよ.

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, $1 + 2 + 4 + 7 + 14 = 28$ であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, $1 + 2 + 3 + 4 + 6 = 16$ となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.

順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

012 021 102 120 201 210

になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?

フィボナッチ数列は以下の漸化式で定義される:$F_n = F_{n-1} + F_{n-2}$, ただし $F_1 = 1, F_2 = 1$.

最初の12項は以下である.

• $F_1 = 1$

• $F_2 = 1$

12番目の項, が3桁になる最初の項である.

1000桁になる最初の項の番号を答えよ.

オイラーは以下の二次式を考案している:

$n^2 + n + 41$

この式は, $n$ を$0$から$39$までの連続する整数としたときに40個の素数を生成する. しかし, $n = 40$ のとき $40^2 + 40 + 41 = 40(40 + 1) + 41$ となり41で割り切れる. また, $n = 41$ のときは $41^2 + 41 + 41$ であり明らかに41で割り切れる.

計算機を用いて, 二次式 $n^2 - 79n + 1601$ という式が発見できた. これは $n = 0$ から $79$ の連続する整数で80個の素数を生成する. 係数の積は, $-79 × 1601$ で $-126479$である.

さて, $|a| < 1000, |b| < 1000$ として以下の二次式を考える (ここで $|a|$ は絶対値): 例えば $|11| = 11, |-4| = 4$である.

$n^2 + an + b$

から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数 の積を答えよ.

1から初めて右方向に進み時計回りに数字を増やしていき, 5×5の螺旋が以下のように生成される:

(表のかきかたと赤色文字)

両対角線上の数字の合計は101であることが確かめられる.

の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか?

驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.

• $1634 = 1^4 + 6^4 + 3^4 + 4^4$

• $8208 = 8^4 + 2^4 + 0^4 + 8^4$

• $9474 = 9^4 + 4^4 + 7^4 + 4^4$

ただし, は含まないものとする. これらの数の和は である.

各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.

イギリスでは硬貨はポンド$£$とペンス$p$があり，一般的に流通している硬貨は以下の8種類である.

$1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)$.

以下の方法で£2を作ることが可能である．

$1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p$

これらの硬貨を使って$£2$を作る方法は何通りあるか?

すべての桁に $1$ から $n$ が一度だけ使われている$n$桁の数をパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.

7254 は面白い性質を持っている. $39 × 186 = 7254$ と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.

掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.

ヒント：いくつかの積は2通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.

100万未満の巡回素数はいくつあるか?

$2 ≤ a ≤ 5$ と $2 ≤ b ≤ 5$について, $a^b$ を全て考えてみよう:

• $2^2=4, 2^3=8, 2^4=16, 2^5=32$

• $3^2=9, 3^3=27, 3^4=81, 3^5=243$

• $4^2=16, 4^3=64, 4^4=256, 4^5=1024$

これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:

で同じことをしたときいくつの異なる項が存在するか?

n桁パンデジタルであるとは, 1からnまでの数を各桁にちょうど1つずつ持つこととする.

例えば2143は4桁パンデジタル数であり, かつ素数である. n桁（この問題の定義では9桁以下）パンデジタルな素数の中で最大の数を答えよ.

$585 = 1001001001_2$ (2進) は10進でも2進でも回文数である.

100万未満で10進でも2進でも回文数になるような数の総和を求めよ.

(注: 先頭に0を含めて回文にすることは許されない.)

$145$は面白い数である. $1! + 4! + 5! = 1 + 24 + 120 = 145$となる.

各桁の数の階乗の和が自分自身と一致するような数の和を求めよ.

注: $1! = 1$ と $2! = 2$ は総和に含めてはならない.

$49/98$は面白い分数である.「分子と分母からそれぞれ$9$を取り除くと, $49/98 = 4/8$ となり, 簡単な形にすることができる」と経験の浅い数学者が誤って思い込んでしまうかもしれないからである. (方法は正しくないが，$49/98$の場合にはたまたま正しい約分になってしまう．)

我々は $30/50 = 3/5$ のようなタイプは自明な例だとする.

このような分数のうち, 1より小さく分子・分母がともに2桁の数になるような自明でないものは, 4個ある.

その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

(言葉が微妙)

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

192 に 1, 2, 3 を掛けてみよう.

192 × 1 = 192 192 × 2 = 384 192 × 3 = 576

積を連結することで1から9のパンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ.

(pediaへのリンク、ちょうど一回なら書くか？)

同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である.

整数と $(1,2,...,n) \; (n > 1)$ との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?

次の級数の和は, $1^1 + 2^2 + 3^3 + \dots + 10^{10} = 10405071317$ である.

では, $1^1 + 2^2 + 3^3 + \dots + 1000^{1000}$ の最後の10桁を求めよ.

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

$9 = 7 + 2×1^2$ $15 = 7 + 2×2^2$ $21 = 3 + 2×3^2$ $25 = 7 + 2×3^2$ $27 = 19 + 2×2^2$ $33 = 31 + 2×1^2$

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

$14 = 2 × 7$ $15 = 3 × 5$

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

$644 = 2^2 × 7 × 23$ $645 = 3 × 5 × 43$ $646 = 2 × 17 × 19$

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?

1の位が3である2桁の数9つを*3と記す。それらのうち、13, 23, 43, 53, 73, 83の6つは素数である。

56**3の第3桁と第4桁に同じ数字を当てはめる。この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

公差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ.

• (i)3つの項はそれぞれ素数である.

• (ii)各項は他の項の置換で表される.

1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する.

それではこの数列の3つの項を連結した12桁の数を求めよ.

数1406357289は0から9のパンデジタル数である（0から9が1度ずつ現れるので）。この数は部分文字列が面白い性質を持っている。

$d_1$を上位1桁目、$d_2$を上位2桁目の数とし、以下順に$d_n$を定義する。この記法を用いると次のことが分かる。

• $d_2d_3d_4=406$ は 2 で割り切れる

• $d_3d_4d_5=063$ は 3 で割り切れる

• は 5 で割り切れる

• は 7 で割り切れる

• は 11 で割り切れる

• は 13 で割り切れる

• は 17 で割り切れる

このような性質をもつ0から9のパンデジタル数の総和を求めよ。

三角数, 五角数, 六角数は以下のように生成される.

であることが分かる.

次の三角数かつ五角数かつ六角数な数を求めよ.

辺の長さが $\{a,b,c\}$ と整数の3つ組である直角三角形を考え, その周囲の長さを $p$ とする. $p = 120$のときには3つの解が存在する:

$\{20,48,52\}, \{24,45,51\}, \{30,40,50\}$

$p ≤ 1000$ のとき解の数が最大になる $p$ はいくつか?

三角数の数列は自然数の和で表わされ, 7番目の三角数は $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$ である. 三角数の最初の10項は:

$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$

となる.

最初の7項について, その約数を列挙すると, 以下のとおり.

1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28

これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.

では, 500個より多く約数をもつ最初の三角数はいくつか.

五角数は $P_n = n(3n-1)/2$ で生成される. 最初の10項は

$1, 5, 12, 22, 35, 51, 70, 92, 117, 145, \dots$

である.

$P_4 + P_7 = 22 + 70 = 92 = P_8$ である. しかし差 $70 - 22 = 48$ は五角数ではない.

五角数のペア $P_j$ と $P_k$ について, 差と和が五角数になるものを考える. 差を $D = |P_k - P_j|$ と書く. 差 $D$ の最小値を求めよ.

12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

組み合わせでは, 以下の記法を用いてこのことを表す: $_5C_3 = 10$.

一般に, $r ≤ n$ について $\displaystyle _nC_r = \frac{n!}{r!(n-r)!}$ である. ここで, $n! = n×(n−1)×...×3×2×1, 0! = 1$ と階乗を定義する.

$n = 23$ になるまで, これらの値が100万を超えることはない: $_{23}C_{10} = 1144066$.

$1 ≤ n ≤ 100$ について, 100万を超える $_nC_r$ は何通りあるか?

素数41は6つの連続する素数の和として表せる:

$41 = 2 + 3 + 5 + 7 + 11 + 13$

100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

Googol ($10^{100}$)は非常に大きな数である: 1の後に0が100個続く. $100^{100}$は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも数字和 ( 桁の和 ) は1である.

$a, b < 100$ について自然数 $a^b$ を考える. 数字和の最大値を答えよ.

2の平方根は無限に続く連分数で表すことができる.

$\displaystyle \sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \dots}}} = 1.414213\dots$

最初の4回の繰り返しを展開すると以下が得られる.

$1 + \frac{1}{2} = \frac{3}{2} = 1.5$ $1 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5} = 1.4$ $1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12} = 1.41666\dots$ $1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}}} = \frac{41}{29} = 1.41379\dots$

次の3つの項は$99/70, 239/169, 577/408$である. 第8項は$1393/985$である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつあるか?

125874を2倍すると251748となる. これは元の数125874と順番は違うがちょうど同じ数字からなる。

$2x, 3x, 4x, 5x, 6x$ が $x$ と同じ数字からなるような最小の正整数 $x$ を求めよ.

カードゲームのポーカーでは, 手札は5枚のカードからなりランク付けされている. 役を低い方から高い方へ順に並べると以下である.

• 役無し(ハイカード): 一番値が大きいカード

• ワン・ペア: 同じ値のカードが2枚

• ツー・ペア: 2つの異なる値のペア

• スリーカード: 同じ値のカードが3枚

• ストレート: 5枚の連続する値のカード

• フラッシュ: 全てのカードが同じスート (注: スートとはダイヤ・ハート・クラブ・スペードというカードの絵柄のこと)

• フルハウス: スリーカードとペア

• フォーカード: 同じ値のカードが4枚

• ストレートフラッシュ: ストレートかつフラッシュ

• ロイヤルフラッシュ: 同じスートの10, J, Q, K, A

ここでカードの値は小さい方から2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, Aである. (訳注：データ中で10は'T'と表される)

もし2人のプレイヤーが同じ役の場合には, 役を構成する中で値が最も大きいカードによってランクが決まる: 例えば, 8のペアは5のペアより強い (下の例1を見よ). それでも同じランクの場合には (例えば, 両者ともQのペアの場合), 一番値が大きいカードによってランクが決まる (下の例4を見よ). 一番値が大きいカードが同じ場合には, 次に値が大きいカードが比べれられ, 以下同様にランクを決定する.

例:

には1000個のランダムな手札の組が含まれている. 各行は10枚のカードからなる (スペースで区切られている): 最初の5枚がプレイヤー1の手札であり, 残りの5枚がプレイヤー2の手札である. 以下のことを仮定してよい

• 全ての手札は正しい (使われない文字が出現しない. 同じカードは繰り返されない)

• 各プレイヤーの手札は特に決まった順に並んでいるわけではない

• 各勝負で勝敗は必ず決まる

1000回中プレイヤー1が勝つのは何回か? (訳注 : この問題においてA 2 3 4 5というストレートは考えなくてもよい)

47とその逆さ読みを足し合わせると$47 + 74 = 121$となり, 回文数になる.

全ての数が直ちに回文数になるわけではない. 349を考えよう,

1. $349 + 943 = 1292$,

2. $1292 + 2921 = 4213$

349は, 3回の操作を経て回文数になる.

まだ証明はされていないが, 196のようないくつかの数は回文数にならないと考えられている. 逆さ読みを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数でないと証明されていない数はLychrel数だと仮定する.

更に, 10000未満の数については，常に以下のどちらか一方が成り立つと仮定してよい.

1. 50回未満の操作で回文数になる

2. まだ誰も回文数まで到達していない

実際, 10677が50回以上の操作を必要とする最初の数である: 4668731596684224866951378664 (53回の操作で28桁のこの回文数になる).

驚くべきことに, 回文数かつLychrel数であるものが存在する. 最初の数は4994である.

10000未満のLychrel数の個数を答えよ.

素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の集合の和の中で最小である.

任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の集合の和の中で最小のものを求めよ.

1から始めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.

(表の書き方、素数を赤くする)

面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≈ 62%である.

渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

5桁の数 は自然数を5乗した数である. 同様に9桁の数 も自然数を9乗した数である.

自然数を 乗して得られる 桁の正整数は何個あるか?

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

平方根は連分数の形で表したときに周期的であり, 以下の形で書ける:

例えば, を考えよう.

となる.

この操作を続けていくと,

を得る.

操作を纏めると以下になる:

コンピュータの中では、文字にはそれぞれ一意のコードが割り当てられている。よく使われる標準としてASCII (American Standard Code for Information Interchange) がある。ASCIIでは、大文字のAは65、アスタリスク (*)は42, 小文字のkは107などと割り当てられている。

モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある. XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である. 65 XOR 42 = 107であり, 107 XOR 42 = 65である.

破られない暗号化のためには, 鍵は平文と同じ長さのランダムなバイト列でなければならない. ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある. また, もし一方が失われると, 暗号文を復号することは不可能になる.

悲しいかな, この手法はほとんどのユーザーにとって非現実的である. そこで, 鍵の変わりにパスワードを用いる手法が用いられる. パスワードが平文より短ければ (よくあることだが), パスワードは鍵として繰り返し用いられる. この手法では, 安全性を保つために十分長いパスワードを用いる必要があるが, 記憶するためにはある程度短くないといけない.

この問題での課題は簡単になっている. 暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIコードの和を求めよ.

立方数 $41063625 \; (345^3)$は, 桁の順番を入れ替えると2つの立方数になる: $56623104 \; (384^3)$ と $66430125 \; (405^3)$ である. $41063625$は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

$n$と$d$を正の整数として, 分数$n/d$を考えよう.$n<d$かつ$\textrm{gcd}(n,d)=1$のとき, 真既約分数と呼ぶ.

(説明なくHCFだったが、ググるとgcdの別名らしいので。)

$d ≤ 8$について既約分数を大きさ順に並べると, 以下を得る:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

3/7のすぐ左の分数は2/5である.

$d ≤ 1,000,000$について真既約分数を大きさ順に並べたとき, 3/7のすぐ左の分数の分子を求めよ.

よく知られているように, 自然数の平方根が整数ではないならば, それは無理数である.

そのような平方根の10進展開(decimal expansion)は繰り返しを持たない無限小数になる.

2の平方根は, 1.41421356237309504880...,であり, その頭から100桁の数字を合計すると475になる.

初めの100個の自然数の平方根のうち, 無理数について, それぞれの頭から100桁の数字を足した数の総和を求めよ.

下図の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる。

   3
  7 4
 2 4 6
8 5 9 3

(3,7,4,9を強調したい)

この例では 3 + 7 + 4 + 9 = 23

100行からなる三角形を持つ15Kのテキストファイル triangle.txt （右クリックして、『名前をつけてリンク先を保存』）の上から下までの最大合計を見つけよ。

注：これは Problem 18のずっと難しいバージョンである。 全部で$2^{99}$通りの組み合わせがあるので、この問題を解くのに全ての経路を試すことは不可能である！ 毎秒1兆($10^{12}$)本の経路を調べることができたとしても、全てを調べるには200億年以上かかるだろう。 この問題を解く効率的なアルゴリズムがある ;o)

オイラーのトーティエント関数$φ(n)$(ファイ関数とも呼ばれる) とは,$n$未満の正の整数で$n$と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので,$φ(9) = 6$となる.

ではの最大値はであることがわかる.

でが最大となる値を見つけよ.

2の平方根は無限連分数として書くことができる。

この無限連分数をと表記することもできる。は2が際限なく繰り返されることを示す。同様にである。

平方根の部分的な連分数の数列から良い有理近似が得られることが分かる.の近似分数について考えよう。

従って,

オイラーのトーティエント関数(ファイ関数とも呼ばれる) とは,未満の正の整数でと互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので,となる. 1 は全ての正の整数と互いに素であるとみなされる. よってである.

面白いことに,であり, はを置換したものとなっている.

でがを置換したものになっているもののうち,が最小となるを求めよ.

次の形式の, 2次のディオファントス方程式を考えよう:

たとえばのとき, を最小にする解はである.

が平方数のとき, 正整数のなかに解は存在しないと考えられる.

に対してを最小にする解は次のようになる:

とを正の整数として, 分数を考えよう. かつのとき, 真既約分数と呼ぶ.

について真既約分数を大きさ順に並べると, 以下を得る:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

この集合は21個の要素をもつことが分かる.

について, 真既約分数の集合は何個の要素を持つか?

ある長さの鉄線を折り曲げて3辺の長さが整数の直角三角形を作るとき, その方法が1通りしかないような最短の鉄線の長さは12cmである. 他にも沢山の例が挙げられる.

12 cm: (3,4,5) 24 cm: (6,8,10) 30 cm: (5,12,13) 36 cm: (9,12,15) 40 cm: (8,15,17) 48 cm: (12,16,20)

それとは対照的に, ある長さの鉄線 (例えば20cm) は3辺の長さが整数の直角三角形に折り曲げることができない. また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある.

120 cm: (30,40,50), (20,48,52), (24,45,51)

を鉄線の長さとする. 直角三角形を作るときに1通りの折り曲げ方しか存在しないようなの総数を答えよ.

145は各桁の階乗の和が145と自分自身に一致することで有名である.

169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは3つしか存在しない.

どのような数からスタートしてもループに入ることが示せる.

例を見てみよう.

69から始めた場合, 列は5つの循環しない項を持つ. また100万未満の数から始めた場合最長の循環しない項は60個であることが知られている.

100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?

下に示す図のようなものを"magic" 3-gon ringという. これは1～6の数字を当てはめて, 各列の数字の和が9となっている. これを例として説明する.

外側のノードのうち一番小さいものの付いた列(例では4,3,2)から時計回りに回ってそれぞれ列の数字を3つ連ねて説明する. 例えば例のものは4,3,2; 6,2,1; 5,1,3という組で説明することができる.

1～6の数字を当てはめて, 各列の数字の和が等しくなるものは次の8通りある.