Who occupies the billionth position?

Consider a sequence in which 1 appears once, 2 appears twice, 3 appears three times, and so on. Which number is exactly in the billionth position? The interval occupied by each number gives the answer without constructing a billion terms.

This paper was originally prepared for the 2011-2012 Newly Appointed Teachers Course and printed on 15 May 2012.

1. Summary

This paper corrects the solution attributed to Ferdinando Arzarello for UMI: 44722 is not the correct result. The exact answer is 44721. The crucial point is that the number n does not occupy one position, but a whole interval of n positions.

2. The problem

Consider the following sequence of natural numbers:

1  2 2  3 3 3  4 4 4 4  5 5 5 5 5  6 6 6 6 6 6  ...

The number 1 is written once, 2 twice, 3 three times and, in general, n is written n times. The question is: what is the billionth term of this sequence?

3. A solution using intervals

To find the final position of 4, for example, add the first four numbers:

1 + 2 + 3 + 4 = 10

Gauss’s formula gives the final position of the block containing n:

end(n) = n(n + 1) / 2 = (n² + n) / 2

The block contains n terms, so its starting position is its final position minus n - 1:

start(n) = n(n + 1) / 2 - (n - 1)
         = n(n - 1) / 2 + 1
         = (n² - n + 2) / 2

The number n occupies every position, inclusive, from (n² - n + 2)/2 through (n² + n)/2.

4. Checking with a spreadsheet

In Excel, or any spreadsheet, create three columns: n, starting position, and final position. The first rows show how the intervals grow; the final two are decisive.

The exact answer is the smallest integer n such that end(n) ≥ 1,000,000,000: that integer is 44721. Position 1,000,000,000 does belong to the interval for 44721. The number 44722 starts only at position 1,000,006,282, beyond the billionth term. Failing to state that there is an interval of positions can easily cause confusion.

5. Modelling and approximation

Let I be the starting position and F the final position of the block for n:

I = (n² - n + 2) / 2
F = (n² + n) / 2

2I = n² - n + 2
2F = n² + n
2I + 2F = 2n² + 2
I + F = n² + 1
n² = I + F - 1

If M = (I + F)/2 is the mean of the positions occupied by the number, then:

n² = 2M - 1

The square of n is exactly twice the mean position minus 1. Since the functions involved are increasing, replacing M with a smaller number gives an underestimate, while replacing it with a larger number gives an overestimate. Without knowing the starting and final positions, we cannot know on which side the approximation falls.

In this case, using one billion directly as the reference value gives:

√(2 · 1,000,000,000)     = 44,721.3595499958
√(2 · 1,000,000,000 - 1) = 44,721.3595388155

Both values are extremely close to the integer solution 44721. For n = 44721, the mean position is:

M = (999,961,561 + 1,000,006,281) / 2
  = 999,983,921

Because 1,000,000,000 is greater than this mean, 44,721.3595388155 is an overestimate. The interval check finally proves without ambiguity that the billionth term is 44721.

Prepared by Salvatore Mosaico.