Records for the iteration $b_{i+1}=a \bmod b_i$

Question

A recent question and another question were both marked as duplicates of an older one which "has an answer."

That is not off base and the answer is very nice but is described as a long comment. It concerns asymptotic growth rate of an integer function. Here I ask a different question regarding specific records.

The question addressed in the others is this:

For each positive integer $a$ and $b \lt a$ define a decreasing sequence of positive integers by setting $b_0=b$ and $b_{i+1}=a \bmod b_i.$ Define $P(a,b)$ to be the length of this sequence (stopped when $b_n \vert a$ which would make $b_{n+1}=0.$)

The previous question is: Bound $\max{P(a,b)}$ in terms of $a.$

It is known that $P(a,b) = O(a^{1/3})$ and that infinitely often $P(a,b) > c \log a.$ The answer on the old question is offered as a long comment and gives a heuristic that $O(\log a)$ is the right order.

My question is:

• What are the known records for the smallest $a$ such that $P(a,b)=n$ for some $b?$
• What is known about the records in general.

In the OEIS are sequences A6538 for $a$ (it starts $1, 3, 5, 11, 11, 19$ ) and A6537 for $b.$ (it starts $1, 2, 3, 4, 7, 12$) giving the smallest $a$ and for each the smallest $b$ with $P(a,b)=n$ so the fifth entries note that for $b=11$ one has $7 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1.$ It turns out that no smaller $b$ gives a chain of length $5$ or even length $4$ which is why the $11$ is also in position four.

With the links in the entries the two lists are given up to $57$ with a comment from 2014 that $a=58017959$ suffices for length $58$ although perhaps some $10616759 \lt a \lt 58017959$ also gives that length.

So:

Are there now any more known record $a$ values or good but not provably minimum values? What features do the pairs $(a,b)$ have?

The more recent questions requested $a$ be prime. It doesn't seem helpful to restrict in that way although is does assure that the sequence ends $b_n=1.$ Many of the records, but not all, are prime. for example $58017959=523 \cdot 110933.$

Answer 1

Here is one observation, probably not new, which yielded a trajectory of length $64$ given at the end. It seems to be (one of the features) behind the known records.

The last numbers listed in A6538 are $10533599=2^53^25^2\ 7\ 11\ 19-1$ and $10616759=2^33^2\ 5\ 7\ 11\ 383-1$ for trajectories of lengths $56$ and $57$

The value mentioned as sufficient for length $58$ is $58017959=2^33^2\ 5\ 7^2\ 11\ 13 \ 23-1$

It is promising to have $a+1$ divisible by the least common multiple of the first few integers. Then $a \bmod b=b-1$ whenever $b$ divides $a+1.$

For example $N=2^53^35^27\ 11\ 13=21621600$ is divisible by all the integers up to $16$ so for $a=N-1=21621599$ a trajectory which arrives at $16$ will finish $15,14,13,12,11,10,9,8,7,6,5,4,3,2,1.$ Actually that wouldn't be optimal since $a-16=83\cdot 337\cdot 773$ so the preceding value would have to be a divisor of that number.

In fact the longest trajectories for that value of $a$ are $50$ iterations which is good but not a record. One can start at any one of $13122281, 13204151, 15955387, 16009967$ or $13780004.$ For the first four of those the trajectory ends

$346751, 123037, 90124, 81963, 65330, 62699, 53143, 45541, 35165, 30289, 25542, 13067, 8781, 2777, 2654, 2115, 2069, 549, 332, \mathbf{99, 98,\ 55, 54, 53}, 37, \mathbf{20, 19}, 17,\mathbf{ 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$ Where the transitions in boldface from $b$ to $b-1$ are explained by the fact that the $b$ are divisors of $a+1.$ The last starting value ends the same way starting at $99$ but arrives there

$338777,278648,165703,80209,45378,21671,15612,14591,12328,10615,9459,7784,5431,788,\mathbf{455,454},303,125$

The smallest $a$ allowing a trajectory of length $50$ is $131719=2^33\ 5\ 7\ 23\ 71-1$ The trajectory starting at $831180$ ends $\mathbf{71, 70, 69, 68},\ \mathbf{23, 22}, 19, \mathbf{14, 13}, 11,\mathbf{ 8, 7, 6, 5, 4, 3, 2, 1}.$

So you might reasonably wonder why I bothered with $21621599$ which is almost $16$ times as large as $131719.$

Taking instead $a=t\cdot 21621600-1$ will allow the same values with $b \mapsto b-1$ and some others. One might expect $t=17$ but it turns out to be better to use $a=19\cdot 21621600-1=410810399$ then any one of the starting values $247845109, 258990746, 261971136, 263955764$ allow $64$ iterations with a trajectory ending $37, \mathbf{28, 27, 26, 25, 24, 23}, \ \mathbf{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$

The part getting to $37$ is $1561, \mathbf{468, 467}, 306, 197, 192, \mathbf{95, 94}, 37$ for the first, $1499,\mathbf{455,454},327,299,246,239,230,\mathbf{39,38,37}$ for the next two and $\mathbf{1824, 1823}, 995, 769, 602, 181, 129, \mathbf{95, 94}, 37$ for the last one.

---

The actual exploring (which was far from optimal) that got to that length $64$ example was slightly different. It started (after a number of similar tries) with $1965600=2^5\ 3^3\ 5^2\ 7 \ 13$ then

$a=t\cdot 1965600-1$ would allow $28,27,26,25,24$ along with $16,15,14$ and $10,9,\cdots ,3,2,1$ and it turns out (after trying $t=1,2,3,4$ ) that $5\cdot 1965600-1=9827999$ allows $17,10,9,\cdots,1$

Then , in an attempt to have $18,17,10,\cdots$, I tried values $a=t\cdot 17 \cdot 1965600+ 9827999$ to find one with a small divisor for $a-18.$ It turned out that $t=2$ allowed $31$ , $t=4$ allowed $29$, $t=7$ allowed $23$ and also $41.$ finally $t=12$ allows $19,18,10,9,\cdots$ The best trajectories in those four cases are of length $52,49,54$ and $64$ respectively.

In fact that was a very inefficient way to arrive at that $a,$ The divisors $11,13$ for $a+1$ showed up, but not by design.

---

It is known that the least common multiple of the first $n$ integers (a function which changes only when $n$ is a prime or prime power) grows like $e^n$ so the fact that $P(a,b)$ can sometimes be as large as $\ln{a}$ follows from taking $b_1=n$ and $a=\mathop{lcm}(2,3,\cdots,n)-1.$ And it is likely that one can do better for that $a$ starting with a well chosen $b$ that eventually arrives at $n$ or a bit below it. And $a=t \cdot \mathop{lcm}(2,3,\cdots,n)-1$ might be even better.