How long iterations of $x \to (p \!\!\! \mod \!\! x)$ can be? [duplicate]

Question

Suppose that $p$ is a prime number and $x_1$ is an integer in range $[1, p - 1]$. If $x_k \not = 1$, define $x_{k + 1} := p \!\!\! \mod \!\! x_k$. Clearly, $x_{k + 1} < x_k$ and $x_{k + 1} > 0$ (because $p$ is prime), so there exists some $n$ (depending on $x_1$) such that $x_n = 1$. Is it true that $n = O(\log p)$?

For reference, it is quite easy to prove that $n = O(\sqrt p)$. Let $q_i := [\frac{p}{x_i}]$, i. e. $p = q_i x_i + x_{i + 1}$ for every $i \in [1, n - 1]$. Because $q_i x_i + x_{i + 1} = p = q_{i + 1} x_{i + 1} + x_{i + 2}$ for $i \in [1, n - 2]$ and $x_i > x_{i + 1}, x_{i + 1} > x_{i + 2}$, $q_i$ is increasing. On the other hand, $x_i$ is decreasing. Also $q_i x_i < q_i x_i + x_{i + 1} < p$ for every $i \in [1, n - 1]$. Therefore $q_i < \sqrt{p}$ or $x_i < \sqrt{p}$ for each $i \in [1, n - 1]$. Because $q_i$ increases, there can be at most $[\sqrt{p}]$ $i$-s with $q_i < \sqrt{p}$. The same way there can be at most $[\sqrt{p}]$ $i$-s with $x_i < \sqrt{p}$. Therefore $n \leqslant 2[\sqrt{p}]$.

Some ideas:

1. Maybe it makes sense to think backwards: i. e. how long can a sequence $y$ be if $y_1 = 1$ and $y_{i + 1}$ is some divisor of $p - y_i$ that is bigger than $y_i$ (in this notation $x_i = y_{n + 1 - i}$)?
2. One more way to look at this is to notice that the question asks to estimate how deep can a rooted tree on $p - 1$ vertices be, with root in $1$ and edges between $x$ and $p \!\!\! \mod \!\! x$ for $x = 2, 3, \ldots, p - 1$. Maybe it is possible to prove that this tree is somewhat balanced?
3. Two heuristics suggest that the number of steps is indeed $O(\log p)$: first one assumes that $p \!\!\! \mod \!\! x$ is a random integer number in range $[1, x - 1]$ and second one uses "backwards" point of view and assumes that $p - y_i$ is divisible by $t$ with probability $t^{-1}$. Of course, both heuristics don't make too much sense, but they show that $n = O(\log p)$ is at least a reasonable enough statement to consider.

In fact, any ideas on proving any bound better than $O(\sqrt{p})$ are appreciated.

Answer 1

Let $g(p)$ be the maximal value of $n$ for $x_1\in\{1,\dotsc,p-1\}$, and put $h(p)=g(p)/log(p)$. Here is a plot of $(p,h(p))$ for the first 2000 primes, together with the functions $13/\log(x)$ and $25/\log(x)$

The six points along the top correspond to the primes 5879, 9743, 10427, 13679, 16673, 16979 with $g(p)=25$. I could not find any other special properties of these primes, and OEIS does not recognise the list. For 20 primes centred at the Mersenne prime 524287, the minimum and maximum values of $h(p)$ are 1.898 and 2.354. In general, there does not seem to be anything special about the Mersenne primes, contrary to what I thought might be the case.

Answer 2

Here is an idea to pursue.

Fix $p$. I will call $p \bmod x$ (your dynamic) $d(x)$, and I look at $H$, the set of $x$ less than $p$ with $2*d(x) \gt x$. The dynamic can stay out of $H$ only a logarithmic number of times, so now we ask how attractive $H$ can be as a dynamic.

$H$ looks like a collection of intervals. Dividing everything by $p$, the set is like $(1/2,2/3)$ union $(1/3,2/5)$ union intervals of the form $(1/k, 2/(2k-1))$, for enough $k$ until you get bored. This is some constant fraction of $p$, so pretty large in logarithmic terms.

However, we don't have to be afraid of $H$. If $d$ visits $H$ and not $H$ alternately, $d$ still reaches $1$ in a logarithmic number of steps. (Indeed, we can set a number in $(1,\log p)$ as a goal to finish in logarithmic time, so I am not going to worry about the very end of the dynamic.) So let us consider when $x$ is in $H$ and $d(x)$ is also in $H$.

Suppose $x$ and $x+1$ are in $H$. Then $d(x+1)-d(x) \gt 1$ when $x \lt p/2$. So the set of $x$ less than $p/2$ which visit $H$ at least twice in a row is less than half the number of $x$ less than $p/2$ which visit $H$ at least once under $d$. If we start from a point less than $p/2$, then the chance it lands in $H$ is small, and the chance it lands in $H$ twice in a row by iterating $d$ gets very small. The idea is to analyze this region below $p/2$, and show that landing in $H$ at least $k$ times in a row is less than $(1/2)^k$ as likely as landing once. I leave the detail to others.

Now we turn our attention to $(2x \gt p)$. The question now is how long can one iterate $d$ and stay above $p/2$. But this happens for no $x$ less than $p$. So the ticket is to show the subsets of $H$ which are visited by $d$ at least $k$ times in a row grows exponentially small.

Gerhard "Seems Better Than Square Root" Paseman, 2018.07.18.