オイラー予想の反例４乗の場合

　　オイラー予想の反例　４乗の場合 会社員 2004/02/20 23:21:51 
　　├発見するのに必要な現実的速度にはぜんぜん... 青木太一 2004/02/21 02:13:31 
　　│└５乗の反例は何とかでてきました。 会社員 2004/02/21 23:04:08 
　　│　└そうですか。あきらめましたか。 青木太一 2004/02/22 19:25:44 
　　│　　└５乗のプログラムのとき気づいたのですが・... 会社員 2004/02/22 22:24:29 
　　│　　　├Ａ≦Ｂ≦Ｃ＜Ｄ 会社員 2004/02/22 22:45:25 
　　│　　　├すいません。高校より上の数学はあまり得意... 青木太一 2004/02/23 00:35:52 
　　│　　　│├まだ、プログラムにしてませんが・・・ 会社員 2004/02/23 22:53:19 
　　│　　　││└まだ会社員さん見てるかな？ 青木太一 2004/02/25 19:54:52 
　　│　　　││　├偶奇判定を使えば多少速くなりました。 会社員 2004/02/28 23:55:51 
　　│　　　││　│├誤記修正。（プログラム間違いました） 会社員 2004/02/29 00:02:04 
　　│　　　││　││└これ間違ってます。 会社員 2004/03/07 21:16:49 
　　│　　　││　│└もっといい参考文献をみつけました。 青木太一 2004/03/06 17:44:13 
　　│　　　││　│　└資料ありがとうございます。 会社員 2004/03/07 21:55:46 
　　│　　　││　└５の剰余で、おもしろいことがわかりました... 会社員 2004/02/29 18:43:13 
　　│　　　│└紹介いただいた「a+b+c=dを満たすようなa,b... 会社員 2004/02/25 21:56:37 
　　│　　　│　└このプログラムだとエラーになります。 会社員 2004/02/26 21:56:45 
　　│　　　├オリラ―の定理、公式は私も興味あります。... 小塚貞典 2004/02/23 16:54:42 
　　│　　　└４次方程式までは複素数で４個の解を持つが... 小塚貞典 2004/02/23 17:29:49 
　　└フェルマ―の問題が解けた話ですか？ 小塚貞典 2004/02/23 17:44:10 
　　　└フェルマーの定理の拡張です 会社員 2004/02/25 22:10:22

　　オイラー予想の反例　４乗の場合 会社員 2004/02/20 23:21:51  ツリーへ

オイラー予想の反例　４乗の場合 返事を書く

会社員 2004/02/20 23:21:51

オイラー予想の反例を探そうとしています。
でも、１つ１つ探す方法は遅くて探しきれそうにありません。

効率の良い探し方を教えてください。
よろしくお願いします。

【１９８８年に見つかった反例】
＝95800＾4 + 217519＾4 + 414560＾4 = 422481＾4を探す

＝＝＝＝(１０００桁モードのみ)＝＝＝＝＝＝＝＝＝＝＝＝
! オイラー予想４乗の場合
! 95800＾4 + 217519＾4 + 414560＾4 = 422481＾4を探す

INPUT PROMPT "どこまで探しますか？":MX

FOR A=1 to MX
FOR J=0 to MX
FOR K=0 to MX
LET B=A+J
LET C=B+K

LET D=ROUND (SQR(SQR(A*A*A*A+B*B*B*B+C*C*C*C)),100)
IF ROUND(D,0)=D THEN
PRINT "見つかりました！"
PRINT "a=",A
PRINT "b=",B
PRINT "c=",C
PRINT "d=",D
END IF
IF C>MX THEN EXIT FOR
NEXT K
IF B>MX THEN EXIT FOR
NEXT J
NEXT A
END

PRINT "終了！"

END

　　├発見するのに必要な現実的速度にはぜんぜん... 青木太一 2004/02/21 02:13:31  ツリーへ

Re: オイラー予想の反例　４乗の場合 返事を書く

青木太一 2004/02/21 02:13:31

発見するのに必要な現実的速度にはぜんぜん達していませんが、
とりあえず書いてみました。
高速化は、時間のかかるsqrを二回に分けて判定することで実現しました。
私の環境ではMXが20のとき2倍ほど速くなりました。
二回に分けないでsqr(sqr(D))のとき：約18秒
二回に分けたとき：約8秒

二倍にはなったけど、見つかっている反例を再発見するにも膨大な時間がかかりそうですね。すでに会社員さんが思いついている高速化手法だったら失礼。
なにかもっといい方法ないかな...

(for文の初期値を工夫することで、プログラムを読みやすくしています。)
OPTION ARITHMETIC DECIMAL_HIGH
!INPUT PROMPT "どこまで探しますか？":MX
LET MX=20!422481
LET t=time
FOR A=1 to MX
FOR B=A to MX
FOR C=B to MX

LET D=SQR(A^4+B^4+C^4)
IF D=int(D) THEN
LET D=sqr(D)
IF D=int(D) THEN
PRINT "見つかりました！"
PRINT "a=",A
PRINT "b=",B
PRINT "c=",C
PRINT "d=",D
END IF
END IF

NEXT C
NEXT B
NEXT A
PRINT "終了！"
print time-t
END

　　│└５乗の反例は何とかでてきました。 会社員 2004/02/21 23:04:08  ツリーへ

Re: 発見するのに必要な現実的速度にはぜんぜん... 返事を書く

会社員 2004/02/21 23:04:08

５乗の反例は何とかでてきました。

青木太一さん　おかげ様でとても読みやすくなりました。
ありがとうございました。

４乗をあきらめて５乗の判例でやってみました。
＝＝（結果）＝＝
見つかりました！
a= 27
b= 84
c= 110
d= 133
e= 144

＝＝＝＝＝＝＝＝＝＝＝＝＝
OPTION ARITHMETIC DECIMAL
INPUT PROMPT "どこまで探しますか？":MX
LET t=time
FOR A=1 to MX
FOR B=A to MX
FOR C=B to MX
FOR D=C to MX

LET E=(A^5+B^5+C^5+D^5)^(0.2)
IF E=INT(E) THEN
PRINT "見つかりました！"
PRINT "a=",A
PRINT "b=",B
PRINT "c=",C
PRINT "d=",D
PRINT "e=",E
INPUT PROMPT "続けますか？":Y$
END IF
IF B/MX=INT(B/MX) AND C/MX=INT(C/MX) AND D/MX=INT(D/MX) THEN PRINT A;B;C;D;"見つかりません"
NEXT D
NEXT C
NEXT B
NEXT A
PRINT "終了！"
print time-t
END

　　│　└そうですか。あきらめましたか。 青木太一 2004/02/22 19:25:44  ツリーへ

Re: ５乗の反例は何とかでてきました。 返事を書く

青木太一 2004/02/22 19:25:44

そうですか。あきらめましたか。
あのあと、A,B,Cを走査するのでなく逆にDを走査する方法などで効率よくならないかとすこしプログラムしてみたのですが、
結局効率が変わらないことに気づいて私もあきらめていました。
4乗の反例を発見した人はひたすら計算機をブン回したのでしょうかね？
効率いい方法があったら知りたい...

ところで5乗のプログラムの
「IF B/MX=INT(B/MX) AND C/MX=INT(C/MX) AND D/MX=INT(D/MX) THEN PRINT A;B;C;D;"見つかりません"」
は
「IF B=MX AND C=MX AND D=MX THEN PRINT A;B;C;D;"見つかりません"」
でいいのではないですか？

　　│　　└５乗のプログラムのとき気づいたのですが・... 会社員 2004/02/22 22:24:29  ツリーへ

Re: そうですか。あきらめましたか。 返事を書く

会社員 2004/02/22 22:24:29

５乗のプログラムのとき気づいたのですが・・

５乗の時、SQR関数による判定が通常できないので因数による判定を
考えていて気づいたのですが、
Ｄは、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので
調べる領域が限定されている場合
Ｄの候補は結構絞られるような気がしています。

エラトステネスのふるいに似たような方法で、Ｄを絞ってから
判定すると効率が上がらないでしょうか？

「逆にDを走査する方法」とはそういうことでしょうか？

>「IF B=MX AND C=MX AND D=MX THEN PRINT A;B;C;D;"見つかりません"」
>でいいのではないですか？
そうですね。

　　│　　　├Ａ≦Ｂ≦Ｃ＜Ｄ 会社員 2004/02/22 22:45:25  ツリーへ

Re: ５乗のプログラムのとき気づいたのですが・... 返事を書く

会社員 2004/02/22 22:45:25

Ａ≦Ｂ≦Ｃ＜Ｄ

今気づいたので　忘れないよう書き込みます。

Ｄの候補がＤ1＜Ｄ2＜Ｄ3＜・・＜Ｄn　すると
最初の小さいＤ1は

Ａ≦Ｂ≦Ｃ＜Ｄから、判定が結構速く出きそうです。

とにかくぼちぼち考えることにします。
お休みなさい。

　　│　　　├すいません。高校より上の数学はあまり得意... 青木太一 2004/02/23 00:35:52  ツリーへ

Re: ５乗のプログラムのとき気づいたのですが・... 返事を書く

青木太一 2004/02/23 00:35:52

すいません。高校より上の数学はあまり得意でないのもので...
＞「Ｄは、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので」
というのがなぜだかわかりません。

「Ｄ^4は、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので」
というのならまだわかりますが、これは「自然数は素因数分解できる」ということを表しているだけで、「ふるい」にはなりませんよね。

＞「逆にDを走査する方法」とはそういうことでしょうか？
えー、もっとヘボイ発想で、どういうわけか

for D=1 to MX
!ここにD^4=A^4+B^4+C^4を満たすA,B,Cがあるかを探索する処理を置く
next D

と書くと効率がいいかもしれないとそのときは思ったのです。
でもこれって(おそらく)効率かわりませんよね...
それに気づいてあきらめた次第です。

変数名が変ですが、こんなプログラムを書いてから気づきました。
(「変」というのは実際にはa,b,c,dは4乗された後の値ということになるから)

!a+b+c=dを満たすようなa,b,cの三つの数の組をすべて書き下すプログラム
LET d=8
LET cnt=0
for a=1 to d/3
for b=a to (d-a)/2
LET c=d-a-b
print a+b+c;a;b;c
LET cnt=cnt+1
next b
next a
print cnt
END

dを「ふるい」にかけることができるなら、会社員さんの言うとおり、
効率よくなるはずですが、どうでしょうね？

発見者のエルキースが書いた
On A4 + B4 + C4 = D4, Math. of Comp. 51 (Oct. 1988), 825-835.
http://www.math.harvard.edu/~elkies/math_pubs.html
にもしかしたら高速化の工夫とか書いてあるかもしれませんね。
英語的にも数学的にも自信ないので、忙しいこともありちょっと調べられそうもないですけど。

　　│　　　│├まだ、プログラムにしてませんが・・・ 会社員 2004/02/23 22:53:19  ツリーへ

Re: すいません。高校より上の数学はあまり得意... 返事を書く

会社員 2004/02/23 22:53:19

まだ、プログラムにしてませんが・・・

>「Ｄ^4は、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので」
>というのならまだわかりますが、
そうですね。　間違いました。

>for D=1 to MX
>!ここにD^4=A^4+B^4+C^4を満たすA,B,Cがあるかを探索する処理を置く
>next D
たぶん同じ発想です。

D^4は、Ｄが１、２、３、４、５、・・
１、１６、８１、２５６、６２５、・・
と、だんだん飛びとびが激しくなるのでかなり限定されると
考えていたのですが・・
Ｄ自体はとびとびではないんですね。

>(おそらく)効率かわりませんよね...
そんな気もしてきました。

明日も仕事なので今日は失礼します。

>発見者のエルキースが書いた
>On A4 + B4 + C4 = D4, Math. of Comp. 51 (Oct. 1988), 825-835.
忙しいので読めませんが、情報ありがとうございます。

　　│　　　││└まだ会社員さん見てるかな？ 青木太一 2004/02/25 19:54:52  ツリーへ

Re: まだ、プログラムにしてませんが・・・ 返事を書く

青木太一 2004/02/25 19:54:52

まだ会社員さん見てるかな？

>発見者のエルキースが書いた
>On A4 + B4 + C4 = D4, Math. of Comp. 51 (Oct. 1988), 825-835.
を大学の電子ジャーナルで読むことができました。
11ページで、数学的にほとんど私には手に負えなさそうでした
(楕円曲線とやらを使うらしいです...)が、要旨の部分と、
最後に求めるときのコツみたいのが載っていたので
(5で割り切れるとか割り切れないとか「ふるい」に使えそうな条件がいくつか載っているように読める)。
そこだけ翻訳してみます。
今は忙しいのでまた今度。

　　│　　　││　├偶奇判定を使えば多少速くなりました。 会社員 2004/02/28 23:55:51  ツリーへ

Re: まだ会社員さん見てるかな？ 返事を書く

会社員 2004/02/28 23:55:51

偶奇判定を使えば多少速くなりました。

でも　やはり実用速度ではありません。
>最後に求めるときのコツみたいのが載っていたので
何かありそうですね。　ん～。　今日はお休みです。

「ふるい」の１つにＤの偶奇と、Ａ^4＋Ｂ^4＋Ｃ^4の偶奇が一致することを利用して、SQR関数をできるだけ使わないことで（＝半分までは判定できる）多少高速になりました。

３で割って余り有無を判定に組み込もうとしましたが、これも条件が増えてかえって遅くなりました。

==偶奇で半分を判定=================================
OPTION ARITHMETIC DECIMAL
PRINT " 95800^4 + 217519^4 + 414560^4=";SQR(SQR( 95800^4 + 217519^4 + 414560^4));"^4"
PRINT " 2682440^4 + 15365639^4 + 18796760^4=";SQR(SQR( 2682440^4 + 15365639^4 + 18796760^4));"^4を探す"
! Ａ≦Ｂ≦Ｃ＜ＤＡ^4≦Ｂ^4≦Ｃ^4＜Ｄ
! Ａは１からＡ^4≦Ｄ＾４／３の条件しか考えなくてよい。
! ＢはＡより大きく(同じも含む) Ｂ^4＜Ｄ＾４／２の範囲だけ考えればよい
! ＣはＢより大きく √（Ｄ＾４－Ａ^4－Ｂ^4）から上を考えればよい。

PRINT DATE$;" ";TIME$
FOR D= 3 to 100000000

FOR A=1 to SQR(SQR(D^4/3))
IF A/100=INT(A/100) then print "D=";D;"A=";A;"を検索中 ";DATE$;" ";TIME$
FOR B=A to SQR(SQR(D^4/2))

!偶数奇数の一致判定　
if MOD(D,2)=MOD(D-A-B,2) then

IF INT(SQR(D^4-A^4-B^4))=SQR(D^4-A^4-B^4) THEN
LET C= SQR(SQR(D^4-A^4-B^4))
IF INT(C)=C and D^4=A^4+B^4+C^4 THEN
PRINT "見つかりました！"
PRINT "a=",A
PRINT "b=",B
PRINT "c=",C
PRINT "d=",D
INPUT PROMPT "続けますか？":y$
END IF
END IF
END IF

NEXT B
NEXT A
NEXT D

PRINT "終了！"
END

　　│　　　││　│├誤記修正。（プログラム間違いました） 会社員 2004/02/29 00:02:04  ツリーへ

Re: 偶奇判定を使えば多少速くなりました。 返事を書く

会社員 2004/02/29 00:02:04

誤記修正。（プログラム間違いました）

PRINT DATE$;" ";TIME$
FOR D= 3 to 100000000

FOR A=1 to SQR(SQR(D^4/3))
IF A/100=INT(A/100) then print "D=";D;"A=";A;"を検索中 ";DATE$;" ";TIME$
FOR B=A to SQR(SQR(D^4/2))
!偶数奇数判定　

if MOD(D,2)=MOD(A+B+C,2) then
IF INT(SQR(D^4-A^4-B^4))=SQR(D^4-A^4-B^4) THEN
LET C= SQR(SQR(D^4-A^4-B^4))
IF INT(C)=C and D^4=A^4+B^4+C^4 THEN
PRINT "見つかりました！"
PRINT "a=",A
PRINT "b=",B
PRINT "c=",C
PRINT "d=",D
! INPUT PROMPT "続けますか？":y$
END IF
END IF
END IF

NEXT B
NEXT A
NEXT D

PRINT "終了！"
END

　　│　　　││　││└これ間違ってます。 会社員 2004/03/07 21:16:49  ツリーへ

Re: 誤記修正。（プログラム間違いました） 返事を書く

会社員 2004/03/07 21:16:49

これ間違ってます。　

没でお願いします。

　　│　　　││　│└もっといい参考文献をみつけました。 青木太一 2004/03/06 17:44:13  ツリーへ

Re: 偶奇判定を使えば多少速くなりました。 返事を書く

青木太一 2004/03/06 17:44:13

もっといい参考文献をみつけました。

On A4 + B4 + C4 = D4
Mathematics of Computation, Vol. 51, No. 184. (Oct., 1988), pp. 825-835.
を理解しようとしたけど暇も能力も無く無理でした。
そもそもここでは楕円曲線うんぬんでオイラー予想の反例を求めていて、
コンピュータで網羅的に求める方法は最後に補遺としてちょっと載っているだけでした。で、そのコツは

・Dは奇数であり、5では割り切れない

・D^4-C^4は625で割り切れる。
　他にもいくつかの合同式を満たし
　割り切れる割り切れないの特性を持つ。

・そのようなDとCのなかで、D^4-C^4であるA^4+B^4の
　A,Bは5で割り切れる。

だそうです。なんでそうなのかわかりません。
そもそも、私が読み間違ったかもしれないので、あんまり信用しないでください。

で、有効なお返事がかけないなと悩んでいたら、
そのものずばり、このコツをエルキースから聞いた
Roger Fryeの書いた
「Finding 95800 4 + 217519 4 + 414560 4 = 422481 4 on the
Connection Machine」
というのが
http://internet.cybermesa.com/~rfrye/collab.htm
にありました。PostScriptファイルで公開されています。
これを読んでみます。

白石先生、十進BASICに関係ないはなしでごめんなさい。

　　│　　　││　│　└資料ありがとうございます。 会社員 2004/03/07 21:55:46  ツリーへ

Re: もっといい参考文献をみつけました。 返事を書く

会社員 2004/03/07 21:55:46

資料ありがとうございます。

でも、英語は苦手なので止まってます。

>・Dは奇数であり、5では割り切れない

とりあえず、Ｄが５で割り切れる場合は考えなくていいんですね。
そのときは、ＡもＢもＣも５で割り切れないとダメな訳ですから。
等式として成り立っても、両辺を　5^4で割ればそれより小さい解がそれ以前に存在する訳ですね。

Ｄが奇数でないといけない理由がわかりません。

Dが奇数だけでいいなら、計算量が半分なので大きいのです。

でも、何故でしょうか？

もし、わかったら教えてください。

　　│　　　││　└５の剰余で、おもしろいことがわかりました... 会社員 2004/02/29 18:43:13  ツリーへ

Re: まだ会社員さん見てるかな？ 返事を書く

会社員 2004/02/29 18:43:13

５の剰余で、おもしろいことがわかりました。

（５で割り切れる数）^４乗＝>５で割り切れる数
　これはあたりまえですが、

（５で１余る数）^４乗＝>５で１余る数
（５で２余る数）^４乗＝>５で１余る数
（５で３余る数）^４乗＝>５で１余る数
（５で４余る数）^４乗＝>５で１余る数

とすべて『５で１余る数』になるんですね。

この性質をうまく『ふるい』に使えそうです。
>5で割り切れるとか割り切れないとか「ふるい」に使えそうな条件がいくつか載っているように読める)
このことが書かれているのかもしれません。

ちなみに　７で同様になるか考えましたが、
（７で１余る数）^４乗＝>７で１余る数
（７で２余る数）^４乗＝>７で２余る数
（７で３余る数）^４乗＝>７で４余る数
（７で４余る数）^４乗＝>７で４余る数
（７で５余る数）^４乗＝>７で２余る数
（７で６余る数）^４乗＝>７で１余る数
となり　５のようにはなりません。

おもしろいです。

　　│　　　│└紹介いただいた「a+b+c=dを満たすようなa,b... 会社員 2004/02/25 21:56:37  ツリーへ

Re: すいません。高校より上の数学はあまり得意... 返事を書く

会社員 2004/02/25 21:56:37

紹介いただいた「a+b+c=dを満たすようなa,b,cの三つの数の組を
すべて書き下すプログラム」を参考に４乗版に書いて見ました。

でも、おっしゃるとおり急激に速くはならないんですね。
困りました。

=====================================================
!OPTION ARITHMETIC DECIMAL_HIGH
! 【１９８８年に見つかった反例】
! 95800＾4 + 217519＾4 + 414560＾4 = 422481＾4
PRINT " 95800^4 + 217519^4 + 414560^4=";SQR(SQR( 95800^4 + 217519^4 + 414560^4));"^4"

!　2682440^4 + 15365639^4 + 18796760^4=20615673＾4 　　を探す
PRINT " 2682440^4 + 15365639^4 + 18796760^4=";SQR(SQR( 2682440^4 + 15365639^4 + 18796760^4));"^4"
PRINT "を探す"

! Ａ≦Ｂ≦Ｃ＜ＤＡ^4≦Ｂ^4≦Ｃ^4＜Ｄ
! Ａは１からＡ^4≦Ｄ＾４／３の条件しか考えなくてよい。
! ＢはＡより大きく(同じも含む) Ｂ^4＜Ｄ＾４／２の範囲だけ考えればよい
! ＣはＢより大きく √（Ｄ＾４－Ａ^4－Ｂ^4）から上を考えればよい。
! 又、
! Ａ^4＋Ｂ^4＋Ｃ^4＞Ｄ＾４になったら、そこから上のＣは探さなくて良い。
! 次のＢを探す

PRINT DATE$;" ";TIME$
FOR D=3 to 100000000

FOR A=1 to SQR(SQR(D^4/3))
print "D=";D;"A=";A;"を検索中　";DATE$;"　";TIME$
FOR B=A to SQR(SQR(D^4/2))

LET C= SQR(SQR(D^4-A^4-B^4))
IF INT(C)=C THEN
PRINT "見つかりました！"
PRINT "a=",A
PRINT "b=",B
PRINT "c=",C
PRINT "d=",D
INPUT PROMPT "続けますか？":y$
END IF

NEXT B
NEXT A

NEXT D

PRINT "終了！"
END

　　│　　　│　└このプログラムだとエラーになります。 会社員 2004/02/26 21:56:45  ツリーへ

Re: 紹介いただいた「a+b+c=dを満たすようなa,b... 返事を書く

会社員 2004/02/26 21:56:45

このプログラムだとエラーになります。

Ｄ＝４６１３でＡ＝１、Ｂ＝１、Ｃ＝４６１３で
「見つかりました！」
と計算間違いになりました。

千桁モードで動かさないとダメなようです。

　　│　　　├オリラ―の定理、公式は私も興味あります。... 小塚貞典 2004/02/23 16:54:42  ツリーへ

Re: ５乗のプログラムのとき気づいたのですが・... 返事を書く

小塚貞典 2004/02/23 16:54:42

オリラ―の定理、公式は私も興味あります。そんな問題があったのですか。最近、講談社からまだ解けていない数学の本が図書館にありましたが読みませんでした。単項イデアル環における加群とか代数の大学院の問題集あたりにガロア理論があったりして、むつかしけど面白いですね。素因数を拡張した概念をイデアルと呼ぶらしいですよ。
例えば、1.5×２＝３　あたりまえですが、けれど、３の1.5が因子になるという考え方のようです。釈迦に説法だったかな。

　　│　　　└４次方程式までは複素数で４個の解を持つが... 小塚貞典 2004/02/23 17:29:49  ツリーへ

Re: ５乗のプログラムのとき気づいたのですが・... 返事を書く

小塚貞典 2004/02/23 17:29:49

４次方程式までは複素数で４個の解を持つが５字以上は解の数と式の次数と対応しないはずです。そうした判例がちょうど、自然数になる数という問題なのでしょうか。roundを使いのは探すのに近い数という意味？二分検索法を用いれば早くなったのだと思いますが、ばぜ、roundがいるのか今いちよく解らない。素数の性格、性向なのでしょうか。
mod =0ではなぜいけないのでしょう。どちらにしても、制限しないと簡単に求まらないかずなのですね。暗号化に使えるかもしれませんね。

　　└フェルマ―の問題が解けた話ですか？ 小塚貞典 2004/02/23 17:44:10  ツリーへ

Re: オイラー予想の反例　４乗の場合 返事を書く

小塚貞典 2004/02/23 17:44:10

フェルマ―の問題が解けた話ですか？
本で読みました、新たな問題が又できたと書いてありました。

　　　└フェルマーの定理の拡張です 会社員 2004/02/25 22:10:22  ツリーへ

Re: フェルマ―の問題が解けた話ですか？ 返事を書く

会社員 2004/02/25 22:10:22

フェルマーの定理の拡張です

小塚貞典さん　こんばんは。
http://amacre.site.ne.jp/Tuyano/Fun/FUN_4.html
http://www.mcc.pref.miyagi.jp/people/ikuro/koramu/fermat.htm
のページの下の方に載ってます。　・・式の答え誤植のようです。
２０６１５６７３＾4が正しい。

１８世紀後半、フェルマーの定理
(X^n＋Y^n＝Ｚ^n;XYZの整数解がない。n≧３)が正しいなら
これも正しいのでは？　　

と　オイラーが考えた予想です。

インデックスへ EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。

オイラー予想の反例　４乗の場合	返事を書く
会社員 2004/02/20 23:21:51
オイラー予想の反例を探そうとしています。でも、１つ１つ探す方法は遅くて探しきれそうにありません。効率の良い探し方を教えてください。よろしくお願いします。【１９８８年に見つかった反例】＝95800＾4 + 217519＾4 + 414560＾4 = 422481＾4を探す＝＝＝＝(１０００桁モードのみ)＝＝＝＝＝＝＝＝＝＝＝＝ ! オイラー予想４乗の場合 ! 95800＾4 + 217519＾4 + 414560＾4 = 422481＾4を探す INPUT PROMPT "どこまで探しますか？":MX FOR A=1 to MX FOR J=0 to MX FOR K=0 to MX LET B=A+J LET C=B+K LET D=ROUND (SQR(SQR(AAAA+BBBB+CCC*C)),100) IF ROUND(D,0)=D THEN PRINT "見つかりました！" PRINT "a=",A PRINT "b=",B PRINT "c=",C PRINT "d=",D END IF IF C>MX THEN EXIT FOR NEXT K IF B>MX THEN EXIT FOR NEXT J NEXT A END PRINT "終了！" END

Re: オイラー予想の反例　４乗の場合	返事を書く
青木太一 2004/02/21 02:13:31
発見するのに必要な現実的速度にはぜんぜん達していませんが、とりあえず書いてみました。高速化は、時間のかかるsqrを二回に分けて判定することで実現しました。私の環境ではMXが20のとき2倍ほど速くなりました。二回に分けないでsqr(sqr(D))のとき：約18秒二回に分けたとき：約8秒二倍にはなったけど、見つかっている反例を再発見するにも膨大な時間がかかりそうですね。すでに会社員さんが思いついている高速化手法だったら失礼。なにかもっといい方法ないかな... (for文の初期値を工夫することで、プログラムを読みやすくしています。) OPTION ARITHMETIC DECIMAL_HIGH !INPUT PROMPT "どこまで探しますか？":MX LET MX=20!422481 LET t=time FOR A=1 to MX FOR B=A to MX FOR C=B to MX LET D=SQR(A^4+B^4+C^4) IF D=int(D) THEN LET D=sqr(D) IF D=int(D) THEN PRINT "見つかりました！" PRINT "a=",A PRINT "b=",B PRINT "c=",C PRINT "d=",D END IF END IF NEXT C NEXT B NEXT A PRINT "終了！" print time-t END

Re: 発見するのに必要な現実的速度にはぜんぜん...	返事を書く
会社員 2004/02/21 23:04:08
５乗の反例は何とかでてきました。青木太一さん　おかげ様でとても読みやすくなりました。ありがとうございました。４乗をあきらめて５乗の判例でやってみました。＝＝（結果）＝＝見つかりました！ a= 27 b= 84 c= 110 d= 133 e= 144 ＝＝＝＝＝＝＝＝＝＝＝＝＝ OPTION ARITHMETIC DECIMAL INPUT PROMPT "どこまで探しますか？":MX LET t=time FOR A=1 to MX FOR B=A to MX FOR C=B to MX FOR D=C to MX LET E=(A^5+B^5+C^5+D^5)^(0.2) IF E=INT(E) THEN PRINT "見つかりました！" PRINT "a=",A PRINT "b=",B PRINT "c=",C PRINT "d=",D PRINT "e=",E INPUT PROMPT "続けますか？":Y$ END IF IF B/MX=INT(B/MX) AND C/MX=INT(C/MX) AND D/MX=INT(D/MX) THEN PRINT A;B;C;D;"見つかりません" NEXT D NEXT C NEXT B NEXT A PRINT "終了！" print time-t END

Re: ５乗の反例は何とかでてきました。	返事を書く
青木太一 2004/02/22 19:25:44
そうですか。あきらめましたか。あのあと、A,B,Cを走査するのでなく逆にDを走査する方法などで効率よくならないかとすこしプログラムしてみたのですが、結局効率が変わらないことに気づいて私もあきらめていました。 4乗の反例を発見した人はひたすら計算機をブン回したのでしょうかね？効率いい方法があったら知りたい... ところで5乗のプログラムの「IF B/MX=INT(B/MX) AND C/MX=INT(C/MX) AND D/MX=INT(D/MX) THEN PRINT A;B;C;D;"見つかりません"」は「IF B=MX AND C=MX AND D=MX THEN PRINT A;B;C;D;"見つかりません"」でいいのではないですか？

Re: そうですか。あきらめましたか。	返事を書く
会社員 2004/02/22 22:24:29
５乗のプログラムのとき気づいたのですが・・５乗の時、SQR関数による判定が通常できないので因数による判定を考えていて気づいたのですが、Ｄは、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので調べる領域が限定されている場合Ｄの候補は結構絞られるような気がしています。エラトステネスのふるいに似たような方法で、Ｄを絞ってから判定すると効率が上がらないでしょうか？「逆にDを走査する方法」とはそういうことでしょうか？ >「IF B=MX AND C=MX AND D=MX THEN PRINT A;B;C;D;"見つかりません"」 >でいいのではないですか？そうですね。

Re: ５乗のプログラムのとき気づいたのですが・...	返事を書く
会社員 2004/02/22 22:45:25
Ａ≦Ｂ≦Ｃ＜Ｄ今気づいたので　忘れないよう書き込みます。Ｄの候補がＤ1＜Ｄ2＜Ｄ3＜・・＜Ｄn　すると最初の小さいＤ1はＡ≦Ｂ≦Ｃ＜Ｄから、判定が結構速く出きそうです。とにかくぼちぼち考えることにします。お休みなさい。

Re: ５乗のプログラムのとき気づいたのですが・...	返事を書く
青木太一 2004/02/23 00:35:52
すいません。高校より上の数学はあまり得意でないのもので... ＞「Ｄは、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので」というのがなぜだかわかりません。「Ｄ^4は、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので」というのならまだわかりますが、これは「自然数は素因数分解できる」ということを表しているだけで、「ふるい」にはなりませんよね。＞「逆にDを走査する方法」とはそういうことでしょうか？えー、もっとヘボイ発想で、どういうわけか for D=1 to MX !ここにD^4=A^4+B^4+C^4を満たすA,B,Cがあるかを探索する処理を置く next D と書くと効率がいいかもしれないとそのときは思ったのです。でもこれって(おそらく)効率かわりませんよね... それに気づいてあきらめた次第です。変数名が変ですが、こんなプログラムを書いてから気づきました。 (「変」というのは実際にはa,b,c,dは4乗された後の値ということになるから) !a+b+c=dを満たすようなa,b,cの三つの数の組をすべて書き下すプログラム LET d=8 LET cnt=0 for a=1 to d/3 for b=a to (d-a)/2 LET c=d-a-b print a+b+c;a;b;c LET cnt=cnt+1 next b next a print cnt END dを「ふるい」にかけることができるなら、会社員さんの言うとおり、効率よくなるはずですが、どうでしょうね？発見者のエルキースが書いた On A4 + B4 + C4 = D4, Math. of Comp. 51 (Oct. 1988), 825-835. http://www.math.harvard.edu/~elkies/math_pubs.html にもしかしたら高速化の工夫とか書いてあるかもしれませんね。英語的にも数学的にも自信ないので、忙しいこともありちょっと調べられそうもないですけど。

Re: すいません。高校より上の数学はあまり得意...	返事を書く
会社員 2004/02/23 22:53:19
まだ、プログラムにしてませんが・・・ >「Ｄ^4は、必ず２＾４、３＾４、５＾４、７＾４・・を因数にもつので」 >というのならまだわかりますが、そうですね。　間違いました。 >for D=1 to MX >!ここにD^4=A^4+B^4+C^4を満たすA,B,Cがあるかを探索する処理を置く >next D たぶん同じ発想です。 D^4は、Ｄが１、２、３、４、５、・・１、１６、８１、２５６、６２５、・・と、だんだん飛びとびが激しくなるのでかなり限定されると考えていたのですが・・Ｄ自体はとびとびではないんですね。 >(おそらく)効率かわりませんよね... そんな気もしてきました。明日も仕事なので今日は失礼します。 >発見者のエルキースが書いた >On A4 + B4 + C4 = D4, Math. of Comp. 51 (Oct. 1988), 825-835. 忙しいので読めませんが、情報ありがとうございます。

Re: まだ、プログラムにしてませんが・・・	返事を書く
青木太一 2004/02/25 19:54:52
まだ会社員さん見てるかな？ >発見者のエルキースが書いた >On A4 + B4 + C4 = D4, Math. of Comp. 51 (Oct. 1988), 825-835. を大学の電子ジャーナルで読むことができました。 11ページで、数学的にほとんど私には手に負えなさそうでした (楕円曲線とやらを使うらしいです...)が、要旨の部分と、最後に求めるときのコツみたいのが載っていたので (5で割り切れるとか割り切れないとか「ふるい」に使えそうな条件がいくつか載っているように読める)。そこだけ翻訳してみます。今は忙しいのでまた今度。

Re: まだ会社員さん見てるかな？	返事を書く
会社員 2004/02/28 23:55:51
偶奇判定を使えば多少速くなりました。でも　やはり実用速度ではありません。 >最後に求めるときのコツみたいのが載っていたので何かありそうですね。　ん～。　今日はお休みです。「ふるい」の１つにＤの偶奇と、Ａ^4＋Ｂ^4＋Ｃ^4の偶奇が一致することを利用して、SQR関数をできるだけ使わないことで（＝半分までは判定できる）多少高速になりました。３で割って余り有無を判定に組み込もうとしましたが、これも条件が増えてかえって遅くなりました。 ==偶奇で半分を判定================================= OPTION ARITHMETIC DECIMAL PRINT " 95800^4 + 217519^4 + 414560^4=";SQR(SQR( 95800^4 + 217519^4 + 414560^4));"^4" PRINT " 2682440^4 + 15365639^4 + 18796760^4=";SQR(SQR( 2682440^4 + 15365639^4 + 18796760^4));"^4を探す" ! Ａ≦Ｂ≦Ｃ＜ＤＡ^4≦Ｂ^4≦Ｃ^4＜Ｄ ! Ａは１からＡ^4≦Ｄ＾４／３の条件しか考えなくてよい。 ! ＢはＡより大きく(同じも含む) Ｂ^4＜Ｄ＾４／２の範囲だけ考えればよい ! ＣはＢより大きく √（Ｄ＾４－Ａ^4－Ｂ^4）から上を考えればよい。 PRINT DATE$;" ";TIME$ FOR D= 3 to 100000000 FOR A=1 to SQR(SQR(D^4/3)) IF A/100=INT(A/100) then print "D=";D;"A=";A;"を検索中 ";DATE$;" ";TIME$ FOR B=A to SQR(SQR(D^4/2)) !偶数奇数の一致判定　 if MOD(D,2)=MOD(D-A-B,2) then IF INT(SQR(D^4-A^4-B^4))=SQR(D^4-A^4-B^4) THEN LET C= SQR(SQR(D^4-A^4-B^4)) IF INT(C)=C and D^4=A^4+B^4+C^4 THEN PRINT "見つかりました！" PRINT "a=",A PRINT "b=",B PRINT "c=",C PRINT "d=",D INPUT PROMPT "続けますか？":y$ END IF END IF END IF NEXT B NEXT A NEXT D PRINT "終了！" END

Re: 偶奇判定を使えば多少速くなりました。	返事を書く
会社員 2004/02/29 00:02:04
誤記修正。（プログラム間違いました） PRINT DATE$;" ";TIME$ FOR D= 3 to 100000000 FOR A=1 to SQR(SQR(D^4/3)) IF A/100=INT(A/100) then print "D=";D;"A=";A;"を検索中 ";DATE$;" ";TIME$ FOR B=A to SQR(SQR(D^4/2)) !偶数奇数判定　 if MOD(D,2)=MOD(A+B+C,2) then IF INT(SQR(D^4-A^4-B^4))=SQR(D^4-A^4-B^4) THEN LET C= SQR(SQR(D^4-A^4-B^4)) IF INT(C)=C and D^4=A^4+B^4+C^4 THEN PRINT "見つかりました！" PRINT "a=",A PRINT "b=",B PRINT "c=",C PRINT "d=",D ! INPUT PROMPT "続けますか？":y$ END IF END IF END IF NEXT B NEXT A NEXT D PRINT "終了！" END

Re: 誤記修正。（プログラム間違いました）	返事を書く
会社員 2004/03/07 21:16:49
これ間違ってます。　没でお願いします。

Re: 偶奇判定を使えば多少速くなりました。	返事を書く
青木太一 2004/03/06 17:44:13
もっといい参考文献をみつけました。 On A4 + B4 + C4 = D4 Mathematics of Computation, Vol. 51, No. 184. (Oct., 1988), pp. 825-835. を理解しようとしたけど暇も能力も無く無理でした。そもそもここでは楕円曲線うんぬんでオイラー予想の反例を求めていて、コンピュータで網羅的に求める方法は最後に補遺としてちょっと載っているだけでした。で、そのコツは・Dは奇数であり、5では割り切れない・D^4-C^4は625で割り切れる。　他にもいくつかの合同式を満たし　割り切れる割り切れないの特性を持つ。・そのようなDとCのなかで、D^4-C^4であるA^4+B^4の　A,Bは5で割り切れる。だそうです。なんでそうなのかわかりません。そもそも、私が読み間違ったかもしれないので、あんまり信用しないでください。で、有効なお返事がかけないなと悩んでいたら、そのものずばり、このコツをエルキースから聞いた Roger Fryeの書いた「Finding 95800 4 + 217519 4 + 414560 4 = 422481 4 on the Connection Machine」というのが http://internet.cybermesa.com/~rfrye/collab.htm にありました。PostScriptファイルで公開されています。これを読んでみます。白石先生、十進BASICに関係ないはなしでごめんなさい。

Re: もっといい参考文献をみつけました。	返事を書く
会社員 2004/03/07 21:55:46
資料ありがとうございます。でも、英語は苦手なので止まってます。 >・Dは奇数であり、5では割り切れないとりあえず、Ｄが５で割り切れる場合は考えなくていいんですね。そのときは、ＡもＢもＣも５で割り切れないとダメな訳ですから。等式として成り立っても、両辺を　5^4で割ればそれより小さい解がそれ以前に存在する訳ですね。Ｄが奇数でないといけない理由がわかりません。 Dが奇数だけでいいなら、計算量が半分なので大きいのです。でも、何故でしょうか？もし、わかったら教えてください。

Re: まだ会社員さん見てるかな？	返事を書く
会社員 2004/02/29 18:43:13
５の剰余で、おもしろいことがわかりました。（５で割り切れる数）^４乗＝>５で割り切れる数　これはあたりまえですが、（５で１余る数）^４乗＝>５で１余る数（５で２余る数）^４乗＝>５で１余る数（５で３余る数）^４乗＝>５で１余る数（５で４余る数）^４乗＝>５で１余る数とすべて『５で１余る数』になるんですね。この性質をうまく『ふるい』に使えそうです。 >5で割り切れるとか割り切れないとか「ふるい」に使えそうな条件がいくつか載っているように読める) このことが書かれているのかもしれません。ちなみに　７で同様になるか考えましたが、（７で１余る数）^４乗＝>７で１余る数（７で２余る数）^４乗＝>７で２余る数（７で３余る数）^４乗＝>７で４余る数（７で４余る数）^４乗＝>７で４余る数（７で５余る数）^４乗＝>７で２余る数（７で６余る数）^４乗＝>７で１余る数となり　５のようにはなりません。おもしろいです。

Re: すいません。高校より上の数学はあまり得意...	返事を書く
会社員 2004/02/25 21:56:37
紹介いただいた「a+b+c=dを満たすようなa,b,cの三つの数の組をすべて書き下すプログラム」を参考に４乗版に書いて見ました。でも、おっしゃるとおり急激に速くはならないんですね。困りました。 ===================================================== !OPTION ARITHMETIC DECIMAL_HIGH ! 【１９８８年に見つかった反例】 ! 95800＾4 + 217519＾4 + 414560＾4 = 422481＾4 PRINT " 95800^4 + 217519^4 + 414560^4=";SQR(SQR( 95800^4 + 217519^4 + 414560^4));"^4" !　2682440^4 + 15365639^4 + 18796760^4=20615673＾4 　　を探す PRINT " 2682440^4 + 15365639^4 + 18796760^4=";SQR(SQR( 2682440^4 + 15365639^4 + 18796760^4));"^4" PRINT "を探す" ! Ａ≦Ｂ≦Ｃ＜ＤＡ^4≦Ｂ^4≦Ｃ^4＜Ｄ ! Ａは１からＡ^4≦Ｄ＾４／３の条件しか考えなくてよい。 ! ＢはＡより大きく(同じも含む) Ｂ^4＜Ｄ＾４／２の範囲だけ考えればよい ! ＣはＢより大きく √（Ｄ＾４－Ａ^4－Ｂ^4）から上を考えればよい。 ! 又、 ! Ａ^4＋Ｂ^4＋Ｃ^4＞Ｄ＾４になったら、そこから上のＣは探さなくて良い。 ! 次のＢを探す PRINT DATE$;" ";TIME$ FOR D=3 to 100000000 FOR A=1 to SQR(SQR(D^4/3)) print "D=";D;"A=";A;"を検索中　";DATE$;"　";TIME$ FOR B=A to SQR(SQR(D^4/2)) LET C= SQR(SQR(D^4-A^4-B^4)) IF INT(C)=C THEN PRINT "見つかりました！" PRINT "a=",A PRINT "b=",B PRINT "c=",C PRINT "d=",D INPUT PROMPT "続けますか？":y$ END IF NEXT B NEXT A NEXT D PRINT "終了！" END

Re: 紹介いただいた「a+b+c=dを満たすようなa,b...	返事を書く
会社員 2004/02/26 21:56:45
このプログラムだとエラーになります。Ｄ＝４６１３でＡ＝１、Ｂ＝１、Ｃ＝４６１３で「見つかりました！」と計算間違いになりました。千桁モードで動かさないとダメなようです。

Re: ５乗のプログラムのとき気づいたのですが・...	返事を書く
小塚貞典 2004/02/23 16:54:42
オリラ―の定理、公式は私も興味あります。そんな問題があったのですか。最近、講談社からまだ解けていない数学の本が図書館にありましたが読みませんでした。単項イデアル環における加群とか代数の大学院の問題集あたりにガロア理論があったりして、むつかしけど面白いですね。素因数を拡張した概念をイデアルと呼ぶらしいですよ。例えば、1.5×２＝３　あたりまえですが、けれど、３の1.5が因子になるという考え方のようです。釈迦に説法だったかな。

Re: ５乗のプログラムのとき気づいたのですが・...	返事を書く
小塚貞典 2004/02/23 17:29:49
４次方程式までは複素数で４個の解を持つが５字以上は解の数と式の次数と対応しないはずです。そうした判例がちょうど、自然数になる数という問題なのでしょうか。roundを使いのは探すのに近い数という意味？二分検索法を用いれば早くなったのだと思いますが、ばぜ、roundがいるのか今いちよく解らない。素数の性格、性向なのでしょうか。 mod =0ではなぜいけないのでしょう。どちらにしても、制限しないと簡単に求まらないかずなのですね。暗号化に使えるかもしれませんね。

Re: オイラー予想の反例　４乗の場合	返事を書く
小塚貞典 2004/02/23 17:44:10
フェルマ―の問題が解けた話ですか？本で読みました、新たな問題が又できたと書いてありました。

Re: フェルマ―の問題が解けた話ですか？	返事を書く
会社員 2004/02/25 22:10:22
フェルマーの定理の拡張です小塚貞典さん　こんばんは。 http://amacre.site.ne.jp/Tuyano/Fun/FUN_4.html http://www.mcc.pref.miyagi.jp/people/ikuro/koramu/fermat.htm のページの下の方に載ってます。　・・式の答え誤植のようです。２０６１５６７３＾4が正しい。１８世紀後半、フェルマーの定理 (X^n＋Y^n＝Ｚ^n;XYZの整数解がない。n≧３)が正しいならこれも正しいのでは？　　と　オイラーが考えた予想です。