コラッツ予想がとけたらいいな
at MATH
[前50を表示]
750:１３２人目の素数さん
17/10/08 15:58:04.91 Pp5mcjdG.net
>>725で指摘されてるが、2^n-1から始めたいなら、
バカ正直に2^n-1からスタートさせるのではなく、
3^n-1からスタートさせないと無駄にも程があるな
751:１３２人目の素数さん
17/10/08 23:28:04.64 Cutv7rfi.net
ちなみに>>1の計算機だと３００００万桁の数値に対して何コラッツステップ/secくらいのスピードで計算できんの？
752:１３２人目の素数さん
17/10/08 23:28:29.03 Cutv7rfi.net
あ間違えたｗ３万桁ねｗ
753:righ1113
17/10/09 00:59:44.36 Vv+x6w6w.net
奇数→奇数を1ステップとして、
2361コラッツ奇数ステップ/sec ぐらいですかね。
754:１３２人目の素数さん
17/10/09 01:11:15.90 93q6V3EV.net
すまん、聞いてはみたものの速いのか遅いのかよくわからんｗ
プログラム言語は何使ってんの？
755:righ1113
17/10/09 01:19:17.60 Vv+x6w6w.net
僕もよく分からないですw
言語はHaskellを使っています。多倍長整数が標準搭載されているので。
756:１３２人目の素数さん
17/10/09 01:28:20.34 93q6V3EV.net
Haskellか～
プロトタイプ作るのには良いかもしれんが計算ぶん回すのにはどうなんだろ？
C++とまではいかなくても速度高めの言語も試してみるといいかもね。
757:righ1113
17/10/09 01:44:12.02 Vv+x6w6w.net
そうですね、考えてみます。
そういえば今年の始め頃にこんなことをやっていました。
Go,C++,F#,Haskellでコラッツを計算してみた
URLﾘﾝｸ(d.hatena.ne.jp)
758:１３２人目の素数さん
17/10/09 01:53:47.71 93q6V3EV.net
ん～haskell最速ってホンマかいなｗ
どんな理屈でそういう結果になるのか想像つかないｗ
759:１３２人目の素数さん
17/10/09 02:00:31.03 93q6V3EV.net
haskellだけ多倍長になってないとかかなぁ
うーん。なんか違和感あることはある。
760:righ1113
17/10/09 02:04:02.85 Vv+x6w6w.net
多分、多倍長整数と並列計算の組み合わせが
低コストで上手くいっているのがHaskellだと思います。
自信は無いですがw
761:righ1113
17/10/09 17:38:37.95 Vv+x6w6w.net
>>726
3^110503-1で再チャレンジしました。
一日かかって40000桁まで下がったのですが、これ以上続けるのはしんどいです。
グダグダですみません。
762:１３２人目の素数さん
17/10/10 11:57:48.23 ziN8w0WH.net
停止するかどうかを 3^110503-1 のときに
確かめようとしてる時点で既にグダグダだけどな。
なぜなら、どうせ停止するに決まってるからだｗ
それが 1 になるかは分からないが、少なくとも
停止することは確実だと予想してよいだろう。
無論それ自体も未解決ではあるのだが、
停止「しない」ことが期待されるような良い根拠はどこにも無く、
逆に必ず停止すると思しき良い根拠はいくつもあるわけで。
763:１３２人目の素数さん
17/10/10 22:17:48.67 n27Dzau3.net
例えばループする自然数があったとして、ループの周期が非常に長く履歴がメモリに納まらないようなことが想定される場合、
ループを検出するアルゴリズムとしてどのようなものが考えられるだろうか？
764:１３２人目の素数さん
17/10/11 01:44:51.35 4RhSgzf6.net
>>739
1ステップずつ移動するのと2ステップずつ移動するのを用意して
同時に走らせて、両者の値が一致するかどうかを毎回チェックする。
一致したらループに入ってるし、逆にループに入ってたら
必ず一致するタイミングが訪れる。
765:１３２人目の素数さん
17/10/11 02:00:01.80 qm6Ubkun.net
最小値。
766:１３２人目の素数さん
17/10/11 05:34:15.97 acXKCTJa.net
〔問題〕
自然数nを1つ選び、2nを元に3倍して2を足す操作をk回繰り返す。
k を 1,2,3,… とすると、いつかは 2の累乗になる？
一般項 （3^k)(2n+1）- 1
ｽﾚﾘﾝｸ(math板:171番)-179
面白スレ２４
767:１３２人目の素数さん
17/10/11 11:00:01.29 qm6Ubkun.net
１３。
768:￥
17/10/23 20:45:36.52 Dl6USvMt.net
￥
769:￥
17/10/23 20:45:57.26 Dl6USvMt.net
￥
770:￥
17/10/23 20:46:15.47 Dl6USvMt.net
￥
771:￥
17/10/23 20:46:40.05 Dl6USvMt.net
￥
772:￥
17/10/23 20:47:01.88 Dl6USvMt.net
￥
773:￥
17/10/23 20:47:18.45 Dl6USvMt.net
￥
774:￥
17/10/23 20:47:37.29 Dl6USvMt.net
￥
775:￥
17/10/23 20:47:54.98 Dl6USvMt.net
￥
776:￥
17/10/23 20:48:12.00 Dl6USvMt.net
￥
777:￥
17/10/23 20:48:33.10 Dl6USvMt.net
￥
778:１３２人目の素数さん
17/12/17 21:47:06.98 VxDAPNtz.net
ABC予想が解かれたとかなんとか
コラッツも解けるといいですね
779:righ1113
17/12/18 03:09:43.02 zmSySbud.net
>>754
そうですね～
成果は出ていないのですが、もう少しだけ頑張ってみます。
780:righ1113
17/12/29 09:10:07.92 miDoSCc+.net
>>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)、……と増大するので、
ずれも際限なく増大していきます。
781:righ1113
17/12/29 09:13:24.23 miDoSCc+.net
ループ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です。
782:righ1113
17/12/29 09:16:25.04 miDoSCc+.net
まとめると、
ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3としたとき、
s > x_0（ループ中の最小値） です。
あるいは同じことですが、
ループ1周期でずれが1、3周期でずれが3としたとき、
1～nまででコラッツの反例がなければ、
n周期以下のループは存在しない です。
783:righ1113
17/12/30 15:51:01.05 4pni1/3N.net
GitHubにまとめを載せました。
良かったらどうぞ。
URLﾘﾝｸ(github.com)
784:１３２人目の素数さん
18/01/13 04:19:02.55 puPuVYkL0
コラッツ予想って、「すべての自然数が
１→４→２→１というループを根とした
二分木で表される」てことだよね？
「すべての原始ピタゴラス数は、｛３、４、５｝を
根とする三分木で表される」っていう定理があるけど
あれの類推でなんとかならないか？
785:righ1113
18/01/21 06:56:30.67 o3XeyIKH.net
新しい証明を考えました。
URLﾘﾝｸ(github.com)
ポイントは、「最下位からの連続するビット1の個数」の帰納法で考えることです。
786:１３２人目の素数さん
18/01/21 21:54:14.87 e4dWohlO.net
>761
1回小さくなることしか証明してない
787:righ1113
18/01/22 00:44:19.88 4mi9P+bz.net
>>762
すみませんが、よく分からないです。
1回でも小さくなることを証明すれば、十分じゃないでしょうか。
nの全ての値がコラッツ操作で小さくなる→n+1の全ての値がコラッツ操作で小さくなる
が言えるので、帰納法により、全ての値がコラッツ操作で小さくなる
ことが言えると思います。
788:１３２人目の素数さん
18/01/22 04:00:15.16 zEZO4ljt.net
8x+3(n=2)→12x+5(n=1)→18x+8(n=0)→9x+4(n=?)
補題1-2がn=1の場合に偽じゃねえかな
789:righ1113
18/01/22 20:40:41.60 CNwla0Dh.net
【補題1-2】を次のように変更します。
旧：￢smaller(n+1)ならば、￢smaller(n)である。
新：￢smaller(k+2)ならば、￢smaller(k+1)である。
これにより、この命題でのsmallerの引数が2以上に制限されます。
>>764の例は
8x+3(n=2)→12x+5(n=1)→ここで打ち止め
となり問題を回避できます。
GitHubも更新しました。
790:１３２人目の素数さん
18/01/23 05:46:43.90 O+AtXeLE.net
問題は「最初の数より小さくなる」かどうかだから次は16x+7で同じことになるね
・2x→x
・4x+1→3x+1
では小さくなっているが
n>2では「最初の数より小さくなる」ことが保証できんのだ
2x→xによって整数全体に移るせいで問題がフラクタル構造持ってる
再帰的な解決はここを回避しないと封じられてしまう気がする
791:righ1113
18/01/23 09:59:19.01 MzJqaum6.net
>>766
すみませんよく分からないです……
じっくり考えてみます。
792:righ1113
18/01/23 10:50:15.55 iVG/+p9N.net
8x+3(n=2)→12x+5(n=1)=4(3x+1)+1→3(3x+1)+1
^^^^^^^^^^^^^^^^^^^^
ここでは小さくなっているが、
^^^^^^^^^^
この最初の数より小さくなっていない、でしょうか。
理解しました。
793:righ1113
18/02/03 16:35:17.43 fD/urjTL.net
◆◆◆■■■■ 15→127
□◆◆■■■□■ 23→95
□□◆■■□□□■ 35→71
□□□■□■□■■ 53
□□□□□□□■□■ 5
□□□□□□□□□□■ 1
新しいコラッツパターンを考えました。
◆を追加します。
すると、nの大小=x_sの大小が言えるので、
smaller(n+1)ならば、smaller(n+2)
が言えると思うのですが、どうでしょうか。
794:１３２人目の素数さん
18/02/04 07:22:20.66 mw9eaFXP.net
2x+1→6x+4→3x+2
2x+0→1x+0
をセットの操作として考える
xの係数は奇数なのでxの偶奇で次の偶奇が定まる
xを2x+1、2x+0で置換してもう1セット操作する
xの係数は奇数(というか3の冪)となるのでやはり次の偶奇はxの偶奇で定まる
あとは帰納法で「下位nビットがnセット操作分の変化を定める」のがわかる
下位ビット固定は固定した分しか定まらないのでうまくいかない印象
795:righ1113
18/02/04 20:03:51.85 iMjXyBGA.net
だめですかねえ……
とりあえずExcelを更新しました。
URLﾘﾝｸ(github.com)
796:righ1113
18/02/09 22:41:34.79 6EKEcZuH.net
コラッツパターン2にしたら、
4x+1が小さくならなくなってしまいました。無念。
797:righ1113
18/02/24 14:20:55.93 RYOtT8nZ.net
構成を大幅に変えました。
コラッツパターン2も変えました。
798:１３２人目の素数さん
18/02/27 22:53:52.42 /Yl+hgqj.net
コラッツ問題の解決の役に立つかどうかはわからんが、思いついたので投下。
f:N→N
f(x)=x/2 (x:even)
f(x)=(3x+1)/2 (x:odd)
g:N×N→Z
g(x, n)=#{0<=i<n| f^i(x):odd}
とする。
このとき、0<k<=n に対し、
f^nは{x∈N|g(x, n)=k}上、広義単調増加である。
(i.e. x<y ⇒f^n(x)<=f^n(y))
例1. g(x, 3)=1
2→1→2→1
4→2→1→2
5→8→4→2
10→5→8→4
例2. g(x, 3)=2
1→2→1→2
3→5→8→4
6→3→5→8
9→14→7→11
799:１３２人目の素数さん
18/02/27 22:55:29.10 /Yl+hgqj.net
以下、超略証。
(n=1)
f(2x+1)=3x+2
f(2x+0)=1x+0
(n=2)
f^2(4x+1)=3x+1
f^2(4x+2)=3x+2
(n>2)
k<=n に対し{x∈N|g(x, n)=k}は周期2^nを持ち、
f^n(x+2^n)=f^n(x)+3^k を満たす。
ここから異なる周期間の単調性が、
n=2からは周期の中での単調性が示せる。
(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)
800:１３２人目の素数さん
18/02/28 19:18:14.81 6Xntgk3f.net
>>775
＞(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)
ここがだめ(全順序にならん)なので不成立。
一定の条件のもとで、近い数は近くなる、くらいしか言えてないか。
801:￥
18/04/06 12:28:59.91 I+Mybrk/.net
￥
802:￥
18/04/06 12:29:18.95 I+Mybrk/.net
￥
803:￥
18/04/06 12:29:38.52 I+Mybrk/.net
￥
804:￥
18/04/06 12:29:56.45 I+Mybrk/.net
￥
805:￥
18/04/06 12:30:18.29 I+Mybrk/.net
￥
806:￥
18/04/06 12:30:38.74 I+Mybrk/.net
￥
807:￥
18/04/06 12:30:58.98 I+Mybrk/.net
￥
808:￥
18/04/06 12:31:16.94 I+Mybrk/.net
￥
809:￥
18/04/06 12:31:36.78 I+Mybrk/.net
￥
810:￥
18/04/06 12:31:59.28 I+Mybrk/.net
￥
811:１３２人目の素数さん
18/04/25 11:21:08.33 syWjwryDn
「コラッツパターン」から、
「オンビットで始まってオンビットで終わるビット列」を
考えてみた。“コラッツむし”という。
全体を下位に１ビットシフトして、キャリーを
立ててから算術加算する。（３ｎ＋１）
つぎに、下位からオフビットをクリアする。（÷２）
その挙動が面白い。なんかしら、(1,)7, 31, 127 のどこかに落ちる。
812:１３２人目の素数さん
18/04/25 11:35:51.96 syWjwryDn
“コラッツむし”は、「１ビットシフト」と「キャリーオン」で、
相対的に上位側に「１」だけ移動している。
これは、通常営業だから勘定に入れなくていい。
「下位からオフビットをクリアする」のが、
実質的な移動量になる。
体長１の“コラッツむし”は、「4 -> 2 -> 1 -> 4」のループだから、
最終形態だ。
ここで 2^n - 1 のメルセンヌ数を出発点に取ると
（基本的に、体長が伸びるのは、このときだけ。
なぜなら最下位のキャリーが伝播しない）、
1 に直接
813:落ちなければ、メルセンヌ素数である7, 31, 127 を経由するらしい。
814:１３２人目の素数さん
18/04/25 11:48:27.28 syWjwryDn
まぁ、結局 >>40 のアイディアの焼き直しなんだが、
二次元セルオートマトンとして実際に目で見てみると、
それなりに面白い。
←こっち下位ビット こっち上位ビット→
として、1101 は
1101
101 +
-----
になり、最下位のビットは 0 になるからクリアされる。
あとは、（メルセンヌ素数ではなく）メルセンヌ数のときに、
体長に関する保存量があるかどうかと、
「伸びてゆくメルセンヌ数」があるかどうかで、
全長に関する限界は示せそうに思う。
たぶん、保存量が「任意のビットパターン」に対して
求められれば、「すべての自然数がメルセンヌ数に
帰着できる」みたいなことが示せそうな気がする。
あくまで「気がする」だけだが。
815:１３２人目の素数さん
18/04/28 16:55:40.82 d9jkS/fs.net
１つ予想を立ててみた。
自然数全体の集合を N とする。
まず木を定義する。
定義
自然数 a に対し、集合 T(a) を
T(a) = {b∈N | a と b はコラッツ操作によって同じ数に到達する}
と定める。
T(a) の形の集合を木と呼ぶ。
コラッツ予想が真であることは、自然数全体が１つの木をなすことと同値である。
で、次のように予想した。
予想
T を木とし、n, k を自然数とする。
このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。
コラッツ予想が正しければ、T は N に一致するので、明らかにこの予想は成り立つ。
逆にいえば、予想が成り立たないような T, n, k が存在する場合、コラッツ予想も偽であることになる。
816:１３２人目の素数さん
18/04/28 16:56:23.83 d9jkS/fs.net
基本的な操作を補題としてまとめておく。
補題
T を木とする。このとき以下が成り立つ。
(1) a∈T かつ a が偶数 ⇒ a/2∈T
(2) a∈T かつ a が奇数 ⇒ 3a+1∈T
(3) a∈T ⇒ 2a∈T
(4) a∈T かつ a が偶数かつ a≡1 (mod 3) ⇒ (a-1)/3 ∈ T
２つの自然数 a,b が同じ木に属することは、(1)～(4) の繰り返しによって
一方から他方に移ることができることと同値。
さて、例えば n=1,2 の場合は予想は明らか。
n=3, k=1 or 2 の場合も難しくはないが、証明を述べておく。
命題
T を木とし、k=1 or 2 とする。
このとき、ある a∈T が存在して a≡k (mod 3) となる。
証明
任意に b∈T をとる。
b が 3 の倍数でない場合、b, 2b のいずれかが mod 3 で k に等しくなる。
2b∈T なのでOK。
b が 3 の倍数の場合、b=2^i*c (c は奇数) となるように非負整数 i, 自然数 c をとれば、
c∈T, c は奇数かつ 3 の倍数となる。
さらに 3c+1∈T であり、3c+1≡1 (mod 3) となる。
よって、上の場合に帰着されてOK。□
まだいろいろと書けることはあるけど、反応を見ながらということで。
817:righ1113
18/04/28 17:56:49.19 UAXb8Z2X.net
考え方として、
いくつもの木を考えるのですか？
それとも1を含む木T1のみに注目するのですか？
818:786
18/04/28 18:15:59.36 d9jkS/fs.net
全ての木を考えます。
それが１つなのか複数なのかは分かりませんが。
819:righ1113
18/04/28 18:26:23.27 LOcVhBQa.net
なるほどありがとうございます。
820:１３２人目の素数さん
18/04/28 18:28:10.02 zCYrfxzC.net
お、新人か。
821:１３２人目の素数さん
18/04/28 18:42:45.61 zCYrfxzC.net
ぜひ新しい風を吹き入れてほしいね。
822:786
18/04/28 18:53:42.76 d9jkS/fs.net
これを書こうと思って忘れていた。
コラッツ予想は初期値が奇数の場合だけ調べればいい、というのは明らかだが
>>790の予想が正しければそれを一般化できる。
すなわち、ある n, k について予想が正しければ、
「コラッツ予想は a≡k (mod n) を満たす自然数 a が初期値の場合だけ調べればいい」
と言える。
>>795>>796
よろしくお願いします。
823:１３２人目の素数さん
18/04/28 19:00:55.51 zCYrfxzC.net
modに関しては2と3には何かあるかもしれないが例えば5はどうか？といわれるとちょと疑問
今の時点ではね
824:１３２人目の素数さん
18/04/28 20:44:50.70 aSLESMuD.net
グラフ理論に「木」があるから名前は変えた方がいいかもね
グラフ理論といえば、コラッツ操作による有向グラフとしてなんかできないかなー、
と昔考えたけど、グラフ理論で扱われるのは有限頂点のグラフだった……
825:１３２人目の素数さん
18/04/28 20:47:56.57 zCYrfxzC.net
いや、まさにグラフ理論の木のつもりで書いたんじゃないか？
826:１３２人目の素数さん
18/04/28 21:05:09.07 aSLESMuD.net
というか「木」は数学では同値類になるか。
自分が書くならこんな感じ。
関数 f:N→N を
f(x)=x/2 (x:偶数) f(x)=3x+1 (x:奇数)とする
x,y∈Nに対し, x～y⇔∃i,j∈N, f^i(x)=f^j(y)
は同値関係となる。
827:１３２人目の素数さん
18/04/28 21:09:57.55 aSLESMuD.net
イメージは1を根とする木かな。
わからなくもないけど
・頂点が無限
・1→4→2→1のループがある
なのでなおさら木とは呼びづらい。
828:786
18/04/28 21:23:20.77 d9jkS/fs.net
確かに「木」だと誤解を招いてしまうかもしれませんね。
「束」のように複数の意味で使われる例もありますが…
良い名称を思いついたら変えようと思います。
829:１３２人目の素数さん
18/04/29 00:40:21.09 daW9MuG1.net
うーん、やっぱり木が一番しっくりくる。
もうしばらく様子を見ます。
同値類を用いた定義も承知していますが、
一応高校数学の範囲で理解できるよう上のように定義しました。
あと、グラフ理論では無限個の頂点や辺を持つグラフも扱っていたと思います。
予想についての結果をひとつ追加。
命題
任意の木は 3 の倍数を含む。
証明
T を木とし、任意に b∈T をとる。
b が 3 の倍数の場合、示すことはない。
b が 3 の倍数でない場合、
b は mod 9 で 1,2,4,5,7,8 のいずれか。
ここで、Z/9Z において 2 は原始根であるので、
b*2^d≡1 (mod 9)
を満たす d∈N が存在する。
b*2^d∈T かつ b*2^d は偶数で b*2^d≡1 (mod 3) なので、
c=(b*2^d-1)/3
とおくと c∈T である。
さらに b*2^d-1≡0 (mod 9) より c=(b*2^d-1)/3≡0 (mod 3) なので、T は 3 の倍数を含む。 □
830:１３２人目の素数さん
18/04/29 01:27:39.57 Z6W4RKDj.net
ふーむ。
例えば同様の議論で他の倍数も通用したりするの？
831:786
18/04/29 18:35:28.76 daW9MuG1.net
>>805
n=3^e, e∈N の形のときは同様に議論できます。これから書きます。
それ以外の場合、Z/3nZ において 2 が原始根になりえないので、全く同じ議論でというわけにはいきません。
n=4,8,16,… の場合は議論するまでもなく成り立ちますが…
ちなみに、ある n に対して n の倍数が木に含まれるかという問題は>>790の予想において k=0 の場合ですが、
n が奇数のとき、これは k が他の値の場合よりも難しいと思います。
n=3 の場合もそうでしたが、n=5 あたりを考えてみても分かります。
これもそのうち書こうと思います。
n=3^e, e∈N の場合を考える。
補題
任意の 2 以上の整数 e に対して 4^(3^(e-2)) ≡ 1+3^(e-1) (mod 3^e)
証明
e=2 のときは (左辺)=(右辺)=4 よりOK。
ある e で成り立つとすると、
4^(3^(e-2)) = 1+3^(e-1)+3^e*m, m∈Z
と表せる。このとき、
4^(3^(e-1)) = (1+3^(e-1)+3^e*m))^3 ≡ 1+3^e (mod 3^(e+1))
より、e+1 でも成り立つ。□
（続く）
832:786
18/04/29 18:36:40.20 daW9MuG1.net
補題
e を 2 以上の整数とする。
このとき、Z/(3^e)Z において 2 は原始根である。
証明
2 の位数を d とおく。
2^d≡1 (mod 3^e) より 2^d≡1 (mod 3)
したがって、d は偶数である。
また、d は φ(3^e)=2*3^(e-1) の約数である。
ここで、前補題より
2^(2*3^(e-2)) = 4^(3^(e-2)) ≡ 1+3^(e-1) ≠ 1 (mod 3^e)
(≠は「≡でない」を表すとする)
なので、d=2*3^(e-1) となるしかない。
したがって、2 は原始根である。□
定理
T を木、e を 2 以上の整数、k を 任意の自然数とする。
このとき、ある a∈T が存在して a≡k (mod 3^e) が成り立つ。
証明
・ k が 3 の倍数でない場合
3 の倍数でない b∈T を任意に取る。
2 が Z/(3^e)Z の原始根であることから、
b*2^d≡k (mod 3^e)
を満たす d∈N が存在する。
a=b*2^d とすればよい。
・ k が 3 の倍数である場合
3 の倍数でない b∈T を任意に取る。
2 が Z/(3^(e+1))Z の原始根であることから、
b*2^d≡3k+1 (mod 3^(e+1))
を満たす d∈N が存在する。
このとき、a=(b*2^d-1)/3 とおくと、
a∈T かつ a≡k (mod 3^e) となる。□
833:１３２人目の素数さん
18/04/29 22:12:16.24 Z6W4RKDj.net
mod 5とか mod 7について何か出すのは難しいかもしれないけど
3^n-1についてとかなら何か出せるんだろうか？
834:786
18/04/30 11:15:04.08 RzdNNNxX.net
>>808
「何か出す」の意味がよく分かりませんが
mod 5, mod 7 の場合は任意の k について予想が成り立つことが分かっています。
3^n-1 の場合は特に考えたことはないんですが、何かアイデアがあれば教えてください。
やはり先に分かっていることについて一通り書いた方がいいですね。
以下、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=7, 13, 17, k は任意
また、次が分かっています。
・m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。
これにより、n が偶数の場合は n が奇数の場合に帰着されます。
835:786
18/04/30 11:45:54.34 RzdNNNxX.net
偶数から奇数への帰着について先に書いておきます。
定理
m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。
証明
T を木とし、n=2m とする。
k が奇数の場合に証明できれば、奇数に 2 をかけていくことで k が偶数の場合も証明できる。
k を奇数とする。
仮定より、ある b∈T が存在して
b≡(3k+1)/2 (mod 3m)
となる。このとき、
2b≡3k+1 (mod 6m)
であり、2b∈T, 2b は偶数かつ 2b≡1 (mod 3)。
よって a=(2b-1)/3 とおくと a∈T かつ a≡k (mod 2m) □
>>807 の結果と合わせれば、
n=2^d*3^e の形の場合、任意の k で予想が正しいことになります。
また、私見ですが、n が偶数の場合はこの定理によって奇数の場合に帰着させる以外の手はなさそうに思います。
他の方法がありそうならご一報ください。
そういうわけで、今後は n が奇数の場合のみ考えようと思います。
836:１３２人目の素数さん
18/04/30 22:46:03.02 OLMy/5mJ.net
>>1に聞いてみたいが>>790の実力はどれくらい期待できる？
837:righ1113
18/05/01 09:19:14.30 heRw5z2i.net
いや、自分よりすごい上だと思います。
838:１３２人目の素数さん
18/05/01 19:50:11.04 ifnyVUo1.net
ほほう、それは楽しみ
839:786
18/05/01 19:52:19.63 w7yajc4M.net
>>812
いえ、それほどでも
個別の n, k について考えるだけならそれほどハードルは高くないと思いますので、
一緒に考えてくれる方がいたら嬉しいなと思います。
さしあたって次の目標は n=15, 19 あたりです。
840:１３２人目の素数さん
18/05/01 21:00:47.74 b6ssvKjY.net
予想
T を木とし、n, k を自然数とする。
このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。
↑まだこれのイメージがわいてない段階だから一緒に考えるっつってもあんま期待すんなよｗ
841:１３２人目の素数さん
18/05/01 21:53:00.73 b6ssvKjY.net
まあ問題のとらえ方というか予想の立て方が、普通の人より高いところに目線があるんだろなって雰囲気は感じる。
842:１３２人目の素数さん
18/05/01 22:30:43.98 b6ssvKjY.net
予想がなかなかイメージ湧かないな～
プロローグでプログラムを組もうとしたときのような困難さを感じるorz.
843:１３２人目の素数さん
18/05/01 23:05:13.72 b6ssvKjY.net
とりあえず、プログラム組んで虱潰しで潰していけばn=15とかもなにがしかの結果が出るのだろうか？
そんな甘くない？
844:１３２人目の素数さん
18/05/01 23:08:54.94 b6ssvKjY.net
例えば>>1なら>>790の予想を理解して、しらみつぶしで探索するようなプログラムを、書けそう？書けなさそう？
845:１３２人目の素数さん
18/05/01 23:19:15.11 b6ssvKjY.net
プログラムでやろうと思ったら結局、原始根である必要があるんだろうか？
うーん。わからん。
846:786
18/05/01 23:36:27.65 EK2mztLp.net
なるほどそんな感じですか…
ちょっと考えてみます
847:１３２人目の素数さん
18/05/01 23:54:58.95 b6ssvKjY.net
>>790はプログラム組める人なんですか？
848:１３２人目の素数さん
18/05/02 00:04:01.57 ykYomvAh.net
x(2^n)-1→x(3^n)-1 (x,nは自然数)
がわかってるから、2か3が原始根ならどうとでもなる気が
849:786
18/05/02 00:46:18.38 uBxaRL/7.net
>>822
プログラムはド素人です。
上で言ったのは、「イメージがわかない」というのをどうにかできないかなーということです。
850:righ1113
18/05/02 11:48:19.30 em/0JAzr.net
>>819
いやー何ともいえないですねー
851:786
18/05/02 17:55:20.98 uBxaRL/7.net
この予想に至った経緯を図を交えて述べてみます。
そんな大層なものではないですが。
まず、木のイメージは次の図のような感じです。
URLﾘﾝｸ(i.imgur.com)
ここで、「3倍して1を足す」は斜めの線、「2で割る」は縦線で表しています。
縦の並びは
(a)全て3の倍数
(b)3n+1, 3n+2 の形の数が交互に現れる
の2通りに分類されます。
(a)の場合はこれ以上分岐しません。
(b)の場合は 3n+1 の形の偶数から分岐があります。
図のようなイメージです。
URLﾘﾝｸ(i.imgur.com)
そして、これは経験的に知っていたんですが、
3n+1 の形の偶数から分岐した先は3回に1回だけ3の倍数になります。
URLﾘﾝｸ(i.imgur.com)
（これをちゃんと証明したのが>>804です）
このことから、
「どんな数からでも上手くさかのぼれば3の倍数に到達する」
⇒「コラッツ予想は初期値が3の倍数の場合だけ調べれば十分」
ということを考えたことがありました。
852:786
18/05/02 17:55:49.20 uBxaRL/7.net
それとは別に
・初期値が奇数の場合だけ調べれば十分
・初期値が 4n+3 の形の場合だけ調べれば十分
とかはよく見る話だと思います。
それで、この間ふと「これって一般化できないかな」と思ったのです。
すなわち「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」は成り立つのかと。
で、これを証明するにはどうすればいいかを考えた結果、
>>790の予想に落ち着きました。
853:１３２人目の素数さん
18/05/02 19:26:48.28 1izSGXat.net
>>825
なに守りに入ってんだよw
854:１３２人目の素数さん
18/05/02 19:29:42.99 1izSGXat.net
>>790は何かトリップ付けといた方がいいかもね
855:１３２人目の素数さん
18/05/02 20:10:19.87 0C84qqBY.net
「コラッツ予想は初期値が3の倍数の場合だけ調べれば十分」
これはこのスレでも>>131で言及されているね
856:１３２人目の素数さん
18/05/02 20:28:11.26 0C84qqBY.net
「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」
こっちのほうがアイディアはわかりやすいな
857:１３２人目の素数さん
18/05/02 21:15:08.89 0C84qqBY.net
ん、「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」と>>790の予想が頭の中で微妙にすっきり繋がらないな
もうちょっと時間くれ
858:１３２人目の素数さん
18/05/02 21:34:00.98 0C84qqBY.net
あ～なんかわかったかも
859:１３２人目の素数さん
18/05/02 21:55:27.60 0C84qqBY.net
てことは例えば「コラッツの予想は5の倍数だけ調べれば十分」も証明済みってことか
へ～～
860:１３２人目の素数さん
18/05/02 22:26:15.60 0C84qqBY.net
個別のnやkに対してどういう戦略で証明を進めていくのか説明してくれたらもしかしたらプログラムでしらみつぶし探索できるかもしれないな。
やや楽観的すぎるかもしれないが。
多分、>>1が実装してくれるｗｗ
861:786
18/05/03 00:08:17.82 VqsJsG3V.net
>>823
確かに使えそうですが…いまいち使い方が思いつきません。
もし具体的なアイデアがあればお願いします。
>>829
ではお言葉に甘えて。
余談ですが、コラッツ予想の証明の方針として、
「1以外のどんな自然数もコラッツ操作によって自身より小さい数になる」
を示すというのが（多分）よく取られます。
例えば偶数や 4n+1 の形の奇数は自身より小さい数になることがすぐに分かるので、
「初期値が 4n+3 の形の場合に調べれば十分」
ということがわかります。
そして、この方針は>>790の予想とは全く別物だと私は思っています。
上の論法では任意の木に 4n+3 の形の数が含まれることは（多分）説明できていませんし、
逆に「任意の木に○○が含まれる」ということから「○○以外の数は自身より小さくなる」という話に繋げることもできないと思います。
このように、
「初期値が n で割って k 余る数の場合だけ調べれば十分」
を証明する方法は1つとは限りません。
>>790の予想はあくまでそのうちの一つの手段です。
たとえ>>790の予想の証明を諦めたとしても
「初期値が n で割って k 余る数の場合だけ調べれば十分」を諦めたことにはなりませんので、
そこらへん混同しないようお願いします。
次は n=5 の場合の証明を書こうと思います。
862:１３２人目の素数さん
18/05/03 10:56:15.25 IWgQe+L2s
>>827 の 謂うとおり、
> 初期値が奇数の場合だけ調べれば十分
のはほぼ自明だが、
・n mod 3 が 1 のケース
・n mod 3 が 2 のケース
は、分けて考えたほうがいいんジャマイカ。
「奇数ｎに対して『３ｎ＋１』」操作を施すと、
必ず偶数に落ちるのだから、
３ｎ＋１の操作は「（３ｎ＋１）／２」に置き換えても
一般性を失わない。
で、その操作を奇数に対して行なった場合、
偶数になった場合は
「６で割ったときに余りが２」に落ちる。
863:786
18/05/03 13:16:10.01 VqsJsG3V.net
・n=5, k=1,2,3,4 の場合
定理
T を木とし、k を 1,2,3,4 のいずれかとする。
このとき、ある a∈T が存在して a≡k (mod 5) となる。
証明
b∈T を任意にとる。
b が 5 の倍数でなければ、
Z/5Z において 2 が原始根であることから、
b*2^d≡k (mod 5)
となる d∈N が存在する。b*2^d∈T なのでOK。
b が 5 の倍数のときは、
奇数になるまで b を 2 で割って得られる奇数を b' とする。
b' も 5 の倍数で、b'∈T である。
さらに b' は奇数だから 3b'+1∈T
3b'+1≡1 (mod 5) なので、上の場合に帰着される。□
864:786
18/05/03 13:17:32.89 VqsJsG3V.net
・n=5, k=0 の場合
まずは証明を書きますが、ちょっと天下り的なのであとで補足を書きます。
定理
任意の木は 5 の倍数を含む。
証明
3 の倍数でない b∈T を任意に取る。
（>>791の命題によってこのような仮定が許される）
(1) b が 5 の倍数の場合
この場合は示すことはない。
(2) b≡1,2,4,8 (mod 15) の場合
Z/15Z において 1 に 2 をかけていくと
1→2→4→8→1→…
となって循環する。したがって、
b*2^d≡1 (mod 15)
を満たす d∈N が存在する。b*2^d は>>791の補題(4)の仮定を満たすので、
(
865:b*2^d-1)/3∈T であり、さらに (b*2^d-1)/3≡0 (mod 5) なので T が 5 の倍数を含むことが示された。 (3) それ以外の場合 0 から 14 のうち 3 の倍数, 5 の倍数, 1,2,4,8 を除くので、残りは b≡7,11,13,14 (mod 15) の場合である。 b は mod 45 では 7,11,13,14,22,26,28,29,37,41,43,44 のいずれか。ここで、7 に 2 をかけていくと 7→14→28→11→22→44→43→41→37→29→13→26→7→… となり、上記の全ての数を通って循環する。（群論の知識があれば直接計算しなくても分かります） したがって、 b*2^d≡7 (mod 45) を満たす d∈N が存在する。b*2^d は>>791の補題(4)の仮定を満たすので、 (b*2^d-1)/3∈T であり、さらに (b*2^d-1)/3≡2 (mod 15) なので、(2) の場合に帰着される。□
866:786
18/05/03 13:19:00.64 VqsJsG3V.net
・3 の倍数でない b をとったことについて
あとで>>791補題(4)（以下、単に(4)と書く）を使うためです。
5 の倍数を構成するには (2) か (4) を使う必要がありますが、
(2) を使って構成するのは難しそうでした。
・≡7 (mod 45) を選んだことについて
(4)によって直接 5 の倍数を作ることができないので、
一旦 mod 15 で 1,2,4,8 のいずれかとなるような数を作ることを目指しています。
そのために、7,11,…,44 のそれぞれから 1 を引いて 3 で割ってみて
1,2,4,8 のいずれかになるかどうかを確かめました。
その結果 (7-1)/3=2 が見つかったので、7 としました。
他にも (13-1)/3=4 なので ≡13 (mod 45) に変えても証明できます。
867:１３２人目の素数さん
18/05/03 13:21:26.72 a3IHhOrY.net
むむう。
この感じだとプログラム化はかなり難易度高いかなぁ
868:righ1113
18/05/03 16:02:07.46 Z16wUiiY.net
ふと思ったのですけど、プログラムとして
・T(1)を列挙
・a∈T(1)がa≡k mod nかを調べる
(kとnには具体的な数を入れる)
とかやっても意味ないですよね……
869:１３２人目の素数さん
18/05/03 17:20:39.15 Q+4f9U1i.net
modを3倍にしていくのが基本戦略なのかな？
870:１３２人目の素数さん
18/05/03 17:32:04.01 Edef9/wk.net
プログラム化は難しいと思うけど、
奇数kについて
R_1(k)={奇数m|ある整数r≧0について3m+1=k･2^r}
R_n+1(k)=∪_[m∈R_n(k)] R_1(m)
という操作でできる集合R_n(k)を考えると、
n→∞におけるR_n(1)の極限R(1)がすべての奇数の集合と一致するかどうか、という問題はコラッツ予想と同じにならないかな？
871:１３２人目の素数さん
18/05/03 17:40:34.30 Q+4f9U1i.net
証明が完成するまでmodに何回3をかけたかに注目したら何か出てくるかな？
872:786
18/05/03 17:56:31.46 VqsJsG3V.net
>>842
うーん、そうですね…
k が既に 1 に到達することが分かっている数の場合、
a=k と取れてしまうわけですから調べる意味がなくなります。
wikipediaによると、5*2^60 までは 1 に到達することが分かっているそうなので、
k を 5*2^60 より大きくしないといけないことになりますが…
>>843
今のところそうですね。
まあ、やってみたら自然とそうなったという感じです。
873:786
18/05/03 17:58:47.10 VqsJsG3V.net
>>845
あ、これはちょっと調べてみたいですね
874:１３２人目の素数さん
18/05/03 18:03:43.93 Q+4f9U1i.net
プログラム組めるとデータ量が圧倒的に違うからなんとかしたいなあ
875:１３２人目の素数さん
18/05/03 20:14:22.88 Q+4f9U1i.net
>>790がプログラム組めないのが痛いなあ
可能な限りシステマチックな手順に証明手順を落とし込めないですか？
876:786
18/05/04 00:22:45.95 he9tcl6d.net
n が素数の場合に限りましたが、なんとか手順をまとめてみました。
以下の操作が終了すれば、n=p の場合に任意の k で予想が成り立つことになるはずです。
プログラムに関しては素人なので、おかしいところ、実装が難しいところ等あるかもしれません。
例を併記して述べますが、あとで操作だけをまとめたものも書きます。
p を 5 以上の素数とする。
以下の例は、p=7 の場合である。
(1) Z/pZ において、2 を何回かかけることによって移りあう元を同じグループとして A1,A2,… とグループ分けする。
例
Z/7Z において
A1={0}
A2={1,2,4}
A3={3,5,6}
(2) Z/3pZ において、3 の倍数でも p の倍数でもない数について同様に B1,B2,… とグループ分けする。
例
Z/21Z において
B1={1,2,4,8,11,16}
B2={5,10,13,17,19,20}
(3) Z/pZ の各元 a に対し、a がどの Ai に属すか、3a+1 がどの Bj に属すかを見る。（どの Bj にも属さないこともある）
各 a に対して得られた組 (Ai,Bj) を記録していく。組が被った場合、改めて記録しなくてもよい。
例
a=0 に対しては 0∈A1,3*0+1=1∈B1 なので、組 (A1,B1) を得る。
全て調べると、(A1,B1),(A2,B1),(A2,B2),(A3,B1),(A3,B2) を得る。
877:786
18/05/04 00:24:05.38 he9tcl6d.net
(4) A1,A2,… のうち、全ての Bj との組が得られていないものがあれば、それをひとつ選び、A'とする。
以下の操作を全て終えた後、まだ選んでない A' の候補があれば A' を取り換えてまたここからやり直す。
A' の候補が残っていなければ操作を終了する。
例
得られていない組は (A1,B2) だけなので、A'=A1 とする。
(5) Z/9pZ において、条件
「mod 3p で見た時、組 (A',Bj) が得られていないような Bj に属する」
を満たす数全体を考え、この数たちを (1), (2) と同様にグループ分けし、C1,C2,… とする。
例
組 (A',Bj) が得られていないような Bj は B2 しかない。
mod 21 で B2 に属するような Z/63Z の元を列挙すると
{5,10,13,17,19,20,26,31,34,38,40,41,47,52,55,59,61,62}
となり、これをグループ分けすると
C1={5,10,17,20,34,40}
C2={13,19,26,38,41,52}
C3={31,47,55,59,61,62}
を得る。
(6) 組 (A',Bj) が得られているような Bj 全てと、C1,C2,… に対して (3) と同じことを行う。
例
組 (A',Bj) が得られているような Bj は B1 のみ。
B1 の元 a に対し、3a+1 が C1,C2,C3 に属するかを見ていく。
(B1,C1),(B1,C2) を得る。
878:786
18/05/04 00:25:04.52 he9tcl6d.net
(7) (4) の「A1,A2,…」を「組 (A',Bj) が得られているような Bj 全て」に、
Bj を Cj に、A' を B' に取り換えて同じことをする。
さらに (5),(6) の A,B,C をそれぞれ B,C,D に、p を 3p に取り換えて同じことをする。
例
組 (B1, C3) のみ得られていないので、B'=B1 とする。
組 (B',Cj) が得られていないような Cj は C3 しかない。
mod 63 で C3 に属するような Z/189Z の元を列挙すると
{31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188}
となり、これをグループ分けすると
D1={31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188}
という一つのみのグループを得る。
組 (B',Cj) が得られているような Cj は C1, C2 の二つ。
(3) と同様に調べると、組 (C1,D1),(C2,D1) を得る。
(8) (7) と同様に、さらに再帰的に繰り返す。
例
C' の候補がないので、(8)を終了する。
(7)に戻るが、B' の候補が残っていないので(7)を終了する。
(4)に戻るが、A' の候補が残っていないので全ての操作を終了する。
879:786
18/05/04 00:25:44.66 he9tcl6d.net
操作だけをまとめます
p を 5 以上の素数とする。
(1) Z/pZ において、2 を何回かかけることによって移りあう元を同じグループとして A1,A2,… とグループ分けする。
(2) Z/3pZ において、3 の倍数でも p の倍数でもない数について同様に B1,B2,… とグループ分けする。
(3) Z/pZ の各元 a に対し、a がどの Ai に属すか、3a+1 がどの Bj に属すかを見る。（どの Bj にも属さないこともある）
各 a に対して得られた組 (Ai,Bj) を記録していく。組が被った場合、改めて記録しなくてもよい。
(4) A1,A2,… のうち、全ての Bj との組が得られていないものがあれば、それをひとつ選び、A'とする。
以下の操作を全て終えた後、まだ選んでない A' の候補があれば A' を取り換えてまたここからやり直す。
A' の候補が残っていなければ操作を終了する。
(5) Z/9pZ において、条件
「mod 3p で見た時、組 (A',Bj) が得られていないような Bj に属する」
を満たす数全体を考え、この数たちを (1), (2) と同様にグループ分けし、C1,C2,… とする。
(6) 組 (A',Bj) が得られているような Bj 全てと、C1,C2,… に対して (3) と同じことを行う。
(7) (4) の「A1,A2,…」を「組 (A',Bj) が得られているような Bj 全て」に、
Bj を Cj に、A' を B' に取り換えて同じことをする。
さらに (5),(6) の A,B,C をそれぞれ B,C,D に、p を 3p に取り換えて同じことをする。
(8) (7) と同様に、さらに再帰的に繰り返す。
880:１３２人目の素数さん
18/05/04 01:15:28.20 PAX/KItK.net
おおお凄い
あんたプログラムの才能あるよ
まあ数学できる人はプログラムできても不思議じゃないけど
あとは>>1に任せたっwww
881:786
18/05/04 09:55:57.24 he9tcl6d.net
すいません、(7) 以降に無駄があったので次のように修正します。
(7) (6) で得られた組に全ての Ci が現れれば操作を終了する((4)に戻る)。
一度も現れなかった Ci があれば、
Z/27pZ において、条件
「mod 9p で見た時、(6)の組に一度も現れなかった Ci に属する」
を満たす数全体を考え、この数たちを (1), (2) と同様にグループ分けし、D1,D2,… とする。
(8) (6)の組に現れた Cj 全てと D1,D2,… に対して (3) と同じことを行う。
(9) (7)(8) の C,D をそれぞれ D,E に、p を 3p に、(6) を (8) に変えて同じこと行う。
以降、同様に繰り返す。
例に変化はありません。
(7) 以降は再帰ではなく単なる繰り返しになります。
882:786
18/05/04 10:25:18.46 he9tcl6d.net
いくつか補足をば。
このアルゴリズムの正当性を説明するには、次の補題が必要です。
補題
p を 5 以上の素数とする。
任意の木には、3 の倍数でも p の倍数でもない数が含まれる。
証明
T を木とし、3 の倍数でない数 b∈T を任意に取る。
b が p の倍数でなければ示すことはない。
b が p の倍数であるとき、
奇数になるまで b を 2 で割って得られる奇数を b' とおくと
3b'+1∈T であり、3b'+1 は 3 の倍数でも p の倍数でもない。□
上で書いた例を元に、
n=7 でどのように証明ができるのかをざっと説明します。
T を木とし、3 の倍数でも 7 の倍数でもない b∈T を任意に取る。
b は mod 21 で B1,B2 のいずれかに含まれる。
B1 であれば Z/7Z の全ての数を構成できる。
B2 であれば Z/7Z の 0 以外の全ての数を構成できる。
b∈B2 のときは、b は mod 63 で C1,C2,C3 のいずれかに含まれる。
C1,C2 であれば、B1 に含まれる数を構成できる。
b∈C3 のときは、b は mod 189 で D1 に含まれる。
よって C1 または C2 に含まれる数を構成できる。
大体こんな流れです。
あと、特定の k のみについて検証したければ
(1)の出力を k が含まれるグループのみにして下さい。
883:１３２人目の素数さん
18/05/04 10:47:29.12 PAX/KItK.net
>>1なら実装出来そう？
>>1が無理ならプログラム板にでもいって助っ人を探してくるけど
884:righ1113
18/05/04 10:54:18.15 BmXbqZ+r.net
>>857
やってみます。
885:１３２人目の素数さん
18/05/04 11:06:01.81 PAX/KItK.net
おっさすが
頑張れー
工数はどれくらいかな
1週間位？
886:righ1113
18/05/04 11:10:02.62 BmXbqZ+r.net
>>859
それぐらい頂けるとありがたいです。
887:１３２人目の素数さん
18/05/04 11:37:11.89 PAX/KItK.net
できればプログラムは計算過程を出力して
>>790が検証できるようにして欲しいな
888:１３２人目の素数さん
18/05/04 15:57:32.57 ksPNdhsW.net
ちなみにこのアルゴリズム素数限定らしいですが
合成数を入力したらどうなるんですかね
無限ループ？
889:786
18/05/04 17:00:03.61 he9tcl6d.net
>>1も>>857もありがとうございます。
>>862
素数に限ったのは>>856の補題があるから…と思っていたのですが、
よく考えたらこれ p が素数じゃなくても奇数なら成り立ちますね。
アルゴリズムの方も、素数に限らず奇数なら大丈夫な気がしてきました。
偶数を入れてしまうと、2倍写像が可逆にならないことにより
仮にプログラムがうまく動いたとしても証明になりません。
890:righ1113
18/05/04 17:42:36.90 Y7qh+Kgz.net
今日は(3)までできました。Haskellでやっています。
*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 [1,2,4,8,11,16]),([1,2,4],Just [1,2,4,8,11,16]),([1,2,4],Nothing),([3,5,6],Just [5,10,13,17,19,20]),([1,2,4],Just [5,10,13,17,19,20]),([3,5,6],Just [1,2,4,8,11,16])]
*CollatzMod>
891:１３２人目の素数さん
18/05/04 17:47:04.88 PAX/KItK.net
おお、乙です
感触はどうですか？
難易度たかい？
892:righ1113
18/05/04 17:51:58.20 xZSMHkYS.net
難易度は、チョイ難しい、ってとこですかね～
893:１３２人目の素数さん
18/05/04 18:09:38.72 PAX/KItK.net
n=19を手計算でやろうとしたら結構大変で中断w
根性なくてすまん
894:１３２人目の素数さん
18/05/04 18:21:33.28 PAX/KItK.net
しかし>>790もプログラム覚えたらいいのに
メキメキ上達すると思いますよ？
便利だし
895:786
18/05/04 23:46:39.07 he9tcl6d.net
>>864
おお、なんか感動した。
ありがとう、続きもなにとぞよろしく頼みます。
>>867
いや、難しさを共有できるだけでもありがたいです。
n=19 の場合は 2 が原始根になるので A は
A1={0}, A2={0以外}
の2つ、B も2つで得られない組は1つのみ、
それから C が3つ、という感じになるはずですがどうだったでしょうか。
2 が原始根かつ p≡1 (mod 3) のときは必ずこうなります。
ですが、この後それぞれの C を含む組が得られるか、という部分について一般的な理論がまだできていません。
プログラムを通じてその辺のヒントが得られればいいなと思っています。
>>868
いや、やろうとしたことはあるんですが、
プログラミングができる環境を得る方法がよく分からなくて断念した経験がありまして。
また試してみようかな
896:１３２人目の素数さん
18/05/05 02:25:34.92 vsDCVod3.net
PCが一台あれば、無償アプリのどれかを使ってなんとかなりそうに思う
897:１３２人目の素数さん
18/05/05 19:02:00.90 WEgbDwmq.net
>>1のプログラム作成の進捗具合はどうですかね？
そろそろ本格的に難しい部分に差し掛かって手が止まってもおかしくないですが
>>1をみくびりすぎかな？
898:righ1113
18/05/05 19:32:02.22 e9pI5FEa.net
>>871
今日は(5)まで作りました。
明日あたりやばそうですw
899:１３２人目の素数さん
18/05/05 20:43:19.54 WEgbDwmq.net
乙です
順調そうでなによりです
900:786
18/05/05 23:35:20.36 WoiID/ke.net
>>872
乙です。
重ね重ねありがとうございます。
>>809で挙げたものの証明が終わってないので
ちょっと進めときます。
・n が 5 以上の素数、Z/nZ において 2 が原始根、k≠0 の場合
まず、k=1,2,…,n-1 の場合は n=5 の場合と同様。
定理
T を木とする。p を 5 以上の素数とし、Z/pZ において 2 が原始根であると仮定する。
k を 1,2,…,n-1 のいずれかとする。このとき、ある a∈T が存在して a≡k (mod p) となる。
証明
n=5 の場合(>>838) と全く同様なので省略。□
これで>>809の残りは4つめと5つめですが、5つめはプログラムで確認できることなので
あとは4つめだけを書いていくことにします。
今日はちょっと時間がないので明日にでも。
901:１３２人目の素数さん
18/05/06 13:40:43.22 JU60Gd4S.net
新参です
コラッツ予想が解ける一歩手前でしたが一瞬寝落ちして表が消えた状態で上書き保存されて泣きそうです
証明はきわめてシンプルになります
902:１３２人目の素数さん
18/05/06 16:04:17.20 mu78La6l.net
>>875
表を早くつくりなおすんだ！
903:786
18/05/06 16:07:53.88 qQXj/e4z.net
昨日の続き。
群論を使います。
Z/nZ の乗法群を (Z/nZ)* と書きます。
・n が 5 以上の素数、Z/nZ において 2 が原始根、k=0 の場合
素数であることを強調するために、n=p とおく。
概ね>>853,>>855のアルゴリズムに沿って進める。
まず (Z/3pZ)* における 2 の位数を求める。
(Z/3pZ)* は (Z/3Z)*×(Z/pZ)* に同型である。
(Z/3Z)*, (Z/pZ)* それぞれにおいて 2 の位数は 2, p-1 であるから、
(Z/3pZ)* における 2 の位数はそれらの最小公倍数 p-1 である。
(Z/3pZ)* の位数は 2(p-1) であるから、2 で生成される部分群 B1 の指数は 2 である。
(Z/3pZ)* の B1 による剰余類を {B1, B2} とおく。
さて、T を木とし、3 の倍数でも p の倍数でもない b∈T を任意に取る。
b を mod 3p で見た時に b∈B1 であれば、ある d∈N で
b*2^d≡1 (mod 3p)
とできるので、あとは>>791補題(4)によって p の倍数を得る。
以下、b∈B2 とする。
射影 Z/9pZ→Z/3pZ による B2 の引き戻しを C とおく。
b を mod 9p で見ると b∈C である。
もし上と同様に>>791補題(4)を用いて B1 の元を得られれば、予想の証明が完了する。
式で表すと、
b*2^d≡1 (mod 3) かつ (b*2^d-1)/3≡2^e (mod 3p)
を満たす d,e∈N が存在すればよいことになる。
これはまとめて一つの式で
b*2^d-1≡3*2^e (mod 9p) …①
と表せる。
①を満たす d,e が存在するかどうかを考える
ここから p≡1 (mod 3) か p≡2 (mod 3) かで状況が変わる。
次ページ最新レス表示スレッドの検索類似スレ一覧話題のニュースおまかせリスト▼オプションを表示暇つぶし2ch
1867日前に更新/407 KB
担当:undef