NEW GAME!を観ました。プログラミング始めます。(21)
記事を書くとき、はてな記法にするのいっつも忘れてしまう。
※基本的に、愛知大学の有澤先生がプログラミングの講義で使用しているテキスト「Pythonによるプログラミング入門」に沿って進めています。
※Python 2.7.13を使用しています。
今回のテーマは「フェルマーの問題」です。
フェルマーの問題
問題提起
ついに Fermat(フェルマー) の大定理が証明されたそうである。この定理は n が 3 以上の整数の時、
の自然数解 (x , y , z) は存在しない事を主張する。
(引用元:Pythonによるプログラミング入門, p. 49)
金色のガッシュ!! でウンコティンティンが出題してたやつだ。
ここではそれに似た問題について考えていくみたいです。
例11
となる自然数の組を見つけよ。
(引用元:Pythonによるプログラミング入門, p. 50)
これの答えを系統的に探すプログラムが以下。
譜 4.12 整数解を求めるプログラム
for z in range(1,20): for y in range(1,z+1): for x in range(1,y+1): v = x**3 + y**3 + z**3 u = int(v**(1.0/3)+0.5) if u**3== v: print x,y,z,u(引用元:Pythonによるプログラミング入門, p. 50)
結果
3 4 5 6 1 6 8 9 6 8 10 12 9 12 15 18 2 12 16 18 7 14 17 20 3 10 18 19
- 全体:x =< y =< z の条件で試す(手あたり次第計算するよりも効率的)
- 1:上限は20(上限を決めておかないとプログラムが終わらないから)
- 4~6:v ** (1/3) + 0.5 の小数点以下を切り捨てた整数値 u を 3乗した値が v と等しいとき、x**3+y**3+z**3=u**3 を満たすと判断→x, y, z, u を表示
補足:Python の小数点計算
譜 4.12 の6行目では、v (= x**3 + y**3 + z**3) の 1/3 乗に 0.5 を足した値の整数値を u にしている。
0.5を足す意味ってあるの?と思ったので、結果の一つ目 (3 4 5 6) を例にやってみた。
プログラム(1)a ** 1/3 の色々な計算結果
a=(3**3)+(4**3)+(5**3) b=a**(1.0/3) c=int(a**(1.0/3)) d=int(a**(1.0/3)+0.5) print b, c, d
結果
6.0 5 6
- 1:小数点以下も考えた計算結果(".0"は小数点以下も考えてますよという Python のアピール)
- 2:int() に 0.5 を含まなかった場合。ここでは 6 が正しいのに、なぜか1少ない値が出た。
- 3:プログラムで使われている結果。問題の答えとしてはこっちが正しい。
これは 1.0/3 が悪いんだと思う。1.0 / 3 は 小数点で書くと、0.33333...だけど、Python の計算だと最大でも小数点以下何桁まで、みたいな制限がある。だから、完璧に1/3を計算できない。
今の a (=(3**3)+(4**3)+(5**3)) について、以下のような計算をしてみると、
プログラム(2)a ** 1/3 の近似値
a=(3**3)+(4**3)+(5**3) b=a**0.3 c=a**0.33 d=a**0.333 print b, c, d
結果
5.01575281247 5.89345182585 5.98925906864
このように、小数点以下の桁が増えるほど 6 に近付いていくものの、ぴったり 6 にはならない。
だから、int() で小数点以下を切り捨てると 5 になってしまった、というわけ。それを防ぐために 0.5 を足してたんすね。0.5 という値自体にはたぶん意味はなくて、1以下ならなんでも良いと思われる。
でもプログラム(1)の2行目だと結果が6.0じゃん!と思うけれど、これは Python で計算できる桁数の値が近似的にほぼ 6 だから 6.0 って表示しときましたよ、みたいなことだと思う。譜 4.12 を見るとわかるけど、最終的には自然数の u と v を比較しないといけないから、int() での整数化は必要な手順なんだよな。
ちなみに Python の計算では、たとえば 0.1 は正確には 0.1 ではないらしい。今回の問題に直接関係はないけど、調べてる過程で知ったので参考までに。これは10進数を2進数で無理矢理表現していることが原因らしい。詳しくは以下のリンクで説明されてる。
問2
となる自然数の組についてはどうだろうか?
(引用元:Pythonによるプログラミング入門, p. 50)
譜 4.12 をちょっと書き換えて試してみた。
プログラム(3)問2
for z in range(1,30): for y in range(1,z+1): for x in range(1,y+1): v = x**4 + y**4 + z**4 u = int(v**(1.0/4)+0.5) if u**4== v: print x,y,z,u
結果
なし
一応1行目で上限を30や50にしてみたけど、結果は出力されず。問題の式を満たす組み合わせはないということか?
調べてみたところ、これはオイラーの予想と呼ばれるものらしい。
上記サイトによると、条件を満たす組み合わせは存在するらしい。でも桁数がヤバイので、上限50では結果が出なくて当然だった。というわけで、とりあえずプログラム的にはOK。
以上!