info prev up next book cdrom email home

Newman-Conway Sequence

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

\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.




© 1996-9 Eric W. Weisstein
1999-05-25