A discrete iteration related to Pierce expansions

Importance: Medium ✭✭
Author(s): Shallit, Jeffrey O.
Subject: Number Theory
Keywords: Pierce expansions
Recomm. for undergrads: yes
Prize: $50 USD
Posted by: shallit
on: June 11th, 2008

\begin{conjecture} Let $a > b > 0$ be integers. Set $b_1 = b$ and $b_{i+1} = {a \bmod {b_i}}$ for $i \geq 0$. Eventually we have $b_{n+1} = 0$; put $P(a,b) = n$.

Example: $P(35, 22) = 7$, since $b_1 = 22$, $b_2 = 13$, $b_3 = 9$, $b_4 = 8$, $b_5 = 3$, $b_6 = 2$, $b_7 = 1$, $b_8 = 0$.

Prove or disprove: $P(a,b) = O((\log a)^2)$.


The best upper bound is currently $P(a,b) = O(a^{1/3})$. For more information, see [ES].


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[ES] P. Erd\"os and J. Shallit, ``New bounds on the length of finite Pierce and Engel series'', S\'eminaire de Th\'eorie des Nombres de Bordeaux 3 (1991), 43--53.

* indicates original appearance(s) of problem.

A different upper bound

This paper shows an upper bound of $O(\sqrt[3]a \sqrt[3]{\log(a)})$.

Edit: But looking at the title page of the paper, I see you already knew that ;)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.