コラッツ予想で分かったことをまとめてみた

先日、コラッツ予想の記事を公開した。

問題文の意味は簡単に分かるが、その証明は未だされていないという未解決問題の一つだ。

以前の記事を公開した後も色々と考えてみて、少し分かってきたことがあるので、それをまとめておこう。

あ、もちろんだが完全な証明はできていないのでそこはご了承を。

完全に備忘録で、かつ論文や他の記事などはほとんど調べていないので、もうすでに分かっていることもある…というか、多いと思う。

が、もし何かの参考になればと思い、書いてみることにする。

ちなみに、改めて書くことでもないと思うが…私は、ただ数学が好きなだけの素人だ。

まずはどういう方針で考えているかを書き、その後にそれについて分かったこと、思った事などをまとめていく。

もしかしたら誤り等含まれているかもしれないが…見つけた時は、そっと教えてくれると嬉しい。

復習：コラッツ予想

以前の記事に書いたが、改めてコラッツ予想の概要を書いておこう。

ある自然数\(n\)に対し、以下の操作を行うことを考える。

• \(n\)が奇数の場合、3倍して1を足す
• \(n\)が偶数の場合、2で割る

このとき、どんな自然数\(n\)からスタートしても、操作を有限回繰り返すことで1にたどり着くか、というのがコラッツ予想だ。

この操作を、この記事ではコラッツ操作と呼ぶことにしよう。

また、奇数の場合に行う操作、偶数の時に行う操作を区別する場合はそのまま奇数操作、偶数操作と呼ぶ。

具体例で見てみると、例えば3からスタートした場合は…

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

という感じで、1にたどり着く。

これが、どんな数でも1にたどり着くのだろうか、という問いかけにまだ誰も答えられていない。

考えている方針

では、私がどういう方針でこれを考えているかをまとめてみよう。

まず、この問題の「1にたどり着くか」という部分は、「元の数より小さい自然数にたどり着くか」と書き換えることができる。

この証明は後でやるとして…これが成り立つとすると、少し示す内容が変わる。

どんな数でも、少しでも小さくなることが示せればコラッツ予想が真であると証明できるのだ。

そこで注目したのが、元の数より小さくなるまでの操作回数。

コラッツ予想には二つの操作があり、その数が奇数の場合と、偶数の場合に分けられる。

この、それぞれの回数に何等かの関係があるのではないかと思い、調べてみた。

すると、面白い性質を見つけたので、それを紹介していこう。

…まあ、それが分かったからなんだという感じもぬぐえないが、何も分からないよりはマシだろう。

定理言い換えの証明

上で書いた書き換えについて、しっかり見ていこう。

改めて書くと、「任意の2以上の自然数\(n\)について、それがコラッツ操作によって自身より小さい数になることができれば、コラッツ予想は成り立つ」となる。

全ての自然数が自身より小さくなるかはまだ分かっていないが、一旦これが証明できたと仮定して話を進めてみる。

これなら私でも証明できたので、\(n\)に関する数学的帰納法でやってみよう。

まずは\(n = 2\)の場合、偶数で2で割って1になるため、自明に成り立つ。

奇数だとパターンが変わるので、\(n = 3\)も見てみるが…これは上でやった通り、2にたどり着くことができる。

で、その2は一回の偶数操作で1にたどり着けるので成立だ。

どちらにしろ、ここまでは明らかに成り立っている。

では、\(n \leq k – 1\)で成り立っていると仮定しよう。

詳しく書くと、全ての自然数において操作を繰り返すことで自身より小さくなることができ、かつ\(k – 1\)までは1にたどり着くということを仮定している。

この時に、\(n = k\)で成り立つかを見ていく。

まず\(k\)が偶数の場合、これも明らかに偶数操作で\(\frac{k}{2}\)になり、\(k – 1\)以下になったので成立する。

次に\(k\)が奇数の場合、一回目の操作では増えるが、その後はどうなるか分からない。

しかし、仮定から操作を続けることによって\(k\)より小さくすることができ、その数は帰納法の仮定から1にたどり着く。

よって、奇数の場合も成立する。

ちょっと仮定が多くて分かりづらいかもしれないが、これで示したいことは示せた。

改めて書くと、全ての自然数で操作を行うことによって自身より小さくなることを示せれば、コラッツ予想が真だと示せたことになる。

以降は、この書き換えた内容で話を進めていこう。

操作の回数

さて、ある自然数が操作によって1にたどり着くなら、必ずどこかのタイミングで自身より小さくなっている。

1が自然数の最小値なので、明らかにこれは言えるだろう。

では、初めて自身より小さくなったタイミングまでに注目し、その操作回数を奇数、偶数それぞれで求めてみよう。

とはいえ、偶数からスタートの場合は明らかに偶数操作1回で小さくなるので、奇数からスタートで考えてみる。

まず、3について、3より小さくなるまでの操作の様子を改めて書いてみよう。

また、奇数、偶数を分かりやすくするため、奇数操作は→、偶数操作は⇒と書き分けてみよう。

3→10⇒5→16⇒8⇒4⇒2

これで回数をそれぞれカウントしてみると、奇数は2回、偶数は4回だ。

次に、5の場合だが…上の中に含まれているので4以下になるまでをカウントすると、奇数が1回、偶数が2回となる。

7の場合も見てみよう。

7→22⇒11→34⇒17→52⇒26⇒13→40⇒20⇒10⇒5

ここで小さくなったので、奇数操作が4回、偶数操作が7回となった。

続けて9の場合。

9→28⇒14⇒7

ここで終わりで、奇数が1回、偶数が2回。

…このまま続けてもいいのだが、具体的な変化の様子はここまでにしておく。

31以下の奇数について、その奇数、偶数操作の回数を以下の表にまとめておこう。

元の奇数	1	3	5	7	9	11	13	15
奇数操作	–	2	1	4	1	3	1	4
偶数操作	–	4	2	7	2	5	2	7
元の奇数	17	19	21	23	25	27	29	31
奇数操作	1	2	1	3	1	37	1	35
偶数操作	2	4	2	5	2	59	2	56

これを含め、一旦プログラムを組んで10万未満の自然数で回数を求め、確認してみた。

そこから、証明もしていないのであくまで予想だが…奇数操作の回数は、条件式で表すことができるのでは？と思っている。

どういうことか、詳しく見ていこう。

奇数操作の回数を表す条件式

さて、上の表をもう一度見て欲しい。

1個おきに、奇数操作が1回、偶数操作が2回で自身より小さくなることが分かる。

奇数の1個おきなので、自然数で見ると4個おきだ。

そして、最小値は5。

ここから、\(4n + 1\)で表せる数は、奇数操作だけ見ると1回で必ず自身より小さくできるのではないか、という推測ができる。

ちなみに、\(n\)は自然数だ。

これはシンプルに証明できるので、してしまおう。

まず、奇数操作を1回、奇数操作直後は必ず偶数操作になるのでその偶数操作までしてしまおう。

$$4n + 1 \rightarrow 12n + 4 \Rightarrow 6n + 2$$

さて、\(6n + 2\)は明らかに偶数なので、もう一回偶数操作ができる。

$$6n + 2 \Rightarrow 3n + 1$$

ここで、元の数\(4n + 1\)との差を求めてみよう。

元の数から出てきた数を引いて、常に正の値になれば、明らかに元より小さくなったと言える。

$$4n + 1 – (3n + 1) = n$$

ということで、\(n\)は自然数なので常に正の値になった。

以上から、\(4n + 1\)という形で表せる数は必ず1回の奇数操作で自身より小さくなることが示せた。

ちなみに、\(n\)を自然数ではなく0以上の整数として考えると、1がループすることも分かる。

差が\(n\)…つまり0になるので、元と同じになるのだ。

では、\(4n\)と\(4n + 2\)は偶数なので0回でいけるとして…\(4n + 3\)はどうなの？と思うだろう。

ただ、これそのままだと7以上になってしまい、3が除外されてしまう。

そのため、書き直して\(4n – 3\)が上で示したもの、残りが\(4n – 1\)としておこう。

ちなみに、\(4n – 3\)の形で遷移を見ると以下のようになる。

$$4n – 3 \rightarrow 12n – 8 \Rightarrow 6n – 4 \Rightarrow 3n – 2$$

また、元の数との差は以下の通り。

$$4n – 3 – (3n – 2) = n – 1$$

では、次のパターンを見てみよう。

上の表に挙げた中には二つしかないが…2回の奇数操作で小さくなる数について見てみる。

31より大きい奇数も含めると、3、19、35、51、67、83、99、…となっている。

2桁以下の自然数では、この7個で全てだ。

さて、これを注意深く見てみると、全て\(16n – 13\)という形で表せていることが分かるだろうか。

隣り合った数の差が常に16となっていることを確かめてみて欲しい。

では、この形に対して操作をしてみよう。

すると…

$$\begin{eqnarray}
16n – 13 & \rightarrow & 48n – 38 \Rightarrow 24n – 19 \rightarrow 72n – 56 \\
& \Rightarrow & 36n – 28 \Rightarrow 18n – 14 \Rightarrow 9n – 7
\end{eqnarray}$$

というわけで、元の数との差を求めてみると…

$$16n – 13 – (9n – 7) = 7n – 6$$

これで、\(n\)は自然数なので明らかに元より小さくなることが分かった。

というわけで、\(16n – 13\)という形で表せる自然数は、2回の奇数操作で元より小さくなることが分かった。

…と、ここまで見てもらえれば分かると思う。

ある数が何回の奇数操作で元より小さくなるかは、\(2^k – l\)という形で表せるのではないか、という推測が立つ。

まだ完全に証明はできていないが…ほぼ確実に成り立つのではないか、と思っている。

そして、これが奇数回数を使って表すことができれば、かなり前進することとなるだろう…が、そこにも問題はある。

これは、奇数回数1種類につき1通りではない。

どういうことかというと、今2回の奇数操作までしか見ていなかったが、3回に増やすと、以下の自然数が該当する。

• 11、43、75、107、139、171、…
• 23、55、87、119、151、183、…

今二つに分けて書いたが、これはそれぞれ\(32n – 21\)、\(32n – 9\)という形で表せるのだ。

そして、実際に計算してみると…

$$\begin{eqnarray}
32n – 21 & \rightarrow & 96n – 62 \Rightarrow 48n – 31 \rightarrow 144n – 92 \\
& \Rightarrow & 72n – 46 \Rightarrow 36n – 23 \rightarrow 108n – 68 \\
& \Rightarrow & 54n – 34 \Rightarrow 27n – 17
\end{eqnarray}$$

$$32n – 21 – (27n – 17) = 5n – 4 > 0$$

$$\begin{eqnarray}
32n – 9 & \rightarrow & 96n – 26 \Rightarrow 48n – 13 \rightarrow 144n – 38 \\
& \Rightarrow & 72n – 19 \rightarrow 216n – 56 \Rightarrow 108n – 28 \\
& \Rightarrow & 54n – 14 \Rightarrow 27n – 7
\end{eqnarray}$$

$$32n – 9 – (27n – 7) = 5n – 2 > 0$$

ということで、いずれも3回の操作で元より小さくなる。

こんな感じで、回数を増やすとパターンも増えるが…一応、2の累乗からそれ未満のなんらかの奇数を引いた形で表せる、というのが今のところの予想だ。

遷移の様子で気づいたこと

さて、ここまでの内容が色々と考えて分かったことで、ここからは記事を書いている段階でふと思ったことになる。

上でやったように、奇数操作の回数で分けると、それが一定の形で書き表せる、という推測だった。

さて、幾つか具体的に計算した中身を見て欲しい。

マイナスしている数だけに注目すると、これは負の値に対してコラッツ操作をしている、と捉えられないだろうか。

そして、それに関してはWikipediaに少し記述がある。

整数全体にコラッツ操作を拡張する、というものだ。

今注目したい負の値だけ見ると、どうやら3つのサイクルがあるらしい。

• -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

で、これと関連して考えることで先に進みそう、という感覚だけある状態だ。

今後は、この方針で考えてみることにしよう。

奇数操作と偶数操作の関係

さて、話は自然数の範囲に戻る。

先ほど、特定の奇数操作回数で見ていたが、実は偶数操作の回数と興味深い関係がある。

これまた証明できたわけではないが…大体100万までの自然数で確認した内容だ。

小さくなるまでの奇数操作の回数が決まると、偶数操作も一意に決まりそうなのだ。

例えば、1回の奇数操作で自身より小さくなる時、それまでに行う偶数操作の回数は2回となる。

2回の奇数操作でも\(16n – 13\)の1パターンで、先ほど計算した通り4回の偶数操作で小さくなる。

しかし、これも先ほど書いたが、3回以上の奇数操作だと表現できるパターンが増える。

このとき、偶数操作の回数が異なるものも出てきそうだが…今のところ、奇数操作の回数が決まると、偶数操作の回数も1つに定まっているようだ。

言い換えると、奇数操作の回数から、何等かの方法で偶数操作の回数も求められそうだ、ということ。

少し、考えてみよう。

まず、大雑把にではあるが、奇数操作で大体何倍程度になるかを考えてみる。

実際は1を足す部分によって割合が変化するので、具体的には分からないが…大きくても1スタートの4倍、次は3スタートの\(\frac{10}{3} = 3.333…\)倍。

そして、元がどれだけ大きくなろうと3倍までにはならない。

ここでは、一旦3倍と仮定して計算してみよう。

すると、奇数操作で大体3倍、偶数操作は明らかに\(\frac{1}{2}\)倍。

奇数操作の回数を\(p\)、偶数操作の回数を\(q\)として、以下の分数を考える。

$$\frac{2^q}{3^p}$$

これは、操作した後の数を1とした時の、操作前の数の割合と考えられる。

つまり、これが初めて1を超えたタイミングで、元の数より小さくなりそうだ。

この値を\(a\)と置き、\(p\)と\(q\)の関係を表現してみよう。

今、奇数回数から偶数回数を求めたいので、\(q\)を\(p\)で表すように変形してみる。

$$\begin{eqnarray}
\frac{2^q}{3^p} & = & a \\
\log_2 (\frac{2^q}{3^p}) & = & \log_2 a \\
\log_2 2^q – \log_2 3^p & = & \log_2 a \\
q & = & p \log_2 3 + \log_2 a
\end{eqnarray}$$

こうなった。

さて…今やりたいのは、元より小さくなる奇数回数が決まれば、偶数回数も決まるという仮定の元、その偶数回数を出したい、ということだった。

で、\(a\)の値は操作後を基にした操作前の比を表していた。

つまり、\(a\)が1を超える時の\(q\)を求めてあげればいい。

\(\log_2 1 = 0\)なので、ようは\(p \log_2 3\)を初めて超える自然数…さらに言い換えると、\(p \log_2 3\)以上のうち、最小の自然数が\(q\)になる。

これをExcelで求め、幾つか計算してみると…

奇数操作回数	偶数操作回数(実測)	偶数操作回数(式による算出)
1	2	2
2	4	4
3	5	5
4	7	7
5	8	8
6	10	10
7	12	12
8	13	13
9	15	15
10	16	16

このように、見事に一致した。

ここには10回までしか書いていないが、奇数操作が60回くらいまで合ってそうなことは確認できた。

…まあ、これも分かったからといってその先の議論はまだ考えられていない。

しかも、これ自体もまだ少ない具体例でしか確認していないので、全ての自然数で成り立っている保証もない。

が、一つの道筋くらいにはなるのではないだろうか…

おわりに

今回は、少し前に概要を紹介したコラッツ予想について、進展をメモ程度に書き記した。

まだまだ証明できていない部分も多い…というか、解決に向かっているかどうかも分からない状態だが、日々楽しく挑戦している。

今後も、もし何か分かれば進捗という形で色々とメモしていこうと思う。

これを見てやってみようかなと思う方、あるいは(この記事が参考になることはあまりないと思うが…)解決したという方が出れば、この上嬉しいことはない。

皆さんも、数学が好きならチャレンジしてみてはいかがだろうか。