コラッツ予想がとけたらいいな

1132人目の素数さん2012/10/14(日) 10:32:39.71
525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22
http://d.hatena.ne.jp/righ1113/
コラッツ予想について、証明を考えてみました。
ご指摘ご意見ご感想など、ぜひよろしくお願いします。

721132人目の素数さん2017/08/07(月) 15:17:03.95ID:0YzkEl/p
耳栓をしたら世界が変わってワロタ

722righ1113 ◆OPKWA8uhcY 2017/10/08(日) 09:15:13.38ID:StPF7u7V
メルセンヌ素数 2^110503 - 1 って
止まらないことないですか?

723132人目の素数さん2017/10/08(日) 11:28:20.81ID:Cutv7rfi
計算機でまわしたのか?
単にデカいから時間かかってるだけじゃないのか?

724righ1113 ◆OPKWA8uhcY 2017/10/08(日) 11:36:26.39ID:V4WPWhh+
2^110503-1が大体30000桁で、
10時間程走らせて、今45000桁ぐらいなのです。
また止まったら報告します。

725132人目の素数さん2017/10/08(日) 15:27:53.11ID:m0FVLI/3
2^n-1をコラッツの操作かけると3^n-1になるんだろ?30000桁が45000桁になってもさほど特別とは思わんな

726132人目の素数さん2017/10/08(日) 15:58:04.91ID:Pp5mcjdG
>>725で指摘されてるが、2^n-1から始めたいなら、
バカ正直に2^n-1からスタートさせるのではなく、
3^n-1からスタートさせないと無駄にも程があるな

727132人目の素数さん2017/10/08(日) 23:28:04.64ID:Cutv7rfi
ちなみに>>1の計算機だと30000万桁の数値に対して何コラッツステップ/secくらいのスピードで計算できんの?

728132人目の素数さん2017/10/08(日) 23:28:29.03ID:Cutv7rfi
あ間違えたw3万桁ねw

729righ1113 ◆OPKWA8uhcY 2017/10/09(月) 00:59:44.36ID:Vv+x6w6w
奇数→奇数を1ステップとして、
2361コラッツ奇数ステップ/sec ぐらいですかね。

730132人目の素数さん2017/10/09(月) 01:11:15.90ID:93q6V3EV
すまん、聞いてはみたものの速いのか遅いのかよくわからんw
プログラム言語は何使ってんの?

731righ1113 ◆OPKWA8uhcY 2017/10/09(月) 01:19:17.60ID:Vv+x6w6w
僕もよく分からないですw
言語はHaskellを使っています。多倍長整数が標準搭載されているので。

732132人目の素数さん2017/10/09(月) 01:28:20.34ID:93q6V3EV
Haskellか〜
プロトタイプ作るのには良いかもしれんが計算ぶん回すのにはどうなんだろ?
C++とまではいかなくても速度高めの言語も試してみるといいかもね。

733righ1113 ◆OPKWA8uhcY 2017/10/09(月) 01:44:12.02ID:Vv+x6w6w
そうですね、考えてみます。

そういえば今年の始め頃にこんなことをやっていました。
Go,C++,F#,Haskellでコラッツを計算してみた
http://d.hatena.ne.jp/righ1113/20170209#1486589174

734132人目の素数さん2017/10/09(月) 01:53:47.71ID:93q6V3EV
ん〜haskell最速ってホンマかいなw
どんな理屈でそういう結果になるのか想像つかないw

735132人目の素数さん2017/10/09(月) 02:00:31.03ID:93q6V3EV
haskellだけ多倍長になってないとかかなぁ
うーん。なんか違和感あることはある。

736righ1113 ◆OPKWA8uhcY 2017/10/09(月) 02:04:02.85ID:Vv+x6w6w
多分、多倍長整数と並列計算の組み合わせが
低コストで上手くいっているのがHaskellだと思います。
自信は無いですがw

737righ1113 ◆OPKWA8uhcY 2017/10/09(月) 17:38:37.95ID:Vv+x6w6w
>>726
3^110503-1で再チャレンジしました。
一日かかって40000桁まで下がったのですが、これ以上続けるのはしんどいです。
グダグダですみません。

738132人目の素数さん2017/10/10(火) 11:57:48.23ID:ziN8w0WH
停止するかどうかを 3^110503-1 のときに
確かめようとしてる時点で既にグダグダだけどな。

なぜなら、どうせ停止するに決まってるからだw

それが 1 になるかは分からないが、少なくとも
停止することは確実だと予想してよいだろう。
無論それ自体も未解決ではあるのだが、
停止「しない」ことが期待されるような良い根拠はどこにも無く、
逆に必ず停止すると思しき良い根拠はいくつもあるわけで。

739132人目の素数さん2017/10/10(火) 22:17:48.67ID:n27Dzau3
例えばループする自然数があったとして、ループの周期が非常に長く履歴がメモリに納まらないようなことが想定される場合、
ループを検出するアルゴリズムとしてどのようなものが考えられるだろうか?

740132人目の素数さん2017/10/11(水) 01:44:51.35ID:4RhSgzf6
>>739
1ステップずつ移動するのと2ステップずつ移動するのを用意して
同時に走らせて、両者の値が一致するかどうかを毎回チェックする。
一致したらループに入ってるし、逆にループに入ってたら
必ず一致するタイミングが訪れる。

741132人目の素数さん2017/10/11(水) 02:00:01.80ID:qm6Ubkun
最小値。

742132人目の素数さん2017/10/11(水) 05:34:15.97ID:acXKCTJa
〔問題〕
自然数nを1つ選び、2nを元に3倍して2を足す操作をk回繰り返す。
k を 1,2,3,… とすると、いつかは 2の累乗になる?

 一般項 (3^k)(2n+1)- 1

http://rio2016.5ch.net/test/read.cgi/math/1502032053/171-179
面白スレ24

743132人目の素数さん2017/10/11(水) 11:00:01.29ID:qm6Ubkun
13。

744◆2VB8wsVUoo 2017/10/23(月) 20:45:36.52ID:Dl6USvMt

745◆2VB8wsVUoo 2017/10/23(月) 20:45:57.26ID:Dl6USvMt

746◆2VB8wsVUoo 2017/10/23(月) 20:46:15.47ID:Dl6USvMt

747◆2VB8wsVUoo 2017/10/23(月) 20:46:40.05ID:Dl6USvMt

748◆2VB8wsVUoo 2017/10/23(月) 20:47:01.88ID:Dl6USvMt

749◆2VB8wsVUoo 2017/10/23(月) 20:47:18.45ID:Dl6USvMt

750◆2VB8wsVUoo 2017/10/23(月) 20:47:37.29ID:Dl6USvMt

751◆2VB8wsVUoo 2017/10/23(月) 20:47:54.98ID:Dl6USvMt

752◆2VB8wsVUoo 2017/10/23(月) 20:48:12.00ID:Dl6USvMt

753◆2VB8wsVUoo 2017/10/23(月) 20:48:33.10ID:Dl6USvMt

754132人目の素数さん2017/12/17(日) 21:47:06.98ID:VxDAPNtz
ABC予想が解かれたとかなんとか
コラッツも解けるといいですね

755righ1113 ◆OPKWA8uhcY 2017/12/18(月) 03:09:43.02ID:zmSySbud
>>754
そうですね〜
成果は出ていないのですが、もう少しだけ頑張ってみます。

756righ1113 ◆OPKWA8uhcY 2017/12/29(金) 09:10:07.92ID:miDoSCc+
>>570-576を再掲します。

・前準備1
例えばx_sが7,11,17,13,5,17,13,5……とループするなら、先頭2項は外して、
さらに最小値をx_0とおいて、5,17,13,5,17,13……にします。
例ではx_3=x_0になります。

・前準備2 
x_0~x_s-1がループ1周期として(x_0=x_s)、コラッツパターンX_sと左端を伸ばすパターンY_sのビット長は
[logY_s] = [log(x_0*(3/2)^s)]
[logX_s] = [log(x_0*(3/2)^s)+log(1+1/3x_0)…(1+1/3x_s-1)]
です。このときの[logY_s]と[logX_s]のずれがあってもなくても、周期を重ねるごとに[logX_s]と[logY_s]の差は
2log(1+1/3x_0)…(1+1/3x_s-1)、3log(1+1/3x_0)…(1+1/3x_s-1)、……と増大するので、
ずれも際限なく増大していきます。

757righ1113 ◆OPKWA8uhcY 2017/12/29(金) 09:13:24.23ID:miDoSCc+
ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3と仮定します。
X_3sを3ビット下位へシフトしてずれを消します。これをX_3s'とおきます。
X_3s'=x_0*(3/2)^3s*(1+1/3x_0)…(1+1/3x_3s-1)/8  です。

[logX_3s'] - [logY_3s] = 0  から始めて 
[log(x_0*(3/2)^3s)+log(1+1/3x_0)…(1+1/3x_3s-1)/8] - [log(x_0*(3/2)^3s)] = 0
切り上げを外して
-1 < log(1+1/3x_0)…(1+1/3x_3s-1)/8 < 1
logを外して
1/2 < (1+1/3x_0)…(1+1/3x_3s-1)/8 < 2

ここで、x_0がループ中最小で、s<=x_0ならば、
(1+1/3x_0)…(1+1/3x_3s-1) < ((1+1/3x_0)^3x_0)^(3s/3x_0) <= (1+1/3x_0)^3x_0 < e
なので、
(1+1/3x_0)…(1+1/3x_3s-1)/8 < e/8 ≒ 0.339
となって1/2を下回って矛盾します。よってs>x_0です。

758righ1113 ◆OPKWA8uhcY 2017/12/29(金) 09:16:25.04ID:miDoSCc+
まとめると、
ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3としたとき、
s > x_0(ループ中の最小値)  です。

あるいは同じことですが、
ループ1周期でずれが1、3周期でずれが3としたとき、
1〜nまででコラッツの反例がなければ、
n周期以下のループは存在しない   です。

759righ1113 ◆OPKWA8uhcY 2017/12/30(土) 15:51:01.05ID:4pni1/3N
GitHubにまとめを載せました。
良かったらどうぞ。

https://github.com/righ1113/collatzLongLoop
 

760righ1113 ◆OPKWA8uhcY 2018/01/21(日) 06:56:30.67ID:o3XeyIKH
新しい証明を考えました。
https://github.com/righ1113/collatzProof

ポイントは、「最下位からの連続するビット1の個数」の帰納法で考えることです。

761132人目の素数さん2018/01/21(日) 21:54:14.87ID:e4dWohlO
>760
1回小さくなることしか証明してない

762righ1113 ◆OPKWA8uhcY 2018/01/22(月) 00:44:19.88ID:4mi9P+bz
>>761
すみませんが、よく分からないです。
1回でも小さくなることを証明すれば、十分じゃないでしょうか。

nの全ての値がコラッツ操作で小さくなる→n+1の全ての値がコラッツ操作で小さくなる
が言えるので、帰納法により、全ての値がコラッツ操作で小さくなる
ことが言えると思います。

763132人目の素数さん2018/01/22(月) 04:00:15.16ID:zEZO4ljt
8x+3(n=2)→12x+5(n=1)→18x+8(n=0)→9x+4(n=?)

補題1-2がn=1の場合に偽じゃねえかな

764righ1113 ◆OPKWA8uhcY 2018/01/22(月) 20:40:41.60ID:CNwla0Dh
【補題1-2】を次のように変更します。
旧:¬smaller(n+1)ならば、¬smaller(n)である。
新:¬smaller(k+2)ならば、¬smaller(k+1)である。

これにより、この命題でのsmallerの引数が2以上に制限されます。
>>763の例は
8x+3(n=2)→12x+5(n=1)→ここで打ち止め
となり問題を回避できます。

GitHubも更新しました。

765132人目の素数さん2018/01/23(火) 05:46:43.90ID:O+AtXeLE
問題は「最初の数より小さくなる」かどうかだから次は16x+7で同じことになるね
・2x→x
・4x+1→3x+1
では小さくなっているが
n>2では「最初の数より小さくなる」ことが保証できんのだ

2x→xによって整数全体に移るせいで問題がフラクタル構造持ってる
再帰的な解決はここを回避しないと封じられてしまう気がする

766righ1113 ◆OPKWA8uhcY 2018/01/23(火) 09:59:19.01ID:MzJqaum6
>>765
すみませんよく分からないです……
じっくり考えてみます。

767righ1113 ◆OPKWA8uhcY 2018/01/23(火) 10:50:15.55ID:iVG/+p9N
8x+3(n=2)→12x+5(n=1)=4(3x+1)+1→3(3x+1)+1
                ^^^^^^^^^^^^^^^^^^^^
                ここでは小さくなっているが、
^^^^^^^^^^
この最初の数より小さくなっていない、でしょうか。
理解しました。

768righ1113 ◆OPKWA8uhcY 2018/02/03(土) 16:35:17.43ID:fD/urjTL
◆◆◆■■■■       15→127
□◆◆■■■□■      23→95
□□◆■■□□□■     35→71
□□□■□■□■■     53
□□□□□□□■□■    5
□□□□□□□□□□■   1

新しいコラッツパターンを考えました。
◆を追加します。
すると、nの大小=x_sの大小が言えるので、
smaller(n+1)ならば、smaller(n+2)
が言えると思うのですが、どうでしょうか。

769132人目の素数さん2018/02/04(日) 07:22:20.66ID:mw9eaFXP
2x+1→6x+4→3x+2
2x+0→1x+0
をセットの操作として考える
xの係数は奇数なのでxの偶奇で次の偶奇が定まる
xを2x+1、2x+0で置換してもう1セット操作する
xの係数は奇数(というか3の冪)となるのでやはり次の偶奇はxの偶奇で定まる

あとは帰納法で「下位nビットがnセット操作分の変化を定める」のがわかる

下位ビット固定は固定した分しか定まらないのでうまくいかない印象

770righ1113 ◆OPKWA8uhcY 2018/02/04(日) 20:03:51.85ID:iMjXyBGA
だめですかねえ……
とりあえずExcelを更新しました。
https://github.com/righ1113/collatzProof

771righ1113 ◆OPKWA8uhcY 2018/02/09(金) 22:41:34.79ID:6EKEcZuH
コラッツパターン2にしたら、
4x+1が小さくならなくなってしまいました。無念。

新着レスの表示
レスを投稿する