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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 317 / 爆竹

爆竹が地上100mの高さで爆発する。爆竹は爆発すると非常に細かい破片となり,四方八方に初速 20m/s で広がる。破片は空気抵抗を受けず,g=9.81 m/s^2 で一定の重力場において動くものと仮定する。破片が地面に到達するまでに動いた領域の体積(m^3)を小数点以…

Project Euler 291 / Panaitopol素数

素数 p がある正の整数 x, y に対してをみたすとき,p を Panaitopol 素数 と呼ぶ。 5x10^15 未満の Panaitopol 素数はいくつあるか。Problem 291 - Project Euler 問題216とほとんど同じ方法で解けてしまった。x と y の最大公約数を g として x=gX, y=gY(…

Project Euler 216 / 2n^2-1 の形の素数

式 t(n) = 2n^2-1 (n>1)で表される数 t(n) について考える。最初の数個を挙げると 7,17,31,49,71,97,127,161 となる。 この中では 49 = 7*7 と 161 = 7*23 だけが素数でない。n ≤ 10000 では 2202 個の t(n) が素数である。n ≤ 50,000,000 で素数である t(n)…

Project Euler 131 / 素数と立方数の関係

いくつかの素数 p では,適当な正の整数 n が存在して n^3+pn^2 が立方数になる。たとえば p = 19のとき 83+19x82=123 である。このような性質を持つ各素数について, n の値は一意に定まる。また,100未満の素数では4つしかこの性質をもたない。この性質を持…

Project Euler 125 / 回文数の和

回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ。 6^2+7^2+8^2+9^2+10^2+11^2+12^21000 未満で連続する平方数の和で表せる回文数は11個あり,その合計は4164である。この問題では正の整数の平方のみを扱うため, 1=0^2+1^2 は含め…

Project Euler 164 / 連続3桁の和は9以下

どの連続した3桁の和も9以下のような20桁の数(先頭は0ではない)はくつあるか?Problem 164 - Project Euler たとえば123の次の桁には0~4が続きますが,これを「下2桁が23の数から下2桁が30, 31, 32, 33, 34の数ができる」ととらえて連立漸化式にもちこむ…

Project Euler 134 / 素数ペアの結合

連続する素数 p1=19, p2=23 について考える。1219は末尾の桁が p1 からなり p2 で割り切れる最小の数である。p1=3, p2=5 を除けばすべての p2>p1 なる連続する素数のペアについて, 末尾の桁が p1 からなり p2 で割り切られる数 n が存在する。S を n の最小…

アワード2つ追加

順調に解き進んで,アワードを2つゲットしました。 As Easy As Pi:IDが3,14,15,92,65,35,89,79,32,38,46(円周率2桁区切り)の問題を解いた One Percenter:問題解答数ランキングで上位1%に入った One Percenter は一つの目標だったので,とれてホッとしま…

Project Euler 138 / 特殊な二等辺三角形

底の長さ b が16,脚の長さ L が17の二等辺三角形を考える。ピタゴラスの定理より三角形の高さは h=√(17^2−8^2)=15 となる。高さは底の長さより1だけ短い。b=272, L= 305とすると h=273 となり,これは底の長さより1だけ長い。この三角形は h=b±1 という性質…

Project Euler 239 / 場違いな素数たち

それぞれ 1 から 100 まで番号の書かれたディスクが一列に無作為に並んでいる。ちょうど 22 個の素数の番号のディスクが番号順の位置と異なる場所にある確率を求めよ。素数でない番号のディスクはどれも番号順の位置にあってもなくてもよい。解答は小数点以…

Project Euler 188 / ハイパーべき乗

数 a の正整数 b によるハイパーべき乗(hyperexponentiation)または テトレーション(tetration)を a↑↑b または ba と書き,以下のように再帰的に定義する。 a↑↑1 = a a↑↑(k+1) = a^(a↑↑k) 定義によれば 3↑↑2=3^3=27 であり,3↑↑3=3^27=7625597484987 と…

Project Euler 169 / ある数を2のべき乗の和で表せる方法の数の探査

整数nを2のべき乗の和で表すことを考える。ただし各数は高々2回しか使ってはいけないものとする。この表し方の数をf(n)とする。f(0)=1と定義する。例として n=10 を考える。 1+1+8 1+1+4+4 1+1+2+2+4 2+4+4 2+8 5通りの異なる表し方があるので f(10)=5 であ…

Project Euler 504 / 四角内部の平方

頂点が以下のような座標軸の格子点に置かれている四辺形を ABCD としよう。A(a, 0), B(0, b), C(−c, 0), D(0, −d)1≤a,b,c,d≤ m であり,a,b,c,d,m は整数とする。m=4 のとき, ABCD を描く方法の数がちょうど 256 個ある。その 256 個の四辺形のうち厳密に平…

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 …

レベル4になりました

100問解けたのでレベル4になりました。また,問題番号が1,3,9,27,81,243(3のべき乗)の問題を解いたので「Trinary Triumph」というアワードをもらいました。アイコンは相変わらず変w自分の実力ではほとんど限界近い感じなのですが,新しいPCを買って作業環…

Project Euler 587 / 凹三角形

左下図のように円に外接する正方形に対し,青い部分を「Lセクション」と呼ぶことにする。 また,右下図のように対角線を引いて,オレンジの部分を凹三角形と呼ぶことにする。この図では凹三角形の面積はLセクションの面積の半分である。 同じ大きさの円2つを…

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 211 / 約数の2乗の和

正の整数 n に対して σ2(n) を約数の2乗の和とする。たとえばσ2(10) = 1+4+25+100 = 1300 Problem 211 - Project Euler 約数の2乗の和は DivisorSigma[2,n] で簡単に求められますが,平方数の判定で苦労しました。Mathematica には isSquareQ みたいな関数が…

Project Euler 101 / 最適多項式

数列のk個の項を与えられたときに,次の項を確実に求めることは不可能である。その数列にあう多項式が無限個存在するからである。例として立方数の数列を考えよう。これは生成関数 u_n = n^3 で定義され,1,8,27,64,125,216,...となる。この数列の最初の2項…

Project Euler 172 / 桁の繰り返しが少ない数

どの数字も3回を超えてあらわれないような18桁の数(先頭の0はゆるされない)はいくつあるか?Problem 172 - Project Euler 漸化式を使って解きました。3回,2回,1回登場する文字がそれぞれ x, y, z 個ある数の個数を f(x, y, z) とおきます。条件をみたす …

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 119 / 数字べき乗和

512は興味深い数である。各桁の和を何乗かしたものに等しくなっているからである。5+1+2 = 8, 8^3=512この特性をもつ他の数はたとえば 614656 = 28^4 がある。この数列の第 n 項を a_n と定義し, また2桁以上であるとしよう。a2 = 512, a10 = 614656 となる…

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 286 / 得点確率

Barbara は数学者でありバスケットボール選手である。彼女は距離 x からシュートしたときに得点できる確率がちょうど (1-x/q) であることに気づいた。ここで q は 50 よりも大きな実定数である。各予行練習では,彼女は 距離 x=1, x=2, ..., x=50 からシュー…

Project Euler 231 / 二項係数の素因数分解

二項係数 C[10, 3] = 120 は 120 = 2^3 ×3×5 = 2×2×2×3×5 2+2+2+3+5 = 14 をみたす。C[10, 3] を素因数分解した項の和は 14 となる。C[20000000, 15000000] を素因数分解した項の和を求めよ。Problem 231 - Project Euler ダメ元で素因数分解させてみたらや…

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 357 / 素数生成整数

30の約数について考えよう。1,2,3,5,6,10,15,3030の約数 d はそのすべてにおいて d+30/d の値が素数になる。n のすべての約数 d について d+n/d が素数になるような 10^8 以下の正の整数 n の合計を求めよ。Problem 357 - Project Euler 素数判定は PrimeQ[ …

Project Euler 381 / (素数-k)階乗

素数 p について,1 ≤ k ≤ 5 の k に対し S(p) = (Σ(p-k)!) mod(p) としよう。たとえば p=7 の場合,(7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)! = 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2 = 872872 mod(7) = 4 となるので, S(7) = 45 ≤ p 5 ≤ p Problem …

Project Euler 17 / 数字の文字数

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

Project Euler 493 / 虹の下で

壺の中に虹の7色と同じ色のボールがそれぞれ10個ずつ計70個入っている。ランダムに20個のボールを取り出したときの異なる色の数の期待値はいくつになるか? a.bcdefghij の形式で小数点以下9桁まで答えよ。Problem 493 - Project Euler これは手計算で解けま…

レベル3になりました

75問解いたのでレベル3になりました。また,101から200までの問題を10問ごとにひとつずつ解いたので Decimation I というアワードをゲットしました。これは狙って取りました。解けるところから解く一方で,Mathematicaの本を読んでます。先日,アジソン ウェ…