読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

001-100

Project Euler 105 / 特殊和集合:検査

大きさ n の集合 A の要素の和を S(A) で表す。空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば,A を特殊和集合と呼ぼう。 S(B)≠S(C); つまり,部分集合の和はすべて異なる B が C より多くの要素を含んでいれ…

Project Euler 83 / 経路の和:4方向

下記の5次の正方行列で左上のセルから出発して上下左右に移動し,右下のセルで終了する道を探索する。一番小さな道は下で赤で示されており,このときの合計は2297になる。いま, 31Kのテキストファイル matrix.txt には 80*80 の行列が書かれている。左上のセ…

Project Euler 66 / ディオファントス方程式

次の形式の2次のディオファントス方程式を考えよう。 x^2 - Dy^2 = 1たとえば D=13 のとき,x を最小にする解は 649^22 - 13×180^22 = 1 である。D が平方数のとき,正整数のなかに解は存在しないと考えられる。D={2, 3, 5, 6, 7} に対して x を最小にする解…

Project Euler 51 / 素数の桁置換

*3の第1桁を置き換えることで 13, 23, 43, 53, 73, 83という6つの素数が得られる。56**3の第3桁と第4桁を同じ数で置き換えることを考えよう。この5桁の数は7つの素数をもつ最初の例である。 56003, 56113, 56333, 56443, 56663, 56773, 5699356003はこのよう…

Project Euler 86 / 直方体のルート

下に示す直方体は寸法が 6×5×3 である。この直方体のある頂点Sにクモがいる。また,反対の頂点Fにはハエがいる。SからFまで壁に沿って移動する最短ルートは図に示す通りで,この長さは10である。最短ルートの候補は3本あるが,最短のものがいつも整数長さと…

Project Euler 44 / 五角数

五角数は Pn = n(3n-1)/2 で生成される。最初の10項は 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ... である。P4+P7 = 22+70 = 92 = P8 であるが,差 70-22 = 48 は五角数ではない。五角数のペア Pj と Pk について差と和が五角数になるものを考える。差を D…

Project Euler 82 / 経路の和:3方向

下記の5次の正方行列で一番左の行の任意のセルから開始し一番右の行の任意のセルで終わる道を探索する。ただし上下右にのみ移動できるものとする。一番小さなパスは下で赤の太字で示されたものである。このときの合計は994になる。1316732341031820196342965…

Project Euler 74 / 桁の階乗による連鎖

145は各桁の階乗の和が自分自身に一致することで有名である。1! + 4! + 5! = 1 + 24 + 120 = 145169の性質はあまり知られていない。これは自分自身に戻る数の中で最長の列をなす。このように他の数を経て自分自身に戻るループは3つしか存在しない。 169 → 36…

Project Euler 60 / 素数ペア集合

素数3, 7, 109, 673は非凡な性質を持っている。任意の2つの素数を任意の順でつなげると,また素数になっている。たとえば7と109を用いると,7109と1097の両方が素数である。これら4つの素数の和は792である。これはこのような性質をもつ4つの素数の集合の和…

Project Euler 62 / 立方数置換

立方数 41063625(=345^3) は桁の順番を入れ替えると2つの立方数になる。56623104(=384^33) と 66430125(=405^33) である。41063625 は立方数になるような桁の置換をちょうど3つもつ最小の立方数である。立方数になるような桁の置換をちょうど5つもつ最小の立…

Project Euler 91 / 整数座標における直角三角形

点 P(x1, y1) と点 Q(x2, y2) はともに格子点であり,原点 O(0,0) とあわせてΔOPQをなす。各座標が 0 ≤ x1, y1, x2, y2 ≤ 2 をみたすとき,直角三角形は14個できる。0 ≤ x1, y1, x2, y2 ≤ 50 のとき,直角三角形は何個作れるか?Problem 91 - Project Euler …

Project Euler 79 / パスコードの導出

オンラインバンクで通常使われるsecurity methodはパスコードからランダムに選んだ3文字をユーザーに要求するものである。たとえばパスコードが531278のとき,2番目,3番目,5番目の文字を要求されるかもしれない。このとき期待される答えは 317 である。テ…

Project Euler 11 / 格子内の最大の積

次の 20x20 の格子のうち,斜めに並んだ4つの数字が赤くマークされている。 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 …

Project Euler 49 / 素数数列

公差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。 3つの項はそれぞれ素数である 各項は他の項の置換で表される 1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが,4桁の増加列にはもう1つ存在する。それではこの数列の3つの…

Project Euler 75 / 1通りの整数直角三角形

ある長さの鉄線を折り曲げて3辺の長さが整数の直角三角形を作るとき,その方法が1通りしかないような最短の鉄線の長さは12cmである。他にも沢山の例がある。 12 cm: (3,4,5) 24 cm: (6,8,10) 30 cm: (5,12,13) 36 cm: (9,12,15) 40 cm: (8,15,17) 48 cm: (12…

Project Euler 38 / パンデジタル倍数

192に1, 2, 3を掛けてみよう。 192×1 = 192 192×2 = 384 192×3 = 576 積を連結することで1から9のパンデジタル数192384576が得られる。192384576を192と(1,2,3)の連結積と呼ぶ。同じようにして, 9を1,2,3,4,5と掛けて連結することでパンデジタル数918273645…

Project Euler 23 / 非過剰数和

完全数とはその数の真の約数の和がそれ自身と一致する数のことである。たとえば28の真の約数の和は1+2+4+7+14=28であるので,28は完全数である。真の約数の和がその数よりも少ないものを不足数といい,真の約数の和がその数よりも大きいものを過剰数と呼ぶ。…

Project Euler 32 / パンデジタル積

すべての桁に1からnまでの数字が一度だけ使われているn桁の数をパンデジタル(pandigital)であるということにしよう。たとえば5桁の数 15234 は1から5のパンデジタルである。7254 は面白い性質を持っている。39×186=7254 と書け,掛けられる数,掛ける数,…

Project Euler 43 / 部分文字列被整除性

数1406357289は0から9のパンデジタル数である(0から9が一度ずつあらわれる数)。この数は部分文字列が面白い性質を持っている。d1を上位1桁目,d2を上位2桁目の数とし,以下順にdnを定義する。この記法を用いると次のことが分かる。 d2d3d4=406 は 2 で割り…

Project Euler 46 / もうひとつのゴールドバッハ予想

Christian Goldbachはすべての奇合成数は平方数の2倍と素数の和で表せると予想した。 9 = 7 + 2×1^2 15 = 7 + 2×2^2 21 = 3 + 2×3^2 25 = 7 + 2×3^2 27 = 19 + 2×2^2 33 = 31 + 2×1^2 後にこの予想は誤りであることが分かった。平方数の2倍と素数の和で表せ…

Project Euler 87 / 3つの素数のべき乗

素数の2乗と3乗と4乗の和で表される最小の数は28である。50未満のこのような数はちょうど4つある。 28 = 2^2 + 2^3 + 2^4 33 = 3^2 + 2^3 + 2^4 49 = 5^2 + 2^3 + 2^4 47 = 2^2 + 3^3 + 2^4 50,000,000未満の数で素数の2乗と3乗と4乗の和で表される数は何個…

Project Euler 50 / 連続する素数の和

素数41は6つの連続する素数の和として表せる。41 = 2 + 3 + 5 + 7 + 11 + 13100未満の素数を連続する素数の和で表したときにこれが最長になる。同様に連続する素数の和で1000未満の素数を表したときに最長になるのは953で,21項を持つ。100万未満の素数を連…

Project Euler 92 / 桁の2乗による連鎖

各桁の2乗を足しあわせて新たな数を作ることを, 同じ数があらわれるまで繰り返す。たとえば次のような列を作る。 44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 どちらも1か89で無限ループにおちいっている。驚くことに, どの…

Project Euler 85 / 長方形の数え上げ

注意深く数えると横が3,縦が2の長方形の格子には18個の長方形が含まれている。ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない。一番近い解を持つような格子の面積を求めよ。Problem 85 - Project Euler いろいろ考えた結果,問題27の類…

Project Euler 37 / 切り詰め可能素数

3797は面白い性質を持っている。まずそれ自身が素数であり,左から右に桁を除いたときにすべて素数になっている (3797, 797, 97, 7)。同様に右から左に桁を除いたときもすべて素数である (3797, 379, 37, 3)。右から切り詰めても左から切り詰めても素数にな…

Project Euler 100 / 組み合わせの確率

箱の中に15個の青い円盤と6個の赤い円盤からなる21個の色のついた円盤が入っていて,無作為に2つ取り出すとき,青い円盤2つを取り出す確率P(BB)はP(BB) = (15/21) × (14/20) = 1/2である。無作為に2つ取り出すとき,青い円盤2つを取り出す確率がちょうど1/2…

Project Euler 94 / 擬正三角形

一辺の長さが整数の正三角形は面積が整数にならないことを示すのは簡単である。しかし, 5-5-6の辺を持つほとんど正三角形に近い擬正三角形 (almost equilateral triangle) は面積が12で整数である。以降, 二等辺三角形で 3つめの辺の長さが他と1つしか違わな…

Project Euler 33 / 桁消去分数

49/98は面白い分数である。「分子と分母からそれぞれ9を取り除くと 49/98 = 4/8 となり,簡単な形にすることができる」と経験の浅い数学者が誤って思い込んでしまうかもしれないからである (方法は正しくないが,たまたま正しい約分になってしまう)。我々は…

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 までのものにして適当な範囲で Selec…

Project Euler 99 / 最大のべき乗

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