a,b を整数とする。このとき
a と b のコラッツ展開が少なくとも第 n 項まで等しい ⇔ a≡b (mod 2^n)
証明
n=1の場合
コラッツ展開の初項が等しい ⇔ a と b の偶奇が等しい
より成り立つ。
n=m まで成り立つとして、n=m+1 の場合を示す。
左⇒右:
少なくとも第 m 項まで等しいので、ある整数 k を用いて
a=b+2^m*k
と表せる。a,b にコラッツ操作を m 回施して得られる数を a', b' とすると、前補題より
a'=b'+3^e*k （e は非負整数）
と表せる。仮定より、a' と b' の偶奇は等しいので k は偶数。
よって a≡b (mod 2^(m+1))
右⇒左:
整数 k を用いて
a=b+2^(m+1)*k
と表せる。a,b にコラッツ操作を m 回施して得られる数を a', b' とすると、前補題より
a'=b'+3^e*2k (e は非負整数)
と表せる。よって、a' と b' の偶奇は等しいので、a と b のコラッツ展開の第 m+1 項は等しい。□
系
整数 a,b に対し、両者のコラッツ展開が一致するならば a=b
