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

Bibliography

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