なんか続いてしまった。
先日当ブログで紹介したコラッツ予想について、未だ挑戦している。
前回は、コラッツ予想を言い換えて「3以上の奇数全てがコラッツ操作で自身より小さくなれるなら、予想は成り立つ」として、自身より初めて小さくなるまでの奇数操作回数に着目していた。
今回は、その方針のまま、さらに色々と調べてみたので、その結果を書いていこう。
なお、前回までの繰り返しになるが、もちろん証明までは出来ていない。
というか、私の力ではこの方針で進めるのが無理そうだ、というのが分かったことになる。
しかし、もし何か他の挑戦者が使えるものがあればと思い、公開する。
それだけでなく、これを見て興味が湧いたら是非挑戦してみて欲しい。
コラッツ予想
初めてこの問題を見る方向けに、改めて紹介しよう。
まず、ある自然数\(n\)に着目する。
この自然数\(n\)に対して、以下の操作を考える。
- \(n\)が奇数なら、3倍して1を足す。
- \(n\)が偶数なら、2で割る。
このとき、どんな自然数に対しても、この操作を繰り返し適用すると1にたどり着くか、というのがコラッツ予想だ。
本記事で使う用語として、この\(n\)に対する1回の操作をコラッツ操作もしくは単に操作、その中でも奇数の場合の操作を奇数操作、偶数の場合の操作を偶数操作と呼ぶことにしよう。
未だ証明されておらず、ネットで少し調べてみても色んな方がチャレンジしているのが分かると思う。
やってみたこと
さて、今回は何をしてみたかというと、前回の継続だ。
冒頭や前回にも書いた通りだが、コラッツ予想は「1にたどり着く」ではなく、「自身より小さくなる」と言い換えても議論を進めることができる。
この詳細は前回の記事を参照してほしい。
そして、3以上の奇数について、それが自身より小さくなるまでの奇数操作回数に着目していた。
そこから、今回は自身より小さくなるまでの変化…でいいのか分からないが、どう変わっていくかに着目して調べてみた。
まあ、これだけだとよく分からないと思うので、中身に入っていこう。
前回の復習
では本題…なのだが、最初は前回の復習から。
\(n\)を0以上の整数とする。
このとき、\(4n + 1\)という形で表せる奇数は、1回の奇数操作と、2回の偶数操作で自身より小さくなる。
証明は以下の遷移を見てもらえれば分かると思う。
本記事では遷移の様子を示す時に、一本線の矢印を奇数操作、二本線の矢印を偶数操作としておこう。
$$\begin{eqnarray}
4n + 1 & \rightarrow & 12n + 4 \\
& \Rightarrow & 6n + 2 \\
& \Rightarrow & 3n + 1
\end{eqnarray}$$
\(n\)は0以上の整数のため、明らかに\(3n + 1\)は\(4n + 1\)以下になっていることが分かる。
以下と書いたが、イコールになるのは\(n = 0\)、つまり元の数が1の時なので、3以上に限定すれば元より小さくなる。
で、\(4n\)と\(4n + 2\)はそれぞれ偶数なので、偶数操作のみで自身より小さくなれる。
残っているのは、\(4n + 3\)型だ。
次に、2回の奇数操作で自身より小さくなるのは、\(16n + 3\)という形。
これも証明は以下の遷移を見れば明らか。
$$\begin{eqnarray}
16n + 3 & \rightarrow & 48n + 10 \\
& \Rightarrow & 24n + 5 \\
& \rightarrow & 72n + 16 \\
& \Rightarrow & 36n + 8 \\
& \Rightarrow & 18n + 4 \\
& \Rightarrow & 9n + 2
\end{eqnarray}$$
操作前と操作後の差が\(7n + 1\)で、\(n\)が0以上の整数から明らかに操作後の方が小さくなっている。
これで、あとは\(16n + 7\)、\(16n + 13\)、\(16n + 15\)となった。
パターンは増えているが、数は減っている。
ここまでが前回の内容だ。
…さて、ではここで、2回の奇数操作で自身より小さくなる\(16n + 3\)の遷移の様子について、1回だけ奇数操作をした後に出てくる奇数を見てみよう。
$$24n + 5$$
という形になっている。
これを少しいじると…
$$24n + 5 = 4(6n + 1) + 1$$
となっていることが分かると思う。
つまり、この数自身は、1回の奇数操作で自身より小さくなることができる。
何が言いたいかというと、2回の奇数操作で自身より小さくなることができる数は、1回奇数操作をすると、1回の奇数操作で自身より小さくなることができる数にたどり着くということ。
そんなところに注目をしてみた。
奇数操作の回数と出てくる奇数
さて、改めて今回注目した内容をまとめてみよう。
ある奇数\(k\)について、それが何回の奇数操作でそれ自身より小さくなるかによって分類する。
それらを2の累乗とそれ未満の自然数の和の形で表すと、以下の表のようになる。
| 小さくなるまでの奇数操作回数 | 式 |
|---|---|
| 1 | \(4n + 1\) |
| 2 | \(16n + 3\) |
| 3 | \(32n + 11\) |
| \(32n + 23\) | |
| 4 | \(128n + 7\) |
| \(128n + 15\) | |
| \(128n + 59\) | |
| 5 | \(256n + 39\) |
| \(256n + 79\) | |
| \(256n + 95\) | |
| \(256n + 123\) | |
| \(256n + 175\) | |
| \(256n + 199\) | |
| \(256n + 219\) |
この後はちょっと数が増えるので、それぞれ何パターンあるかだけ書いていこう。
13回までプログラムで求めたので、その結果を以下に記載する。
| 小さくなるまでの奇数操作回数 | パターン数 |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 7 |
| 6 | 12 |
| 7 | 30 |
| 8 | 85 |
| 9 | 173 |
| 10 | 476 |
| 11 | 961 |
| 12 | 2652 |
| 13 | 8045 |
こんな感じだ。
これらについて、自身より小さくなるまでの数の変化について、元の数を含めると左の列だけ奇数が出てきている。
例えば2回の\(16n + 3\)であれば、これと1回操作後の\(24n + 5\)の2つということ。
その、それぞれの奇数が何回の奇数操作で自身より小さくなるか、というものに注目した、というわけだ。
幾つか求めた結果
これも今回求めたものを全部貼ると1万行を超えてしまうので、6回操作まで表で載せることにしよう。
式の形と、その遷移の様子で出てきた奇数が何回の奇数操作で自身より小さくなるかを表にまとめてみる。
ちなみに、0回のところが、その式自体が自身より小さくなるまでの奇数操作回数になっている。
| 式 | 0回 | 1回 | 2回 | 3回 | 4回 | 5回 |
|---|---|---|---|---|---|---|
| \(4n + 1\) | 1 | |||||
| \(16n + 3\) | 2 | 1 | ||||
| \(32n + 11\) | 3 | 1 | 1 | |||
| \(32n + 23\) | 3 | 2 | 1 | |||
| \(128n + 7\) | 4 | 3 | 1 | 1 | ||
| \(128n + 15\) | 4 | 3 | 2 | 1 | ||
| \(128n + 59\) | 4 | 1 | 2 | 1 | ||
| \(256n + 39\) | 5 | 4 | 1 | 2 | 1 | |
| \(256n + 79\) | 5 | 3 | 2 | 1 | 1 | |
| \(256n + 95\) | 5 | 4 | 3 | 2 | 1 | |
| \(256n + 123\) | 5 | 1 | 3 | 1 | 1 | |
| \(256n + 175\) | 5 | 4 | 3 | 1 | 1 | |
| \(256n + 199\) | 5 | 3 | 1 | 1 | 1 | |
| \(256n + 219\) | 5 | 1 | 3 | 2 | 1 | |
| \(1024n + 287\) | 6 | 5 | 4 | 3 | 1 | 1 |
| \(1024n + 347\) | 6 | 1 | 4 | 3 | 1 | 1 |
| \(1024n + 367\) | 6 | 5 | 4 | 1 | 2 | 1 |
| \(1024n + 423\) | 6 | 5 | 1 | 3 | 1 | 1 |
| \(1024n + 507\) | 6 | 1 | 4 | 1 | 2 | 1 |
| \(1024n + 575\) | 6 | 5 | 4 | 3 | 2 | 1 |
| \(1024n + 583\) | 6 | 3 | 1 | 1 | 2 | 1 |
| \(1024n + 735\) | 6 | 5 | 3 | 2 | 1 | 1 |
| \(1024n + 815\) | 6 | 5 | 3 | 1 | 1 | 1 |
| \(1024n + 923\) | 6 | 1 | 4 | 3 | 2 | 1 |
| \(1024n + 975\) | 6 | 3 | 2 | 1 | 2 | 1 |
| \(1024n + 999\) | 6 | 5 | 1 | 3 | 2 | 1 |
もう少し、表の見方を説明しておこう。
例えば、一番下の\(1024n + 999\)について、これは6回の奇数操作で自身より小さくなる数だ。
このとき…
- 1回の奇数操作を行った後の奇数は、5回の奇数操作で自身より小さくなる
- 2回の奇数操作を行った後の奇数は、1回の奇数操作で自身より小さくなる
- 3回の奇数操作を行った後の奇数は、3回の奇数操作で自身より小さくなる
- 4回の奇数操作を行った後の奇数は、2回の奇数操作で自身より小さくなる
- 5回の奇数操作を行った後の奇数は、1回の奇数操作で自身より小さくなる
となっている、ということだ。
さて、これを見て幾つか気づいたことがあるので、それをまとめていこう。
元以上の回数は出てこない
一つ目、ある奇数操作回数で自身より小さくなる場合、それに奇数操作を行う遷移の中には、その回数以上の回数で小さくなる数は出てこない。
どういうことかというと、例えば5回の奇数操作で自身より小さくなるものに注目してみよう。
そこから右、つまり1回以上奇数操作をした後の奇数は、必ず4回以下で自身より小さくなることが分かる。
まあ、これはほぼ自明だろう。
もし5回操作で自身より小さくなる数に対して奇数操作を行った結果6回の操作が必要となったら、その時点で5回では自身より小さくなれない。
あるいは、6回必要だったとしても、その時点で自身より小さくなっているはず。
なんの役に立つか分からないが…一応書いておいた。
一つ少ない回数の操作が出てくるパターン
次に、1回は分かりづらいが…2回以上奇数操作が必要なパターンについて。
1回の奇数操作後に、元より1回少ない回数で自身より小さい数になる奇数が出てきているのが分かるだろうか。
例えば、さっきと同じ5回に着目すると、1回操作後の奇数の中には、4回で自身より小さくなるパターンが出てきている。
しかも、今回調べた範囲ではあるが…13回以下の場合は全てのパターンが出てきているのだ。
まだ厳密な証明はしていないが…まあ、これは成り立つと思う。
本記事では、このパターンを自明なパターンと呼ぶことにしよう。
非自明なパターン
となると、気になることが出てくる。
それ以外のパターンも出てきているのだ。
例えば、4回の奇数操作で自身より小さくなる\(128n + 59\)。
これに対して操作を行うと…
$$\begin{eqnarray}
128n + 59 & \rightarrow & 384n + 178 \\
& \Rightarrow & 192n + 89 \\
& \rightarrow & 576n + 268 \\
& \Rightarrow & 288n + 134 \\
& \Rightarrow & 144n + 67 \\
& \rightarrow & 432n + 202 \\
& \Rightarrow & 216n + 101 \\
& \rightarrow & 648n + 304 \\
& \Rightarrow & 324n + 152 \\
& \Rightarrow & 162n + 76 \\
& \Rightarrow & 81n + 38
\end{eqnarray}$$
こんな感じで、表通り最終的には4回の奇数操作で自身より小さくなる。
このとき、1回だけ奇数操作した後の奇数は…
$$192n + 89 = 4(48n + 22) + 1$$
という形なので、ここからは1回の奇数操作でこれより小さくなる。
実際、2回の奇数操作を終えた後は\(144n + 67\)になっており、1回操作後の奇数\(192n + 89\)よりも小さい。
つまり、1回操作した後には、元より1回少ないだけの自明なパターン以外にも、2回以上少ない非自明なパターンも存在する…のだが、問題はここから。
表を注意深く見てもらえば分かるが、それまでの全ての回数が1回操作後に出てくるわけでもない。
具体的には、2回や4回は非自明なパターンの先頭に出てこない。
表には入っていないが、7回や9回も同じくだ。
2回の場合だけ実際に確認してみたが、確かに計算すると、1回操作後に2回の操作で自身より小さくなる場合、その時点で元の数より小さくなる、つまり元の数は3回で自身より小さくなることが分かった。
もしこれが計算で求められたとすると、非自明なパターンの先頭がどうなっているかまで求めることができるのだが…まだ問題は残る。
例えば、9回の操作で自身より小さくなる奇数で、\(32768n+12827\)という数がある。
これは1回操作を行うと\(4n+1\)型になり、そこからは1回の操作で自身より小さくなる。
その結果は5回の奇数操作で小さくなるが、この5回を終えた段階でもまだ元よりは大きく、残る奇数操作は2回。
…そう、ここからは2回の奇数操作で小さくなる数になっており、そこでようやく元よりも小さくなる。
先ほど、元の数に対して1回操作した直後に2回の奇数操作で自身より小さくなることはないと書いた。
つまり、パターンの先頭にはそれが出てこないのだが、その後には出てくる可能性がある。
ここまで来ると、ちょっと条件をどう出せばいいかが分からなくなってくる。
今の私の最前線が、ここだ。
おわりに
ちょっと中途半端になってしまったが、今回はここまでだ。
やっているうちに、この方針ではあまり進めないのではないか、という感じがしてきている。
というわけで、今後はまた方針を変えて考えてみようかなと思っているところだ。
具体的には、2進数方面だ。
これは他のサイトでも紹介されている内容だが、コラッツ操作は2進数と親和性が高い。
…というか、実は今回やった内容も、最初は2進数で考えていた内容なのだ。
表していた\(2^k + a\)という形なのだが、これは2進数で見ると1の位を0桁目として\(k\)桁目まで共通で、\(k+1\)桁目以降が1ずつ増えている、という状態になっていた。
これを発見した時はなんか進みそう、と思ったのだが…そううまくはいかなかった。
今後はこの2進数に戻って、また何か分かりそうだったら記事にまとめてみることにしよう。
皆さんも、もし気になれば是非チャレンジしてみてほしい。
コメント