# improving known bounds for Pierce expansions; cash prize

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$. - 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 –  Gerhard Paseman Apr 23 at 17:14
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 –  Gerhard Paseman Apr 23 at 17:21
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 –  Gerhard Paseman Apr 23 at 17:27