8
$\begingroup$

In a recent question the following recursive sequence was considered: $ a_{n+1} = \cases{\frac{a_n}{2} & $a_n$ is even \\ a_n +d & $a_n$ is odd}, \quad a_1 = d + 1 $ where $d$ is an odd positive integer. Such a sequence will eventually reach $1$, and let $m(d)$ be the value of the index, where the sequence element equals one, $a_m = 1$. Here is a visualization of $m(d)$: Plot of the length of Collatz-like sequence as a function of parameter d

It is apparent from the plot that $m(d) \leqslant 3 \left\lfloor \frac{d-1}{2} \right\rfloor$. Selecting those $d$ which saturate the bound: enter image description here OEIS tells us that this is sequence A001122 of "primes with primitive root $2$".

This begs for an explanation. References, intuitive insights, solutions are welcome.

  • 0
    I think the [answer](http://math.stackexchange.com/a/183311/11069) of @SamL. to the linked question also answers this one. I hope he posts the solution here, otherwise I will fill in the answer in few days.2012-08-16

1 Answers 1

4

Instead of the sequence $a_n$, let us look at the following related sequence:

$b_0 = 1, \qquad b_{k+1} = \begin{cases} \dfrac{b_{k}}2 & (b_{k}\text{ even}) \\[6pt]\dfrac{b_{k}+d}2 & (b_{k} \text{ odd})\end{cases}$

Since $d$ is odd, we can write it in the form $d = 2n-1$ for some natural number $n\ge 1$. By a simple induction argument, we see that $0 for all $n$. So that

$b_k = 1\quad \iff\quad b_k\equiv 1 \pmod d$

Since $2n = d + 1 \equiv 1 \pmod d$, it follows that $\frac 12 \equiv n \pmod d$ and hence that the sequence $b_k$ satisfies

$ b_k \equiv n^k \pmod d$

But then the smallest integer $k\ge 1$ such that $b_k=1$ is given by $k=\mathrm{ord}_{\mathbb Z_d^\times}(n)$, the order of $n$ in $\mathbb Z_d^\times$. Remember that $n \equiv 2^{-1}$, so $\mathrm{ord}_{\mathbb Z_d^\times}(n) = \mathrm{ord}_{\mathbb Z_d^\times}(2)$.

How does this relate to the initial sequence $a_n$?

The sequence $b_k$ meets each element of $\mathbb Z_d^\times$ at most once and therefore – for the sequence $a_k \pmod d$ – we must have that each odd element in $\mathbb Z_d^\times$ (when represented by $\mathbb Z_d^\times \subset \{1, \dots, p-1\}$) is visited exactly twice or never, each even element at most once. Hence we obtain the following formula for the length $m(d)$ of the sequence $a_k$, until reaching $1$:

Formula for $m(d)$: \begin{align} m(d) &= 2\cdot (\# \text{ of odd elements in }\langle 2 \rangle\subset \mathbb Z_d^\times ) + (\# \text{ of even elements in }\langle 2 \rangle \subset\mathbb Z_d^\times ) \end{align}

In particular, this shows that if $2$ is a primitive root of $\mathbb Z_d^\times$ for $d$ prime, then $m(d) = 2 \frac{d-1}2 + \frac{d-1}2 = 3\left\lfloor \frac{d-1}{2}\right\rfloor$ and if $2$ is not a primitive root, or $d$ is not a prime, then $m(d) < 3\left\lfloor \frac{d-1}{2}\right\rfloor$. $\quad \square$