[過去ログ] コラッツ予想がとけたらいいな その2 (1002レス)
1-

このスレッドは過去ログ倉庫に格納されています。
次スレ検索 歴削→次スレ 栞削→次スレ 過去ログメニュー
1
(25): righ1113 ◆OPKWA8uhcY 2018/05/10(木)22:10 ID:ogyKPvh0(1/2) AAS
コラッツ予想に挑戦するスレです。

前スレ コラッツ予想がとけたらいいな
2chスレ:math

>>1の証明(未検証)
https://github.com/righ1113/collatzProof

それより弱い成果もあります(未検証)
コラッツのループはあるとしてもとても長い
https://github.com/righ1113/collatzLongLoop
2
(3): righ1113 ◆OPKWA8uhcY 2018/05/10(木)22:12 ID:ogyKPvh0(2/2) AAS
今は前スレ>>786氏の予想を検証しています。

自然数aに対し、集合T(a)を
T(a)={b∈N|aとbはコラッツ操作によって同じ数に到達する}
と定める。
T(a)の形の集合を木と呼ぶ。
コラッツ予想が真であることは、自然数全体が1つの木をなすことと同値である。
で、次のように予想した。
予想
Tを木とし、n,kを自然数とする。
このとき、あるa∈Tが存在してa≡k(mod n)が成り立つ。
省2
3
(1): 2018/05/10(木)22:17 ID:vsrY1r+A(1) AAS
>>1
4
(1): 前786 ◆5A/gU5yzeU 2018/05/10(木)23:48 ID:Ws8+Hi53(1/2) AAS
前スレ>>786の予想は、以下の場合に証明できています。
以下、0≦k≦n-1 とします。
・n=1,k=0
・n=3^e, e∈N, k は任意
・n が 5 以上の素数、Z/nZ において 2 が原始根、k≠0
・n が 5 以上の素数、Z/nZ において 2 が原始根、n≡2 (mod 3), k=0
・n は 83 以下の奇数, k は任意 (righ1113氏のプログラムによる検証)

また、次が分かっています。
・m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。
これにより、n が偶数の場合は n が奇数の場合に帰着されます。
5
(2): 前786 ◆5A/gU5yzeU 2018/05/10(木)23:53 ID:Ws8+Hi53(2/2) AAS
あれ、コピペが抜けてた。
>>1
6: 2018/05/11(金)00:02 ID:lDGPA2LH(1) AAS
自己満足しました
7: 前786 ◆5A/gU5yzeU 2018/05/11(金)20:23 ID:OFsS5uwl(1/3) AAS
アルゴリズムのどこに無駄があったのかという話

(前スレ>>967の出力結果を参照してください)
詳しい理屈は後で述べますが、例えば n=15 でいうと
(3) のところは A3 と B1 の組を探す必要がありません。
さらに、A'=A3 としたときの C は [5,10,…] の方のグループは不要です。
新しい方のアルゴリズムでは、このあたりを除いています。

以下、詳しい理屈。

例えば n=15, k=5 の証明をしたいとします。
まずは普通に進めます。

〜〜〜〜〜〜〜〜〜
省17
8: 前786 ◆5A/gU5yzeU 2018/05/11(金)20:23 ID:OFsS5uwl(2/3) AAS
証明は次のように進みます。

〜〜〜〜〜〜〜〜〜〜

(ii) b が mod 45 で B0={1,2,4,8,16,17,19,23,31,32,34,38} に属する場合
b に何度か 2 をかけると mod 45 で 16 になるので、
そこから 1 を引いて 3 で割ることによって、mod 15 で 5 である元を得る。

〜〜〜〜〜〜〜〜〜〜

あとは mod45 で B2 に属する元について調べるのみです。
B2 の元は mod 135 では
 C1=[7,11,13,14,22,26,28,29,37,41,43,44,52,56,58,59,67,71,73,74,82,86,88,89,97,101,103,104,112,116,118,119,127,131,133,134]
に含まるので、ある B0 の元に 3 をかけて 1 を加えて C1 に属せばOKです。
省13
9: 2018/05/11(金)20:56 ID:b0n49LZW(1/3) AAS
俺はあんまり素数についてのノウハウ知らないんだよね。
素数のノウハウあれば「n=q,n=qで予想が成り立つ」から「n=pqで予想が成り立つ」へ繋げるアイディアももっと湧くのかもしれない、等と思ったり。
10: 2018/05/11(金)21:47 ID:b0n49LZW(2/3) AAS
とりあえず、目の前に大量のデータがあるわけだけど、
こういうのから何か法則を見出すのって、コツとかあるのかな
11
(2): 前786 ◆5A/gU5yzeU 2018/05/11(金)23:35 ID:OFsS5uwl(3/3) AAS
とりあえず 5 以上の奇数を次のように分類してみる。

?素数かつ 2 が原始根かつ mod 3 で 2:5,11,29,53,59,83,…
?素数かつ 2 が原始根かつ mod 3 で 1:13,19,37,61,67,…
?素数かつ 2 が原始根でない:7,17,23,31,41,43,47,71,73,79,89,97,…
?合成数:15,21,25,33,35,39,45,49,51,55,57,63,65,69,75,77,85,87,91,93,95,99,…

?は任意の k で証明済み。

?は n の倍数でない k で証明済み。
現行のプログラムでは、
・A' の候補は {0} のみ、
・B は 2 グループになり、A' と組ができる B は片方のみ
省8
12: 2018/05/11(金)23:57 ID:b0n49LZW(3/3) AAS
ふーむ、まずは分類ですか。
まあいきなりきれいな法則は見つかりそうにないし、正しい方針かも。
13: righ1113 ◆OPKWA8uhcY 2018/05/11(金)23:58 ID:SBH2/eHc(1) AAS
プログラミングは3割ぐらい進みました。
あと2,3日には出来ると思います。
アルゴリズムも進化して、こちらもコーディングのやりやすさを感じています。
14: 前786 ◆5A/gU5yzeU 2018/05/12(土)01:03 ID:xLUYWUsP(1/5) AAS
あ、3 の累乗は証明済みなので、>>11では抜いてあります。
15
(1): 2018/05/12(土)01:06 ID:fD/walWV(1/8) AAS
なんかこの予想に名前つけたいですね。
名前あったほうが議論しやすいですよね?
>>786なにか名前考えてもらえませんか?
16: 2018/05/12(土)01:19 ID:fD/walWV(2/8) AAS
なんかこの予想が肯定的に解決するなら素因数分解が多項式時間でとけちゃうとか、重大な結果に繋がったりしないかな?w
17: 2018/05/12(土)02:27 ID:fD/walWV(3/8) AAS
離散対数問題とか絡んできそうな気が若干する
18
(2): righ1113 ◆OPKWA8uhcY 2018/05/12(土)04:55 ID:+tHVZn3R(1) AAS
ジェバンニが一晩でやってくれました
*Main> main
5以上の奇数nを入力してください
7
A : [[0],[1,2,4],[3,5,6]]

[0]
B : [[1,2,4,8,11,16],[5,10,13,17,19,20]]
(4) tuple : [(0,Just 0)]
一度も現れなかったBi : [1]

C : [[5,10,17,20,34,40],[13,19,26,38,41,52],[31,47,55,59,61,62]]
省15
19: 2018/05/12(土)09:10 ID:fD/walWV(4/8) AAS
おお、乙です。
20
(1): 前786 ◆5A/gU5yzeU 2018/05/12(土)10:47 ID:xLUYWUsP(2/5) AAS
>>18
はやいw
乙です。

(6) でいちいち全部出力すると後々大変なことになりそうな予感。
もちろんデータが多いのは利点でもあるけど、うーむ
1-
あと 982 レスあります
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル

ぬこの手 ぬこTOP 0.270s*