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

PEをMathematicaで

Project Eulerに挑戦してみよう

101-200

Project Euler 142 / 完全平方数コレクション

x+y, x-y, x+z, x-z, y+z, y-z がすべて平方数となる整数の組 x > y > z > 0で, 最小の x+y+z を求めよ。Problem 142 - Project Euler 与えられた数を順に a^2, b^2, ..., f^2 とおいて x, y, z について解きます。 x=(a^2+b^2)/2=(c^2+d^2)/2 y=(a^2-b^2)/2…

Project Euler 133 / レピュニットの非因数

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。 R(6) = 111111R(10^n) というレピュニット数について考える。R(10), R(100), R(1000) は 17 では割り切れないが,R(10000) は 17 で割り切れる。さらに,R(10^n) が 19…

Project Euler 132 / 巨大なレピュニットの素因数

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。R(10) = 1111111111 = 11×41×271×9091 の素因数の和は 9414 である。R(10^9) の最初の40個の素因数の和を求めよ。Problem 132 - Project Euler 非常に大きな数が相手で…

Project Euler 130 / 素数桁レピュニットと同じ性質を持つ合成数

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。 R(6) = 111111GCD(n, 10)=1 となる正整数 n について, 必ず正整数 k が存在し n が R(k) を割り切ることが証明できる。A(n) でそのような最小の k を表す。 A(7) = 6, …

Project Euler 129 / レピュニットの非整除性

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。 R(6) = 111111GCD(n, 10) = 1 なる正の整数 n が与えられたとき,R(k) が n で割り切られるような k が常に存在することが示せる。A(n) をそのような k の最小のものと…

Project Euler 174 / 穴あき正方形の数え上げ

輪郭が正方形で,正方形の穴を持ち,縦にも横にも対称性をもつものをlaminaeと定義する。8個のタイルが与えられると,3x3の1x1の穴をもつlaminaしか作れないが,32個のタイルならば2つの異なったlaminaeが作れる。タイルの枚数を t で表すと,t=8 は L(1) 型…

Project Euler 173 / 100万枚以下のタイルで何通りの穴あき正方形を作れるか

輪郭が正方形で,正方形の穴を持ち,縦にも横にも対称性をもつものをlaminaeと定義する。たとえば32個のタイルを使うと以下の二つの異なったlaminaeが作れる。100個以下のタイルを使うと41種類のlaminaeが作れる。100万個以下のタイルを使うと何種類のlamina…

Project Euler 124 / 順序付き根基

n の"根基"(radical)は rad(n) で表し,n の素因数の積を意味する。たとえば 504 = 2^3 × 3^2 × 7より rad(504) = 2×3×7 = 421 ≤ n ≤ 10 に対して rad(n) を計算し, rad(n) を対象にソートする。rad(n) が同じ場合は n を対象にソートすると以下のようになる…

Project Euler 168 / 数の循環

自然数 142857 を考える。最後の桁 7 を一番前に持っていく,すなわち,右に循環させると 714285 を得る。714285 = 5*142857これは 142857 の珍しい性質を示している。右に循環させた数の約数になっている。10 Problem 168 - Project Euler nの一般形は? 10…

Project Euler 136 / 単体差分

x, y, z を等差数列となるような正の整数とする。正の整数 n が n=20 と与えられたとき方程式 x^2 - y^2 - z^2 = n はただ一つの解を持つ。13^2 - 10^2 - 7^2 = 20100未満の n で方程式がただ一つの解を持つ n は25個ある。5000万未満の n で方程式がただ一…

Project Euler 190 / 加重積の最大化

Sm = (x1, x2, ..., xm) を x1 + x2 + ... + xm = m かつ Pm = x1^1 * x2^2 * ... * xm^m を最大にする m 項の正の実数の組とする。たとえば [P10] = 4112 である([ ]は実数の整数部分を取り出す関数)。2 ≤ m ≤ 15について Σ[Pm] を求めよ。Problem 190 - …

Project Euler 197 / 再帰的に定義された数列のふるまい

f(x) = [2^(30.403243784 - x^2)] /10^9 ([ ] は床関数)とし,数列 un を u0 = -1, u(n+1) = f(un) と定義する。n = 10^12 に対して un + u(n+1) を求めよ。小数点以下9桁で解答せよ。Problem 197 - Project Euler 多分,周期性があるんだろうなあと思ってプ…

Project Euler 144 / レーザーの多重反射

レーザー物理学では, "white cell"とはレーザー光線を遅延させるための鏡の装置のことである。光線はcellに入り,鏡で反射して最終的には飛び出す。white cell が楕円 4x^2 + y^2 = 100 の場合を考える。 −0.01 ≦ x ≦ +0.01 に対応する上部に穴が空いていて…

Project Euler 191 / 賞をもらえる文字列

ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している。3日連続で休むか2回以上遅刻した生徒は褒賞金を得る権利を失う。n日間の各生徒の出席状況を3進の文字列で表す。文字はL (late,遅刻),O (on time,出席),A (absent,欠席) である。4日間の…

Project Euler 135 / 同一差分

正の整数 x, y, z が等差数列として与えられたとき, x^2 - y^2 - z^2 = n がちょうど2個の解を持つような最小の正の整数は n=27 である。 34^2 − 27^2 − 20^2 = 12^2 − 9^2 − 6^2 = 27n=1155 は方程式がちょうど10個の解を持つ最小の値である。ちょうど10個…

Project Euler 102 / 三角形の包含

3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように平面上にランダムに与えられる。次の2つの三角形を考える。 A(-340,495), B(-153,-910), C(835,-947) X(-175,41), Y(-421,-714), Z(574,-645) 三角形ABCは原点を内部に含み,XYZは原点を内部に含…

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 の最小…

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

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

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

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

Project Euler 113 / 非はずみ数

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

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

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