Problem 78分割数p(k)には、実は次のような漸化式があります。 p(k) = p(k - 1) + p(k - 2) - p(k - 5) - p(k - 7) + p(k - 12) + p(k - 15) - … p(0) = 1 p(k) = 0 (k 漸化式のpの中のk - mのmは五角数になっています。符号は、+ + - - + + - -となります。…

Problem 77前問とほとんど同じです。再帰に持ち込んでメモ化です。

Problem 76f(n, m)は同じ引数で何度も呼び出されます。例えば、f(1, 1)は169229875回呼ばれるようです。fは引数が同じならいつも同じ答えを返すので、それを記録しておけばよいです。メモ化ですね。これで3msくらいです。本当はもっと速い方法があるのですが…

Problem 76Project Eulerには再帰に持ち込めば簡単になる問題が多いです。5を分割することを考えます。まず5から4を取ります。残り1なのでその分割数を考えればよいです。次に5から3を取ります。残り2なので2の分割数を取ります。次に5から2を取ります。残り…

Problem 75 a = 2lmn b = l(m2 - n2) c = l(m2 + n2) (m, n) = 1 m + nは奇数 に従えば簡単に直角三角形が列挙できるので、それで長さについてカウントしていくだけですね。

Problem 74大きさ100000の0に初期化した配列を用意します。 例えば、69を考えます。このインデックスの配列の要素を-1とします。69の次は363600です。ここは-2とします。次の1454は-3とします。このように進んでいくと、1454がやってきます。ここは0でなく負…

Problem 73対象を1/3より大きく1/2より小さいより、1/3以下とするほうが考えやすそうなのでそうしましょう。1/2より小さいは、前問の1より小さいから1/2の1個を引いて半分にするだけです。例えば、d = 40で考えましょう。取りうるnは1〜13です。ここから2の…

Problem 73単にその範囲の分数を列挙して分母分子が互いに素なものを数えるだけで1秒以内でした。

Problem 72dを固定して考えましょう。例えば10とか。nで取りうるのは1〜9です。しかし、nとdは互いに素なので、結局とりうるのは 1 3 7 9の4つです。これはφ(10)です。定義そのものですね。したがって、 φ(2) + φ(3) + ... + φ(1000000) を計算すればよいで…

Problem 71N = 1000000として、分母がN - 6以上だけを考えればよいです。なぜなら、分母がN - 7以下のとき、a / bとして、(a + 3) / (b + 7)のほうが3 / 7に近いからです。

Problem 70この問題は、 Aを満たす数でBが最小のものを求めよ というパターンなので、 Bの昇順に並べてAを満たす最初の数を求めよ と読み替えればよいです。すなわち、n / φ(n)（以下、phi比と呼びます）の小さい順に並べればよいです。幸いこれはそんなに難…

Problem 70とりあえず、素直に解いてみましょう。ふるい的に素因数分解して、全ての対象の整数についてφを求め並べ替えになっているか調べ、n/φ(n)が最小のものを選びます。 これで10秒です。Pythonでは16倍くらい遅かったです。

Problem 69オイラーのφ関数は前に書いたように、 なので、 です。素数を昇順に掛けていくだけですね。

Problem 68まず外の5つを決めます。その和をsext、内側の和をsintとします。 sext + sint = 55 です。1列の和をslineとします。全ての列の和を取ると、内側は2回ずつカウントするので、 5sline = sext + 2sint sint = 5(sline - 11) sintは5の倍数、sextも5…

Problem 67メモ化ですね。 3 7 4 2 4 6 8 5 9 3一番下はそのままにして、2番目の左端、2を考えます。2の下は8と5ですが、トータルで最大になるのは8を選んだ時です。それを2に加えます。 3 7 4 10 4 6 8 5 9 3この列を同じように処理すると、 3 7 4 10 13 15…

Problem 66Pell方程式の最小解と連分数には驚くべき関係があります。たとえば、Problem 64で例に挙げられた√23は、 √23 + 4 = [ 8; 1, 3, 1, 8, 1, 3, 1 ... ] ですが、1周期で打ち切ったとき、 [ 4; 1, 3, 1 ] = 24 / 5 で、この(24, 5)が 242 - 23 * 52 = …

Problem 66 x - Dy2 = 1 これをPell方程式と呼びます。これには必ず整数解があることが知られています。この整数解が大きくなると、 x/y√(1-x-2) = √D よりx/yは√Dの近づくことになります。√Dの連分数展開と同じですね。実際、Pell方程式の解は連分数展開を…

Problem 65連分数の最後に書いた漸化式を使うと簡単です。ただし、64ビットの範囲で解けないので多倍長整数が必要です。

Problem 64ループの長さが奇数になる数を具体的に並べてみましょう。 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, ... これらを素因数分解すると、因数は2か4で割って1余る素数になっています。 ただ、逆は違うようです。すなわち、すべて2…

Problem 64連分数です。連分数はペル方程式と関係が深く、この後の問題の前振りになっているかもしれません。 問題を解くには問題文に書かれた手順を実行すればよいです。 としてa, b, cの変化をチェックします。そしてループを検出します。(a, b, c)が以前…

アップミスで順番が逆になってしまいました。Problem 623乗して同じ桁になる数を用意して並び替えると同じになる数ごとに分類します。同じ数は、降順にでも並び替えればいいですね。8なら3乗して512を並び替えて521です。並び替えて同じになる数が5つあれば…

Problem 63この問題はふつうに解くと64ビットの範囲では解けません。多倍長整数を使ってもよいのですが、ここはlogを使いましょう。基数b、指数eに対して題意が成り立つには、 be ≥ 10e-1 logを取って、 e log b ≥ (e - 1)log 10 e log (b / 10) ≥ -log 10 e…

Problem 61これはグラフにすると比較的考えやすいです。例にあるように8128は三角数ですが、81という点と28という点が線で結ばれていて重みが3と考えます。ネットワークですね。4桁の3〜8角数を全て求めてネットワークを作ります。そうしたときに、ある点か…

Problem 60まず、素数列を用意します。これにどの向きに結合しても素数になるような素数を探します。例えば(3, 7)ですね。これを結合素数と呼ぶことにします。こうして2つの素数の組を列挙します。これにさらにもう一つ素数を加えて3つの素数による結合素数…

Problem 59シャーロックホームズに出てきたようにeが一番多いのだろうと思ったら違いました。

エラトステネスのふるいです。ふつうに書いてみます。 def sieve1(N :Int) :List[Int] = { val a = new Array[Boolean](N + 1) for(n <- 2 to N) a(n) = true for(p <- Iterator.range(2, N + 1).takeWhile(p => p * p <= N) if a(p); k <- Iterator.range(p…

Pythonと同じことをします。 まずは試し割りから。 def is_prime1(n :Int) :Boolean = Iterator.from(2).takeWhile(p => p * p <= n).forall(p => n % p != 0) def make_primes(N :Int, is_prime :Int => Boolean) :List[Int] = Iterator.range(2, N + 1).fi…

Problem 58どうしても素数判定に時間がかかりますが、どうにかならないのでしょうか。素数判定を高速に行うといえばエラトステネスのふるいですが、ふるい的な手法は使えないでしょうか。実は使えます。 対角線上の数を分けて考えましょう。まず、右下は平方…

Problem 58解を概算してみましょう。 素数定理が使えそうです。素数定理で素数の密度がだいたいわかります。x付近で整数log x個に平均約1個素数があります。例えば、10000の前後だとlog10000 ≒ 9.2個に1個、1億だと18.4個に1個素数があることになります。 さ…

Problem 58Problem 28の対角線上を辿るコードをそのまま使えます。あとは適当に素数判定するだけです。 10%で3.4s、9%で26sでした。かなり遅い素数判定ですが。