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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 317 / 爆竹

爆竹が地上100mの高さで爆発する。爆竹は爆発すると非常に細かい破片となり,四方八方に初速 20m/s で広がる。破片は空気抵抗を受けず,g=9.81 m/s^2 で一定の重力場において動くものと仮定する。

破片が地面に到達するまでに動いた領域の体積(m^3)を小数点以下4桁に丸めて答えよ。

Problem 317 - Project Euler


普通の高校生に解けそうな問題でした。まず適当な座標をとります。

 x = v \cos\theta\, t,\, y = h + v \sin \theta\, t-\dfrac{1}{2}gt^2

t を消去。

 y=h+x\tan\theta-\dfrac{g}{2v^2 \cos^2 \theta}x^2

これの包絡線を求めてバウムクーヘン法で体積を求めます。


答えの表示が地味に面倒でした。Mathematica は大きな数は a*10^b の形で表示する仕様です。N[ ] で桁精度を指定したり,ScientificForm[ ] を使ったりしてもうまくいかなかったので,整数部分と小数部分にわけて表示してお茶を濁しました。

Project Euler 291 / Panaitopol素数

素数 p がある正の整数 x, y に対して

 p=\dfrac{x^4-y^4}{x^3+y^3}

をみたすとき,p を Panaitopol 素数 と呼ぶ。
5x10^15 未満の Panaitopol 素数はいくつあるか。

Problem 291 - Project Euler


問題216とほとんど同じ方法で解けてしまった。

x と y の最大公約数を g として
x=gX, y=gY(XとYは互いに素)
とおいて与式に代入します。

 p=\dfrac{(X-Y)(X^2+Y^2)}{X^2-XY+Y^2}g

a と b の最大公約数を (a, b) であらわして,約分の様子を調べます。

 (X^2+Y^2, X^2-XY+Y^2)=(X^2+Y^2, -XY)

X と Y は互いに素なので,X^2+Y^2 は X の1以外の約数でも Y の1以外の約数でも割り切れません。上式の値は1。

 ( (X+Y)^2, X^2-XY+Y^2)=(4XY, X^2-XY+Y^2)

これも1です。p が素数だということも考えると

 p=(X-Y)(X^2+Y^2),\, g=X^2-XY+Y^2

X-Y=1 が言えて,
 p=(Y+1)^2+Y^2=2Y^2+2Y+1

この形の素数を探します。


variee.hatenadiary.com

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) はいくつあるか。

Problem 216 - Project Euler


ひねりのないブルートフォースで解けてしまった…… 出題されたころのPCでは不可能な計算量だったんでしょうか?

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

いくつかの素数 p では,適当な正の整数 n が存在して n^3+pn^2 が立方数になる。たとえば p = 19のとき 83+19x82=123 である。

このような性質を持つ各素数について, n の値は一意に定まる。また,100未満の素数では4つしかこの性質をもたない。

この性質を持つ100万未満の素数は何個あるだろうか?

Problem 131 - Project Euler


数学の問題でした。PCは最後の計算に使うだけです。

n^3+pn^2=n^2(n+p) の素因数分解を考えます。a と b の最大公約数を (a,b) であらわすと

 (n+p,n)=(p,n)=p,\,1

■(n+p,n)=p のとき

n=kp とおけます。

 n^3+pn^2=(kp)^3+p (kp)^2=p^3 k^2(k+1)

k と k+1 は互いに素なので,これは立法数になりません。

■(n+p,n)=1 のとき

n^3+pn^2=n^2(n+p) において n, n+p はともに立法数です。
n=x^3, n+p=y^3 とおいて n を消去すると

 p=y^3-x^3=(y-x)(y^2+yx+x^2)

p は素数かつ y^2+yx+x^2>1 なので y-x=1。y=x+1 として上式に代入すると

 p=(x+1)^3-x^3=3x^2+3x+1

この形の素数を数えれば終わりです。

Project Euler 125 / 回文数の和

回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ。

6^2+7^2+8^2+9^2+10^2+11^2+12^2

1000 未満で連続する平方数の和で表せる回文数は11個あり,その合計は4164である。この問題では正の整数の平方のみを扱うため, 1=0^2+1^2 は含めないことに注意せよ。

回文数であり,かつ連続する平方数の和で表せる10^8未満のすべての数の合計を求めよ。

Problem 125 - Project Euler


「下手にリストをつくってはいけない」みたいな問題でした。

最初の解答がこちらです。平方数の和 f(n) の差のリストを作ったところ,106秒かかりました。


f(n) - f(n-1)≧10^8 で n の上限(n=7072)をおさえましたが,これだけでは差の最大値は
f(7072) - f(1)=117922753519
と12桁もの数になって,10^8を大幅に超えます。こういう無駄な数が大量に含まれている結果,計算時間がのびているのだと思います。

次の解答がこちら。For ループを二重に使って無駄な計算を避けました。結果は約3秒。30倍以上速くなりました。