コラッツ数列の偶奇の順から、初期整数を求める

ある日の晩に考えた事の走り書き。

コラッツの問題

コラッツ予想、3n+1問題など、いくつか呼び名があるが、ここではコラッツの問題で通していく。

任意の正の整数nに対し、nが偶数ならばnを2で割り、nが奇数ならば3をかけて1を足す操作を行う。

どのようなnに対しても、この操作を繰り返せば1に到達するか？

試しに、3でやってみる。

3->10->5->16->8->4->2->1

たしかに、1になった。

この操作によって得られた数列をコラッツ数列と呼ぶ。

本記事の内容

奇数nの3n+1は必ず偶数になる。これでは、任意の数列を考える上でめんどくさいので、以降は3n+1を$\frac{3n+1}{2}$に変更したコラッツショートカットを用いることにする。

コラッツショートカット、3の場合(かっこの中は、3n+1の値)

3->(10)5->(16)8->4->2->1

これを偶奇の順に直すと、奇奇偶偶偶偶となる。(1は除いた)

コラッツショートカットの操作は、整数nから数列を取り出す。

逆に、この偶奇の順から、nを導出する方法を考えてみたい。

問題文としてはこんな感じ。

任意の偶奇の順に対し、コラッツの問題が成り立つ初期整数nは求める方法は？

まあ、1から逆算すればすぐ求まるのだが、もう少し数式で考えてみる。

準備

<偶奇の順の表現>

偶数を0、奇数を1として、順を表現する。

奇奇偶偶偶偶->110000

そして、それを逆順にし、先頭に並ぶ0を消去する

110000->000011->11

(補足)
先頭に並ぶ0を消去したのは、(ある程度分かり切った)存在しない偶奇の順序を省く意図がある。
0を省略しなかった場合、例えば001(奇遇遇)の順序を持つnが存在しないことは、1から逆算すれば分かる。

n->(8)4->2->1

コラッツの問題のルールより、nは、3n+1=8となる奇数だが、そのようなnは存在しない。

また、01の並びを2進数として見ることで、一つの整数で表せる利点もある。

(その方がプログラムが書きやすいはず)

<$C_{ord}$関数>

$ f_1(n)=\frac{3n+1}{2}$、$f_0(n)=\frac{n}{2} $とし、
$f_1$と$f_0$をord順で合成したものを、$C_{ord}(n)$とする。

$C_{ord}(n)$は、ordの桁数をL、1の数をk、ある定数をAとして、次のように表せる。

$C_{ord}(n) = \frac{3^{k}n+A}{2^{L}}$

(数列の奇数の数だけ、3n+1が行われるので、分子、nの係数は3^k
数列の長さだけ、n/2が行われるので、分母は2^Lとなる)

例えば、ord=1010の場合、$C_{ord}(n)$は以下のようになる。

$C_{1010}(n)$
$=f_1(f_0(f_1(f_0(n))))$
$=f_1(f_0(f_1(n/2)))$
$=f_1(f_0(\frac{3(n/2)+1}{2}))$
$=f_1((\frac{3(n/2)+1}{2})/2)$
$=\frac{3((\frac{3(n/2)+1}{2})/2)+1}{2}$
$= \frac{3^{2}n+14}{2^{4}}$

式変形

偶奇の順ordから、nを求めるには、$C_{ord}(n)=2^{u}$をnについて解けばよい。

(コラッツ数列を求める操作において、2の累乗が出れば、あとは1になるまで偶数のみであるため)

以下、式変形

$\frac{3^{k}n+A}{2^{L}}=2^{u}$
$3^{k}n+A=2^{u-L}$

(1) $n=\frac{2^{u-L}-A}{3^{k}}$

これがnを求める式である

u-Lの値は、一つ変形前の式に対し、mod 3^k をとることで、

(2) $2^{u-L}≡A \pmod{3^{k}}$

ordからA,k,が求められるので、この離散対数の式から、u-Lが求まる。

u-Lの値は一意ではないが、離散対数の周期性から、等差数列になる。

結論

偶奇の順ordから、整数nを求める手順は、

①ordから、$C_{ord}$関数のA,kを求める。

②$2^{u-L}≡A \pmod{3^{k}}$を用いて、u-Lを求める。

③$n=\frac{2^{u-L}-A}{3^{k}}$を用いて、nを求める。

u-Lが取り得る値は無限にあるので、nは無限に計算できる。

プログラム

pythonでコードを実装した。

from math import *

#離散対数
def DLP(q,p,m):      
    xs=[]
    for x in range(2*p):
        if(q**x%p==m%p):
            xs.append(x)
        if len(xs)==2:
            return xs[0],xs[1]-xs[0]

#Clz関数をordから求める
#return L,K,A
#Clz(N)=(3^K*N-A)/2^L
def ClzByOrd(ord):
    L,K,A=0,0,0
    while ord != 0:
        if ord%2==1:
            A=3*A+2**L
            K+=1
        L+=1
        ord=int(ord/2)
    return L,K,A

#OrdからNを求める
def NsByOrd(ord):
    L,K,A=ClzByOrd(ord)
    u_minus_L,T=DLP(2,3**K,A%3**K)
    Ns,ERs=[],[]
    #変数サイズが許す限り計算
    try:
        while True:
            N=int((2**u_minus_L-A)/3**K)
            #check
            if N>0:
                if ord==OrdByN(N):
                    Ns.append(N)
                else:
                    ERs.append(N)
            u_minus_L+=T
    except:
        return Ns,ERs

#Nからordを求める(チェック用)
def OrdByN(N):
    if N<=1:
        return None
    ord=0
    b=0
    while N !=1:
        if N%2==1:
            N=int((3*N+1)/2)
            ord+=2**b
        else:
            N=int(N/2)
        b+=1    
    return ord

if __name__=='__main__':
    #ordが0から1001まで,nを計算
    for ord in range(10):
        Ns,ERs=NsByOrd(ord)
        if len(Ns)==0:
            continue
        print(Ns[:10],bin(ord))

感想

計算するだけなら、深さ優先探索の方が速そう。(身も蓋もない)

離散対数が絡んでくるのは、個人的に楽しい発見だった。

思考メモ

ときたま、考えたことを出力する。