**************************************
* Proof that A101402(n) = Theta(n)
* Benoit Jubin, 16 september 2014
**************************************

In the following, we write a = A101402.

The definition of a(n) shows that terms are gathered in blocks 2^k < n <= 2^{k+1}.

For n >= 3, one has
a(2^n)       = a(2^{n-1}) + a(2^{n-1}-1)
a(2^{n-1}-1) = a(2^{n-2}) + a(2^{n-2}-2)
...
a(2^{n-k}-k) = a(2^{n-k-1}) + a(2^{n-k-1}-k-1)
...
as long as 2^{n-k} - k > 2^{n-k-1}.
Else, 0 <= a(2^{n-k}-k) <= a(2^{n-k-1}).

The condition 2^{n-k} - k > 2^{n-k-1} is equivalent to k 2^k < 2^{n-1}, that is, k < W(2^{n-1}),
where W is the base-2 Lambert function, defined implicitly by W(x) 2^{W(x)} = x.

Putting these together, we obtain
a(2^n) = a(2^{n-1}) + a(2^{n-2}) + ... + a(2^{n-ceil(W(2^{n-1})))+a'(n)
with 0 <= a'(n) <= a(2^{n-1-ceil(W(2^{n-1}))}).

We set u(n) = a(2^n).
Therefore,
u(n) = u(n-1) + u(n-2) + ... + u(n-ceil(W(2^{n-1}))) + a'(n)
with 0 <= a'(n) <= u(n-1-ceil(W(2^{n-1}))).

For n -> +infinity, one has W(2^{n-1}) = n - log_2(n) - 1 + o(1).
This implies that u = Theta(A246878).
It is proved in the entry for A246878 that A246878(n) = Theta(2^n).
Therefore, a(2^n) = Theta(2^n).
Since a is nondecreasing, this implies a(n) = Theta(n).