アカウント名:
パスワード:
脂漏徒にでも分かる解説よろしく。
if文の連結のループだと100年かかるとか?一晩で出来そうに見えるが。
x,y,zに入りうる整数がN個あるとすると、ありうる答えの組み合わせはN^3個。愚直に値を入れてみて調べる場合, 1から100万まで探すだけでも100万の3乗個調べる必要がある。実際,上の記事に記載されている解で, xは1兆をはるかに超える数なので1兆^3よりもずっと膨大な解候補から見つけ出した事になる。
最後の数は計算すればいいから3乗じゃなくて2乗ですむだろ
そうですね。それでも膨大、ということでしょうね。
最後の数はケース分けしなくてもいいですが、三乗根を求めなきゃいけないので、それはそれで計算量はありそうです。
三乗根を求めなくても、整数の三乗の数を表にしておけばいいだけじゃないの?
80538738812075974が56bitpetaを越え、下手するとexa byteクラスのテーブル検索ですか。
いくら富豪プログラミングでも追いつかねぇ。
ああそうか勘違いしてた、ありがとう。2分法なら約56回で解が求まるってことですかね。
普通に三乗根求めてもそんなに重くないよ。低い精度で求めておいて最後だけニュートン法使えば求まるから。
x=80435758145817515y=80538738812075974z=12602123297335631
という桁数を見て欲しい、10GHzで数え上げるだけでも何十年と掛かる。その組み合わせを単純に総当たりをすれば、百万年の単位になる。
数学を駆使することで100万時間といったレベルで検索が済むように範囲を絞って、BOINCに参加する家庭用パソコン50万台以上を投入して計算したらしい。
33をやっつけたときの論文がプレスリリースからリンクされてるけど同じ方法かな?ざっと眺めてみたところ初等的な議論しかしてないようだけど、だからこそ難しいんでしょうね
ぜひやってみて。
探索プログラムが難しいかといえばそんなことはない。もちろん、計算量削減のためにいろんな工夫と分散処理が必要だが。
脂漏徒には解説してもわからないよ
1秒間に1000個の演算結果が得られるとすると、1日は86,400秒だから、1日で確かめられる場合の数は8640万個ですな。
1日ほぼ1億として、100年がかりで3兆6500億ですわ。
こんな桁数の数になるまで見つからなかったのが驚きだなあ。
素数とか整数の問題は、人間の数字感覚とズレがあって面白い。
>素数とか整数の問題は、人間の数字感覚とズレがあって面白い。これだなあ。足したり引いたりして42になるのなら、せいぜい何十とか何百くらいの数字の範囲に解があって、その範囲になければもうなさそうなのに、18桁かな?そんなところにポコンと解があるなんて。
銀河ヒッチハイクガイドを旧訳版・新訳版ともに持ってるファンとしてはそれが「42」であることにニヤニヤですよ。映画版も日本ではイマイチ受けなかったんだっけなあ
むしろ「42」の方は残しておいて欲しかった…
この図を見てみると、非常に簡単な解がある領域と、巨大な数が出てくる領域が構造を持って現れているようなhttps://upload.wikimedia.org/wikipedia/commons/2/2d/Sum_of_3_cubes.svg [wikimedia.org]これがx3+y3+z3=kという図形が持っている構造ときっと関係あるんだろう。
x+y+z=42 →無限に答えがあるx^2+y^2+z^2=42 →答えが有限なので簡単(n^2は常に正の数なので)
という中で件の x^3+y^3+z^3=42 は、(x+y+z=42の)無限にある答えの中に条件に合致する(x,y,zの三乗根が整数になる)ものが見つかる場合は簡単だけど、答えが無い場合はそれを証明する必要がある。無限の藁山の中に、あるかないかもわからない針を探すような問題。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike
何が難しいのか分からない (スコア:0)
脂漏徒にでも分かる解説よろしく。
if文の連結のループだと100年かかるとか?
一晩で出来そうに見えるが。
Re:何が難しいのか分からない (スコア:1)
x,y,zに入りうる整数がN個あるとすると、ありうる答えの組み合わせはN^3個。
愚直に値を入れてみて調べる場合, 1から100万まで探すだけでも100万の3乗個調べる必要がある。
実際,上の記事に記載されている解で, xは1兆をはるかに超える数なので1兆^3よりもずっと膨大な解候補から見つけ出した事になる。
Re:何が難しいのか分からない (スコア:1)
最後の数は計算すればいいから3乗じゃなくて2乗ですむだろ
Re: (スコア:0)
そうですね。それでも膨大、ということでしょうね。
Re: (スコア:0)
最後の数はケース分けしなくてもいいですが、三乗根を求めなきゃいけないので、それはそれで計算量はありそうです。
Re: (スコア:0)
三乗根を求めなくても、整数の三乗の数を表にしておけばいいだけじゃないの?
Re:何が難しいのか分からない (スコア:2)
80538738812075974が56bit
petaを越え、下手するとexa byteクラスのテーブル検索ですか。
いくら富豪プログラミングでも追いつかねぇ。
Re: (スコア:0)
ああそうか勘違いしてた、ありがとう。
2分法なら約56回で解が求まるってことですかね。
Re: (スコア:0)
普通に三乗根求めてもそんなに重くないよ。
低い精度で求めておいて最後だけニュートン法使えば求まるから。
Re:何が難しいのか分からない (スコア:1)
x=80435758145817515
y=80538738812075974
z=12602123297335631
という桁数を見て欲しい、10GHzで数え上げるだけでも何十年と掛かる。その組み合わせを単純に総当たりをすれば、百万年の単位になる。
数学を駆使することで100万時間といったレベルで検索が済むように範囲を絞って、BOINCに参加する家庭用パソコン50万台以上を投入して計算したらしい。
Re:何が難しいのか分からない (スコア:1)
33をやっつけたときの論文がプレスリリースからリンクされてるけど同じ方法かな?
ざっと眺めてみたところ初等的な議論しかしてないようだけど、だからこそ難しいんでしょうね
Re: (スコア:0)
ぜひやってみて。
Re: (スコア:0)
探索プログラムが難しいかといえばそんなことはない。
もちろん、計算量削減のためにいろんな工夫と分散処理が必要だが。
Re: (スコア:0)
脂漏徒には解説してもわからないよ
Re: (スコア:0)
1秒間に1000個の演算結果が得られるとすると、1日は86,400秒だから、1日で確かめられる場合の数は8640万個ですな。
1日ほぼ1億として、100年がかりで3兆6500億ですわ。
Re:何が難しいのか分からない (スコア:1)
こんな桁数の数になるまで見つからなかったのが驚きだなあ。
素数とか整数の問題は、人間の数字感覚とズレがあって面白い。
Re: (スコア:0)
>素数とか整数の問題は、人間の数字感覚とズレがあって面白い。
これだなあ。足したり引いたりして42になるのなら、せいぜい何十とか何百くらいの数字の範囲に解があって、
その範囲になければもうなさそうなのに、18桁かな?そんなところにポコンと解があるなんて。
銀河ヒッチハイクガイドを旧訳版・新訳版ともに持ってるファンとしてはそれが「42」であることにニヤニヤですよ。
映画版も日本ではイマイチ受けなかったんだっけなあ
Re: (スコア:0)
むしろ「42」の方は残しておいて欲しかった…
Re: (スコア:0)
おもしろいなぁ。
Re:何が難しいのか分からない (スコア:5, 興味深い)
この図を見てみると、非常に簡単な解がある領域と、巨大な数が出てくる領域が構造を持って現れているような
https://upload.wikimedia.org/wikipedia/commons/2/2d/Sum_of_3_cubes.svg [wikimedia.org]
これがx3+y3+z3=kという図形が持っている構造ときっと関係あるんだろう。
Re: (スコア:0)
x+y+z=42 →無限に答えがある
x^2+y^2+z^2=42 →答えが有限なので簡単(n^2は常に正の数なので)
という中で件の x^3+y^3+z^3=42 は、(x+y+z=42の)無限にある答えの中に条件に合致する(x,y,zの三乗根が整数になる)ものが見つかる場合は簡単だけど、答えが無い場合はそれを証明する必要がある。
無限の藁山の中に、あるかないかもわからない針を探すような問題。