Newman-Conway Sequence

The sequence 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, ... (Sloane's A004001) defined by the recurrence ,

$\begin{displaymath} P(n)=P(P(n-1))+P(n-P(n-1)). \end{displaymath}$

It satisfies

$\begin{displaymath} P(2^k)=2^{k-1} \end{displaymath}$

and

$\begin{displaymath} P(2n)\leq 2P(n). \end{displaymath}$

References

Bloom, D. M. ``Newman-Conway Sequence.'' Solution to Problem 1459. Math. Mag. 68, 400-401, 1995.

Sloane, N. J. A. Sequence A004001/M0276 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.