Project Euler – 問題30

驚くことに各桁の数の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

1^4=1は和ではないのとで含めない。

これらの数の和は1634+8208+9474=19316となる。

各桁の数の5乗の和が自分自身になるような数の和を求めよ。

条件を満たす数がn桁としたとき、それぞれの桁の数の5乗の和というのは最大 で9^5*nなので、9^5*nがn桁になる必要がある。すると条件を満たす数は最大で も6桁、しかも9^5*6以下ということがわかるので、ここでは2から300000の数の リストについてfilterで判定を行いsumを用いて和を求めることにする。

各桁の5乗の和が元の数に等しいかをチェックするローカル関数fpは以下のよう に定義をそのままプログラムにしたものとする。ソースコード的美しさにはか けるが一応答えは求まる。

Project Euler – 問題29

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, 5^2=25, 5^3=125, 5^4=625, 5^5=3125 これらの値を重複を取り除いて小さい順に並べると以下のように15項の数列と なる。4,8,9,16,25,27,32,64,81,125,243,256,625,1024,3125 2<=a<=100, 2<=b<=100のときのa^bは何種類の異なる項からなる数列を生成する か求めよ。

リストの内包表記を利用して全ての場合を求め、リストから重複した要素を取 り除くnub関数を適用して重複を取り除き、lengthで長さを求める。

Project Euler – 問題28

1から順に時計回りに数字を並べて5×5の渦巻きを作ると以下のようになる(図 省略)。

このとき両方の対角線上の値の合計は101になる。

同じように1001×1001の渦巻きを作ったときに両方の対角線上にくる数の和を求 めよ。

実際に数字を並べて解くことも考えられるが、1001×1001というサイズや渦巻き 状に並べる処理なども大変そうなので、ここでは数学的な法則で求めることに する。問題ページの例を見ると一番中心は1、その周りは3,5,7,9と差が2の等差 数列、その周りは13,17,21,25と差が4の等差数列となっていることがわかる。 大きさnの渦巻きの場合、中心と、中心を除いた部分の半分の回数の4つの対角 線上の点の値の合計を求めればよいことがわかる。

まずは2,2,2,2,4,4,4,4,6,6,6,6…という差分diffsを定義する。ここでは repeatを用いて2の無限リストを生成し、それと自分自身を4つずらして zipWithで足しあわせることで生成している。次に1からその差分を使った数列 を生成する。scanl関数は与えられた関数と初期値にリストの値を順番に適用す る関数で、ここでは初期値1に+を適用することで、その差分を用いた数列を生 成している。この数列を前から(1001-1)/2周x4頂点+中心分の長さで取り出し和 を求める。

Project Euler – 問題27

オイラーは特徴的な2次方程式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である。

次の形式の2次方程式を考える。n^2+an+b, |a| < 1000かつ|b| < 1000 nが0から始まる連続した値のときに最大の個数の素数を生成する2次方程式の係 数aとbの積を求めよ。

リストの内包表記を用いて全てのパターンを求め、その中で最大のものを求め る方針とする。求める値はabで比較する値は素数が連続する数なので、その tupleのリストを生成する。まず素数かどうかの判定は問題10で使用した素数の 無限リストの中のnより小さい部分の中にnが含まれるかどうかで判定する。素 数が連続する数は再帰的にnに0から順に値を計算して求める。

aとbの組み合わせは全部で400万通りであるが、n=0の時に式の値が素数になる のでbは少なくとも素数である。bが2の場合n=2で式の値が偶数になるので、bは 奇数であると仮定すると、n=1が素数になるためには少なくともaは奇数である。 以上の条件より計算を若干高速化すると以下のようなプログラムになる。

Project Euler – 問題26

分子が1の分数を単位分数と呼ぶ。分母が2から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.16666666…を意味し、1桁の繰り返し周期を持つ。1/7は6桁 の繰り返し周期を持つことがわかる。

d<1000の範囲で、分数1/dを少数であらわしたとき繰り返し周期がもっとも 大きくなるdを求めよ

比較する対象は分数を少数で表したときの繰り返し周期の長さで求める解は分 数の分母なので、問題12のときと同様にその二つの値のtupleのリストを生成し、 maximumByで最大のものを求めて解を求めるという方針にする。

繰り返す部分の長さは以下のように関数recurringCycleを定義する。割り算を 筆算でやるときの要領で、現時点のあまりをnで割り、そのあまりを10倍して次 の桁の計算を行う。途中であまりが0になったら、それは割り切れるので繰り返 す部分は存在しない。そうでない場合は、現時点でのあまりをリストとして順 に渡し、ある時点でのあまりが以前のあまりと一致すればそれ以降は同じ値を 繰り返すことがわかる。一致するまでのリストの長さが繰り返し周期の長さと なる。

関数recurringCycleをパターンマッチ的な書き方で書いてみる。まずif文で判 定するかわりに関数rec’にガードを使う。次にmaybe関数を使っていたところを caseに書き換える。こっちのほうがHaskellぽいか。少なくともJustとNothing の処理は明示されてわかりやすいかな。

Project Euler – 問題25

フィボナッチ数列は次のように再帰的に定義できる。F1 = 1, F2 = 1, Fn = Fn-1+Fn-2。

したがって、最初の12項は次のようになる。F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7=13, F8 = 21, F9 = 34, F10 = 55, F11 = 89, F12 = 144。

12番目の項であるF12が3桁になる最初の項である。

初めて1000桁になる最初の項を求めよ。

問題2で定義したfibを使い、findIndexを用いて初めて1000桁になる数のインデッ クスを求める。ここでは必ず解が存在するがfindIndex関数はMaybeを返すので、 Maybeに対する処理をする関数maybeを使い、見つからなかったら0、見つかった らインデックスに+1をして返すという処理をする。リストのインデックスは0か ら始まっているので、これで解がもとまる。

Project Euler – 問題24

順列というのは対象を順番に並べるときの並べ方である。例えば、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万番目を求めよ。

与えられたリストの要素を順番に使って全ての順列のリストを返す関数 permutationを考える。順列は要素のリストとする。要素が一つしかないとき、 そのリストが全ての順列のリストとなる。

要素が複数あるときは、その中のひとつが一番最初にくると考えたとき、後ろ に続く順列は残りの要素の順列として再帰的に順列が定義できる。具体的には ここではmapを用いて、全ての要素がそれぞれ先頭だった場合について、 deleteで残りの要素を求め、permutationを再帰的に適用することで残りの部分 の順列を求めている。そして求まった順列に最初に取り除いた要素を付け加え ることで順列を求めている。この結果は先頭要素ごとの順列のリストになるの で、最後にconcatを使ってひとつのリストにする。

求める答えは0から9までの順列の1000000番目である。リストのインデックスは 0から始まるので999999を取り出せば答えとなる。前から順番に要素を使って順 列を生成していく場合、ソートしなくても結果は順番に並んでいる。

Project Euler – 問題23

自分自身を含まない約数の和がちょうど自分自身と等しくなる数を完全数と呼 ぶ。例えば28の場合、自分自身を含まない約数の和は1+2+4+7+14=28となり、 28が完全数であることがわかる。

自分自身を含まない約数の和が自分自身より小さいものは不足数と呼び、自分 自身より大きいものは過剰数と呼ぶ。

12は一番小さい過剰数で、1+2+3+4+6=16となる。二つの過剰数の和で一番小さ いものは24である。数学的な解析により、28123より大きな全ての整数は二つの 過剰数の和で表せることがわかっている。一方で、二つの過剰数の和として表 せない最大の数はこの上限より小さいことがわかっているにもかかわらず、解 析的にはこれ以上この上限を下げることはできない。

二つの過剰数の和として表すことができない全ての正の整数の和を求めよ。

まず過剰数の無限リストをabundantsとして定義する。1からの自然数に対して 自分自身を含まない約数の和が自分自身より大きいかどうかでチェックし filterをかける。28123以上の数は全て二つの過剰数の和で表せることがわかっ ているので、1から28123までの数に対して二つの過剰数の和で表せるかをチェッ クし、表せないものの和を求めれば答えが求まる。

ここで二つの過剰数の和で表せるかをチェックする関数をnotSumとする。チェッ クする対象の数より小さい過剰数のリストを取り出しasとする。対象の数から asのそれぞれの要素を引いた答えがasの要素の中にあれば、それは対象の数が 二つの過剰数の和で表せるとわかる。intersectは二つのリストの共通要素を求 める関数なのでこれを用いて求めることができる。この方法は非常に遅いがと りあえず解が求まったので今回はこれでよしとする。

Project Euler – 問題22

テキストファイルに含まれる5000個以上の名前をアルファベット順にソートし て、その位置と文字から計算した値の積がその名前の得点とする。

例えばCOLINは3+15+12+9+14=53で、938番目に位置するので 938×53=49714が得点となる。

ファイルに含まれる全ての名前の得点の和を求めよ。

与えられたデータファイルはダブルコーテーションでくくられた名前をカンマ で区切ったものであるが、その最初と最後に[]を追加するとHaskellからread関 数で読み込めて便利なので、ここではデータファイルをエディタ等で書き換え ることとする。書き換えたファイルのファイル名はeuler022.datとする。

まずはファイルをreadFileで読み込み、それをreadでStringの配列に変換する。 次にsort関数でソートし、その結果に対してscore関数をmapして文字列の得点 を計算する。得点の計算にはord関数を用いて文字を数値に変換し、Aが1になる ように64を引いている。1から始まる自然数の数列を順番としてzipWithでかけ て和を計算すると解が求まる。

Project Euler – 問題21

d(n)をnの真の約数(nの約数でnより小さいもの)の和と定義する。

a≠bでd(a)=bかつd(b)=aのとき、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未満の全ての友愛数の和を求めよ。

友愛数とは2つの異なる自然数a,bで自分自身を含まない約数の和が他方と等し くなるものである。まずは問題12で定義したfactorsを元に自分自身を含まない 約数のリストを求めるproperFactorsを定義する。1で割り切れるか試す部分を 特別扱いし2以降についてはfactorsと同様に処理することで自分自身を含まな い約数のリストを求めることができる。

次に友愛数かどうかのチェックをする関数amicableを定義する。ここでは友愛 数の定義をそのまま実装し、引数aの約数の和bを求め、aとbが異なり、bの約数 の和がaであった場合に友愛数であると判定する。最後に10000未満の数のリス トからfilterで友愛数を取り出しsumで和を求める。