TOPICS
Search

Self-Counting Sequence

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The self-counting sequence is the sequence in which each positive integer k occurs k consecutive times, beginning with 1. Its first terms are 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ... (OEIS A002024). For a positive integer n, the nth term a(n) is given by

a(n)=|_1/2+sqrt(2n)_|
(1)
=[1/2(sqrt(8n+1)-1)],
(2)

where |_x_| is the floor function and [x] is the ceiling function (Graham et al. 1994, p. 97). The sequence is also given by the recurrence relation

a(n)=1+a(n-a(n-1))
(3)

for n>=2, with a(1)=1 (Wolfram 2002, p. 129).

Explore with Wolfram|Alpha

References

Gould, H. W. "Solution to Problem 571." Math. Mag. 38, 185-187, 1965.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Exercise 3.23 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, p. 97, 1994.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, p. 43, 1997.Sloane, N. J. A. Sequence A002024/M0250 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 129, 2002.

Referenced on Wolfram|Alpha

Self-Counting Sequence

Cite this as:

Weisstein, Eric W. "Self-Counting Sequence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Self-CountingSequence.html

Subject classifications