読者です 読者をやめる 読者になる 読者になる

1 から始めて 3x+1 と 4x+1 で生成される数の問題

ふと思い付いた問題ですが、自分ではよくわかりませんので、誰か解いて答えを教えてください。

\(x\) の初期値を \(1\) とします。
\(x\) に対して、次の操作 A または B を選んで、適用します。
A : \(x\) を \(3\) 倍してから \(1\) を加えます。(\(x:=3x+1\))
B : \(x\) を \(4\) 倍してから \(1\) を加えます。(\(x:=4x+1\))
これを任意の回数繰り返します。

例えば、最初に操作 B を行い(\( 1 \times 4 + 1 = 5 \))、次に操作 A を行うと(\( 5 \times 3 + 1 = 16 \))、 \(x\) の値は \(16\) になります。
これを、「 \(16\) の生成列は BA である」と表現します。

別の例として、 \(10000\) の生成列は ABBABBA です(確かめてみてください)。

ここで問題です。

異なる2つの生成列を持つような数は存在するでしょうか?
存在する場合には、例を示してください。
存在しない場合には、それを証明してください。

追記:寄せられた考察(2015年12月9日)

上記の問題に対して、何人かの方から、様々なアプローチの考察を頂きました。ありがとうございます。頂いた順に、結論だけ簡単にまとめて掲載します。(私の解釈に基づいて記載しているため、元々の表現と異なっていたり、結論自体が異なっているものもありますが、ご了承ください。また、最終的な結論の正しさが確認できないものについて、正しいと考えられる中間段階の結論を記載しているものもあります。)

  1. 最後の共通部分を取り除いた2つの異なる生成列の一方は A で終わり、もう一方は B で終わるため、生成される数は奇数である。
    ―― roiti (@roiti46)
  2. 最後の共通部分を取り除いた2つの異なる生成列を持つ数を \(36\) で割った余りは \(13\) である。
    ―― %20 (@henkoudekimasu)
  3. 2つの異なる生成列を持つ数は、4億以下には存在しない。
    ―― ろくかん松 (@rokukan)
  4. 最後の共通部分を取り除いた2つの異なる生成列の一方は AAAAAA で終わり、もう一方は BBB で終わる。
    ―― %20 (@henkoudekimasu)
  5. A のみからなる生成列と B のみからなる生成列とが同じ数を生成することはない。
    ―― %20 (@henkoudekimasu)
  6. 最後の共通部分を取り除いた2つの異なる生成列の一方は BBB で終わるので、生成される数を \(64\) で割った余りは \(21\) である。したがって、もう一方の生成列の最後の A の行う前の値を \(64\) で割った余りは \(28\) となる。
    ―― ぴろず (@p_shiki37)
  7. \( A = \begin{pmatrix} 3 & 1 \\ 0 & 1 \end{pmatrix} , B = \begin{pmatrix} 4 & 1 \\ 0 & 1 \end{pmatrix} \)
    と表現でき、これらを用いた2つの生成列を \( S_1 , S_2 \) とすると、
    \( {S_1}^{-1} S_2 = \begin{pmatrix} a & 1-a \\ 0 & 1 \end{pmatrix} \) の形になる。
    ―― ぬ (@nu4nu)
  8. 操作 A を \(3x+1\) の代わりに \(2x+1\) にした場合には、二進数で表した時に、 A は右に 1 を追加する操作、 B は右に 01 を追加する操作になるため、異なる生成列が同じ数を生成することはない。
    ―― roiti (@roiti46)
  9. 元の問題は、「\(n \ge 1 \) で定義される2つの異なる非負整数列 \( \{p[n]\},\{q[n]\} \) と正整数 \(X,Y \) であって、次を満たすものが存在するか」と同値。
    • \(p[1]=0,q[1]=1\) (「最後の操作が同じでない」と対応)
    • \( p[n+1]-p[n] \in \{0,1\} \) ( \(q\) も同様)
    • \( \sum_{k=1}^{X} 3^{p[k]} 4^{k-p[k]} = \sum_{k=1}^{Y} 3^{q[k]} 4^{k-q[k]} \)
    よって \( \#\{k|p[k]=0\} \equiv 0 \) mod \(3\) などが示される。
    ―― かならい (@sugarknri)

また、以下は私自身の考察です。

\(x\) の初期値を \(0\) にした場合、自明な解 A \(=\) B \(=1\) があります。
また、初期値を \(2\) にした場合、 ABAAAA \(=\) BBBBB \(=2389\) という解が見付かります(なので、解が存在しない証明で、初期値に依存せずに、このケースを含んでしまっているものは、誤りであることがすぐにわかります)。
初期値を他の自然数にした場合も含めて、これら以外に解は見付かっていません。