1994 OIM Problems/Problem 6

Problem

Show that every natural number $n \le 2^{1,000,000}$ can be obtained after 1 by doing less than 1,100,000 additions; more precisely, there is a finite sequence of natural numbers

\[x_0, x_1, \cdots , x_k \; \text{with }\; k \le 1,100,000,\; x_0=1,\; x_k=n,\]

such that for each $i=1,2, \cdots ,k$, there exist $r$, $s$, with $0 \le r < i$, $0 \le s$, $0 \le i$, and $x_i=x_r+x_s$.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

See also

https://www.oma.org.ar/enunciados/ibe9.htm