はじめに
コラッツの問題(コラッツ予想)に関心のある方もそうでもない方も初めまして。
コラッツの問題について詳しくはWikipediaのコラッツの問題 などを読んでいただければと思います。
簡単に言うと、
「すべての正の整数は、偶数なら2で割り、奇数なら3倍して1を足す、を繰り返すと1を含むループに収束する」
が正しいか否か、という未解決の問題です。
「1を含まないループになる値」「1に収束せず無限に増え続ける値」のどちらかを見つければこの予想を否定できます。
今回は「解けたらコラッツ予想を否定できる式」と題しましたが、
正確に言うと「整数解で割り切れればループする値が得られる式」を立てたので、それを紹介していきます。
操作の言い換え
まず今回の式の元となる、コラッツの操作の言い換えを行います。
すべての正の奇数は、
(手順1) $1$を足すと偶数になるので、奇数になるまで$\frac{3}{2}$を掛け続ける。
(手順2) $1$を引くと偶数になるので、奇数になるまで$\frac{1}{2}$を掛け続ける。
この手順1、手順2を繰り返すと$1$を含むループに収束するか。
これが元のコラッツの操作と変わっていないということを説明していきます。
まず、偶数は2で割り続ければ奇数になるので、初期値を奇数に限定しても問題はありません。
（他にも、3で割った時の余りに注目すると3の倍数も初期値から除外できたりします）
次に、任意の奇数を以下のような形で表現します。
$n = (R \cdot 2^x) - 1$
$R: 1$以上の奇数
$x: 1$以上の整数
この式で、「3倍して1を足して、1回しか2で割れない(すぐ奇数になる)」パターンを見てみます。
- 3倍する
$\bigl((R \cdot 2^x) - 1\bigr) * 3 = (R \cdot 2^x \cdot 3) - 3$ - 1を足す
$\bigl((R \cdot 2^x \cdot 3) - 3\bigr) + 1 = (R \cdot 2^x \cdot 3) - 2$ - 2で割る
$\bigl((R \cdot 2^x \cdot 3) - 2\bigr) \hspace{5pt} / \hspace{5pt} 2 = (R \cdot 2^{x-1} \cdot 3) - 1$
$x$が$2$以上の大きな数だったとして、これを繰り返すとどうなるでしょうか？
あらためて初期値から書くと、以下のように変化していきます。
(R * 2^(x ) ) - 1
(R * 2^(x-1) * 3^1) - 1
(R * 2^(x-2) * 3^2) - 1
...
(R * 3^x) - 1
この一連の操作は、「$2^x$を$3^x$に置き換えた」または「左の項だけ$x$回$\frac{3}{2}$倍した」と表現できます。(これが前述の手順1)
そして最後の状態は「$(奇数\cdot奇数)-1$」で偶数なので、奇数になるまで2で割り続ける必要があります。(これが前述の手順2)
式の変化と照らし合わせながら再度、手順1と手順2を確認してみましょう。
| 手順 | 式の操作 |
|---|---|
| (手順1) $1$を足すと偶数になるので、 |
$1$を足すことで、$(R \cdot 2^x)$の部分だけを取り出します。 |
| 奇数になるまで$\frac{3}{2}$を掛け続ける。 | 結果、$(R \cdot 2^x)$ から $(R \cdot 3^x)$ に変わります。 |
| (手順2) $1$を引くと偶数になるので、 |
$(R \cdot 3^x) - 1$ の形に戻します。 |
| 奇数になるまで$\frac{1}{2}$を掛け続ける。 | 「2回以上2で割れる場合の、2回目以降の2で割る操作」に相当します。 |
「3倍して1を足して、1回だけ2で割ったら奇数になるパターン」の連続はすべて手順1の中に含まれ、
「3倍して1を足して、2回以上2で割ったら奇数になるパターン」が出てきた時、手順2まで回るという形です。
よって、元のコラッツの操作をそのまま実行しているだけ、となります。
「1回しか2で割れないパターン」つまり「値が増加するパターン」の連続をひとまとめにしているところがポイントです。
次の章では、この言い換えた手順を元にしてループする値を探す式を立てます。
割り切れればループする値が得られる式
前章では、以下のような操作に言い換えても問題ない旨を説明しました。
すべての正の奇数は、
(手順1) $1$を足すと偶数になるので、奇数になるまで$\frac{3}{2}$を掛け続ける。
(手順2) $1$を引くと偶数になるので、奇数になるまで$\frac{1}{2}$を掛け続ける。
この手順1、手順2を繰り返すと$1$を含むループに収束するか。
この言い換えた操作に従ってループする値を探す式を立ててみましょう。
ここからは「手順1＋手順2の実行」を「1周」と表現します。
1周の場合
一番単純な「1周でループする」場合です。
2で何回割れるかの部分には変数$y$を追加します。
初期値: $n = (R \cdot 2^x) - 1$
$R: 1$以上の奇数
$x: 1$以上の整数
(1)手順1後 $\hspace{11pt} R \cdot 3^x$
(2)手順2後 $\bigl((R \cdot 3^x - 1) \hspace{5pt} / \hspace{5pt} 2^y\bigr) = (R \cdot 2^x) - 1 \hspace{5pt}$ (等式1) 初期値nに戻ってくるとした場合
(等式1)を整理すると、
$R = \dfrac{(2^y - 1)}{(2^{x+y} - 3^x)}$
これが1周の式となります。
$x=1,y=1$のとき$R=1$になるのが$1$を含むループの解ですね。
他の整数解が見つかれば、1を含まないループの発見です。そのときの $(R \cdot 2^x) - 1$ が求めている初期値です。
割り切れる見込みはありそうか、この式を観察してみましょう。2進数で考えます。
2^(y) - 1 : 11...11 (y桁)
2^(x+y) : 10000000000000000000 (x+y+1桁)
3^(x) : 1111111111110000001 (x+y桁) これくらい2の累乗に近い値でないと 分母<=分子 にならない
~~~~~~~~~~~~_______ 上位x桁くらい1の連続が必要
3の累乗を大きくしていくと、1が並ばないといけない桁数も増えていきます。
これを満たす3の累乗を見つけるのは難しそうです。
2周以上の場合
次は2周の式を立てましょう。
ここからは$R_1$、$x_1$、$y_1$のように添字を付けていきます。
初期値: $n = (R_1 \cdot 2^{x_1}) - 1$
(1)手順1後 $\hspace{11pt} R_1 \cdot 3^{x_1}$
(2)手順2後 $\bigl((R_1 \cdot 3^{x_1} - 1) \hspace{5pt} / \hspace{5pt} 2^{y_1}\bigr) = (R_2 \cdot 2^{x_2}) - 1 \hspace{5pt}$ (等式1)
(3)手順1後 $\hspace{10pt} R_2 \cdot 3^{x_2}$
(4)手順2後 $\bigl((R_2 \cdot 3^{x_2} - 1) \hspace{5pt} / \hspace{5pt} 2^{y_2}\bigr) = (R_1 \cdot 2^{x_1}) - 1 \hspace{5pt}$ (等式2) 初期値nに戻ってくるとした場合
2つの等式から$R_2$を排除して整理します。
$R_1 = \dfrac{\Bigl(\bigl(2^{(y_1+x_2)} \cdot (2^{y_2} - 1)\bigr) + \bigl(3^{x_2} \cdot (2^{y_1} - 1)\bigr)\Bigr)}{(2^{(x_1+y_1+x_2+y_2)} - 3^{(x_1+x_2)})}$
1周の式よりは分子が大きくなりそうです。
$R_2$も式にして比べて見ましょう。
$R_2 = \dfrac{\Bigl(\bigl(2^{(y_2+x_1)} \cdot (2^{y_1} - 1)\bigr) + \bigl(3^{x_1} \cdot (2^{y_2} - 1)\bigr)\Bigr)}{(2^{(x_1+y_1+x_2+y_2)} - 3^{(x_1+x_2)})}$
分母は同じで、分子の変数の添字が入れ替わる形になります。
分母を固定して考えた時、R1、R2のどちらかを大きくしようとするともう片方が小さくなるようです。
3周の式も立てましょう。
初期値: $n = (R_1 \cdot 2^{x_1}) - 1$
(1)手順1後 $\hspace{11pt} R_1 \cdot 3^{x_1}$
(2)手順2後 $\bigl((R_1 \cdot 3^{x_1} - 1) \hspace{5pt} / \hspace{5pt} 2^{y_1}\bigr) = (R_2 \cdot 2^{x_2}) - 1 \hspace{5pt}$ (等式1)
(3)手順1後 $\hspace{10pt} R_2 \cdot 3^{x_2}$
(4)手順2後 $\bigl((R_2 \cdot 3^{x_2} - 1) \hspace{5pt} / \hspace{5pt} 2^{y_2}\bigr) = (R_3 \cdot 2^{x_3}) - 1 \hspace{5pt}$ (等式2)
(5)手順1後 $\hspace{10pt} R_3 \cdot 3^{x_3}$
(6)手順2後 $\bigl((R_3 \cdot 3^{x_3} - 1) \hspace{5pt} / \hspace{5pt} 2^{y_3}\bigr) = (R_1 \cdot 2^{x_1}) - 1 \hspace{5pt}$ (等式3) 初期値nに戻ってくるとした場合
3つの等式を使って、$R_2$と$R_3$を排除して整理します。
$R_1 = \dfrac{\Bigl(\bigl(2^{(y_1+x_2+y_2+x_3)} \cdot (2^{y_3} - 1)\bigr) + \bigl(3^{x_3} \cdot 2^{(y_1+x_2)} \cdot (2^{y_2} - 1)\bigr) + \bigr(3^{(x_2+x_3)} \cdot (2^{y_1} - 1)\bigr)\Bigr)}{ (2^{(x_1+y_1+x_2+y_2+x_3+y_3)} - 3^{(x_1+x_2+x_3)})}$
同じ要領で、4周の式です。
$R_1 = \dfrac{\Bigl(\bigl(2^{(y_1+x_2+y_2+x_3+y_3+x_4)} \cdot (2^{y_4} - 1)\bigr) + \bigl(3^{x_4} \cdot 2^{(y_1+x_2+y_2+x_3)} \cdot (2^{y_3} - 1)\bigr) + \bigl(3^{(x_3+x_4)} \cdot 2^{(y_1+x_2)} \cdot (2^{y_2} - 1)\bigr) + \bigl(3^{(x_2+x_3+x_4)} \cdot (2^{y_1} - 1)\bigr)\Bigr)}{(2^{(x_1+y_1+x_2+y_2+x_3+y_3+x_4+y_4)} - 3^{(x_1+x_2+x_3+x_4)})}$
位置を揃えて並べてみると法則性が分かりやすいかと思います。
1周の式: R1 = ( (2^y1 - 1) ) / (2^(x1+y1) - 3^(x1) )
2周の式: R1 = ( ( 2^(y1+x2) * (2^y2 - 1)) + (3^(x2) * (2^y1 - 1))) / (2^(x1+y1+x2+y2) - 3^(x1+x2) )
3周の式: R1 = ( ( 2^(y1+x2+y2+x3) * (2^y3 - 1)) + (3^(x3) * 2^(y1+x2) * (2^y2 - 1)) + (3^(x2+x3) * (2^y1 - 1))) / (2^(x1+y1+x2+y2+x3+y3) - 3^(x1+x2+x3) )
4周の式: R1 = ((2^(y1+x2+y2+x3+y3+x4) * (2^y4 - 1)) + (3^(x4) * 2^(y1+x2+y2+x3) * (2^y3 - 1)) + (3^(x3+x4) * 2^(y1+x2) * (2^y2 - 1)) + (3^(x2+x3+x4) * (2^y1 - 1))) / (2^(x1+y1+x2+y2+x3+y3+x4+y4) - 3^(x1+x2+x3+x4))
n周の場合
$n$周の式は以下のように表現できます。
R_1 = \dfrac{\sum_{i=1}^{n} \left( 2^{\sum_{j=1}^{i-1} (x_{j+1} + y_j)} \cdot 3^{\sum_{j=i+1}^{n} (x_j)} \cdot \left( 2^{y_i} - 1 \right) \right)}{2^{\sum_{i=1}^{n} (x_i + y_i)} - 3^{\sum_{i=1}^{n} (x_i)}}
$x$,$y$はすべて$1$以上の整数です。
$Σ$は 終了値＜開始値 の場合は$0$です。
もし整数解を見つけたなら $(R_1 \cdot 2^{x_1}) - 1$ がループする値です。
何周であっても$x$,$y$がすべて$1$のとき$R_1 = 1$となり、これが既知である1を含むループの解です。
この式を元にして、総当たりで探すコードの例を下に載せています。
何周まであり得るのか
解があり得る範囲と言う意味で限界があります。
変数$x$,$y$は$1$以上という制約により、値の配分に限度があるためです。
分母が $2^p - 3^q$ の場合を考えましょう。
答えを先に書くと「$q$と$(p-q)$の小さい方」が周数の限界です。
以下はその説明です。
$p$の下限は分かりやすいです。
分子には正の数しか出てこないので、分母も正の値である必要があります。
例えば、
$q=100$ のとき
$p=159$ 以上
です。$p$の下限は$log2(3)$倍の端数切り上げで算出されます。
2進数で見たとき、$2^p$の方が$3^q$より1桁大きくなる値です。
このとき、
$x[1 \ldots n]$の合計値: $100$
$y[1 \ldots n]$の合計値: $159-100=59$
となります。
つまり$n=59$のとき、$y[1 \ldots 59]$はすべて1で固定され、$p=100,q=159$のとき、59周が限界だということが分かります。
一方、$p$の上限は、$p$が$q$の2倍の時に$1$を含むループの解があるのでこれが限界と言えるかもしれません。
とはいえ、$x$は$\frac{3}{2}$倍する回数、yは$\frac{1}{2}$倍する回数なのですから、$p$が増えると値の減少の方が大きくなっていきます。
周数の上限を見るためだけに$p$を大きくしてみましょう。
$q=100$
$p=300$
で考えると、
$x[1 \ldots n]$の合計値: $100$
$x[1 \ldots n]$の合計値: $300-100=200$
となります。
今度は$x$の方がボトルネックとなり、$n=100$のとき、$x[1 \ldots 100]$はすべて$1$で固定され、100周が限界となります。
従って「$q$と$(p-q)$の小さい方」が周数の限界となります。
検証コード例
JavaScriptで書きました。Node.jsで試しましたが、ブラウザでも動くかもしれません。
並列化とか、見込みのない計算を省くとかはしていません。
// Copyright © 2024 https://qiita.com/tanin_no_sorani
// Released under the MIT license. (https://opensource.org/license/mit)
'use strict';
// qに対する「0 < (2^p - 3^q)」を満たす最小のpとの組み合わせを順に確認する
// (p=2*q のとき全変数が1の解(1を含むループ)があり、このコードでは「p=2,q=1」「p=4,q=2」で解として出力される)
for (let q = 1; ; q++) { // 3^qのq
const p = Math.ceil(Math.log2(3) * q); // 2^pのp (2進数での桁数が3^qより1多くなる値)
console.log(`p=${p} q=${q}`);
check(p, q);
}
// 現在の(p,q)の組み合わせで探す処理
function check(p, q) {
const max = Math.min(q, (p - q)); // 最大周数 (小さい方は、最大周数の際に配列の値がすべて1となる)
const denominator = (2n**(BigInt(p)) - 3n**(BigInt(q))); // 分母 2^p - 3^q
for (let n = 1; n <= max; n++) { // 各周 (周数が浅いとほぼ分子＜分母のため、絞りたい場合はここ)
// 分母の値を変えず、各変数への振り分けパターンをすべて列挙する (n周のときx[1..n],y[1..n]の変数がある)
each_pattern(n, q, x => { // x[1..n] それぞれ1以上 合計値 q 両方の累乗に出てくる変数
each_pattern(n, p - q, y => { // y[1..n] それぞれ1以上 合計値 p-q 2の累乗の方にのみ出てくる変数
const numerator = calc_numerator(x, y, n); // 分子を計算 (別関数)
const quotient = numerator / denominator; // 分子/分母 の商
const remainder = numerator % denominator; // 分子/分母 の余り
//console.log(` x=[${x.slice(1)}] y=[${y.slice(1)}] quotient=${quotient} remainder=${remainder}`);
// 割り切れた場合は出力
if (remainder === 0n) { console.log(`[found] p=${p} q=${q} quotient=${quotient} x=[${x.slice(1)}] y=[${y.slice(1)}]`); }
}) });
}
}
// 各変数への値の振り分けパターンをすべて列挙する
// 例 (3,5): [3,1,1] [2,2,1] [2,1,2] [1,3,1] [1,2,2] [1,1,3]
// (4,7): [4,1,1,1] [3,2,1,1] [3,1,2,1] [3,1,1,2] [2,3,1,1] [2,2,2,1] [2,2,1,2] [2,1,3,1] [2,1,2,2] [2,1,1,3] [1,4,1,1] ... [1,1,1,4]
function each_pattern(n, total, callback) {
const leaf = Array(n + 1).fill(1n); leaf[0] = 0n; // 数式の添字と合わせるため[0]は使わず[1]から使用している
let depth = 0 ; // 現在の深さ
const max = (total - n); // 深さの最大
const branch = Array(max).fill(0); // 各分岐でどの位置を選択したかを保持
function forward() { leaf[++branch[ depth++]]++; } // 選択処理
function rewind () { leaf[ branch[--depth ]]--; } // 巻き戻し処理
for (;;) {
if (depth < max) { forward(); continue; } // 選択途中 (branch配列の状態から決定)
callback && callback(leaf); // 通知
rewind(); // 少なくとも一手は戻す
while ((0 <= depth) && (branch[depth] === n)) { rewind(); } // 最後の選択がleafの末尾の場合は、さらに何手でも戻す
if (depth < 0) { break; } // 全て列挙した場合は抜ける 例(4,7):branch[4,4,4] leaf[1,1,1,4] のとき上記でdepth=-1になる
// 次の選択位置の調整(上記で二手以上戻したとき作動する)
// 例(4,7): branch[1,4,4] leaf[2,1,1,3]のとき、上記でdepth=0まで戻るので、ここでbranch[1,1,1]と書き換えている
// 結果、この後forward()を3回呼ぶと branch[2,2,2] leaf[1,4,1,1] となる
for (let i = depth + 1; i < max; i++) { branch[i] = branch[depth]; }
}
}
// 分子を計算
function calc_numerator(x, y, n) {
let numerator = 0n;
for (let i = 1; i <= n; i++) { // 外側のΣ
let s2 = 0n; for (let j = 1; j <= (i - 1); j++) { s2 += (x[j+1] + y[j]); } // Σ 2の係数
let s3 = 0n; for (let j = i + 1; j <= n ; j++) { s3 += (x[j] ); } // Σ 3の係数
const base = (2n**(y[i]) - 1n); // 「2^(y[i]) - 1」
numerator += ((2n**s2) * (3n**s3) * base);
}
return numerator;
}
以下、出力例です。$p$が$q$の2倍になるとき、すべての$x$,$y$が$1$になるパターン(1を含むループ)が解として出力されています。
「$p=6,q=3$」なども試せばオール1の解が出力されます。
> node search_collatz_loop.js
p=2 q=1
[found] p=2 q=1 quotient=1 x=[1] y=[1]
p=4 q=2
[found] p=4 q=2 quotient=1 x=[1,1] y=[1,1]
p=5 q=3
p=7 q=4
p=8 q=5
p=10 q=6
...
おわりに
1以外のループする値が存在するならば、必ずこの式の解になっているはずです。
存在しないことを証明できるならそれでもよいのですが。
何か思いついたら追記なりするつもりです。
最後まで読んでいただきありがとうございました。