PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 243 / 弾性

分子が分母より小さい正の分数を真分数と呼ぶ。任意の分母 d に対して真分数は d-1 個ある。たとえば, d = 12 では次のようになる。1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12約分できない分数を弾性分数(resilient fraction)と呼…

Project Euler 307 / チップの欠陥

ある工場では,製造するICチップ n 個あたり k 箇所の欠陥がランダムに生じる。一つのチップにつき複数の欠陥が生じ得る。3箇所以上の欠陥を持つチップができる確率を p(k,n) とおく。 p(3,7) = 0.0204081633...p(20,000, 1,000,000) を小数点以下10桁に丸め…

Project Euler 204 / 一般化ハミング数

ハミング数とはどの素因数も5以下であるような正整数のことである。小さい方から順に並べると次のようになる。 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 1510^8以下のハミング数は1105個ある。素因数が n 以下の正整数を type n の一般化ハミング数と呼ぶことにする…

Project Euler 549 / 階乗の整除性

10 が m! を割り切る最小の m は m=5 である。25 が m! を割り切る最小の m は m=10 である。n が m! を割り切る最小の m を s(n) とする。s(10)=5, s(25)=10 である。2 ≤ i ≤ n において Σs(i) を S(n) とする。S(100)=2012 である。S(10^8) を求めよ。Prob…

Project Euler 500 / 500問目!!!

120 は 16 個の約数を持つ最小の数である。2^(500500) 個の約数を持つ最小の数を求めよ。回答を modulo 500500507 にして答えよ。Problem 500 - Project Euler 以下,n 個の約数をもつ最小の自然数を f(n) であらわします。 f(16)=120 の吟味 入試問題などで…

Project Euler 86 / 直方体のルート

下に示す直方体は寸法が 6×5×3 である。この直方体のある頂点Sにクモがいる。また,反対の頂点Fにはハエがいる。SからFまで壁に沿って移動する最短ルートは図に示す通りで,この長さは10である。最短ルートの候補は3本あるが,最短のものがいつも整数長さと…

Project Euler 303 / 小さい桁を持つ倍数

正の整数 n の倍数の中で各位の数字がすべて2以下(10進法)のものの最小値を f(n) とする。 f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222Σ[n=1...100] f(n)/n =1136107 である。Σ[n=1...10000] f(n)/n を求めよ。Problem 303 - Project Euler f(n) …

Project Euler 348 / 平方数と立方数の和

多くの数は平方数と立方数の和として表せる。2通り以上の方法で表せるものもある。いずれも1より大きな平方数と立方数の和としてちょうど4通りの方法で表せる回文数を考えよう。たとえば 5229225 は回文数であり,ちょうど4通りの異なる方法で表せる。 2285^…

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 44 / 五角数

五角数は Pn = n(3n-1)/2 で生成される。最初の10項は 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ... である。P4+P7 = 22+70 = 92 = P8 であるが,差 70-22 = 48 は五角数ではない。五角数のペア Pj と Pk について差と和が五角数になるものを考える。差を D…

Project Euler 235 / 等差等比数列

等差数列と等比数列を用いた次の数列を考える。 u(k) = (900-3k)r^(k-1)s(n) = Σ[k=1...n]u(k) とする。s(5000) = -600,000,000,000 をみたす r を求めよ。小数点以下12桁に四捨五入して解答を入力せよ。Problem 235 - Project Euler これは易しい。等差と等…

Project Euler 407 / 冪等元

0 ≤ a ≤ 5 のときの a に対し a^2 mod 6 を計算すると 0,1,4,3,4,1 となる。a2 ≡ a (mod 6) をみたす最大の a は 4 となる。 a2 ≡ a (mod n) をみたす a 1 ≤ n ≤ 10^7 のときの ΣM(n) を求めよ.Problem 407 - Project Euler a^2-a = a(a-1) において a と a-…

Project Euler 346 / 強いレピュニット

7は特別な数である。2進数では111と表せ,6進数では11と表せる。 7(10) = 11(6) = 111(2)別の言い方をすると,7は少なくとも二種類の1より大きい底の記数法でレピュニット(全ての桁が1である自然数)である。上記の特徴を有する正の整数を「強いレピュニッ…

Project Euler 82 / 経路の和:3方向

下記の5次の正方行列で一番左の行の任意のセルから開始し一番右の行の任意のセルで終わる道を探索する。ただし上下右にのみ移動できるものとする。一番小さなパスは下で赤の太字で示されたものである。このときの合計は994になる。1316732341031820196342965…

Project Euler 205 / サイコロゲーム

ピーターは4面のサイコロを9つ持っている。サイコロの各面には1, 2, 3, 4と書いてある。コリンは6面のサイコロを6つ持っている。サイコロの各面には1, 2, 3, 4, 5, 6と書いてある。ピーターとコリンはサイコロを投じ,出た目の合計を比べる。合計が多い方が…

Project Euler 74 / 桁の階乗による連鎖

145は各桁の階乗の和が自分自身に一致することで有名である。1! + 4! + 5! = 1 + 24 + 120 = 145169の性質はあまり知られていない。これは自分自身に戻る数の中で最長の列をなす。このように他の数を経て自分自身に戻るループは3つしか存在しない。 169 → 36…

Project Euler 60 / 素数ペア集合

素数3, 7, 109, 673は非凡な性質を持っている。任意の2つの素数を任意の順でつなげると,また素数になっている。たとえば7と109を用いると,7109と1097の両方が素数である。これら4つの素数の和は792である。これはこのような性質をもつ4つの素数の集合の和…

Project Euler 62 / 立方数置換

立方数 41063625(=345^3) は桁の順番を入れ替えると2つの立方数になる。56623104(=384^33) と 66430125(=405^33) である。41063625 は立方数になるような桁の置換をちょうど3つもつ最小の立方数である。立方数になるような桁の置換をちょうど5つもつ最小の立…

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 343 / 分数数列

正の整数 k に対して分数 xi/yi による有限数列 ai は次のように定義される。a1 = 1/k ai = (x(i-1)+1)/(y(i-1)-1) [i>1 で約分可能なときは約分する]ai がある整数 n になったとき数列はそこで終了とし,f(k) = n とする。たとえば k = 20 のときは次のよう…

Project Euler 347 / 二つの素数で割り切れる最大の整数

素数2と3の両方のみで割り切れる最大の整数 ≤ 100 は96である。 96 = 2^5*3 2つの異なる素数 p と q に対し,p と q の両方のみで割り切れる最大の正の整数 ≤N を M(p,q,N) とする。そのような正の整数が存在しなければ M(p,q,N) = 0 である。たとえば M(2,3…

Project Euler 301 / Nim

Nimは2人のプレイヤーがいくつかの山に分かれた石を交互にとっていくゲームである。次のようなNimについて考える。 ゲーム開始時点で3つの山がある 各ターンでプレイヤーは任意の1つの山から1つ以上の任意の数の石をとる すべての石がなくなり,石を取ること…

Project Euler 340 / クレイジー関数

整数 a, b, c に対してクレイジー関数 F(n) を次のように定義する。 F(n) = n - c (n > b のとき) F(n) = F(a + F(a + F(a + F(a + n)))) (n ≤ b のとき) また, S(a, b, c) =Σ[n=0,b] F(n) と定義する。たとえば a = 50, b = 2000, c = 40 ならば F(0)=3…

Project Euler 323 / ランダムな整数のビット論理和演算

y0, y1, y2,... をランダムな32ビット符号なし整数からなる数列とする。0≦yi<2^32 で,すべての値が同様に確からしい。数列 xi に対し次の反復が与えられる。 x0 = 0 xi = x(i-1) | y(i-1) (i>0)(| はビット単位のOR演算) すべての i≧N に対し xi = 2^3…

Project Euler 267 / 億万長者

あなたに変わった投資の機会が与えられる。£1 の資産からはじめて固定した比率 f を選び, 資産の中でその比率を公正なコイントスに賭け, 1000 回繰り返す。賭け金は表のときは倍戻り,裏の時は失う。例えば f=1/4 のとき,最初のトスでは £0.25 賭け,表が出…

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

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

大数の学コンを解いてみた

『大学への数学』2017年5月号の学力コンテスト第6問が非常に Mathematica 向きの問題だったのでやってみました*1。 29^1+29^2+29^3+...+29^(2017) を n で割った余りが29になるような自然数 n を小さい順に5個求めよ。 とりあえず答を出す いかにも Mod や S…

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

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

Project Euler 277 / 修正コラッツ列

整数の修正コラッツ列は値 a1 から始めて次のようにして得られる。an が 3 で割り切れるならば a(n+1) = an/3 これを大きな下ステップ "D" と表す。an を 3 で割った余りが 1 ならば a(n+1) = (4an + 2)/3 これを大きな上ステップ "U" と表す。an を 3 で割…

Project Euler 265 / 2進円

2^N の2進数の数字は時計回りに N 桁連続する数字すべてで網羅するように円状に並べることができる。例えば N=3 では回転を無視すると2つの円状の配置が可能である。最初の配置では時計回りの3桁の数列は 000, 001, 010, 101, 011, 111, 110, 100 である。そ…

Project Euler 250 / 250250

要素の合計が250で割り切れるような {1^1, 2^2, 3^3,..., 250250^250250} の空でない部分集合の個数を求めよ。最下位の16桁を答えとして入力せよ。Problem 250 - Project Euler 部分集合の個数は 2^250250 個。とても全部は調べられないので,漸化式を使って…

Project Euler 225 / トリボナッチを割り切らない数

数列 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 ...は T1=T2=T3=1 および Tn=T(n-1)+T(n-2)+T(n-3) によって定義される。27はこの数列の任意の項を割り切らないことが証明できる。27はこの性質を持つ最初の奇数である。この数列の任意の項を…

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 91 / 整数座標における直角三角形

点 P(x1, y1) と点 Q(x2, y2) はともに格子点であり,原点 O(0,0) とあわせてΔOPQをなす。各座標が 0 ≤ x1, y1, x2, y2 ≤ 2 をみたすとき,直角三角形は14個できる。0 ≤ x1, y1, x2, y2 ≤ 50 のとき,直角三角形は何個作れるか?Problem 91 - Project Euler …

Project Euler 429 / 単約数の自乗和

ある数 n の単約数(unitary divisor)d とは gcd(d, n/d)=1 となる n の約数のことである。4!=24 の単約数は 1, 3, 8, 24 であり,これらの自乗和は1^2 + 3^2 + 8^2 + 24^2 = 650n の単約数の自乗和を S(n) で表す。S(4!)=650 である。S(100,000,000!) を求…

Project Euler 401 / 約数の平方和

6の約数は 1,2,3,6 であり,これらの数の平方和は 1+4+9+36=50 となる。n の約数の平方和を sigma2(n) で表し,sigma2 の総和を SIGMA2 で表す。 SIGMA2(n)=Σsigma2(i) (i=1 から n まで)SIGMA2 の最初の6項は 1,6,16,37,63,113 である。SIGMA2(10^15) modul…

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 問題131とほとんど同じ方法で解けてしまった。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 の最小…

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 個の四辺形のうち厳密に平…