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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 162 / 16進数

16進法では数は以下の16個の数字によって表される。0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F16進数の AF は10進法での 10x16 + 15 = 175 と等しい。3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A のすべてがあらわれている。 10進数で書くときと同様に先頭の0は書…

Project Euler 193 / 平方因子を含まない数

正の整数 n が任意の素数の2乗によって割り切れないとき,n を「平方因子を含まない(squarefree)」と呼ぶ。1, 2, 3, 5, 6, 7, 10, 11 は平方因子を含まないが,4, 8, 9, 12 は含む。2^50 未満で平方因子を含まない数はいくつあるか?Problem 193 - Project…

Project Euler 187 / 半素数

合成数とは2つ以上の素因数を含む整数のことである。たとえば 15=3×5, 9=3×3, 12=2×2×3 は合成数である。30以下にはちょうど2つの素因数を含む合成数(異なる素因数でなくてもよい)が10個存在する。4, 6, 9, 10, 14, 15, 21, 22, 25, 26である。自然数 n Pr…

Project Euler 155 / コンデンサー回路

静電容量が等しい理想的なコンデンサーのみを使った電気回路がある。複数のコンデンサーを直列または並列に接続してサブユニットを形成し,そのサブユニットを他のコンデンサーやサブユニットと直列または並列に接続してより大きなサブユニットを形成……のよ…

Project Euler 179 / 連続する正の約数

n と n + 1 の正の約数の個数が等しい 1 Problem 179 - Project Euler brute force 約数の個数を扱う問題は前にもやりました。DivisorSigma[0, #] で約数の0乗の和を求めて比較します。この方法だと96秒。 並列化 第146問でやったのと同じように並列化してみ…

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 146 / 素数パターンの調べ上げ

n^2+1, n^2+3, n^2+7, n^2+9, n^2+13, n^2+27 が連続する素数になる最小の正整数 n は 10 である。100万未満の n の総和は 1242490 である。1億5000万未満の n の総和を求めよ。Problem 146 - Project Euler 第1案 素朴な brute force 「連続する素数」とあ…

Project Euler 206 / 覆面平方数

平方すると 1_2_3_4_5_6_7_8_9_0("_"は1桁の数) の形の数になる自然数がただ一つある。その値を求めよ。Problem 206 - Project Euler 第1案 もとの数を n とします。n^2 の一の位が0なので,n は10の倍数です。また,n^2 の百の位が9であることから,n の…

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 112 / はずみ数

左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ。例 134468同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ。例 66420増加数でも減少数でもない正の整数を「はずみ数」と呼ぶことにする。例 155349100以下にはずみ数がないのは明らか…

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 113 / 非はずみ数

ある数の桁を左から右へと順に見たとき,任意の桁の数が自身の左にある桁の数以上であるとき,その数を増加数(increasing number)と呼ぶ。たとえば134468は増加数である。同様に,任意の桁の数が自身の右にある桁の数以上であるとき,その数を減少数(decr…

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

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

Project Euler 108 / ディオファントス逆数1

次の等式で x, y, n は正の整数である。1/x + 1/y = 1/nn = 4 では 3 つの異なる解がある。 1/5 + 1/20 = 1/4 1/6 + 1/12 = 1/4 1/8 + 1/8 = 1/4 解の数が 1000 を超える最小の n を求めよ。Problem 108 - Project Euler 約数の個数の問題ということで,問題…

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) 通りとおいて,はじめはのような漸化式…

アワード Daring Dozen ゲット

IDが3桁の問題を12問解いたので,Daring Dozenというアワードをもらいました。「たった12問で?」という気がしないでもないのですが,100番あたりを境に回答者がガクッと減るようなので,参加をうながすご褒美なのでしょう。統計のページによると,このアワ…

Project Euler 140 / 変形フィボナッチ金塊

Gk = G(k-1) + G(k-2), G1 = 1, G2 = 4 によって与えられる無限級数がある。この問題では AG(x) が正の整数となるような x の値について考える。最初の5つの自然数に対する x の値を下表に示す。xAG(x)(√5−1)/412/52(√22−2)/63(√137−5)/1441/25x が有理数と…

Project Euler 121 / 円盤ゲームの賞金額

袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている。賭けゲームにおいてプレイヤーは円盤を 1 枚ランダムに取り出し,その色を記録する。各ターンの終わりに円盤は袋に戻され,追加の赤い円盤 1 枚が袋に足され,次の円盤がランダムに取り出される。プレイ…

Project Euler 145 / reversibleな数

n + reverse(n) の各桁が奇数のみであるような n が存在する。たとえば 36 + 63 = 99, 409 + 904 = 1313 である。この性質を持つ数を reversible と呼ぶことにする。36, 63, 409, 904は revesible である。先頭の0は n でも reverse(n) でも許されない。1000…

レベル2になりました

正解数が50になり,レベル2になりました。アイコンはこちら。1行で解けるような易しい問題が見当たらなくなってきたので,ここから先は苦戦しそうです。今後の勉強の方向は3つ考えています。 Mathematica(=Wolfram 言語)にくわしくなる アルゴリズムの本…

Project Euler 115 / ブロックの組み合わせ方の数え上げ その2

(注意)これは Problem 114 をより難しくした問題である。長さ n ユニットからなる 1 列上に最低 m ユニットの長さを持つ赤ブロックが置かれている。ただし,どの赤ブロック同士も少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なって…

Project Euler 114 / ブロックの組み合わせ方の数え上げ その1

長さ 7 ユニットからなる 1 列上に最低 3 ユニットの長さを持つ赤ブロックが置かれている。ただしどの赤ブロック同士も少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい)。これを敷き詰める方法は 17 通りある。50 ユニット…

Project Euler 116 / 赤タイル,緑タイル,青タイル

5 個の黒い正方形のタイルの列を赤(長さ 2),緑(長さ 3),青(長さ 4)から選んで,この色のついた長方形のタイルでいくつか置き換える。赤のタイルを選んだ場合は 7 通りの方法がある。緑のタイルを選んだ場合は, 3 通りである。青のタイルを選んだ場合…

Project Euler 117 / 赤タイル,緑タイル,青タイル

黒い正方形のタイルと,2 ユニットの長さの赤のタイル,3 ユニットの長さの緑のタイル,4 ユニットの長さの青のタイルから選んで組み合わせて,5 ユニットの長さの 1 列をタイルで敷く方法は 15 通りある。長さ 50 ユニットの 1 列をタイルで敷く方法は何通…

Project Euler 123 / 素数の自乗で割った余り

pn を n 番目の素数とする(p1 = 2, p2 = 3, ...)。 r を (pn - 1)^n + (pn + 1)^n を pn^2 で割った余りとする。たとえば n = 3 のとき p3 = 5 であり,4^3 + 6^3 = 280 ≡ 5 (mod 25)余り r が 10^9 より大きくなる n の最小値は 7037 である。余り r が 10^…

Project Euler 120 / 自乗で割った余り

(a-1)^n+(a+1)^n を a^2 で割った余りを r とする。たとえば a=7, n=3 のとき r=42 である。6^3 + 8^3 = 728 ≡ 42 (mod 49)n が変われば r も変わるが,a=7 のとき r の最大値 r_max は 42 であることがわかる。3 ≤ a ≤ 1000 において Σ r_max を求めよ。Pro…

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 ≤ …

Project Euler 104 / 両端がパンデジタル

フィボナッチ数列は再帰的な関係によって定義される。Fn = Fn−1 + Fn−2F541(113桁)は下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である。そして,F2749(575桁)は上9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である。Fkが…

Project Euler 137 / フィボナッチ金塊

フィボナッチ数列 Fk = F(k-1) + F(k-2), F1 = 1, F2 = 1 (Fk = 1, 1, 2, 3, 5, 8, ...) によって与えられる無限級数 を考える。この問題では,A_F(x) が正の整数となるような x の値について考える。驚くべきことにである。最初の5つの自然数に対する x の…

Project Euler 36 / 2種類の基数による回文数

585 = 10010010012(2) は10進法でも2進法でも回文数である。100万未満で10進でも2進でも回文数になるような数の総和を求めよ。注:先頭に0を補って回文にすることは許されない。Problem 36 - Project Euler 回文数を判定する関数 PalindromeQ が用意されてい…

Project Euler 21 / 友愛数

d(n) を n の真の約数の和と定義する。真の約数とは n 自身以外の約数のことである。d(a) = b かつ d(b) = a(a ≠ b)が成立するとき,「a と b は友愛数である」という。たとえば 220の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284…