OIM

Demostrar que todo número natural $n\leq 2^{1000000}$ puede ser obtenido a partir de $1$ haciendo menos de $1100000$ sumas; más precisamente, hay una sucesión finita de números naturales \[x_0, x_1, \dots , x_k \text{ con } k\leq 1100000, x_0=1, x_k=n,\] tal que para cada $i=1,2,\dots ,k$, existen $r$, $s$, con $0\leq r\leq s \lt i$ y $x_i=x_r+x_s$.