MathDB

Prove that for every positive integer

n,

there is a sequence of integers

a_0,a_1,\dots,a_{2009}

with a_0\equal{}0 and a_{2009}\equal{}n such that each term after

a_0

is either an earlier term plus

2^k

for some nonnnegative integer

k,

or of the form

b\mod{c}

for some earlier positive terms

b

and

c.

[Here

b\mod{c}

denotes the remainder when

b

is divided by

c,

0\le(b\mod{c})<c.

]

B6