Project Euler
1 - 10までの数を下の図の◯に入れて、各3つ組の和が等しくなるようにする。問題で与えられた方法により数の並びを表現した時に、16桁となる数の中で最大の数を求める。 problem 68 実はこの問題は飛ばしていたのである。6月ころに一回手を付けて、良い解法が…
素数の和として表現できる数を小さい方から順に並べたとき、その表現方法が初めて5,000通りを超える数はいくつか Problem76に続く、両替問題の変形である。今度は「素数円玉」を使って両替すれば事足りるので、再びProblem31のコードを使い回す。 あとは問題…
100を2つ以上の整数の和で表現する方法は何通りあるか 真正面から正直にぶつかっても解けそうだが、現実的には計算量の壁に阻まれて答えは出ない。一方、これは数学で言う「分割数」の問題だと見れば、分割数の漸化式を利用する解法もありそうだ。 しかしこ…
周の長さが12で、各辺の長さが全て整数の直角三角形は(3,4,5)だけである。 同様に24 -> (6,8,10), 30 -> (5,12,13) 等々、長さを与えれば3辺の長さが決まる。 中には120 -> (30,40,50), (20,48,52), (24,45,51) のように、ある周長に対して複数の直角三角形…
145 → 1! + 4! + 5! = 1 + 24 + 120 = 145 である。 このように各桁の階乗の和を取る作業を繰り返すことで、一連の数列を得ることができる。例えば169なら 169 → 363601 → 1454 → 169 と長さ3のループ(4回目でもとに戻る)を得る。 完全なループにならない…
分母が12,000以下の既約分数は1/3と1/2の間にいくつあるか。 いくつかの方法を試すが計算が終わらない。これは例によって「知らないと解けない」系ではないかと疑い周辺情報を調べた結果、"Farey sequence"という有名な数列に関する問題であることが判明。そ…
分母が1,000,000以下の既約分数は全部でいくつあるか。 問題は を求めることと同義である。ここまで重い計算を避けるために、φ関数を直接計算することは避けてきたが、この問題ではさすがにそうもいかない。連想リストで効率化をはかりつつ、計算は真っ向勝…
分母が1,000,000までの既約分数を小さい順に並べた時に、3/7の1つ前に来る分数(3/7より小さく、3/7に最も近い数)はなにか まず思いつくのは、全ての分数を列挙してsortして…というナイーブな手法だが、恐らくその方法では時間が掛かり過ぎる。もう少し論理…
引き続きオイラーのφ関数; 今度は n と φ(n) が順列入れ替えの関係にあるものを探す。 n / φ(n) が最小となる n < 10,000,000 を求める。 懸案が多い。 n / φ(n) が小さいということは、素因数は少ないほうがいいんだろうという予想は立つものの、厳密に証…
オイラーのφ関数。 n / φ(n) が最大となる n < 1,000,000 を求める。 φ(n) = n より小さく n と互いに素な数の個数(下表) 手始めに素直にφ関数を実装してみる。やってみると分かるが、数が大きくなると全く使えない。本質的に素因数分解と同じなので、大き…
1から1000までの数を英語でカウントするときの全文字数を求める; 1 なら one なので 3文字。342なら three hundred and forty two なので23 文字 115 なら one hundred and fifteen なので20 文字 イギリス流に正しく and を入れましょう。 嫌だ…。見られた…
頂点から下へ降りていく中で通った数の和が最大となるときの和はいくつか。 Problem 18 のコードを全くそのまま再利用すれば完了である。Problem 18の時に悩んでおいて良かった。 mitstream.hatenablog.jp 再利用☆
次の形式の2次のディオファントス方程式; x2 - Dy2 = 1 においてxを最小とするD(≦1000)を求める。 力技でリスト内包表記をぶつけてみても答えは返ってこない。問題でディオファントス方程式とあるが、与えられた式は特別なディオファントス方程式で、名前…
ネイピア数eの連分数展開による有理数近似。 多分プログラミング的にアレコレやることも可能なのだろう。しかし考えるのが面倒(問題としてあまり魅力を感じない)ので、数学の知識を使ってストレートに漸化式を解くことにする。 無理数の有理数近似について…
無理数の連分数展開 Project Euler を解き続けて60問。今回初めて諦めようかと思ってしまった。難しい。 無理数の連分数展開はそんなに難しくない。しかしそれを数値計算でやろうとすると、誤差の問題でうまく行かないのである。引き算を回避したり割り算を…
mnの形をしたn桁の数は全部でいくつあるか 一行日記である。考えどころは探索範囲だが、数xの桁数はlog_10 x で調べることができることを踏まえれば、mとnをどの範囲まで調べれば良いか判断することができる。 以下のプログラムではmとnが逆になっているが…。…
3乗数でお互いに数字の並べ替えとなる5組の数を見つけ、その最小値を求める。 3乗数を小さい方から順番に調べつつ、[使っている数字の順列が同じ]という分類で同値類にまとめていく。元の数が5つになったところでそれを出力すれば完了である。各3乗数に「使…
三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される. 三角数P3,n=n(n+1)/21, 3, 6, 10, 15, ...四角数P4,n=n21, 4, 9, 16, 25, ...五角数P5,n=n(3n-1)/21, 5, 12, 22, 35, ...六角数P6,n=n(2n-1)1, 6, 15, 28, 45…
3,7,109,673 の素数の組は、それぞれをつなぎ合わせた数(例:7109, 1097, 673109など)も全て素数になる。そのように連結可能な5つの数の組を探し、その中で5数の和が最も小さくなるものを見つける。 ある条件を満たす素数を見つけるパターンは、計算に時間…
1から順に数字を半時計回りに並べていくと奇数の二乗の長さの正方形を順に作ることができる。このときに、対角線に現れる数のうちの素数の割合が10%を下回るのは、正方形の一辺の長さがいくつになったときか。 原理的には難しくない。数字を規則的に並べると…
√2の連分数表記を有限で打ち切り、既約分数の形にする操作を連分数の展開という。1000回までの展開のうち、分子の桁数が分母の桁数より多い形は何回現れるか。 連分数を再帰的に定義して計算することもできるのではないかと思ったが、最後に分数の形にする手…
ab ( 1 ≦ a,b ≦ 100)で与えられる数の各桁の和を比べたときに、値が最大となる数を探し、その和を求める。 Haskellは大きな数も、数字⇔文字列の行き来もなんの制約もないので、この手の問題はお茶の子である。 Integer様様☆
例えば47に対して47:→47+74=121 のように、反転した数を足すことで新しい数を得る操作を50回繰り返してもそれまでの間に一度も回分数を踏まないものが、10,000より小さい数の中にいくつあるか調べる。 特に悩むところはない。与えられた手続きに従って数を評…
与えられたカードの組み合わせ(1,000通り)でポーカーの勝負をした際に、Player 1 が勝つ組み合わせはいくつあるか。 これまで50問以上を解いてきて、Project Euler はプログラミング素人でも日本の高校数学程度の素養があればなんとかなる…と思っていた。…
コンビネーション nCr の数が100万を超える (n,r) の組は何組あるか。( 1 ≦ n ≦ 100 ) 方針は立ちやすい。(n,r)を振ってコンビネーションを計算して、100万以上のものを拾う(問題文まんまやんけ)のみである。問題はコンビネーションを定義どおりに計算する…
ある数xに対して、その倍数 x,2x,3x,4x,5x,6x のすべてが順列(同じ数字の組の並べ替え)となるようなxを求める。 前問からは一転、何も悩む必要のない問題である。数字列と文字列を自在に行き来できるようになると、この手の問題はお茶の子である。 イージ…
2桁の数 *3 の*に数字を入れると、13,23,43,53,73,83 の6つの素数を得る。同様に5桁の数 56**3 の*に同じ数字を入れたもののうち、56003, 56113, 56333, 56443, 56663, 56773, 56993 の7つが素数となる。同じルールで数のうちのいくつかの数字を同じ数…
41は連続する6個の素数の和で表すことのできる素数(41 = 2 + 3 + 5 + 7 + 11 + 13)である。100以下では41の持つ6連続が最長である。100万以下で最も長い連続する素数の和で表される素数を求める。 100万以下の素数の列から2つ選んで総当りで答えを求めるこ…
4桁の素数3つからなる等差数列で、各々が他の並べ替え(同じ4つの数字を使っている)になっている組を見つける。 コードは普通に書くだけであるが、4桁の素数が同じ数字の組み合わせであることから、等差数列の公差が9の倍数でなければならないと分かる…
11 + 22 + ... + 10001000 の答えの最後の10桁を求める。 Use Integer オンリーである。Haskell 様様 である。 Integer…☆