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.

add new comment