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

PEをMathematicaで

Project Eulerに挑戦してみよう

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 105 / 特殊和集合:検査

大きさ n の集合 A の要素の和を S(A) で表す。空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば,A を特殊和集合と呼ぼう。 S(B)≠S(C); つまり,部分集合の和はすべて異なる B が C より多くの要素を含んでいれ…

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 83 / 経路の和:4方向

下記の5次の正方行列で左上のセルから出発して上下左右に移動し,右下のセルで終了する道を探索する。一番小さな道は下で赤で示されており,このときの合計は2297になる。いま, 31Kのテキストファイル matrix.txt には 80*80 の行列が書かれている。左上のセ…

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 203 / 無平方二項係数

二項係数 nCk は三角形の形に並べることができる(パスカルの三角形)。上から8行見るとパスカルの三角形は12個の異なる数を含む。1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35である。任意の素数の二乗が n を割り切らないとき,「n は平方因子を持たない」と…

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

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

Project Euler 66 / ディオファントス方程式

次の形式の2次のディオファントス方程式を考えよう。 x^2 - Dy^2 = 1たとえば D=13 のとき,x を最小にする解は 649^22 - 13×180^22 = 1 である。D が平方数のとき,正整数のなかに解は存在しないと考えられる。D={2, 3, 5, 6, 7} に対して x を最小にする解…

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 51 / 素数の桁置換

*3の第1桁を置き換えることで 13, 23, 43, 53, 73, 83という6つの素数が得られる。56**3の第3桁と第4桁を同じ数で置き換えることを考えよう。この5桁の数は7つの素数をもつ最初の例である。 56003, 56113, 56333, 56443, 56663, 56773, 5699356003はこのよう…

Project Euler 168 / 数の循環

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

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である自然数)である。上記の特徴を有する正の整数を「強いレピュニッ…

レベル6になりました

150問解けたのでレベル6になりました。限界近いはずが意外と頑張れるもんですね。レベル5になったときに「最新の第601問を解いて~」と書きましたが,第601問の記事は非公開にすることにしました。普段私が解いているような古い易しい問題ならいざしらず,こ…

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

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はこの性質を持つ最初の奇数である。この数列の任意の項を…

レベル5になりました

解いた問題数が125問になり,レベル5に昇格しました。また,最新の第601問を解いて,その解答を掲示板にポストしたことでアワードを2つもらいました。 On The Ball(最新の問題を解く) Hello World!(はじめて永久保存ポストを投稿) 行き詰まりかけたとき…

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