コラッツ予想がとけたらいいな
レス数が950を超えています。1000を超えると書き込みができなくなります。
525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22
http://d.hatena.ne.jp/righ1113/
コラッツ予想について、証明を考えてみました。
ご指摘ご意見ご感想など、ぜひよろしくお願いします。 >>876
乙です。
もうプログラムも完成間近か
予定を前倒ししそうな勢いですな。
素晴らしいことです。 意外と行数がすくないですがこれがHaskellのパワーなんですかね? >>880
そうですHaskellのチカラです。
1行で5コぐらい事をおこなっていて、高密度に圧縮されています。 >>876
乙です。
あれ、もしかして修正前のもので作ってる?
もしよければ>>850の修正バージョンでお願いしたいなーと おおっとw 修正依頼来ましたかw
>>1ガンバ!w >>882
あれ、修正前で作ってますかね?!
(7)が違うのかな〜 >(7)B1,B2,…のうち、全てのCjとの組が得られていないもの を調査
修正後ではこの操作が不要で B' というものがそもそも現れないはずなので…
すみませんがよろしくお願いします。 まあ開発にハプニングは付き物ですねw
それ込みで予定通りくらいですかね? >>1って前、グーグルドライブでファイル公開してたよね?
今回のファイルもグーグルドライブとかで公開してくれないですか?
インデントが消えてるのかなんなのか>>877-878コピペじゃ上手く動かないみたい。 UTF-8がどうとかいわれたので日本語けしてインデントつけたら動いたみたいです。
19を入力してみました。
$ ./collatz.exe
19
input num
Z/pZ : [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
A : [[0],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]]
Z/3pZ : [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56]
B : [[1,2,4,7,8,14,16,25,28,29,32,41,43,49,50,53,55,56],[5,10,11,13,17,20,22,23,26,31,34,35,37,40,44,46,47,52]]
(3) tuple : [(0,Just 0),(1,Just 0),(1,Just 1),(1,Nothing)]
(4) A' No. : [0]
C : [[5,10,11,20,22,40,44,80,83,88,91,127,131,149,151,160,161,166],[13,23,26,37,46,52,67,74,79,92,97,104,119,125,134,145,148,158],[17,31,34,35,47,62,68,70,77,94,101,103,109,124,136,137,140,154]]
(6) tuple : [(0,Nothing),(0,Just 1),(0,Just 0),(0,Just 2)]
(7) B' No. : [] まあ、なんにしても>>786がこのプログラムを自分のマシンで動かせるところまではなんとか持っていきたいですねぇ 一応酉
コラッツ数列について綺麗な法則性を見つけました
簡単な計算規則の適用で4→2→1ループまでの計算回数を半分以下にできます
早く完成させねば >>786のPCってOSは何ですか?
Haskell動かせるようになってほしいんですが。 >>891 >>893
私としては今は証明を考えるのが楽しいので
プログラムはそのうち気が向いたら…ぐらいに思ってたのですが
一応OSはメインのPCが windows8.1, 他に windows10 も使える環境にあります。
あ、よく見たら>>890で n=19 が証明できてますね。 >>1のhaskell環境ってどうなってますか?
合わせられるならなるべくあわせたほうがいいよね? できればこれを機にプログラムに目覚めてほしいw
まあ自分でプログラム書くところまでいかなくても
せっかく>>1がここまで頑張ったので
プログラム動かすだけでも試してほしいな >>895
自分の環境はWindows10で、
Haskell Platform 8.0.2-a
GHC 8.0.2
です。
最新版のHaskell Platformでも問題ないと思います。 >>907
乙です。
>>890は>>1が書きかけのプログラムに19を食わせただけなのでちゃんと証明になってるかわかんないです。
証明になってるんですかね?
>>786はせっかく才能あるんだから食わず嫌いは勿体ないですよ! >>908
嫌ってるわけじゃありません。興味もあります。
ただ、そもそも私はそういう話をしに来たんじゃなく、
もっとこう、ここまでの証明がいいとか悪いとか、
全く別のアイデアがあるだとか、この予想から何が分かるかとか、
そういう数学の話をしたくてここに来たんです。
その辺ノってくれる方はいないっぽいですかね…
>>890では B' の候補が無いと出力されているので、この時点でアルゴリズムが終了します。
アルゴリズムが終了する⇒その n で予想が成り立つ
です。 まあ>>786がそういうなら無理強いはできませんね。
あと>>786が期待しているようなレベルの人は今はこのスレにはいないかもしれませんが、
スレが盛り上がってもっと人の目に留まるようになればあるいは凄い人が来てくれるかもしれません。
頑張って盛り上げていきましょう! とりあえず、いまは>>1のプログラムが仕上がるのを待つ、ですかね。
データがそろったら新事実が見つかるかもしれないし。 一日遅延ですがp=7が出来ました。
繰り返し処理は明日以降考えます。
*CollatzMod> main
素数pを入力してください
7
Z/pZ : [0,1,2,3,4,5,6]
A : [[0],[1,2,4],[3,5,6]]
Z/3pZ : [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
B : [[1,2,4,8,11,16],[5,10,13,17,19,20]]
(3) tuple : [(0,Just 0),(1,Just 0),(1,Nothing),(2,Just 1),(1,Just 1),(2,Just 0)]
(4) A' No. : [0]
C : [[5,10,17,20,34,40],[13,19,26,38,41,52],[31,47,55,59,61,62]]
(6) tuple : [(0,Nothing),(0,Just 1),(0,Just 0)]
一度も現れなかったCi : [2]
D : [[31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188]]
(8) tuple : [(0,Nothing),(0,Just 0),(1,Nothing),(1,Just 0)]
一度も現れなかったDi : []
*CollatzMod> ノってくれる方がいない、は言い過ぎでした。
>>801や>>837などで、これまでも数学的な話はできています。
こういう意見を頂けるのは非常にうれしいし、返信を考えるのは楽しいです。
ついカッとなってしまってああいう言い方になってしまいました。
>>921
待つしかないなんてことはありません。
私は私でまた証明の続きを考えます。
>>922
おお、例と同じ結果になってる
乙です。 >>1が>>758で
1〜nまででコラッツの反例がなければ、
n周期以下のループは存在しない です。
ていうアイディアを出してたんだけど>>786の予想から繋げて何か言えないかなーと妄想中 仮に1を含まない木が存在したとして、さらにその木がループを含むと仮定し、
かつコラッツの予想がnの倍数だけ調べればいいとすれば何か言えそうな気がするが
いまのところ気がするだけw いちおう出来ましたが、あやしいです。
p=21で止まってしまうのです。
ログをつけましたので、見ていただけないでしょうか。
https://github.com/righ1113/CollatzMod 見たところ48行目までは正常に動いてるっぽい。
確かに49行目が怪しいですね。
46行目で 0,1,2,3 番目の C に対して組が得られているので、
本来なら (0,Just 0) などが出力されるところだと思います。
例えば33行目でDを扱った後に何かがリセットされてない…とか? >>940,941
ありがとうございます。
ペアが空っぽというのは無いのですね。
明日は午後が空くので、そこで見ようと思います。 >>938
直したと思います。
昨日の場所にログを置きました。
と思ったらp=73でまたしてもバグが!
配列のインデックスをオーバーとかこうとか……
プログラム、普通には動くと思いますので、 僕はマイペースでバグ取りしたいと思います。 ちなみに73と言うのはどこから来たの?
100くらいまで全部計算まわしたの? >>945
7以上の奇数を順番に見ていって、
73でバグに当たりました。 おれもバグ取り協力したいけどアルゴリズムも十分理解してないしhaskellも十分理解してないからダブルで難しいorz それにしてもまだバグがあるかもしれないけど5以上71以下の奇数で全部>>786予想が成り立つってこと?
けっこう凄くね? >>943
バグ直ったかも。
でも家のPCのネットワーク系がダメになってしまったので、
GitHubは更新できません。 >>950
家のネットが一時的に直ったのでGitHub更新しました。
これにて完了?かな? >>1乙です
手間じゃなければ例えば100以下の奇数に対してとかの実行結果もGitHubに上げてほしいです。
そうすれば>>786とか他の人も参照できるだろうし。 まあそれよりも>>786のOKをもらうのが先ですかね? いやー手計算でn=19とかでひーこら言ってるところにあっさり73とか言われると
さすがにプログラムの力を思い知らされますねえ。
>>1乙です。
p=21 は大丈夫そうですね。p=73 はあとでじっくり見てみます。
>>949
証明できたことは凄いですけど、
「予想が成り立つのが凄い」という意味で言ってるんであれば、
それは全然不思議ではありません。
というのも、>>786で書いた通り
この予想が成り立たない⇒コラッツ予想が成り立たない
なので、簡単に反例が見つかる方がおかしいのです。 >>955
ところで、「全てのn,kでa≡k (mod n)が成り立つ→コラッツ予想は真」
って証明あるのですか?
あるなら見てみたいです。 >>956
うーん、ないですね。
それは成り立たないんじゃないかと思っています。
もし成り立つなら、>>786はコラッツ予想と同値になるので一気に>>786の重要度が増すんですがw
逆であれば、>>786に書いた通り成り立ちます。 「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」
というのは、初期値が1になるまで調べるのか、
初期値が自身より小さくなればOKなのか、
どちらだろう? nは奇数に限るのかな?
8m+5と2m+1は同じ数に移るから8m+5(n=8,k=5)は調べなくて良い、のような例はあるんじゃないかな n=pとn=qで予想が成り立つ => n=pqで予想が成り立つ
が言えたら面白そう >>959
1になるまで調べる、ですね。
実際に一つずつ調べるんであれば、もちろん「既に調べた数が得られるまで」とするのが自然かと思います。
>>960
奇数だけ扱っているのは、>>806によって偶数は奇数に帰着されるからです。
8m+5 と 2m+1 は両方とも 3m+2 に移るから 3m+2 を調べれば十分、という具合です。
>>961
これが言えれば素数だけ示せばよくなるのでだいぶ楽になりますね。
n=p, n=q と n=pq の間に何かしら繋がりがありそうな感じはしますが、まだよく分かりません。 プログラムの実行結果からn=p,n=q,n=pqの関係を考察できそう? やっぱプログラムの実行結果公開してほしいなぁ。
>>1頼んます。 >>965
そうですね。とりあえずそれで。
頼んます。 おお、仕事速いすな。
乙です。
さてここから何か見つかるか… うーん。
パッと見では法則は見えないですな。
まあそりゃそうか。 >>805によれば
2が原始根かどうかとmod 3 の値がなにか
あたりがミソになるのかなぁ 100以下の素数に対して2が原始根か?とmod 3の値、一覧
3 true 0
5 true 2
7 false 1
11 true 2
13 true 1
17 false 2
19 true 1
23 false 2
29 true 2
31 false 1
37 true 1
41 false 2
43 false 1
47 false 2
53 true 2
59 true 2
61 true 1
67 true 1
71 false 2
73 false 1
79 false 1
83 true 2
89 false 2
97 false 1 10000くらいまでデータ欲しいかもw
でも計算量的に厳しいですよね? >>967
ありがとうございます!
いろいろ見てみます!
ID:vsrY1r+A もいろいろと意見をありがとう。
3 の倍数に限らず、合成数なら比較的長くなると思われます。
また、素数でも 31 なんかはかなり長くなっています。
これは、2 の累乗がすぐに 1 になってしまう (2^5≡1 (mod 31)) ということに起因していると思われます。
127 なんかはどうなることやら。 …ところで、プログラムにまだ無駄があって、改良版を考えたので実装してほしい、って言ったら怒る? >>973
実はこっそりp=999をやっていたのですが、7時間ぐらいかかったもので。
>>975
またまたご冗談をw あ、無駄があるのはプログラムではなくアルゴリズムですね。
>>1のプログラムではなく私の理論に問題があったということです。 レス数が950を超えています。1000を超えると書き込みができなくなります。