2011-08-01から1ヶ月間の記事一覧

ScalaでProject Euler(80)

Problem 50PriorityQueueを使えば簡単です。まず、2からはじまる最長の素数列を求めます。そして、(列の長さ, 最初の素数のインデックス, 列の和)というタプルをPriorityQueueに入れます。PriorityQueueから要素を取り出して、今までの最長の素数未満の長さ…

ScalaでProject Euler(79)

Problem 49この問題はどうやっても解けると思いますが、なるべく速そうな方法を考えます。 まず0〜9で4要素の重複組合せを生成します。例えば[1, 4, 7, 8]です。順番を入れ替えて生成される4桁の数はこれで代表されます。そして、ここから順列を生成します。…

ScalaでProject Euler(78)

Problem 48この手の問題でBigIntを使ってはいけません。Longの範囲で解きましょう。ただ、10桁同士の掛け算を行うとLongの範囲を超える可能性があるので、少し工夫します。ここは5桁ずつに区切って計算します。

ScalaでProject Euler(77)

Problem 47順番に素因数分解を生成しても遅くないのですが、それでは面白くないので別の方法を考えましょう。4つの素数から成る数を昇順に生成すればよいのです。これは、約数の個数がある数より大きい自然数を昇順に列挙する(1)とほとんど同じです。初期…

ScalaでProject Euler(76)

Problem 46範囲がわからないと計算しにくい問題ですが、こういうときは範囲を適当に決めて、その中に解が無ければ範囲を2倍にする、という操作を繰り返しますのが簡単です。本当は計算量の増加具合で範囲の広げ方を決めるべきなのですが、2倍でもよいでしょ…

ScalaでProject Euler(75)

Problem 45三角数は六角数を含むので、三角数は考えなくてもよいことになります。 単に五角数と六角数を昇順に並べてマージ法を使うのが簡単でしょう。 // Polygonal number def P(p :Int) :Stream[Long] = Stream.from(1).map(n => n * ((p - 2L) * n - p +…

ScalaでProject Euler(74)

Problem 44どうすればうまく解けるんでしょうね。 D = Pk - Pj = Pi として、 k(3k - 1) / 2 - j(3j - 1) / 2 = i(3i - 1) / 2 (36k2 - 12k) - (36j2 - 12j) = (36i2 - 12j) (6k - 1)2 - (6j - 1)2 = (6i - 1)2 - 1 ここで、 a = 6i - 1 b = 6j - 1 c = 6k -…

ScalaでProject Euler(73)

Problem 43まず、1000未満の17の倍数を生成します。例えば、289ですね。その上2桁を取って、28。その上の桁に数字をつけた数が13の倍数になっている必要があります。 13n = 100d + 28 このディオファントス方程式を0 ≤ d < 10の範囲で解いて、d = 7。これを…

ScalaでProject Euler(72)

Problem 42問題の意図がわかりません。 三角数の判定は、 n(n + 1) / 2 = t n2 + n - 2t = 0 これを解いて、 nが整数になる必要十分条件は、1 + 8tが平方数です。

ScalaでProject Euler(71)

Problem 411〜7の順列を逆向きに出して最初の素数です。

ScalaでProject Euler(70)

Problem 40この問題はIteratorを使うと簡単ですね。Streamだとメモリを使ってしまうはずです。 def digits(n :Int) :List[Int] = if(n == 0) Nil else n % 10 :: digits(n / 10) def f(k :Int) = { val it = Iterator.from(1).flatMap(n => digits(n).revers…

ScalaでProject Euler(69)

Problem 39めんどうなので、前回n'と書いていたものをnとします。 もうちょっとなんとかならないでしょうか。 例えば、p / 2 = qが素数だったとしましょう。そうすると、 (l, m, n) = (q, 1, 1), (1, q, 1), (1, 1, q) はどれも直角三角形ではないので、0個…

ScalaでProject Euler(68)

Problem 39この問題はピタゴラス数の生成を使えば簡単です。 a = 2lmn b = l(m2 - n2) c = l(m2 + n2) p = 2lm(m + n) ここで、n' = m + nとおけば、 p / 2 = lmn' (m, n') = 1 m n' m p / 2を素因数分解して3つの積に分解してそれが上の条件を満たす組合せ…

ScalaでProject Euler(67)

Problem 38積が合わせると9桁になるので、例えば被乗数が1〜4だとすると、桁数の分配は2,2,2,3になります。この分配の計算は次のように簡単に行えます。 9 / 4 = 2 -> 9 - 2 = 7 -> 7 / 3 = 2 -> 7 - 2 = 5 -> 5 / 2 = 2 -> 5 - 2 -> 3 -> 3 / 1 = 3 そうす…

ScalaでProject Euler(66)

Problem 373797 → 379 → 37 → 3のような右から短縮しても素数になる数は逆向きに生成できます。まず1桁の素数[ 2, 3, 5, 7 ]を用意して、それぞれに0〜9を右に加えて、元が2なら[ 23, 29 ]が素数なのでこれは「右短縮」になっています。さらに23に0〜9を右に…

マージ法

前に書いたものを少し書き直します。 マージ法(Merge algorithm)は、ソートされた二つの列を合体して一つのソートされた列を作るアルゴリズムです。(「マージ法」という用語はあまり使われていないようです) 原理は非常に簡単です。例えば次のような列が…

ScalaでProject Euler(65)

Problem 3610進の回文数を生成して2進の回文数になっているかを調べます。

ScalaでProject Euler(64)

Problem 35長さ1からはじめて、N/2までのパターンを列挙します。 1 : [ 0 ] 次に長さ2ですが、0に長さ2をあてはめます。[ 0, 0 ]は特別として、0が続いてそこから0以外が続く、というのは[ 0, 1 ]のみです。[ 0, 2 ]のような抜けがあるというのは無しです。 …

ScalaでProject Euler(63)

Problem 35 1 3 1 7 1 3 1 3 1 9 これを、1とそれ以外を合体して一つのブロックと考えましょう。そうすると、 13 17 13 13 19 これに順番をつけましょう。コードの都合上0からつけます。 0 1 0 0 2 これでわかりやすくなりましたが、さらに同じことを繰り返…

ScalaでProject Euler(62)

Problem 35この問題はある意味難しいです。 1, 3, 7, 9の4つの数字だけ作って、回して全てが素数かどうか調べればいいので簡単です。ただ、例えば197が「回転素数」だったとして、197・971・719に対して素数判定だったとします。そうすると、719についてもや…

ScalaでProject Euler(61)

Problem 34Problem 30とほとんど同じです。

ScalaでProject Euler(60)

Problem 3310進で(ab)10と(bc)10という二つの自然数があり、それがbを消しても分数の値が同じなら、a cならa / c、a > cならc / aを出力するだけです。

ScalaでProject Euler(59)

Problem 32この問題は9の剰余で考えるとかなり絞れるのですが、めんどうなので省略です。10進の各桁を列挙するIteratorは次のように書けます。 def digits(n :Int) :Iterator[Int] = if(n == 0) Iterator() else Iterator(n % 10) ++ digits(n / 10) その上…