A sequence related to prime counting

The current note arose as an exploration branching off from the matter discussed in these earlier notes: this one and this one. As we saw before, Carl Gauss, while still in his teens, produced his first estimate of the prime number distribution in the form of the function:

Here is is the prime counting function, which counts the number of prime numbers up to a given number , and is the natural logarithm of . The notation indicates that the prime counting function is asymptotic with , i.e. as the ratio .

Subsequently, Gauss refined his fit for the prime counting function by using the famed logarithmic integral . We were curious if there was some arithmetic function, which was actually fitted by rather it being merely a single term approximation of the . In course of some arithmetic experiments, we stumbled upon a sequence, which we believe, without formal proof, is fitted by in terms of average behavior.

This sequence is defined thus: . Thereafter, add to all terms . Count how many of are primes. This count is . For example when we add 2-1=1 to 1 we get 2. Which is a single prime; hence, . Now for we add 3-1=2 to the first two terms and we get 3, 3. Thus, we have 2 primes; hence . For , we add 4-1=3 to the prior terms and get 4, 4, 5, which yields a single prime, 5; hence, . Thus, the first few terms of the sequence goes: 1, 1, 2, 1, 3, 1, 4, 1, 1, 2, 7, 2, 7, 1, 1, 4, 11, 3, 9, 2, 4, 4, 11, 0, 2, 4, 4, 11, 11, 6. Figure 1 shows a plot of the first 20000 terms of the sequence.

Figure 1

The blue line is the plot of this sequence and we notice right away that despite the fluctuations the average tendency is to grow with . Via numerical experiments we were able to establish that this average growth is fitted best by the function (red line in Figure 1). The green line in Figure 1 is the count of primes . We observe that though some extreme values of exceed , the average behavior of , i.e. . This relates to a central development in the number theory: when Gauss conjectured the asymptotic relationship between and the mathematical apparatus was not yet in place to prove it. This was finally developed by his last student Bernhard Riemann. Using those ideas, nearly century after Gauss’ conjecture, Hadamard and de la Vallée-Poussin proved it and it became known as the Prime Number Theorem. Further, de la Vallée-Poussin showed that was related to thus:

Here, the second term is gives the error and is denoted using the big-O notation which was explained in an earlier note. This indicates that indeed would be less than . Thus, as can be seen in Figure 1 the average growth of .

We then used to ‘rectify’ i.e. obtain:

Figure 2

This rectified is plotted in Figure 2 and provides a clear picture of fluctuations in once we have removed the average growth trend. We observe right away that the amplitude of the fluctuations grows with . To determine this growth trend of the rectified , we first noticed from Figure 1 that tends to run close to the maxima of . Hence, we utilized the asymptotic expansion of , which is a better approximation of and captures the behavior beyond the basic term:

Using the first 4 terms to approximate the growth of the amplitude of rectified we get the red bounding curves shown in Figure 2. Thus, we conjecture that while grows on an average as , the amplitude of its fluctuations is roughly approximated by (Green bounding curves in Figure 2).