内容
- 周期性からの予測
- イントロ
- 2n-1と6n-2の数列におけるnの規則性
- Collatz treeの一意性
- 枝構造の周期性規則性
1. 周期性からの予測
長い記事になるので、まず最初に、Collatz treeの枝構造の周期性の一例を紹介する。現在、Oliveira e Silvaの計算によると、5x2^60=5764607523034234880（19桁）まではコラッツの予想が成立している事が確認されている。
この範囲を超えて周期的に存在する枝構造の一例を紹介する。
以下の背景色の異なる部分は、pythonのプログラムである。（私はGoogle Colaboratory上で実施した。C, Fortran他ならinteger8では不足と思われる。integer16が必要。）
i0=0
a0=6*(4*(205891132094649*i0 + 171575943412207)+3)-2
a9=2*(3*(1152921504606846976*i0 + 960767920505705813)+2)-1
print(a0,a9)
for i in range(29):
b0=(a0-1)//3 # 6n-2 -> 2n-1
a1=4*b0 # 2n-1 -> 6n'-2
# print(i,a0,b0,a1)
a0=a1
print((a0-1)//3 -a9)
このプログラム内ではコラッツの操作を逆向きに実施しており、a0からa9へと値が変化する。
途中の操作は29回に固定しているが、iを変えてa0とa9を変化させても、その関係は成り立つ。
a0は奇数に2のべき乗をかけた合成数であり、a9は3の合成数である。
i0=0は、最初に現れる枝構造を意味する。
i0=0の時、a9=5x2^60+1である。
a0とa9に含まれる定数は、3^30=205891132094649, 4^30=1152921504606846976, である。
29以外に対応する枝構造の周期性ももちろん存在し、また、プログラム中の「a1=4*b0」を「a1=2*b0」に置き換えたもの、あるいはそれらの任意の順序・回数の組み合わせの周期的な枝構造が存在する。
今回参照した枝構造は、上記のプログラムで全て表現される。
他のa0とa9のペアでは、上記のプログラムは一致しない。
記事中の用語でこの例を紹介すると、「6n-2のn=4i+3から出発し、`3i+1:2n-1 => 4i+1:6n-2'を29回繰り返して、2n-1のn=3i+2にたどり着く枝構造」である。
この意味を以下で説明する。
2. イントロ
この記事で解析する2n-1は全奇数を意味し、6n-2=3(2n-1)+1は奇数に接続する偶数を意味する。
Colatz treeは、奇数に2をかけ続ける事によって伸びる枝と、この奇数と他の枝の接続によって構成される。
従って、2n-1と6n-2の数列を調べる事によって枝構造の規則性を理解できる、と期待される。
得られた結果は次の通り
- 2n-1と6n-2の数列における奇数とその合成数の配置は、nについての規則性を持つ。この規則性は数列全体に及ぶ。
- この規則性から以下の事が導かれる。
- 1以外の全ての奇数は他の奇数に接続しているため、1以外の単独の奇数からから始まるColatz treeは存在しない。
- 枝が閉じて環状になる事はなく、環状構造を基部に持つColatz treeは存在しない。
- 全ての6n-2のn=4i+3からは、2n-1のn=3i+2へと枝が伸びており、1対1関係が存在する。また全ての枝構造は周期性を持つ。
- １と２より、Colatz treeは単独で存在し、全ての自然数をカバーしている。従って、コラッツ予想は証明される。
これらの事を以下の3, 4, 5節で説明する。
3. 2n-1と6n-2の数列におけるnの規則性
次の表1は、n=60までの2n-1と6n-2の数列の一部である。（全体は末尾のPDFの末尾に表示）
表1の6n-2と2n-1の数列が枝構造を示している事は、初見では理解しにくいかもしれない。
例えば、コラッツの問題でよく示される例の一つは、6→3→10→5→16→8→4→2→1である。
これは、今回のCollatz tree の数列中では、1→4→16→5→10→3、と示される。
次の表2は、2n-1と6n-2の数列中の、奇数とその合成数の配置のnについての規則性を示している。（以下、ｉとｊは0以上の整数）
例えば、1とその合成数である4^jの配置は、表1の濃淡の紫色で示されている。（1→4→16→64→256）
これらの数字の位置nは、表2のn=3i+1の柱の項に、i=0を代入する事で得られる。
１の位置は2n-1でn=1、4の位置は6n-2でn=1、16の位置は6n-2でn=3、64の位置は6n-2でn=11、、、である。
ｉの値を変える事で、他の奇数とその合成数の位置nを得る。
これらの規則性を得た経緯を説明する。
6n-2におけるj=0の項の規則性は、次の表3から理解できる。
自然数を6n-4から6n+1に分類した表において、3の合成数(6n-3)を除いた奇数である6n-1と6n-1の合成数を調べる。
結果、6n-2の数列は、n=2i+2を2(6n-1)で埋められ、n=4i+1を4(6n+1)で埋められている。（緑と橙の濃い背景色は、6n-1, 6n+1とそれらの合成数。）
次に、6n-2のn=4i+3を見ると、2(6n-1)及び4(6n+1)と4のべき乗の積が出現している。（紫、緑、橙の薄い背景色）
ここから、4^j*2(6n-1)と4^j*4(6n+1)が、6n-2のn=4i+3を埋め続けていると推測される。
下の式1は、表2の項に持っていくため式変形である。
6n-1と6n+1の奇数は、2n-1においてn=3i+3, 3i+1に存在しており、2n-1=6i+5, 6i+1と書ける。
4^j*2(6n-1)と4^j*4(6n+1)について、6n-1と6n+1を6i+5, 6i+1に置き換え、さらに6n-2に変形すると、表2の4^{j+1}*i +(2*4^j+1)/3, 2i*4^j +(5*4^j+1)/3が得られる。
ここで、6n-2のn=4i+3がこれらの項で満たされている事を確認しよう。
このために、6n-2の1 <= n <= 2*4^j'の範囲が、j<=j'の項で満たされている事を帰納法で示す。
j'=0の時、1 <= n <= 2の範囲は、j=0におけるn=4i+1, 2i+2の項で満たされる。
j'=1の時、1 <= n <= 8の範囲は、iの異なるn=4i+1, 2i+2に加え、j=1のn=16i+3, 8i+7の項によって満たされる。
ここでのポイントは、2i+2の項が1 <= n <= 8に4回出現するのに対し、4i+1の項は2回だけである。残りの2個のnを埋めるために、n=16i+3, 8i+7の項が出現する。
さらにj'=2の時、1 <= n <= 32の範囲において、n=4i+1, 2i+2, 8i+7は、1 <= n <= 8を埋めたｎの4倍のｎを埋める。
しかし、n=16i+3は、1 <= n <= 32に2回しか出現できない。
残りの空いている2個のｎは、j=2のn=64i+11, 32i+27が埋める。
これを繰り返す事によって、6n-2のn=4i+3が全て満たされている事が分かる。
表2から分かる事は、2n-1のn=3i+1, 3i+3は、n=1を除いて、6n-2の各項と同じnをとらない、という事である。
n=1では、2n-1=1, 6n-2=4である。
従って、この組合せ以外では、n>1では、奇数は必ず別の奇数の合成数と接続している事が分かる。
2. Colatz treeの一意性
ここでは、1に起源を持つCollatz treeが単独である事を示すため、次の2点について述べる。一つは、1以外の単独の奇数に起源を持つ他のCollatz treeが存在しない事、もう一つは、1に起源を持つCollatz treeから独立した環状の基部を持つ他のCollatz treeが存在しない事。
前節の最後に述べたように、1以外の全ての奇数は、他の奇数の合成数と接している。
従って、1以外の単独の奇数に起源を持つCollatz treeは存在しない。
ここで、「1以外の全ての奇数は、他の奇数の合成数と接している」事はわかっているが、その接続の構造については分かっていない。
2n-1と6n-2の数列中に独立したtree構造があるかもしれない。
しかし、1以外の単独の奇数に起源を持つCollatz treeは否定されているので、次に、その基部に閉じた構造を持つtreeの可能性を考える。
Collatz treeの枝は、1本の枝から2本に分岐するが、2本の枝が合流する事は無い。
したがって、せいぜい枝が閉じている（元の奇数に戻る）閉環構造の可能性を考えれば十分である。（2次元的な閉面構造は作れない。）
もし閉環構造が存在すれば、それは、2n-1と6n-2の数列中でも閉じていなければならない。
この場合、n上におけるその底はn=6i+4に位置し、その天井はn=12i+9に位置しなければならない。
なぜならば、これらのnでは、その枝がn→0かn→無限大のどちらかの方向にのみ伸びているからである。
以下、枝が閉じない事を示すために、項を展開をする。
この時、2n-1のn=3i+1, 3i+3から6n-2のn=4i+1, 2i+2への枝の進展のみを考える。
6n-2のn=4i+1, 2i+2に存在する4(6n+1), 2(6n-1)から、n=4i+3に存在する4^j*4(6n+1), 4^j*2(6n-1)への枝の進展は考えない。
次の節の枝構造で述べるが、6n-2のn=4i+3から伸びる枝は、必ず2n-1のn=3i+2（つまり3の倍数）に行き着く。
これが冒頭のサンプルプログラムで紹介した、周期性を持つ枝構造である。
話を閉環構造に戻そう。
項の展開の一例として、n=6i+4=3(2i+1)+1の2n-1から伸びる枝を考える。
表2中の、2n-1のn=3i+1と6n-2のn=4i+1の関係から、この枝は6n-2のn=8i+5=4(2i+1)+1につながる。
ここで、i=3i', 3i'+1, 3i'+2とおくと、n=8i+5を以下のように置き換える事ができる。(i_1=i'とみなす)
この式の意味は、iの値によって、6n-2のn=8i+5は、2n-1の3i+1, 3i+2, 3i+3に均等に接続している、という事である。
ここで、n=3(8i'+6)+3に着目する。
ここから伸びる枝は、6n-2のn=2(8i'+6)+2にたどり着く。
ここで、i'=3i'', 3i''+1, 3i''+2とおくと、次の式変形を得る。(i_2=i'')
やはり同じように、6n-2のn=2(8i'+6)+2は、2n-1の3i+1, 3i+2, 3i+3に均等に接続している。
ここで、n=3(16i''+15)+1を考えた時、i=3i'+2=3(3i''+2)+2=9i''+8である。
一方、3(16i''+15)+1=6(8i''+7)+4である。
ここで、もし6(9i''+8)+4を得ていたら、6(9i''+8)+4 = 6i+4となるｉが存在し、閉環構造が存在すると言えた。
しかし 8i''+7 != 9i''+8 であり、閉環構造は存在しないと結論付けられる。
理由は、任意の i_l について、2^a i_l + b != 3^a' i_l +b'、だからである。
上記の式変形を繰り返した結果、3(2^a''i_l+b'')+1が得られる。
b''の値次第で変形できて、6(2^ai_l+b)+4が得られる。
一方、iを3i, 3i+1, 3i+2で展開していくと、i=3^a'i_l+b' が得られる。
結局、2^ai_l+b != 3^a'i_l+b' なので、閉環構造は存在しない。
よって、1に起源を持つCollatz tree以外の樹は存在せず、Collatz treeは全ての奇数をカバーし、従って全ての自然数をカバーすると結論付けられる。
5. 枝構造の周期性規則性
ここでは2n-1と6n-2の数列中のCollatz treeの枝を、2種類、第1種の枝と第2種の枝に分類する。第1種の枝は、6n-2のn=4i+1, 2i+2に位置する値から伸びる、n=4i+3上に位置する値で構成される。（例、（4）→16→64→256）
第2種の枝は、6n-2のn=4i+3から、2n-1のn=3i+2へと伸びる枝である。（例、16→5→10→3. 40→13→52→17→34→11→22→7→28→9. 64→21.）
これらの枝は互いを生み出し、Collatz treeを形成している。
周期性について示そう。
冒頭でのサンプルプログラムで示した周期性は、第2種の枝の周期性である。
サンプルプログラム中のa0はn=4i+3の6n-2の値であり、a9はn=3i+2の2n-1の値である。
前節で示したように、6n-2のn=4i+3に接続する2n-1のnを、i=3i', 3i'+1, 3i'+2で分類すると次のようになる。
ここでn=3(4i')+3の接続先である、6n-2のn=2(4i')+2について、同じように2n-1のnを分類すると次の式を得る。
n=3(8i'')+2に着目すると、i=3i'=9i''であり、従って6n-2のn=4(9i'')+3から伸びた枝は2n-1のn=3(8i'')+2につながる。
i''=0, 1, 2についてまとめたのが次の表である。
ここに示された数字の変化（表中のNumbers）は、6n-2のn=4i+3から出発して、16→5→10→3のように、nが一度減少して、つまり2n-1のn=3i+3から6n-2のn=2i+2への一度の接続の後で3の合成数につながる枝構造である。
この枝構造は、無限のi''に対応して、2n-1と6n-2の数列上に無限に出現する。
サンプルプログラムの枝構造は、6n-2のn=4i+3から出発して、2n-1のn=3i+1から6n-2のn=4i+1への接続を29回繰り返したあとで3の合成数につながる。
6n-2のnに接続する2n-1のnについて、i=3i', 3i'+1, 3i'+2の分類は無限に繰り返す事ができる。
従って、2n-1のn=3i+1から6n-2のn=4i+1への接続と、2n-1のn=3i+3から6n-2のn=2i+2への接続の組み合わせの全ては、2n-1と6n-2の数列中に周期的かつ無限に存在すると結論付けられる。
後は、第1種の枝が第2種の枝とどう接続しているか規則性を理解できれば良い。
簡単な規則性は見出すことができたが、どうすればあるいはどこまでの規則性を見い出せばフラクタル構造の条件を満たしているのか、経験のない私には分からない。
この第1種と第2種の枝の接続の簡単な規則性については冒頭のPDFで。
0 件のコメント:
コメントを投稿