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

PEをMathematicaで

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個の組を…

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 のリストを作って,何の工夫もせずに数えました。サクッと終了。計算時間は0.013秒でした。

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…

Project Euler 69 / nとφ(n)の比

オイラーのファイ関数 φ(n) は n と互いに素な n 未満の数の数を表す。たとえば1, 2, 4, 5, 7, 8は9未満かつ9と互いに素であるから φ(9)=6 である。n互いに素な数φ(n)n/φ(n)211231,221.541,32251,2,3,441.2561,52371,2,3,4,5,661.1666...81,3,5,74291,2,4,5,…

Project Euler 65 / e の近似分数

√2の連分数による近似分数を考える。この数列の最初の10項は次のようになる。1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...e の近似分数からなる数列も考えることができる。2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71,…

Project Euler 72 / 分数の数え上げ

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/8この集合は21個の要素をもつ。d ≤ …