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$.

3more comments