47
$\begingroup$

Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have thought about it. As I'm getting older, I now offer a cash prize for anyone who can make new progress.

The problem concerns the number of steps in an extremely simple algorithm. Let $a, b$ be positive integers with $a > b$. Set $b_0 = b$, and for $i \geq 1$ define $b_i = a \bmod b_{i-1}$. Since in general $x \bmod y < y$, this means $b_0 > b_1 > \cdots$ and so eventually $b_n = 0$. Define $P(a,b) = n$ in this case. Thus, for example, $P(35,22) = 7$, since $b_0 = 22$, $b_1 = 35 \bmod 22 = 13$, $b_2 = 9$, $b_3 = 8$, $b_4 = 3$, $b_5 = 2$, $b_6 = 1$, $b_7 = 0$. This looks superficially like the Euclidean algorithm for the gcd, but behaves quite differently.

Question: how big is $P(a,b)$ as a function of $a$? The upper bound $P(a,b) = O(a^{1/3})$ is known and the lower bound $P(a,b) > c \log a$ for infinitely many $a$ is also known. (See, for example, http://archive.numdam.org/ARCHIVE/JTNB/JTNB_1991__3_1/JTNB_1991__3_1_43_0/JTNB_1991__3_1_43_0.pdf - my first and only paper with Erdos, and https://cs.uwaterloo.ca/research/tr/1996/21/cs-96-21.pdf .)

I offer US \$200 for any significant improvement to either the upper or lower bounds. If I had to guess, I'd say probably $P(a,b) = O((\log a)^2)$.

One reason why this is interesting is because $P(a,b)$ is essentially the length of the "Pierce expansion" for $b/a$, which is an alternating series expansion of the form ${1 \over {x_1}} - {1 \over {x_1 x_2}} + {1 \over {x_1 x_2 x_3}} - \cdots$.

$\endgroup$
9
  • 2
    $\begingroup$ Here's something that might be worth at least $2: I'm seeing some vague similarities between this problem and the one's complexity problem. Let S_r be the set of those a for which P(a,b) <= r for all b < a, and with equality for at least 1 b. The sequence of S_r bears some resemblance to sequence of T_r, the set of numbers with one complexity = r (see arxiv:1404.2183 by de Reyna and van de Lune for a recent treatment). In particular, max S_r = 2,6,24,72,240,720,2880,6720,9240 for r from 1 through 9. Gerhard "But Wait! There is More!" Paseman, 2014.04.23 $\endgroup$ Apr 23, 2014 at 17:14
  • $\begingroup$ Min S_r is 1,3,5,13,11,19,35,47,53,95, 103,179,251,299,503,743,1019,1319,1439,2939, 3359,3959,6619,5387,5879, a mostly monotonic sequence for r from 1 to 26, with several entries of high integer complexity. I would set this problem in front of those working on integer complexity and see what they think. (Of course, these are results from a quickly written and possibly error prone program. The line of attack should still be worth pursuing.) Gerhard "Is It Coincidence, Or Murder?!?" Paseman, 2014.04.23 $\endgroup$ Apr 23, 2014 at 17:21
  • $\begingroup$ Also, for each a in S_r, I suspect the smallest b for which P(a,b)=r satisfies a < 2b < a + O(log^2 a), but I have not verified this yet. Gerhard "Just Adding My Two Cents" Paseman, 2014.04.23 $\endgroup$ Apr 23, 2014 at 17:27
  • $\begingroup$ Now that I spent minutes in the lab, I've spent seconds reading the 1996 pdf which reproduces the results in the comments above, except that max S_9 is 20160, and my table for min S_r measures something slightly different. I imagine the $2 connection has already been explored. Gerhard "Decades Late, Two Dollars Short" Paseman, 2014.04.23 $\endgroup$ Apr 23, 2014 at 17:38
  • 1
    $\begingroup$ Zachary Chase and Mayank Pandey have recently posted a preprint to the arXiv, arxiv.org/abs/2211.08374 , where they improve the upper bound from 1/3 to 1/3-2/177. $\endgroup$ Nov 24, 2022 at 23:26

1 Answer 1

9
$\begingroup$

Very nice question! This is a (long) comment, not an answer

I found a heuristic suggesting the lower bound is sharp, and wonder if you have some reason to doubt it. The model is that given $n$ and $a_k$, $a_{k+1}$ is uniformly chosen from the set $\{0,\ldots,a_k-1\}$. Alternatively, $a_{k+1}=\lfloor Ua_k\rfloor$, where $U$ is a uniform random variable. So you're asking starting from somewhere in the range 1 to $a$, how many $U$'s do you have to multiply before you get 0 (integer part). You can check quickly that the probability you don't get 0 after multiplying $100\log a$ terms is $O(a^{-K})$ for some reasonably large power.

So even accounting for the a different values of $b$, the probability that any of them lead to a chain of length 100$\log a$, is $O(a^{1-K})$. Since this is summable, by Borel-Cantelli, there is $a_0$ such that for all $a\ge a_0$, there's no chain of length $100\log a$.

$\endgroup$
1
  • 5
    $\begingroup$ Yes, this is a good heuristic. I used a version of it to prove some (pretty easy) theorems about the "metric" version of the algorithm, where you start with a real number $x \in (0,1)$ and you repeatedly apply the operation $1 \bmod {}$ to it. See fq.math.ca/Scanned/24-1/shallit.pdf . But I don't know how to convert these metric ideas to a proof in the integer case. The available numerical evidence suggests a growth rate very slightly greater than $\log a$, but the available evidence is admittedly rather weak. $\endgroup$ Apr 24, 2014 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.