Examples of integer sequence density calculations

There are many ways that the density of an integer sequence has been considered.
Perhaps the most natural is the natural density. For a sequence of positive integers S, define
A(x) to be the counting function for S, i.e.,
A(x) = |{n ∈ S : 1 ≤ n ≤ x}|.
So A(x) is the number of terms in S that are less than or equal to x. Then, the natural density
of S is defined to be
A(x)
d(S) = lim
x→∞ x
provided the limit exists.
We see that if S consists of all positive integers, then A(x) = x, and so d(S) = 1.
If S consists of all odd positive integers, then A(x) = b x+1
2
c, so
x+1 x+1
− 1 ≤ A(x) ≤
2 2
and so
1 1 A(x) 1 1
− ≤ ≤ + .
2 2x x 2 2x
A(x) 1
Hence, lim = , and so d(S) = 12 for the odd positive integers.
x→∞ x 2
If we let m be a positive integer, and B a set of residue classes modulo m, and let S be the set
of all positive integers that fall into an element of B, then, with an argument similar to the one
above,
|B|
d(S) = .
m
So for example, the set of integers congruent to 1, 4 or 7 modulo 8 has natural density 83 .

Can the limit not exist?

The definition of the natural density requires the existence of a limit. It turns out that there are
sequences for which the limit does not exist, and these sequences do not have a natural density.
Consider the set of integers S which have an odd number of digits. Consider some values of
A(x)
x
. We have A(9)
9
= 1, A(99)
99
9
= 99 1 A(999)
= 11 909
, 999 = 999 101
= 111 , and A(9999)
9999
909
= 9999 1
= 11 . One can show
k A(x) 1 A(x) 9
that, if x = 10 − 1 and k is even, then x = 11 , while if k is odd, then x > 10 . As a result of
this behavior, we can see that A(x)/x does not approach a limit as x approaches infinity, and so
this set does not have a natural density.
It is not hard to construct many sequences which fail to have natural densities.

Example: partitioning the sequence

Consider the sequence of numbers, S, which have a binary representation that ends in an even
number of zeros. This is A003159 in the OEIS, and begins 1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, . . . .
Let’s work out what the natural density of this sequence is.
A very helpful approach here is to partition the sequence into disjoint subsequences and work
out the density of each. A nice property of the natural density is that it is additive: if disjoint
sequences S1 and S2 have natural densities, then the natural density of their union exists and
we have
d(S1 ∪ S2 ) = d(S1 ) + d(S2 ).
(The proof of this fact makes a nice exercise.)
To partition S, we can note that it consists of numbers with binary expansions ending in exactly
0 zeros, exactly 2 zeros, exactly 4 zeros, etc.
We can characterize precisely each type.
The set of numbers with binary expansions ending in exactly 0 zeros is the set of odd numbers,
i.e. the numbers congruent to 1 mod 2.
The set of numbers with binary expansions ending in exactly 2 zeros is the set of all numbers
congruent to 4 mod 8.
The set of numbers with binary expansions ending in exactly 4 zeros is the set of all numbers
congruent to 16 mod 32.
Generally, the set of numbers with binary expansion ending in exactly 2k zeros is the set of all
numbers congruent to 22k mod 22k+1 .
As mentioned earlier, the density of such a set is
1
22k+1
and so the density of the set S of number with binary expansions ending in an even number of
zeros is ∞
X 1 2
d(S) = 2k+1
= .
k=0
2 3

Example: probability heuristic and Dirichlet density

Let’s consider the sequence S of all numbers whose prime factorization consists only of odd
exponents. S contains all primes, all odd powers of primes (e.g., 33 , 75 , etc.), and all products
of relatively odd powers of primes, e.g., 25 33 119 .
This is sequence A002035 at the OEIS.
The sequence begins, 2, 3, 5, 6, 7, 8, 10, 11, 13, 14, 15, 17, 19, 21, 22, . . . . If we count terms, we find
A(100) = 70, A(10000) = 7055 and A(106 ) = 704464, which experimentally suggests the se-
quence might have a natural density around 0.7.
Here’s a way we can get a good handle on the density. We begin by noting that, if an integer is
not in this sequence, then it must have an even exponent somewhere in its prime factorization.
That is, it must be exactly divisible by an even power of a prime.
For any prime p and positive integer k, the density of integers that are exactly divisible by pk is
1 1
k
− k+1 .
p p
This comes from the additivity property of the natural density mentioned earlier. Hence, the
density of positive integers that are exactly divisible by an even power of p is
1 1 1 1 1 1
− + − + − + ···
p2 p3 p4 p5 p6 p7
and so the density of numbers that are not exactly divisible by an even power of p is

1 1 1 1 1 1 p2 + p − 1
1− + − + − + − · · · = .
p2 p3 p4 p5 p6 p7 p2 + p
5
For example, the set of numbers not exactly divisible by an even power of 2 has density 6
and
the set of numbers not exactly divisible by an even power of 3 has density 11
12
.
Now, heuristically, treating these densities as probabilities we can calculate the density of the
full sequence S. For an integer n to be in S, it must not by exactly divisible by an even power
of 2, and it must not be exactly divisible by an even power of 3, and it must not be divisible by
an even power of 5, etc.
Hence, the probability that the number is not divisible by an even power of any prime is
Y p2 + p − 1 Y  1

= 1− .
p
p2 + p p
p(p + 1)

where the product is over all primes. This is the density of the set S.
A more formal argument can be made with Dirichlet series. This begins by noting that, for any
complex z,
Y 1 + p−z − p−2z
 Y
X
−z 1 1 1
L(z) = n = 1 + z + 3z + 5z + · · · = −2z
.
n∈S p
p p p p
1 − p

Then the Dirichlet density of S, µ(S) is given by

L(z)
µ(S) =Resz=1 L(s) = lim+
z→1 ζ(z)
Y 1 − 2p−2z + p−3z
= lim
z→1
p
1 − p−2z
Y 1 − 2p−2 + p−3 Y 1

= = 1− .
p
1 − p−2 p
p(p + 1)

which is the same as we worked out heuristically above.

If we calculate this product through the millionth prime, the result is

0.704442203598081...

and by bounding the tail we can conclude that the true density d(S) is in the range

0.704441 < d(S) < 0.704442.