Problem 3

A sequence of real numbers

a_0,a_1,\ldots

is said to be good if: (i)

a_0

is a positive integer; (ii) for each non-negative integer

i

a_{i+1}=2a_i+1

a_{i+1}=\frac{a_i}{a_i+2}

; (iii) there exists a positive integer

k

such that

a_k=2014

. Find the smallest positive integer

n

such that there exists a good sequence with

a_n=2014

Step 4 of 4: Compute the least return time

Previous step Next step

2015=5\cdot13\cdot31,\qquad \operatorname{ord}_{2015}(2)=\operatorname{lcm}(4,12,5)=60

Detailed analysis

The orders of two modulo 5, 13, and 31 are respectively 4, 12, and 5, since 2^5=32 is 1 modulo 31; the order modulo their product is their least common multiple, namely 60. The inverse orbit at step 60 has denominator one, so it supplies a good sequence, and no smaller positive step can do so.