Problem 29少し戻って、ScalaでProject Euler（51）の続きです。5乗のときで考えてみます。例えば32です。前回は、 U - (S1 ∪ S2 ∪ S3 ∪ S4) = (U - S1) ∩ (U - S2) ∩ (U - S3) ∩ (U - S4) を利用しましたが、今回は包除原理そのもの、 |S1 ∪ S2 ∪ S3 ∪ S4| …

Problem 31もっと速くならないでしょうか。例えば一般項を求めるというのはどうでしょう。 Q1(x) = P1(x) の一般項はak(1) = 1ですね。 Q2(x) = P1(x)P2(x) は、kが奇数なら、 ak(2) = (k + 1) / 2 は、kが偶数なら、 ak(2) = k / 2 + 1 となります。ここま…

Problem 31さらに速い方法があります。 Pk(x) = 1 / (1 - xk) なので、 (1 - x)(1 - x2)...(1 - x100)(1 - x200) を計算して逆数を取るだけです。本当は証明が必要なのですが手抜きします。 N = 5000で前回の方法より2桁速かったです。O(N2)がO(N)ですからね…

Problem 31場合の数ですね。場合の数や確率を求める問題は、まず母関数の手法が使えるかどうか考えたほうが良いです。この問題はわかりやすいです。 Pk(x) = 1 + xk + x2k + ... という母関数を考えます。各係数はkペンスだけ使ったときの場合の数です。例え…

次問の準備でクラスの理解も兼ねて分数クラスを作ります。 まず、クラス名はPythonと同じくFractionとします。分母・分子は都合でBigIntです。 コンストラクタ 分母と分子を引数に取ります。こんな感じでしょうか。 class Fraction(num :BigInt, den :BigInt…

Problem 30重複組合せを使えばかなり速くなります。重複組合せを生成して、その各要素の5乗和の各桁をソートして元のリストと同じになればOkです。例えば、 List(0, 1, 3, 4, 6) -> 04 + 14 + 34 + 44 + 64 = 1634 > List(0, 1, 6, 3, 4) -> List(0, 1, 3, 4…

Problem 30上限を見つけてあとは等式が成り立つかどうか調べるだけですね。

Problem 29もう一度考え直してみましょう。N = 100で底8の重複を考えてみましょう。底2に重複するのは公差1で33まで、底4は公差2で66まで。とりあえず81も含めて両方とも33個あります。ただし、ダブっている部分があって、公差2で33までだから16個あるので33…

Problem 29単純に考えると99×99通りのべき乗があるのですが、重複があるのでそれより少ない数になります。どれだけ重複があるのかを考えるとこの問題は速く解けます。 例を考えましょう。 28 = 44 = 162 ここでダブってカウントしないように、大きい底から小…

Problem 29多倍長整数でなく素因数分解を使うのがふつうでしょうね。これならべき乗も簡単ですし。でも、N = 2000が限界でした。

Problem 29この問題は100までと範囲が非常に狭いので次のような乱暴なコードでも瞬時に答えが出てしまいますが、 def pows(n :Int) = Iterator.iterate(BigInt(n * n))(_ * n).take(N - 1) val N = 100 println (Iterator.range(2, N + 1).flatMap(pows).toS…

Problem 28座標と値のタプルからその次の対角線上の座標と値のタプルを得る関数を作れば簡単です。あとはIterator#iterateを使うだけです。

Problem 27まず、bは3以上の奇数で、aも奇数であることがわかります。2以外の素数についても同様の考察ができてそれはそれで面白いのですが、そんなことをしなくても素数判定をメモ化するだけで十分速くなります。

Problem 26この問題は以前に詳しく説明しました。Project Euler 26 - 桃の天然水要約すると、 dは素数でなければならない 10n ≡ 1(mod d)となる最小の自然数nはd-1でなければならない 上の合同式が成り立つnはd-1の約数のみ だから、d-1以外の全ての約数につ…

Problem 25この問題は公式を使えば実数計算で答えが出る、数学はえらいなあというのを実感させるための問題です。この公式の求め方は高校で勉強しましたが、オイラーもこれを発見したそうです。 数学関数は、 import scala.Math._ と書いておくと標準的なも…

Problem 25多倍長整数ですが、加算だけなので簡単ですね。

Problem 24この問題には順列を生成する練習という面もあります。生成はIteratorで簡単に実現できます。

Problem 24この問題は答えを出すだけなら手計算レベルです。階乗で割っていって余りを求めるだけです。ただ、関数型らしく書いたらややこしくなってしまったので、var使いまくりで書いてみました。

Problem 23本当は6の剰余で分けて考えると速いのですが、何も考えずに書いても十分に速いです。

Problem 22Scalaでテキストファイルから1行読むのはこんな感じだそうです。 val s = io.Source.fromFile("names.txt") val str = s.getLines.next 文字列のソートにはcompareToを使うそうです。

Problem 21エラトステネスのふるい的に約数の和を求めるだけですね。

Problem 20これもProblem 16と同じです。

Problem 19 iterate Iterator.iterate(x)(f) とすると、 x, f(x), f(f(x)), ... という列が生成されます。(曜日, 年, 月)というタプルを次の月のタプルにする関数fとすれば簡単に曜日の列が生成できます。

Problem 18深さ優先探索ですね。簡単です。 split val a = "1 2".split(" ") splitを使うとStringのArrayになるんですね。この問題に最適です。

Problem 16PythonとScalaで多倍長整数の性能を比較してみます。3を自乗して9、9を自乗して81、という操作を繰り返します。 import time def test(): t0 = time.clock() n = reduce(lambda x, y: x * x, xrange(N), 3) print n % 100 return time.clock() - t…

Problem 16多倍長整数を使えば簡単ですが、 def sum_digits(n :BigInt) :Int = if(n == 0) 0 else (n % 10).toInt + sum_digits(n / 10) val N = 1000 val n = (1 to N).foldLeft(BigInt(1))((x, y) => x * 2) println (sum_digits(n)) これでは面白くないの…