MathDB

Terms in a sequence divisible by 3^2011

Source: Canadian Repêchage 2012: Problem 5

May 19, 2014

number theory proposednumber theory

Problem Statement

Given a positive integer

n

, let

d(n)

be the largest positive divisor of

n

less than

n

. For example,

d(8) = 4

and

d(13) = 1

. A sequence of positive integers

a_1, a_2,\dots

satisfies

a_{i+1} = a_i +d(a_i),

for all positive integers

i

. Prove that regardless of the choice of

a_1

, there are inﬁnitely many terms in the sequence divisible by

3^{2011}