Sum of three cubes問題、42に対して解かれる 79
ストーリー by hylom
デカい 部門より
デカい 部門より
qfwfq曰く、
整数kに対してx^3+y^3+z^3=kとなる整数x、y、zを求める（あるいは存在しないことを証明する）という問題を「Sum of three cubes」問題と言う。
100以下のkに対してほとんどは1954年に提起されてまもなく解決していたが、33と42についてだけは未解決だった。33について解かれたのも今年になってのことだが、先日とうとう42についても次のような解が発見された（ブリストル大学の発表）。
-80538738812075974^3 + 80435758145817515^3 + 12602123297335631^3 = 42探索には分散コンピューティングソフトウェア「BOINC」が使われたが、プロジェクトを主導したBristol大のプレスリリースではBOINCをSF小説「銀河ヒッチハイク・ガイド」の「Deep Thought」になぞらえている。
Windows CALCでも４２ (スコア:3)
検算してみたらちゃんと４２がでますね。ちなみにWindows10のCALC
-5.2241359903697915028096614485365e+50 + 5.2041221158249736173865271846355e+50 + 2.0013874544817885423134263901005e+48
=42
３乗だから結果は同じですが (スコア:2)
(-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3 = 42
括弧をつけて欲しいです。
Deep Thought (スコア:1)
各項は生命、宇宙、万物のどれにあたるのでしょうか？
Re: (スコア:0)
それを調べるために別のコンピューターが必要なのじゃよ。
Re:Deep Thought (スコア:1)
ちょっと待て。
元ネタでは地球は惑星型コンピュータで、その上に住む人類は究極の問いを求めるための生体素子なんだが、
我々スラド民はその演算に役立っているのだろうか？
ノイズを発生させているだけではないのだろうか？
「80538738812075974は友情、80435758145817515は努力、12602123297335631は勝利」 とか
「80538738812075974は空、80435758145817515は海、12602123297335631は陸」 とか
「80538738812075974はジオウ、80435758145817515はゲイツ、12602123297335631はウォズ」 とか
「80538738812075974はガイア、80435758145817515はオルテガ、12602123297335631はマッシュ」 とか
「80538738812075974はガラミティ、80435758145817515はニェット、12602123297335631はダー」 とか混ぜていいのだろうか？
Re:Deep Thought (スコア:2)
100万年前に原生種は滅びてゴルガフリンチャム人の棄民があとを継いだくらいだから、誰かいればいいのでは。
べき乗 (スコア:0)
x3+y3+z3=k
のような表現が出来ない場合、
べき乗の表現において^を使うのは、一般的なのでしょうか？
Re: (スコア:0)
一般的です．
Re: (スコア:0)
逸般的だと思うが。
TeXnicianとかプログラムを書く人なんかが一般的な人というなら一般的かもしれないけど。
Re:べき乗 (スコア:2)
Re:べき乗 (スコア:3)
なるほど、上付きと言う意味だったのか…
Re: (スコア:0)
プログラム書かない人でも結構使うし、使えば通じると思うけど。
Re: (スコア:0)
そこそこ一般的じゃないですかね。
エクセル(他の表計算ソフトも？)で「=2^3」のようにべき乗計算するとき使うので。
Re: (スコア:0)
どう見ても排他論理和だが。
Re:べき乗 (スコア:2)
C++が流行り始めた頃、演算子オーバーロードの例で、
operator^ をべき乗として定義する、というのをちょこちょこ見かけましたが
そのままべき乗のつもりで使うと、優先順位の問題ではまる罠が。
べき乗数式的には、a+b^cはa+bcと解釈するべきだけど、
C言語的には(a+b)^cと解釈されて、その優先順位は演算子オーバーロードでも変えられない…
Re: (スコア:0)
論理積ではありませんか。
https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E7%A9%8D [wikipedia.org]
本当は ^ ではなくて ∧ ですが。
排他的論理和でも使うことがあるようですね。
https://ja.wikipedia.org/wiki/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%... [wikipedia.org]
自分は排他的論理和の演算子として ^
Re: (スコア:0)
> 自分は排他的論理和の演算子として ^ を使うプログラム言語を使ったことがありません。
C が ^ を xor の意味で使うので、C/C++やその流れを組むJava/C#だったり、PythonやRubyなんかも ^ を xor に使うのですが使ったことありません？
Re: (スコア:0)
LaTeXでよく使われるのが広まった感じかなあ？
それとも大元はBASICかな。
かなり一般的・・・と思ったけど
流行りのスクリプト言語は大体「**」使うのな。またはpow()関数とか。。
Re:べき乗 (スコア:1)
ALGOLとかもそうなので、結構歴史はありそう。
ExcelとかLotusとかでもべき乗記号はハットマークなので、プログラム言語限定で使われたわけでもない。
自分的には、当たり前すぎて一般的か否かを考えたこともなかったけど、最近の言語じゃ使われないし、ExcelにもPow関数あるし、若い人とかは知らないのかも。
Re: (スコア:0)
まあ一般的じゃないですかね。
^も**も、よく見かけるし通じます。
逆に何なら一般的だと考えてますか？
Re: (スコア:0)
整数kをx^3+y^3+z^3で表現できないからって^を使うなって何言ってんだと一瞬思った（混乱
1954年？ (スコア:0)
なんだか紀元前数千年からあってもおかしくないような問題なのに割と最近なのね。
思いついた人はもちろん1954年以前から山ほどいたとは思うが、それにしてもなんでそんなに遅いんだろう？
Re:1954年？ (スコア:3)
アラビア数字が現れる前の数学の話って、結構面倒なんですよね。
無茶苦茶大きい数とか無理数とか表記方法を、どう考えていたかをアラビア数字（桁上がりの記法。10進法すら）を捨てて考えなくてはいけない。
＃三平方の定理を理解している訳だから無理数の理解はあると思うんだけど。
逆に分数が現代人より身近。税金の名前が分数の名前だったり。（属州民の税金が十分の一税とか）
Re:1954年？ (スコア:2)
> ピタゴラス教団というのがあってだな
のちの、安倍晴明でしたっけ。
Re: (スコア:0)
そもそも負の数が発見（発明）されたのって、そんな昔でしたっけ？
零が発見されたのだって、紀元前数百年くらいだったような。
何が難しいのか分からない (スコア: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:何が難しいのか分からない (スコア:2)
80538738812075974が56bit
petaを越え、下手するとexa byteクラスのテーブル検索ですか。
いくら富豪プログラミングでも追いつかねぇ。
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)
＞素数とか整数の問題は、人間の数字感覚とズレがあって面白い。
これだなあ。足したり引いたりして４２になるのなら、せいぜい何十とか何百くらいの数字の範囲に解があって、
その範囲になければもうなさそうなのに、１８桁かな？そんなところにポコンと解があるなんて。
銀河ヒッチハイクガイドを旧訳版・新訳版ともに持ってるファンとしてはそれが「４２」であることにニヤニヤですよ。
映画版も日本ではイマイチ受けなかったんだっけなあ
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という図形が持っている構造ときっと関係あるんだろう。
素朴な疑問 (スコア:0)
x^3+y^3+z^3=k でkが与えられた時、x,y,z は一意に決まるの?
あと、存在しないことが証明されたkもあるの?
Re:素朴な疑問 (スコア:3, 興味深い)
また、k を9で割ったあまりが 4か 5のときは解がありません証明例 [stackexchange.com]
Re: (スコア:0)
今回発見されたk=42も別解があるかもしれない、ということ?
もっと桁数の少ないのは多分ないんだろうけど。
Re:素朴な疑問 (スコア:1)
今回発見されたk=42も別解があるかもしれない、ということ?
それはもちろん。
// なお、k mod 9 ≠±4 で必ず解があるかというと、これは予想の範疇(未証明)です
Re:素朴な疑問 (スコア:1)
この予想に取り組むことで数論の進展に寄与したりするんでしょうか。
Fermat予想のように
Re:素朴な疑問 (スコア:1)
Re: (スコア:0)
n=1,2 はパラメータ的に表現できる解が無限に存在しますが、n=3になったとたんに「何も分からない」だそうです。(3つの数字のmod9が等しくあるべきことと、(1,1,1)(4,4,-5)の2組の解があること以外に)
Re: (スコア:0)
x,y,zの組み合わせが一意に決まらないkもあることは簡単に例を上げられますね。
k=0 の場合、任意の自然数aに対して、以下の等式が成り立ちます。
a^3 + (-a)^3 + 0^3 = 0
x,y,zが互いに異なるという条件がなければ、他にも
k=1
1^3 + 1^3 + (-1)^3 = 1
0^3 + 0^3 + 1^3 = 1