MathDB

Show that every natural number

n\leq2^{1\;000\;000}

can be obtained first with 1 doing less than

1\;100\;000

sums; more precisely, there is a finite sequence of natural numbers x_0,\ x_1,\dots,\ x_k\mbox{ with }k\leq1\;100\;000,\ x_0=1,\ x_k=n such that for all

i=1,\ 2,\dots,\ k

there exist

r,\ s

with

0\leq{r}\leq{s}<i

such that

x_i=x_r+x_s

Problem Statement