PEをMathematicaで

Project Eulerに挑戦してみよう

001-100

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…

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

Project Euler 22 / 名前のスコア

5000個以上の名前が書かれている46Kのテキストファイル filenames.txt を用いる。まずアルファベット順にソートせよ。その後,各名前についてアルファベットに値を割り振り,リスト中の出現順の数と掛けあわせることで名前のスコアを計算する。たとえば,ソ…

Project Euler 89 / ローマ数字

ローマ数字の記法は一つの数について沢山ある場合が存在する。しかし,ある数については最良の記法が必ず存在する。例として16は次のように表せる。IIIIIIIIIIIIIIII VIIIIIIIIIII VVIIIIII XIIIIII VVVI XVI最後の例は最小の文字数で表せるという意味で最も…

Project Euler 9 / 特別なピタゴラス数

ピタゴラス数とは a a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する。これらの積 abc を計算しなさい。Problem 9 - Project Euler Mathematica は解の範囲として Integers を指定するだけで方程式の整数解を求められます。 今回,実は解の a,…

Project Euler 45 / 三角数,五角数,六角数

三角数,五角数,六角数は次のような数である。三角数Tn=n(n+1)/21, 3, 6, 10, 15, ...五角数Pn=n(3n-1)/21, 5, 12, 22, 35, ...六角数Hn=n(2n-1)1, 6, 15, 28, 45, ...T285 = P165 = H143 = 40755である。次の三角数かつ五角数かつ六角数な数を求めよ。Prob…

Project Euler 30 / 各桁の5乗

各桁を4乗した数の和が元の数と一致する数は3つしかない。1634 = 1^4 + 6^4 + 3^4 + 4^48208 = 8^4 + 2^4 + 0^4 + 8^49474 = 9^4 + 4^4 + 7^4 + 4^4ただし,1=1^4 は含まないものとする。これらの数の和は 1634 + 8208 + 9474 = 19316 である。各桁を5乗した…

Project Euler 34 / 桁の階乗

145は面白い数である。1! + 4! + 5! = 1 + 24 + 120 = 145 となる。各桁の数の階乗の和が自分自身と一致するような数の和を求めよ。(注)1! = 1 と 2! = 2 は総和に含めてはならない。Problem 34 - Project Euler どこまで調べればいいか どこかの国の数学…

Project Euler 28 / 対角線上の数の和

1からはじめて右方向に進んで時計まわりに数を増やしていくと,5×5 のらせんができる。21222324252078910196121118543121716151413両対角線上の数字の合計は101である。1001×1001のらせんを同じ方法で作ると,両対角線上の数字の和はいくつになるか?Problem…

Project Euler 48 / 自身のべき乗

1^1 + 2^2 + 3^3 + ... + 1000^(1000) の最後の10桁を求めよ。Problem 48 - Project Euler 単純に足して Mod をとりました。 k^k のかわりに PowerMod を使ってみたら,こちらの方がずっと速かったです。

Project Euler 40 / チャンパーノウン定数

正の整数を順に連結して得られる以下の10進の無理数を考える。0.123456789101112131415161718192021...小数第12位は1である。dnで小数第n位の数を表す。 d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000 を求めよ。Problem 40 - Project Euler 小数…

Project Euler 29 / a^bの個数

2 ≦ a ≦ 5 と 2 ≦ b ≦ 5について a^b をすべて考えてみよう。22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243 42=16, 43=64, 44=256, 45=1024 52=25, 53=125, 54=625, 55=3125これらを小さい順に並べて同じ数を除くと15個の項を得る。4, 8, 9, 16, 25,…

Project Euler 25 / 1000桁のフィボナッチ数

フィボナッチ数列の最初の12項は以下である。1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 14412番目の項F12が3桁になる最初の項である。1000桁になる最初の項の番号を答えよ。Problem 25 - Project Euler IntegerLength@Fibonacci でフィボナッチ数の桁数を調べ…

Project Euler 12 / 三角数の約数の個数

三角数の数列は自然数の和で表わされ,7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である。三角数の最初の10項は 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... となる。最初の7項の約数を列挙すると次のようになる。 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,1…

Project Euler 8 / 数字列中の最大の積

次の1000桁の数字のうち,隣接する4つの数字の総乗の中で最大となる値は 9 × 9 × 8 × 9 = 5832 である。 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 858615607891129494954595017379583319528…

Project Euler 19 / 日曜はじまりの月

次の情報が与えられている。 1900年1月1日は月曜日である 9月, 4月, 6月, 11月は30日まであり,2月を除く他の月は31日まである 2月は28日まであるが,うるう年のときは29日である うるう年は西暦が4で割りきれる年に起こる。しかし,西暦が400で割りきれず10…

Project Euler 4 / 最大の回文積

左右どちらから読んでも同じ値になる数を回文数という。2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である。3桁の数の積で表される回文数の最大値を求めよ。Problem 4 - Project Euler 回文数の判定は IntegerDigits と Reverse でで…

Project Euler 2 / 偶数のフィボナッチ数

フィボナッチ数列の項は前の2つの項の和である。最初の2項を1, 2とすれば,最初の10項は以下の通りである。1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...400万以下の偶数値をとる項の総和を求めよ。Problem 2 - Project Euler 1, 1からはじまる普通のフィボナッチ…

Project Euler 6 / 二乗の和と和の二乗

最初の100個の自然数について二乗の和と和の二乗の差を求めよ。Problem 6 - Project Euler これはシグマの公式を使うのが自然でしょう。 ためしにやってみたら Range の Total でもできました。Range[]^2 で平方数のリストができて,しかもこちらの方が速い…

Project Euler 1 / 3か5の倍数の総和

10未満の自然数のうち3か5の倍数は3, 5, 6, 9の4つがあり,これらの和は23である。1000未満の自然数で3か5の倍数になっているものの和を求めよ。Problem 1 - Project Euler 「3か5の倍数」で抽出して総和を求めました。

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万番目はいくつか?Problem …

Project Euler 13 / 大きな数の首位10桁

以下の50桁の数字100個の合計の上から10桁を求めなさい。3710728753390210279879799822083759024651013574025046376937677490009712648124896970078050417018260538(中略)53503534226472524250874054075591789781264330331690Problem 13 - Project Euler …

Project Euler 10 / 200万以下の素数の和

200万以下のすべての素数の和を求めよ。Problem 10 - Project Euler 200万以下の素数は PrimePi[2*10^6] 個。この範囲の数を引数として Prime[n] の和を取ります。

Project Euler 20 / 100!の各位の数字の和

100! の各位の数字の和を求めよ。Problem 20 - Project Euler 1つ前に書いたproblem 16とほぼ同じ。リストを作って総和を求めるだけ。

Project Euler 16 / 2^(1000) の各位の数字の和

2^(1000) の各位の数字の和を求めよ。Problem 16 - Project Euler IntegerDigitsで各位の数字を並べたリストを作って,総和を求めれば終わり。

Project Euler 3 / 最大の素因数

13195の素因数は5, 7, 13, 29である。600851475143の素因数のうち最大のものを求めよ。Problem 3 - Project Euler 素因数分解して一番大きな数を素因数を取り出せばいいはずです。 FactorInteger の結果はリストのリストになっているので,次のようにします…

Project Euler 15 / 格子の最短経路

2×2のマス目の左上からスタートした場合,引き返しなしで右下にいくルートは6つある。では,20×20のマス目ではいくつのルートがあるか。Problem 15 - Project Euler 二項係数を使うだけ。要するに C[40, 20] です。

Project Euler 7 / 10001番目の素数

素数を小さい方から6つ並べると2, 3, 5, 7, 11, 13であり,6番目の素数は13である。10001番目の素数を求めよ。Problem 7 - Project Euler これは簡単。Prime[n] で n 番目の素数を取り出せます。

Project Euler 5 / 最小公倍数

2520は1から10までのすべての整数で割りきれる最小の自然数である。1から20までのすべての整数で割りきれる最小の自然数を求めよ。Problem 5 - Project Euler 答えは1から20までの数の最小公倍数です。手計算で解く場合,1から20までの数を素因数分解して求…