5

Given a prime number $p$ and an integer $0<a_0<p$. Consider a sequence $a_i=p \mod a_{i-1}$. How to estimate the smallest $i$ where $a_i=1$?

I tried some prime numbers, and found that such $i$ is always small. I have never found an $i$ larger than 50 when $p$ is smaller than $10^7$. How to estimate the upper bound of $i$?

Chris Wuthrich
  • 8,341
zbh2047
  • 601
  • 1
    If $a_i=1$, then $a_{i+1}=0$, and $a_{i+2}$ is undefined, so the smallest $i$ such that $a_i=1$ is the only $i$ such that $a_i=1$. Or do you mean the smallest $i$ as you vary $a_0$, keeping $p$ fixed? – Gerry Myerson Feb 06 '18 at 11:26
  • I had the same question. Probably my edit was not useful. There is a unique $i$ such that $a_i=1$. Do you want a bound on $i$ depending on $p$ and $a_0$ or only on $p$? The latter would rather be the "largest" $i$ for a fixed $p$ and varying $a_0$. – Chris Wuthrich Feb 06 '18 at 11:39
  • I mean the only $i$ such that $a_i=1$. In fact, I just wonder why such $i$ are always small, for any $p$ and $a_0$. I guess such $i$ is equal to $O(\log p)$, for example. – zbh2047 Feb 06 '18 at 12:43
  • I want a bound which only depends on $p$. That is, for any $0<a_0<p$, the bound is always correct. Your understanding and modification is really helpful. Thanks! – zbh2047 Feb 06 '18 at 12:48
  • It is likely that the answer is $O(\sqrt{p})$. Note that for a_j greater than $\sqrt{p}$ that the difference between successive a_j grows by a multiplicative factor, so it takes roughly $(\log p)^2$ at most to get a_j down to $\sqrt{p}$. I imagine the rest of the journey to 1 is almost as quick. Gerhard "Look At The Step Size" Paseman, 2018.02.06. – Gerhard Paseman Feb 06 '18 at 16:02
  • Is there a tight bound of $p$? $\sqrt p$ is about 3000 when $p=10^7$, but results shows that it is never larger than 50. – zbh2047 Feb 07 '18 at 09:22
  • 3
    Jeffrey Shallit has asked essentially the same question (with partial results and a cash prize) here: https://mathoverflow.net/questions/164129/improving-known-bounds-for-pierce-expansions-cash-prize – Ravi Boppana Feb 07 '18 at 21:05

1 Answers1

1

This is a long comment rather than an answer.

Let $p$ be a prime. Consider the map $f(a)$ which assigns to $0<a<p$ the remainder of $p$ modulo $a$. The questions asks when the sequence $a$, $f(a)$, $f(f(a))$,... reaches $1$ for a starting $1<a<p$. Let $I(p)$ be the length of the longest such sequence as $a$ varies in $1<a<p$. The question asks for an upper bound on $I(p)$.

In average, we expect that $f(a)$ is half of $a$. So we should expect sort of $\log_2(p)$ steps in $a$, $f(a)$, $f(f(a))$, ... to reach $1$.

We can look at it the other way. What are the $a$ such that $f(a)=b$? Any such $a$ will be a divisor of $p-b$. Now we build a tree with root $1$. The branches to $1$ are all divisors of $p-1$ except $1$. Repeatedly, we put above any $b$ so far added to the tree all the divisors of $p-b$ which did not yet appear. The length of the longest path from the root is $I(p)$.

Since there are at most $\log_2(p)$ branches above each number, one gets (if I got that right) that $I(p)> C \log(p)/\log\log(p)$. On the other hand we expect less than $\log(p)$ branches in average, that would again confirm that $I(p)$ might be bounded by something like $O(\log(p))$. But I am not certain; it might be larger. Most likely though the averge of $I(p)$ is logarithmic in $p$.

This also illustrates that primes $p$ where $\tfrac{p-1}{2}$ is a Sophie Germain prime are likely to have a larger $I(p)$ while $p$ where $p-1$ has many factors should have smaller $I(p)$.

Chris Wuthrich
  • 8,341