PEをMathematicaで

Project Eulerに挑戦してみよう

001-100

Project Euler 70 / ファイ関数の置換

オイラーのファイ関数 φ(n)とは,n 未満の正の整数で n と互いに素なものの個数を表す。たとえば1, 2, 4, 5, 7, 8は9未満で9と互いに素であるので, φ(9) = 6 となる。1はすべての正の整数と互いに素であるとみなされ,φ(1) = 1 である。面白いことに φ(87109…

Project Euler 27 / 二次式素数

オイラーは以下の二次式を考案している。n^2 + n + 41この式は n を0から39までの連続する整数としたときに40個の素数を生成する。しかし, n = 40 のとき 4^02 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる。また,n = 41 のときは 41^2 + 41 + 41 で…

Project Euler 31 / 硬貨の和

イギリスでは硬貨はポンド£とペンスpがあり,一般的に流通している硬貨は以下の8種類である。1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p)以下の方法で£2を作ることが可能である。1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1pこれらの硬貨を使って£2…

Project Euler 81 / 経路の和:2方向

下記の5次の正方行列で左上のセルから開始し,右下のセルで終わるパスを探索する。ただし,下方向と右方向にのみ移動できるものとする。通過したセルの和が最小となるパスは赤の太字で示されたもので,その値は2427である。13167323410318201963429651506308…

Project Euler 67 / 最大経路の和 その2

以下の三角形の頂点から下まで移動するとき,その数値の合計の最大値は23になる。 3 7 4 2 4 6 8 5 9 3 この例では 3 + 7 + 4 + 9 = 23。100列の三角形を含んでいる15Kのテキストファイル triangle.txt の上から下までの最大合計をみつけよ。Problem 67 - Pr…

Project Euler 18 / 最大経路の和 その1

以下の三角形の頂点から下まで移動するとき,その数値の和の最大値は23になる。 3 7 4 2 4 6 8 5 9 3 この例では 3 + 7 + 4 + 9 = 23。以下の三角形を頂点から下まで移動するとき。その最大の和を求めよ。 75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 …

Project Euler 14 / 最長のコラッツ数列

正の整数に以下の式で繰り返し生成する数列を定義する。 n → n/2 (n が偶数) n → 3n+1 (n が奇数) 13からはじめると,この数列は以下のようになる。13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 113から1まで10個の項になる。この数列はどのような数字からはじ…

Project Euler 17 / 数字の文字数

1から5までの数字を英単語で書けば one, two, three, four, five であり,全部で 3+3+5+4+4=19 個の文字が使われている。では,1から1000 (one thousand) までの数字をすべて英単語で書けば全部で何文字になるか。注:空白文字やハイフンを数えないこと。た…

Project Euler 73 / 分数の数え上げ

n と d を正の整数として分数 n/d を考えよう。n 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/81/3 と 1/2 の間には3つの分数が存在する。では,d ≤ 12,000 について真既約分数をソートした集…

Project Euler 55 / Lychrel数

47とその反転を足しあわせると 47 + 74 = 121となり,回文数になる。全ての数が素早く回文数になるわけではない。349を考えよう。3回の操作を経て回文数になる。 349 + 943 = 1292 1292 + 2921 = 4213 4213 + 3124 = 7337 まだ証明はされていないが,196のよ…

Project Euler 35 / 巡回素数

197は巡回素数と呼ばれる。桁を回転させたときに得られる数 197, 971, 719 がすべて素数だからである。100未満には巡回素数が13個ある。2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97である。100万未満の巡回素数はいくつあるか?Problem 35 - Project Eu…

Project Euler 57 / 平方根の近似分数

2の平方根は無限に続く連分数で表すことができる。√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...最初の4回の繰り返しを展開すると以下が得られる。 1 + 1/2 = 3/2 = 1.5 1 + 1/(2 + 1/2) = 7/5 = 1.4 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...…

Project Euler 58 / 螺旋素数

1からはじめて以下のように反時計回りに数字を並べていくと,辺の長さが7の渦巻きができる。37363534333231381716151413303918543122940196121128412078910274221222324252643444546474849面白いことに奇平方数が右下の対角線上に出現する。もっと面白いこと…

Project Euler 26 / 逆数の循環節その1

単位分数とは分子が1の分数である。分母が2から10の単位分数を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.166666... という数字であり…

Project Euler 80 / 平方根の10進展開

よく知られているように自然数の平方根が整数ではないならば,それは無理数である。そのような平方根の10進展開(decimal expansion)は繰り返しを持たない無限小数になる。2の平方根は 1.41421356237309504880... であり,その頭から100桁の数字を合計する…

Project Euler 77 / 素数の和

10は素数の和として5通りに表すことができる。 7 + 3 5 + 5 5 + 3 + 2 3 + 3 + 2 + 2 2 + 2 + 2 + 2 + 2 素数の和としての表し方が5000通り以上になる最初の数を求めよ。Problem 77 - Project Euler n の表し方を f(n) 通りとおいて,はじめはのような漸化式…

Project Euler 39 / 整数の直角三角形

辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え,その周囲の長さを p とする。p = 120のときには3つの解が存在する。{20,48,52}, {24,45,51}, {30,40,50}p ≤ 1000 のとき解の数が最大になる p はいくつか?Problem 39 - Project Euler ピタゴラス…

Project Euler 47 / 異なる素因数

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは 14 = 2 × 7 15 = 3 × 5 それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは 644 = 22 × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19 最初に現れるそれぞれ4つの異なる素…

Project Euler 41 / 最小の倍数

n桁パンデジタルであるとは,1からnまでの数を各桁に1つずつ持つこととする。たとえば2143は4桁パンデジタル数であり,かつ素数である。n桁パンデジタルな素数の中で最大の数を答えよ(n≦9)。Problem 41 - Project Euler この定義では3桁の数に使える数字は…

Project Euler 42 / 符号化三角数

三角数は tn =1/2 n(n+1)で与えられ,最初の10項は次のとおりである。1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...単語中のアルファベットを数値に変換した後に和をとり,この和を「単語の値」と呼ぶことにする。例えば SKY は 19 + 11 + 25 = 55 = t10である…

Project Euler 52 / 置換倍数

125874を2倍すると251748となる。これは元の数125874と順番は違うが同じ数を含む。2x, 3x, 4x, 5x, 6x が x と同じ数を含むような最小の正整数 x を求めよ。Problem 52 - Project Euler まず x と 2x で実験。 条件を 6x までのものにして探します。

Project Euler 99 / 最大のべき乗

指数の形で表される2つの数,たとえば 2^11と3^7の大小を調べることは難しくはない。電卓を使えば 2^11 = 2048 しかし, 632382^518061 > 519432^525806 を確認することは非常に難しい(両者ともに300万桁以上になる)。各行に1組が書かれている1000個の組を…

Project Euler 71 / 順序分数

nとdを正の整数として分数 n/d を考えよう。n d ≤ 8について既約分数を大きさ順に並べると,以下を得る。1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/83/7のすぐ左の分数は2/5である。 d ≤ 1,0…

Project Euler 97 / 大きな非メルセンヌ素数

100万桁を超えるはじめての素数は1999年に発見された。これはメルセンヌ素数であり,2^6972593-1 である。2,098,960桁ある。それ以降も,より大きなメルセンヌ素数(2^p-1の形の数)がいくつも発見されている。しかし,2004年に非常に大きな非メルセンヌ素数…

Project Euler 63 / べき乗の桁の個数

5桁の数 16807 = 7^5は自然数を5乗した数である。同様に9桁の数 134217728 = 8^9も自然数を9乗した数である。自然数を n 乗して得られる n 桁の正整数は何個あるか?Problem 63 - Project Euler x^n がn桁になる条件は右側の不等式から x ≦ 9 がわかります。…

Project Euler 76 / 和の数え上げ

5は数の和として6通りに書くことができる。4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 12つ以上の正整数の和としての100を表す方法は何通りか。Problem 76 - Project Euler 問題78と似ていてずっとやさしい。整数の分割数は Partitions…

Project Euler 78 / コインの分割

n 枚のコインを異なった方法で山に分ける場合の数を p(n) で表す。たとえば5枚のコインを山に分ける方法は7通りなので p(5)=7 となる。◯◯◯◯◯◯◯◯◯ ◯◯◯◯ ◯◯◯◯◯ ◯ ◯◯◯ ◯◯ ◯◯◯ ◯ ◯ ◯◯ ◯ ◯ ◯ ◯p(n) が100万で割り切れるようなnの最小値を求めよ。Problem 78 - Pro…

Project Euler 53 / 組み合わせ選択

1 ≤ n ≤ 100 について,100万を超える nCr は何通りあるか?Problem 53 - Project Euler 全 nCr のリストを作って,何の工夫もせずに数えました。サクッと終了。

Project Euler 64 / 奇数周期の平方根

平方根は連分数の形で表したときに周期的であり,以下の形で書ける。√N = a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + ...)))たとえば√23を考えよう。√23 = 4 + √23 - 4 = 4 + 1 / (1 / (√23 - 4)) = 4 + 1 / (1 + (√23 - 3) / 7)この操作を続けていくと次のように…

Project Euler 56 / もっとべき乗の数字和

Googol(10^100)は非常に大きな数である。1の後に0が100個続く。100^100は想像を絶する。1の後に0が200回続く。その大きさにも関わらず,両者とも数字和(各桁の数字の和)は1である。a, b Problem 56 - Project Euler 第29問に似ている。Total[IntegerDigi…