コラッツ予想派生問題コレクション(1)

こんにちは、チオールです。

少し前、とある数学の未解決問題に関するニュースがTwitterで話題になりました。

そう、

コラッツ予想です。

ja.wikipedia.org

2021年7月7日に株式会社音圧爆上げくんが1億2千万円の懸賞金の支払いを宣言したことにより一気に注目を浴びました。

えっ？

「この始まり方見覚えあるぞ」って？

はい、約1年前にもほとんど同じ文で始まるコラッツ予想の記事を投稿しています。

hassium277.hatenablog.com

前回の記事では、コラッツ予想の真偽そっちのけでコラッツ予想やその派生問題がいかに暇つぶしに適しているかを語りました。

しかし諸々の都合で削らざるを得なかった話が沢山あるので、この記事ではそういった話題を拾っていこうと思います。

初期値の範囲を変えてみる
- ガウス整数への拡張
式を変えてみる
次回

初期値の範囲を変えてみる

Wikipediaのコラッツ予想のページでは、派生問題についても色々と触れられています。

※☟Wikipediaの記事
ja.wikipedia.org

その中で、初期値の範囲の拡張に関する話題があります。

具体的には、以下の3点が取り上げられています。

整数全体への拡張

奇数分母の有理数への拡張

複素数への拡張

整数全体への拡張では1に辿り着かない新たなループが発生し、奇数分母の有理数への拡張では分母の値ごとに全く異なる挙動を見せるようになります。

複素数への拡張では、まず三角関数を使ってコラッツ数列を場合分け無しで定義し、そしてその式に複素数を代入して拡張します。

有限の値に収束するような初期値を複素平面上にプロットするとフラクタル図形になることが知られており、その図形はコラッツフラクタルと呼ばれます。

実軸が正の領域では、マンデルブロ集合に似た形が串刺しにされています。

ちなみに以前のブログ記事での定義ではコラッツフラクタルはジュリア集合に分類されるので、何故マンデルブロ集合に似た形になるのかは完全に謎です。

※☟以前のブログ記事
hassium277.hatenablog.com

一方、実軸が負の領域ではトクホのマークのような形が見られます。

ところで、実は奇数分母の有理数への拡張と複素数への拡張は、コラッツ予想の拡張としては全くの別物です。

例として、 $\frac{2}{3}$ に対してどのように計算されるかを確認します。

まず有理数版では、分母が偶数なので2で割って $\frac{1}{3}$ になります。

しかし複素数版では、 $\frac{1}{2}z\text{cos}^2\left(\frac{\pi}{2}z\right)+(3z+1)\text{sin}^2\left(\frac{\pi}{2}z\right)$ に $z=\frac{2}{3}$ を代入すると $\frac{7}{3}$ になり、全く違う値になることがわかります。

さて、ここまではWikipediaの記事をなぞっただけですが、ここからはオリジナルの要素を紹介していきます。

ガウス整数への拡張

ガウス整数は、整数 $a,b$ と虚数単位 $i$ で $a+bi$ と表せる複素数のことです。

これを使って、以下のような数列を考えました。

$a_{n+1}=\begin{cases} \frac{1}{2}a_n&\text{if}　a_n\equiv0　&\pmod2\\ 3a_n+1&\text{if}　a_n\equiv1　&\pmod2\\ (3+2i)a_n+i&\text{if}　a_n\equiv i　&\pmod2\\ \frac{1}{1+i}a_n+1&\text{if}　a_n\equiv1+i　&\pmod2 \end{cases}$

※自然数では $N$ で割った余りは $N$ 個でしたが、ガウス整数では $|N|^2=a^2+b^2$ 個( $N=2$ なら4個)になります。

例として $a_0=8+i$ として計算すると以下のようになります。

8+i→22+20i→11+10i→34+30i→17+15i→17-i→9-9i→1-9i→-3-5i→-3-i→-1+i→1+i→2→1

上記の例では自然数の時と同じく1になりましたが、それ以外にも以下のようなループが見つかっています。

0→0

-1→-2→-1

-5→14→-7→-20→-10→-5

-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122→-61→-182→-91→-272→-136→-68→-34→-17

1-i→1-i

212-207i→1050-196i→525-98i→1576-294i→788-147i→2658+1136i→1329+568i→3988+1704i→1994+852i→997+426i→2992+1278i→1496+639i→3210+4910i→1605+2455i→2031+425i→1229-803i→214-1016i→107-508i→322-1524i→161-762i→484-2286i→242-1143i→3012-2944i→1506-1472i→753-736i→2260-2208i→1130-1104i→565-552i→1696-1656i→848-828i→424-414→212-207i

90-169i→608-326i→304-163i→1238+120i→619+60i→1858+180i→929+90i→2788+270i→1394+135i→3912+3194i→1956+1597i→2674+8704i→1337+4352i→4012+13056i→2006+6528i→1003+3264i→3010+9792i→1505+4896i→4516+14688i→2258+7344i→1129+3672i→3388+11016i→1694+5508i→847+2754i→2542+8262i→1271+4131i→2702+1430i→1351+715i→1034-318i→517-159i→180-338i→90-169i

107-196i→322-588i→161-294i→484-882i→242-441i→1608-838i→804-419i→3250+352i→1625+176i→4876+528i→2438+264i→1219+132i→3658+396i→1829+198i→5488+594i→2744+297i→7638+6380i→3819+3190i→11458+9570i→5729+4785i→5258-472i→2629-236i→7888-708i→3944-354i→1972-177i→6270+3414i→3135+1707i→2422-714i→1211-357i→428-784i→214-392i→107-196i

225-266i→676-798i→338-399i→1812-520i→906-260i→453-130i→1360-390i→680-195i→2430+776i→1215+388i→3646+1164i→1823+582i→5470+1746i→2735+873i→1805-931i→438-1368i→219-684i→658-2052i→329-1026i→988-3078i→494-1539i→4560-3628i→2280-1814i→1140-907i→5234-440i→2617-220i→7852-660i→3926-330i→1963-165i→900-1064i→450-532i→225-266i

上の4つは整数の時にもあったループですが、その下の5つがガウス整数への拡張で新たに出現したループです。

また、実部と虚部がともに±1000の範囲でどのループに入るのか統計を取ってみたところ、以下のようになりました。

※"over"は途中の値が大きすぎてループ判定ができなかったケース

まず、1番到達頻度が高かったのは1ではなく1-iでした。

また、整数範囲では0に到達するのは $a_0=0$ の1例のみでしたが、ガウス整数へ拡張したことで他の値からも到達可能になったことも特徴的です。

さらに、どの初期値がどのループに入るのかを複素平面上で図示してみたところ、以下のようになりました。

ループと色の対応関係は以下の通りです。

1-i,1,-1,0,-5,-17,212-207i,90-169i,107-196i,225-266i,over

0を中心として放射状の濃淡がうっすらと見えますが、それ以外に規則性はなさそうです。

なお、拡張するにあったって追加した2本の式は、発散しにくいように選んだだけで特に意味はありません。

元々の式も含めた4本の式を変えることで様々な派生問題を作ることができるのは言うまでもないことですが、組み合わせが膨大過ぎるので今回は触れないことにします。

式を変えてみる

式が4本あると複雑すぎて手出ししづらいですが、元のコラッツ予想と同じ2本だと総当たり的アプローチを試してみようという気になります。

というわけで、いくつかのルール群に対して力業での調査を強行してみました。

n/2,3n+kルール

以前の記事では、以下のルール群について調べました。

$a_{n+1}=\begin{cases}\frac{a_n}{2}&\text{if}　a_n\equiv0　\pmod2\\3a_n+k&\text{if}　a_n\equiv1　\pmod2\end{cases}$
※ $k$ は奇数

今回の記事では、このルールをn/2,3n+kルールと呼ぶことにします。

そして、前回の記事では分析の結果から以下の疑問が生じていました。

疑問4：n/2,3n+3kルールでのループってn/2,3n+kルールのときのやつを3倍したやつだけなの？

※わかりやすさのため少し表現を変えてあります。

例えばk=7のときは以下のようなループが存在しますが、

7→28→14→7

11→40→20→10→5→22→11

k=21とすると以下のようなループが見つかります。

21→84→42→21

33→120→60→30→15→66→33

k=21のループ内の数値は全てk=7の時の3倍になっており、k=21ではこのようなループしか存在しないのか、他の値でも同じ法則性があるのか、というのが疑問4の内容です。

以前のブログを投稿した時点ではこの疑問は未解決のものとして扱っていましたが、最近になってこの疑問が非常に簡単に解決可能であることに気付きました。

まず、n/2,3n+kルールによる数列 $a_n$ と区別するために、n/2,3n+3kルールによる数列を $b_n$ と表記します。

例えばk=7、つまり

$a_{n+1}=\begin{cases}\frac{a_n}{2}&\text{if}　a_n\equiv0　\pmod2\\3a_n+7&\text{if}　a_n\equiv1　\pmod2\end{cases}$

とするとき、 $b_n$ は

$b_{n+1}=\begin{cases}\frac{b_n}{2}&\text{if}　b_n\equiv0　\pmod2\\3b_n+21&\text{if}　b_n\equiv1　\pmod2\end{cases}$

になります。

さて、疑問4の解決には、以下の性質が役立ちます。

性質1：いかなる初期値 $b_0$ に対しても、 $b_n$ が3の倍数になるような計算回数 $n$ が存在する。

性質2： $b_n=3a_m$ (初期値は同じでなくてもよい)が成り立つなら、 $b_{n+1}=3a_{m+1}$ も成り立つ。

まず性質1から説明します。

$b_j$ が奇数の場合、 $b_{j+1}=3b_j+3k$ になるので $b_{j+1}$ は3の倍数になります。

偶数の場合は、2で割られ続けていつか奇数になるので、その次で必ず3の倍数になることがわかります。

よって、どんな初期値であっても必ず3の倍数になることがわかります。

次は性質2ですが、これも性質1と同じように奇数と偶数で場合分けすることで容易に示せます。

性質2より、 $b_n$ は一度3の倍数になると2/n,3n+kルールと全く同じ運命をたどり、2/n,3n+kルールがループに入ったら $b_n$ もその3倍の値からなるループを形成します。

そして性質1より全ての値は3の倍数に到達するので、n/2,3n+3kルールはn/2,3n+kルールの3倍の値からなるループしか持たないことがわかります。

定理1
n/2,3n+3kルールは、n/2,3n+kルールのループの値を3倍にしたループしか持たない。

※上記の説明はちゃんとした証明ではありませんが、細部を補ったり表現を整えればちゃんとした証明にできると思います。この記事は全体的にこんな感じのノリで説明します。

もし私の説明が下手だったら難しそうに見えるかもしれませんが、仕組みとしては非常に単純です。

恥ずかしながら、私は前回の記事を書いてからこれに気付くのに約1年近くかかりました。

ちなみに性質のダブりといえば、実は「n/2,3n+k数列」の挙動は「奇数分母の有理数に拡張されたn/2,3n+1数列」と同じです。

例えばk=5の時の以下の数列は、

19→62→31→98→49→152→76→38→19

奇数分母コラッツ数列では以下の列に対応します。

$\frac{19}{5}$ → $\frac{62}{5}$ → $\frac{31}{5}$ → $\frac{98}{5}$ → $\frac{49}{5}$ → $\frac{152}{5}$ → $\frac{76}{5}$ → $\frac{38}{5}$ → $\frac{19}{5}$

このことを「n/2,3n+k数列は奇数分母コラッツ数列と同じなのでn/2,3n+k数列について調べる必要はない」と解釈するか「奇数分母コラッツ数列はn/2,3n+k数列と同じなので奇数分母コラッツ数列について調べる必要はない」と解釈するかは個人の自由ですが、私はn/2,3n+k数列の方を先に調べ始めて思い入れがあるので後者の立場をとっています。

話を戻します。前回は初期値として自然数のみを扱っていましたが、整数全体を考えるとどうなるのかが気になったので試してみました。

結果として、各kに対して以下のようなループパターンが見つかりました。

※ここからしばらく数字の羅列が続きますが、興味が無ければ読み飛ばしてもいいし読むとしても「このループは長いなぁ」「このルールはループの個数が多いなぁ」程度の認識で十分です。

k=1
- 1→4→2→1
- 0→0
- -1→-2→-1
- -5→-14→-7→-20→-10→-5
- -17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122→-61→-182→-91→-272→-136→-68→-34→-17

k=3
- 3→12→6→3
- 0→0
- -3→-6→-3
- -15→-42→-21→-60→-30→-15
- -51→-150→-75→-222→-111→-330→-165→-492→-246→-123→-366→-183→-546→-273→-816→-408→-204→-102→-51

k=5
- 5→20→10→5
- 1→8→4→2→1
- 19→62→31→98→49→152→76→38→19
- 23→74→37→116→58→29→92→46→23
- 187→566→283→854→427→1286→643→1934→967→2906→1453→4364→2182→1091→3278→1639→4922→2461→7388→3694→1847→5546→2773→8324→4162→2081→6248→3124→1562→781→2348→1174→587→1766→883→2654→1327→3986→1993→5984→2992→1496→748→374→187
- 347→1046→523→1574→787→2366→1183→3554→1777→5336→2668→1334→667→2006→1003→3014→1507→4526→2263→6794→3397→10196→5098→2549→7652→3826→1913→5744→2872→1436→718→359→1082→541→1628→814→407→1226→613→1844→922→461→1388→694→347
- 0→0
- -5→-10→-5
- -25→-70→-35→-100→-50→-25
- -85→-250→-125→-370→-185→-550→-275→-820→-410→-205→-610→-305→-910→-455→-1360→-680→-340→-170→-85

k=7
- 7→28→14→7
- 5→22→11→40→20→10→5
- 0→0
- -35→-98→-49→-140→-70→-35
- -119→-350→-175→-518→-259→-770→-385→-1148→-574→-287→-854→-427→-1274→-637→-1904→-952→-476→-238→-119
- -7→-14→-7

k=9
- 9→36→18→9
- 0→0
- -9→-18→-9
- -45→-126→-63→-180→-90→-45
- -153→-450→-225→-666→-333→-990→-495→-1476→-738→-369→-1098→-549→-1638→-819→-2448→-1224→-612→-306→-153

k=11
- 11→44→22→11
- 1→14→7→32→16→8→4→2→1
- 13→50→25→86→43→140→70→35→116→58→29→98→49→158→79→248→124→62→31→104→52→26→13
- 0→0
- -11→-22→-11
- -55→-154→-77→-220→-110→-55
- -19→-46→-23→-58→-29→-76→-38→-19
- -187→-550→-275→-814→-407→-1210→-605→-1804→-902→-451→-1342→-671→-2002→-1001→-2992→-1496→-748→-374→-187

k=13
- 13→52→26→13
- 1→16→8→4→2→1
- 211→646→323→982→491→1486→743→2242→1121→3376→1688→844→422→211
- 227→694→347→1054→527→1594→797→2404→1202→601→1816→908→454→227
- 251→766→383→1162→581→1756→878→439→1330→665→2008→1004→502→251
- 259→790→395→1198→599→1810→905→2728→1364→682→341→1036→518→259
- 283→862→431→1306→653→1972→986→493→1492→746→373→1132→566→283
- 319→970→485→1468→734→367→1114→557→1684→842→421→1276→638→319
- 331→1006→503→1522→761→2296→1148→574→287→874→437→1324→662→331
- 131→406→203→622→311→946→473→1432→716→358→179→550→275→838→419→1270→635→1918→959→2890→1445→4348→2174→1087→3274→1637→4924→2462→1231→3706→1853→5572→2786→1393→4192→2096→1048→524→262→131
- 0→0
- -13→-26→-13
- -65→-182→-91→-260→-130→-65
- -221→-650→-325→-962→-481→-1430→-715→-2132→-1066→-533→-1586→-793→-2366→-1183→-3536→-1768→-884→-442→-221

k=15
- -255→-750→-375→-1110→-555→-1650→-825→-2460→-1230→-615→-1830→-915→-2730→-1365→-4080→-2040→-1020→-510→-255
- 3→24→12→6→3
- -75→-210→-105→-300→-150→-75
- -15→-30→-15
- 0→0
- 57→186→93→294→147→456→228→114→57
- 15→60→30→15
- 69→222→111→348→174→87→276→138→69
- 561→1698→849→2562→1281→3858→1929→5802→2901→8718→4359→13092→6546→3273→9834→4917→14766→7383→22164→11082→5541→16638→8319→24972→12486→6243→18744→9372→4686→2343→7044→3522→1761→5298→2649→7962→3981→11958→5979→17952→8976→4488→2244→1122→561
- 1041→3138→1569→4722→2361→7098→3549→10662→5331→16008→8004→4002→2001→6018→3009→9042→4521→13578→6789→20382→10191→30588→15294→7647→22956→11478→5739→17232→8616→4308→2154→1077→3246→1623→4884→2442→1221→3678→1839→5532→2766→1383→4164→2082→1041

k=17
- 17→68→34→17
- 1→20→10→5→32→16→8→4→2→1
- 23→86→43→146→73→236→118→59→194→97→308→154→77→248→124→62→31→110→55→182→91→290→145→452→226→113→356→178→89→284→142→71→230→115→362→181→560→280→140→70→35→122→61→200→100→50→25→92→46→23
- 0→0
- -17→-34→-17
- -85→-238→-119→-340→-170→-85
- -65→-178→-89→-250→-125→-358→-179→-520→-260→-130→-65
- -73→-202→-101→-286→-143→-412→-206→-103→-292→-146→-73
- -289→-850→-425→-1258→-629→-1870→-935→-2788→-1394→-697→-2074→-1037→-3094→-1547→-4624→-2312→-1156→-578→-289

k=19
- 19→76→38→19
- 5→34→17→70→35→124→62→31→112→56→28→14→7→40→20→10→5
- 0→0
- -19→-38→-19
- -95→-266→-133→-380→-190→-95
- -323→-950→-475→-1406→-703→-2090→-1045→-3116→-1558→-779→-2318→-1159→-3458→-1729→-5168→-2584→-1292→-646→-323
- -115→-326→-163→-470→-235→-686→-343→-1010→-505→-1496→-748→-374→-187→-542→-271→-794→-397→-1172→-586→-293→-860→-430→-215→-626→-313→-920→-460→-230→-115

k=21
- 21→84→42→21
- 15→66→33→120→60→30→15
- 0→0
- -21→-42→-21
- -105→-294→-147→-420→-210→-105
- -357→-1050→-525→-1554→-777→-2310→-1155→-3444→-1722→-861→-2562→-1281→-3822→-1911→-5712→-2856→-1428→-714→-357

k=23

- 23→92→46→23
- 5→38→19→80→40→20→10→5
- 7→44→22→11→56→28→14→7
- 41→146→73→242→121→386→193→602→301→926→463→1412→706→353→1082→541→1646→823→2492→1246→623→1892→946→473→1442→721→2186→1093→3302→1651→4976→2488→1244→622→311→956→478→239→740→370→185→578→289→890→445→1358→679→2060→1030→515→1568→784→392→196→98→49→170→85→278→139→440→220→110→55→188→9447→164→82→41
- 0→0
- -23→-46→-23
- -115→-322→-161→-460→-230→-115
- -391→-1150→-575→-1702→-851→-2530→-1265→-3772→-1886→-943→-2806→-1403→-4186→-2093→-6256→-3128→-1564→-782→-391
- -2263→-6766→-3383→-10126→-5063→-15166→-7583→-22726→-11363→-34066→-17033→-51076→-25538→-12769→-38284→-19142→-9571→-28690→-14345→-43012→-21506→-10753→-32236→-16118→-8059→-24154→-12077→-36208→-18104→-9052→-4526→-2263
- -2359→-7054→-3527→-10558→-5279→-15814→-7907→-23698→-11849→-35524→-17762→-8881→-26620→-13310→-6655→-19942→-9971→-29890→-14945→-44812→-22406→-11203→-33586→-16793→-50356→-25178→-12589→-37744→-18872→-9436→-4718→-2359
- -2743→-8206→-4103→-12286→-6143→-18406→-9203→-27586→-13793→-41356→-20678→-10339→-30994→-15497→-46468→-23234→-11617→-34828→-17414→-8707→-26098→-13049→-39124→-19562→-9781→-29320→-14660→-7330→-3665→-10972→-5486→-2743
- -2963→-8866→-4433→-13276→-6638→-3319→-9934→-4967→-14878→-7439→-22294→-11147→-33418→-16709→-50104→-25052→-12526→-6263→-18766→-9383→-28126→-14063→-42166→-21083→-63226→-31613→-94816→-47408→-23704→-11852→-5926→-2963
- -3091→-9250→-4625→-13852→-6926→-3463→-10366→-5183→-15526→-7763→-23266→-11633→-34876→-17438→-8719→-26134→-13067→-39178→-19589→-58744→-29372→-14686→-7343→-22006→-11003→-32986→-16493→-49456→-24728→-12364→-6182→-3091
- -3415→-10222→-5111→-15310→-7655→-22942→-11471→-34390→-17195→-51562→-25781→-77320→-38660→-19330→-9665→-28972→-14486→-7243→-21706→-10853→-32536→-16268→-8134→-4067→-12178→-6089→-18244→-9122→-4561→-13660→-6830→-3415
- -3743→-11206→-5603→-16786→-8393→-25156→-12578→-6289→-18844→-9422→-4711→-14110→-7055→-21142→-10571→-31690→-15845→-47512→-23756→-11878→-5939→-17794→-8897→-26668→-13334→-6667→-19978→-9989→-29944→-14972→-7486→-3743
- -4819→-14434→-7217→-21628→-10814→-5407→-16198→-8099→-24274→-12137→-36388→-18194→-9097→-27268→-13634→-6817→-20428→-10214→-5107→-15298→-7649→-22924→-11462→-5731→-17170→-8585→-25732→-12866→-6433→-19276→-9638→-4819

k=25
- 25→100→50→25
- 5→40→20→10→5
- 95→310→155→490→245→760→380→190→95
- 115→370→185→580→290→145→460→230→115
- 17→76→38→19→82→41→148→74→37→136→68→34→17
- 7→46→23→94→47→166→83→274→137→436→218→109→352→176→88→44→22→11→58→29→112→56→28→14→7
- 935→2830→1415→4270→2135→6430→3215→9670→4835→14530→7265→21820→10910→5455→16390→8195→24610→12305→36940→18470→9235→27730→13865→41620→20810→10405→31240→15620→7810→3905→11740→5870→2935→8830→4415→13270→6635→19930→9965→29920→14960→7480→3740→1870→935
- 1735→5230→2615→7870→3935→11830→5915→17770→8885→26680→13340→6670→3335→10030→5015→15070→7535→22630→11315→33970→16985→50980→25490→12745→38260→19130→9565→28720→14360→7180→3590→1795→5410→2705→8140→4070→2035→6130→3065→9220→4610→2305→6940→3470→1735
- 0→0
- -25→-50→-25
- -125→-350→-175→-500→-250→-125
- -425→-1250→-625→-1850→-925→-2750→-1375→-4100→-2050→-1025→-3050→-1525→-4550→-2275→-6800→-3400→-1700→-850→-425
- -113→-314→-157→-446→-223→-644→-322→-161→-458→-229→-662→-331→-968→-484→-242→-121→-338→-169→-482→-241→-698→-349→-1022→-511→-1508→-754→-377→-1106→-553→-1634→-817→-2426→-1213→-3614→-1807→-5396→-2698→-1349→-4022→-2011→-6008→-3004→-1502→-751→-2228→-1114→-557→-1646→-823→-2444→-1222→-611→-1808→-904→-452→-226→-113

k=27
- 27→108→54→27
- 0→0
- -27→-54→-27
- -135→-378→-189→-540→-270→-135
- -459→-1350→-675→-1998→-999→-2970→-1485→-4428→-2214→-1107→-3294→-1647→-4914→-2457→-7344→-3672→-1836→-918→-459

k=29
- 29→116→58→29
- 1→32→16→8→4→2→1
- 11→62→31→122→61→212→106→53→188→94→47→170→85→284→142→71→242→121→392→196→98→49→176→88→44→22→11
- 3811→11462→5731→17222→8611→25862→12931→38822→19411→58262→29131→87422→43711→131162→65581→19677298386→49193→147608→73804→36902→18451→55382→27691→83102→41551→124682→62341→187052→93526→46763→140318→70159→210506→105253→315788→157894→78947→236870→118435→355334→177667→533030→266515→799574→399787→1199390→599695→1799114→899557→2698700→1349350→674675→2024054→1012027→3036110→1518055→4554194→2277097→6831320→3415660→1707830→853915→2561774→1280887→3842690→1921345→5764064→2882032→1441016→720508→360254→180127→540410→270205→810644→405322→202661→608012→304006→152003→456038→228019→684086→342043→1026158→513079→1539266→769633→2308928→1154464→577232→288616→144308→72154→36077→108260→54130→27065→81224→40612→20306→10153→30488→15244→7622→3811
- 0→0
- -29→-58→-29
- -145→-406→-203→-580→-290→-145
- -493→-1450→-725→-2146→-1073→-3190→-1595→-4756→-2378→-1189→-3538→-1769→-5278→-2639→-7888→-3944→-1972→-986→-493
- -109→-298→-149→-418→-209→-598→-299→-868→-434→-217→-622→-311→-904→-452→-226→-113→-310→-155→-436→-218→-109

前回の記事では1～999までしか調べませんでしたが、今回は-5000～5000までに広げたので、負の初期値から生じるものだけでなく前回見つけられなかった正のループ(k=29での3811から始まる106周期のものなど)もいくつか見つかりました。

さて、まずわかることとして、「2/n,3n+3kルールが2/n,3n+kルールの3倍の値からなるループしか持たない」という定理1の内容は整数全体で考えても成り立つというのがあります。

例えばk=1のときには以下のようなループがありますが、

0→0
-1→-2→-1
-5→14→-7→-20→-10→-5
-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122→-61→-182→-91→-272→-136→-68→-34→-17

k=3の時のループは全てその3倍の値になっています。

0→0
-3→-6→-3
-15→-42→-21→-60→-30→-15
-51→-150→-75→-222→-111→-330→-165→-492→-246→-123→-366→-183→-546→-273→-816→-408→-204→-102→-51

先程の定理1の説明を振り返ると、負の整数に関しても全く同じように適用可能であることがわかると思います。

また、k=5では以下のようなループがありました。

5→20→10→5
0→0
-5→-10→-5
-25→-70→-35→-100→-50→-25
-85→-250→-125→-370→-185→-550→-275→-820→-410→-205→-610→-305→-910→-455→-1360→-680→-340→-170→-85

これらのループの値をよく見ると、どれもk=1でのループの5倍の値になっていることがわかります。

実は、以下のような定理が成り立ちます。

定理2
2/n,3n+mkルールは、2/n,3n+kルールのループの値をm倍にしたループを持つ。

仕組みは定理1の説明に出てきた性質2とほぼ同じですが、定理1(上の定理でのm=3のケースに相当する)ではm倍ループが存在するだけでなく「m倍ループ以外存在しない」という事まで言えたのに対し、一般の場合ではm倍ループが存在することまでしか言えません。

例えばk=5で存在する以下のループは、k=1には対応するループが存在しません。

1→8→4→2→1
19→62→31→98→49→152→76→38→19
23→74→37→116→58→29→92→46→23
187→566→283→854→427→1286→643→1934→967→2906→1453→4364→2182→1091→3278→1639→4922→2461→7388→3694→1847→5546→2773→8324→4162→2081→6248→3124→1562→781→2348→1174→587→1766→883→2654→1327→3986→1993→5984→2992→1496→748→374→187
347→1046→523→1574→787→2366→1183→3554→1777→5336→2668→1334→667→2006→1003→3014→1507→4526→2263→6794→3397→10196→5098→2549→7652→3826→1913→5744→2872→1436→718→359→1082→541→1628→814→407→1226→613→1844→922→461→1388→694→347

この定理は「あるkで現れたループ(と似た性質を持つループ)が、いつ他の値で再登場するか」
「あるkがにおけるループが、最低でも何個以上存在するか」などを予測するのには使えますが、コラッツ予想の本質である「最大で何個のループが存在するか」「ループに入らない初期値は存在しないのか」という疑問に対しては無力です。

さて、ここまでは初期値を整数全体に拡張しただけでしたが、kの方を拡張するとどうなるのでしょうか？

さっきの話と同じようにループを探してみると、以下のようになりました。

k=-1
- -1→-4→-2→-1
- -0→-0
- 1→2→1
- 5→14→7→20→10→5
- 17→50→25→74→37→110→55→164→82→41→122→61→182→91→272→136→68→34→17

k=-3
- -3→-12→-6→-3
- -0→-0
- 3→6→3
- 15→42→21→60→30→15
- 51→150→75→222→111→330→165→492→246→123→366→183→546→273→816→408→204→102→51

k=-5
- -5→-20→-10→-5
- -1→-8→-4→-2→-1
- -19→-62→-31→-98→-49→-152→-76→-38→-19
- -23→-74→-37→-116→-58→-29→-92→-46→-23
- -187→-566→-283→-854→-427→-1286→-643→-1934→-967→-2906→-1453→-4364→-2182→-1091→-3278→-1639→-4922→-2461→-7388→-3694→-1847→-5546→-2773→-8324→-4162→-2081→-6248→-3124→-1562→-781→-2348→-1174→-587→-1766→-883→-2654→-1327→-3986→-1993→-5984→-2992→-1496→-748→-374→-187
- -347→-1046→-523→-1574→-787→-2366→-1183→-3554→-1777→-5336→-2668→-1334→-667→-2006→-1003→-3014→-1507→-4526→-2263→-6794→-3397→-10196→-5098→-2549→-7652→-3826→-1913→-5744→-2872→-1436→-718→-359→-1082→-541→-1628→-814→-407→-1226→-613→-1844→-922→-461→-1388→-694→-347
- 0→0
- 5→10→5
- 25→70→35→100→50→25
- 85→250→125→370→185→550→275→820→410→205→610→305→910→455→1360→680→340→170→85

よく見ると、k=-1,-3,-5のループはk=1,3,5のループを-1倍にしたものになっています。

このことは、定理2のm=-1のケースに相当します。

ただし、この場合は定理1と同じで「-1倍ループしかない」とまで言えます。

以上の結果をまとめると、以下のようなことが言えます。

n/2,3n+kルールにどんなループがあるかを調べるとき、以下のケースは他のパターンと結果が被るので調べなくてもよい。

kが3の倍数のとき

kが負のとき

ちなみに、実はn/2,3n+kルールとn/2,3n+3kルールには意外な違いがありました。

kが3の倍数でないときは0→0というループに入るのは0のみですが、例えばk=3のときは

-2→-1→0→0

というように、0以外の初期値からでも0に到達できるようになっています。

0に収束する過程を逆にたどると、以下のようになりました。

前回載せた、k=1で1になる過程を逆にたどった図(コラッツ木)と比べると非常に単純な構造をしています。

また、k=9、27というように3で割れる回数を増やすとだんだん構造が複雑になっていくようです。

n/2+j,3n+kルール

次に、以下のルール群について考えます。

$a_{n+1}=\begin{cases}\frac{a_n}{2}+j&\text{if}　a_n\equiv0　\pmod2\\3a_n+k&\text{if}　a_n\equiv1　\pmod2\end{cases}$
※ $k$ は奇数

今まで扱っていたn/2,3n+kルールとは違い、 $a_n$ が偶数だったときに2で割った後にjが足されます。

定理3
$a_n$ 、 $b_n$ を以下の通り定義する。
$a_{n+1}=\begin{cases}\frac{a_n}{2}+j&\text{if}　a_n\equiv0　\pmod2\\3a_n+k&\text{if}　a_n\equiv1　\pmod2\end{cases}$
※ $k$ は奇数
$b_{n+1}=\begin{cases}\frac{b_n}{2}&\text{if}　b_n\equiv0　\pmod2\\3b_n+k+4j&\text{if}　b_n\equiv1　\pmod2\end{cases}$
$a_0=b_0+2j$ とするとき、全ての自然数 $n$ について $a_n=b_n+2j$ が成り立つ。

要するに、全てのn/2+j,3n+kルールはj=0である別のルールと同じような挙動をするということです。

例えば $j=2$ 、 $k=-7$ 、 $a_0=7$ とすると、 $a_n$ は以下のようになります。

7→14→9→20→12→8→6→5→8→...

このとき、 $b_n$ の奇数ケースの定数項は $-7+4×2=1$ になり、 $b_0=a_0-2j=3$ とすると $b_n$ は以下のようになります。

3→10→5→16→8→4→2→1→4→...

この $a_n$ と $b_n$ を比較すると、実際に $a_n=b_n+2j=b_n+4$ が成り立っていることがわかります。

この仕組みは実は単純で、 $a_n$ が以下のように変形できるのが関わっています。

$a_{n+1}=\begin{cases}\frac{a_n-2j}{2}+2j&\text{if}　a_n\equiv0　\pmod2\\3(a_n-2j)+k+4j+2j&\text{if}　a_n\equiv1　\pmod2\end{cases}$

さて、これによりn/2+j,3n+kルールはj=0以外調べる必要が無いことがわかりました。

-n/2,3n+kルール

次はこちら。

$a_{n+1}=\begin{cases}-\frac{a_n}{2}&\text{if}　a_n\equiv0　\pmod2\\3a_n+k&\text{if}　a_n\equiv1　\pmod2\end{cases}$
※ $k$ は奇数

$a_n$ が偶数のときにマイナスが付きます。

まず、k=1の時は以下のようなループが見つかりました。

k=1
- 0→0
- 1→4→-2→1

n/2,3n+1ルールでは負の初期値からは1を含まないループに収束していましたが、このルールでは0以外は全部1に到達するようでした。

n/2,3n+kルールではループが2つしかないルールは無かったので、被らないことが期待できます。

必ず1に到達する(ように見える)という性質が美しいと感じたので、以下の命題を個人的に「真・コラッツ予想」と呼んでいます。

真・コラッツ予想
0以外の整数を初期値とする-n/2,3n+1数列は必ず1に到達する。

1に到達する数の樹形図を描いてみると、以下のようになりました。

生成規則は前回の記事のものと同じで以下の通りです。

nの右に-2nを書く
nを6で割った余りが4なら(n-1)/3を書く

数字の色は3で割った余りを表しており、赤、緑、青がそれぞれ0、1、2に対応しています。

n/2,3n+kルールと比較すると、以下のような違いがあります。

3で割った余りが0か2(赤か青)の数は永久に分岐しない
- n/2,3n+kルールでは、分岐しなくなるのは余りが0になった時だけだった。
3で割った余りが1の数は、毎ステップで分岐し続ける。
- n/2,3n+kルールでは、1本の枝が2ステップ連続で分岐することは無かった。

このような違いが生じるのには、-2を3で割った余りが1であるため、整数に掛けても3で割った余りが変化しないという理由があります。

描いてみた感想として、分岐する条件が少し単純なので、n/2,3n+1ルールの樹形図よりも何となく規則的であるような印象を受けました。

もしかしたら、真・コラッツ予想の方が簡単で、コラッツ予想より簡単に解かれるかもしれませんね。

さて、kが1でないときは以下のようになります。

k=3
- 0→0
- 3→12→-6→3

k=5
- 0→0
- -1→2→-1
- 5→20→-10→5

k=7

- 0→0
- 7→28→-14→7
- 1→10→-5→-8→4→-2→1

k=9

- 0→0
- 9→36→-18→9

k=11

- 0→0
- 11→44→-22→11
- -1→8→-4→2→-1
- 5→26→-13→-28→14→-7→-10→5
- -1231→-3682→1841→5534→-2767→-8290→4145→12446→-6223→-18658→9329→27998→-13999→-41986→20993→62990→-31495→-94474→47237→141722→-70861→-212572→106286→-53143→-159418→79709→239138→-119569→-358696→179348→-89674→44837→134522→-67261→-201772→100886→-50443→-151318→75659→226988→-113494→56747→170252→-85126→42563→127700→-63850→31925→95786→-47893→-143668→71834→-35917→-107740→53870→-26935→-80794→40397→121202→-60601→-181792→90896→-45448→22724→-11362→5681→17054→-8527→-25570→12785→38366→-19183→-57538→28769→86318→-43159→-129466→64733→194210→-97105→-291304→145652→-72826→36413→109250→-54625→-163864→81932→-40966→20483→61460→-30730→15365→46106→-23053→-69148→34574→-17287→-51850→25925→77786→-38893→-116668→58334→-29167→-87490→43745→131246→-65623→-196858→98429→295298→-147649→-442936→221468→-110734→55367→166112→-83056→41528→-20764→10382→-5191→-15562→7781→23354→-11677→-35020→17510→-8755→-26254→13127→39392→-19696→9848→-4924→2462→-1231

n/2,3n+kルールでは出てこなかった、超長いループが現れました。

これを見ると、やはりn/2,3n+kルールと-n/2,3n+kルールは全くの別物であるように見えます。

より詳しく調べるために、それぞれのkに対して現れるループの周期を比較してみます。

k	n/2,3n+k	-n/2,3n+k
1	1,2,3,5,18	1,3
3	1,2,3,5,18	1,3
5	1,2,3,4,5,8,8,18,44,44	1,2,3
7	1,2,3,5,6,18	1,3,6
9	1,2,3,5,18	1,3
11	1,2,3,5,7,8,18,22	1,3,4,7,137
13	1,2,3,5,5,13,13,13,13,13,13,13,18,39	1,3,5,13,13,13,13,13,13,13
15	1,2,3,4,5,8,8,18,44,44	1,2,3
17	1,2,3,5,9,10,10,18,49	1,3,5,10,10
19	1,2,3,5,16,18,28	1,3,11
21	1,2,3,5,6,18	1,3,6
23	1,2,3,5,7,7,18,31,31,31,31,31,31,31,31,69	1,3,19,62
25	1,2,3,4,5,8,8,12,18,24,44,44,56	1,2,3,12
27	1,2,3,5,18	1,3
29	1,2,3,5,6,18,20,26,106	1,3,16,20

まず、n/2,3n+kの定理1(n/2,3n+3kルールに現れるループはn/2,3n+kルールと同じ)と定理2(n/2,3n+mkルールにはn/2,3n+kルールと同じループが現れる)と同じ性質が、-n/2,3n+kルールでも成り立つことが予想できます。(実際に成り立ちます)

また、n/2,3n+kルールと-n/2,3n+kルールで出現するループに共通点はなさそうですが、唯一k=13のときに13周期のループがたくさん現れるという点のみ共通しています。

n/2,3n+kルールではkが13の倍数でないときでもk=23,47,59,71で似たような現象が起きますが、-n/2,3n+kルールでは再現されませんでした。

k	n/2,3n+k	-n/2,3n+k
13	1,2,3,5,5,13,13,13,13,13,13,13,18,39	1,3,5,13,13,13,13,13,13,13
23	1,2,3,5,7,7,18,31,31,31,31,31,31,31,31,69	1,3,19,62
47	1,2,3,5,11,11,11,11,11,18,25,44	1,3,22
59	1,2,3,5,16,16,16,16,16,16,18,39	1,3,8,8,16,16,16
71	1,2,3,5,15,15,18,44,44,44,44,44	1,3,15,15

再現されないといってもk=59では16が3つあったり、k=71でも15が2つあったりして、「なんだかよくわからないけど、何かありそうだ」という感じがします。

n/2,-3n+kルールと-n/2,-3n+kルール

他の位置にマイナスをつけたルールです。

k	n/2,3n+k	-n/2,3n+k	n/2,-3n+k	-n/2,-3n+k
1	1,2,3,5,18	1,3	1,5,31	1,2
3	1,2,3,5,18	1,3	1,5,31	1,2
5	1,2,3,4,5,8,8,18,44,44	1,2,3	1,2,5,31	1,2,4,8,8
7	1,2,3,5,6,18	1,3,6	1,3,5,6,21,31	1,2,3,6
9	1,2,3,5,18	1,3	1,5,31	1,2
11	1,2,3,5,7,8,18,22	1,3,4,7,137	1,4,5,31	1,2,8
13	1,2,3,5,5,13,13,13,13,13,13,13,18,39	1,3,5,13,13,13,13,13,13,13	1,5,9,26,31	1,2,9,26
15	1,2,3,4,5,8,8,18,44,44	1,2,3	1,2,5,31	1,2,4,8,8
17	1,2,3,5,9,10,10,18,49	1,3,5,10,10	1,5,10,10,31	1,2,5,10,10
19	1,2,3,5,16,18,28	1,3,11	1,5,5,31	1,2,5,22
21	1,2,3,5,6,18	1,3,6	1,3,5,6,21,31	1,2,3,6
23	1,2,3,5,7,7,18,31,31,31,31,31,31,31,31,69	1,3,19,62	1,5,7,7,31,31,31,31,31,31,31,31,31,31	1,2,14,62
25	1,2,3,4,5,8,8,12,18,24,44,44,56	1,2,3,12	1,2,5,12,31	1,2,4,8,8,12,28
27	1,2,3,5,18	1,3	1,5,31	1,2
29	1,2,3,5,6,18,20,26,106	1,3,16,20	1,5,16,31	1,2,6