退出

Why does repeatedly prepending a fixed bit-block converge the Collatz step-count difference to the block's own length?

数论 Math StackExchange 0 票 0 回答 59 浏览 提问者: MAEDA AKIHIRO 2026-07-24 09:42
number-theory elementary-number-theory p-adic-number-theory collatz-conjecture experimental-mathematics

问题内容

I've been experimenting with a self-similar construction for the Collatz map (the $n \to n/2$ / $n \to 3n+1$ function) and found a pattern I can partially — but not fully — explain. I'd appreciate a sanity check and any pointers to relevant literature.

Construction. Fix an odd integer $x$ with bit length $L$. Define a sequence by repeatedly prepending $x$ to the front (most significant bits) of the previous term:

$$N_1 = x, \qquad N_{k+1} = (x \ll \operatorname{bitlength}(N_k)) \mathbin{|} N_k$$

So $N_k$ is just $x$ written $k$ times in a row in binary (the base-$2^L$ analogue of a repunit). One can check this satisfies the exact closed form

$$N_{k+1} = 2^L \cdot N_k + x.$$

Let $\operatorname{steps}(n)$ be the Collatz total stopping time. Define $\operatorname{diff}_k = \operatorname{steps}(N_{k+1}) - \operatorname{steps}(N_k)$.

Empirical finding. For every one of 105 tested blocks $x$ (bit lengths 4–24: all-ones, alternating, random, and known "delay record" values), the most frequent value of $\operatorname{diff}_k$ converges (with increasing frequency as $k$ grows) to exactly $L$, the block's own bit length — not to the ≈$7L$ that generic Collatz statistics would suggest (average total stopping time grows about 7 steps per bit for a "random" integer).

What I can prove. Since $N_{k+1} = 2^L N_k + x$, we get $N_{k+1} \equiv N_k \pmod{2^{Lk}}$. Combined with the standard fact that a number's first $m$ Collatz steps (its parity vector) are determined by the number mod $2^m$ (Lagarias; conjugacy map of Bernstein–Lagarias, Canad. J. Math. 1996), $N_k$ and $N_{k+1}$ are forced to share an identical sequence of odd/even steps for at least the first $Lk$ iterations (empirically even longer, ~$1.5Lk$).

What I can't prove. This shared-prefix argument explains why $N_k$ and $N_{k+1}$ move in lockstep for a long time, but not why the total step difference, after they eventually diverge, keeps landing on the small, $k$-independent value $L$ rather than scaling with the (growing) length of that shared prefix.

A clean special case. Blocks of the alternating form $x = 1010\ldots10$ ($L$ bits) give exactly 100% convergence (not just "usually"). These satisfy $3\cdot(x/2)+1 = 2^L$ exactly — i.e. $x$'s own trajectory lands precisely on $2^L$ (the power of two matching its own bit length) within 2 steps. A control test with numbers landing on unrelated powers of two (traced backward from $2^m$ for $m \ne L$) does not reproduce the 100% effect, so it really does seem to be this self-referential alignment between $x$'s trajectory and its own bit length that matters, not merely "reaching some power of two quickly."

Questions.

  1. Is there a clean argument (or known reference) for why $\Pr(\operatorname{diff}_k = L) \to 1$ as $k \to \infty$ for generic $x$?
  2. Is $3(x/2)+1 = 2^L$ exactly the condition for the 100% case, or are there other algebraic identities producing the same effect? Full write-up, code (Python), and raw data: https://github.com/5124053z-pixel/collatz

I'm aware this doesn't bear on the Collatz conjecture itself (true/false, existence of other cycles) — it's a narrower question about this specific self-similar family. Happy to add more numerical evidence if useful.

回答 (0)

暂无回答记录。