CA77's Site.

Articles

Distribution of Series ℤ[>0] ( ℤ[≥0] 𝑝 + 𝑘 )

Published on: 9/18/2025

Updated on: 9/21/2025

Distribution of Series ℤ[>0] ( ℤ[≥0] 𝑝 + 𝑘 ) . For example, 𝑝 = 10, 𝑘 = 7, the series is [7, 14, 17, 21, 27, 28, 34, 35, 37,...].

Tags: number theory, math

Background

本文灵感来自于小潮院长视频 BV1HbM3zrEYY 中的 “敲7” 游戏，但为了避免对数字进制的复杂分析，本文考虑的情况更简单，即规则简化为以数字 7 结尾的数的倍数。

First, we stipulate that arithmetic operations on number sets are performed in a broadcast manner.

Definition

For number sets $A, B$ and numbers $a, b$ , their arithmetic operations are defined as:

$A + B = {x + y ∣ x \in A, y \in B}$
$A + b = A + {b}, a + B = {a} + B$
$A B = {x y ∣ x \in A, y \in B}$
$A b = A {b}, a B = {a} B$

We wish to discuss a set of the form

F_{k}^{(p)} = Z_{> 0} (Z_{⩾ 0} p + k) (1)

where $p \in Z_{> 0}$ and $k \in Z \cap [0, p] = {0, 1, 2, \dots, p}$ .

Natural Density

Definition

For a subset $A \subset N$ of natural numbers $N : = Z_{⩾ 0}$ , its natural density is defined as

d (A) = x \to + \infty lim \frac{# { a \in A ∣ a ⩽ x }}{x} = x \to + \infty lim \frac{# ( A \cap [ 0 , x ])}{x} (2)

We can additionally define the upper density and lower density of natural density as

\overline{d} (A) = x \to + \infty lim sup \frac{# { a \in A ∣ a ⩽ x }}{x}, \underline{d} (A) = x \to + \infty lim inf \frac{# { a \in A ∣ a ⩽ x }}{x} (3)

We point out that natural density has the following properties:

Proposition

Range $[0, 1]$
Insensitive to finite changes: If $F$ is a finite set of numbers, then the symmetric difference has the same natural density $d (A △ F) = d (A)$
If $d (A), d (B)$ exist, then $d (A \cup B) = d (A) + d (B) - d (A \cap B) (4)$ Its existence also depends on $d (A \cap B)$ . Therefore, if $A$ and $B$ are disjoint, then densities can be added.
For any positive integer $c$ , if $A$ has density $d (A)$ , then the set $c A$ also has density, and $d (c A) = d (A) / c$ , because $d (c A) = x \to + \infty lim \frac{# ( c A \cap [ 0 , x ])}{x} = x \to + \infty lim \frac{# ( c ( A \cap [ 0 , x / c ]))}{x} = x \to + \infty lim \frac{# ( A \cap [ 0 , x / c ])}{x}$ Substituting $u = x / c$ , we have $(x \to + \infty) ⟺ (u \to + \infty)$ , thus $d (c A) = x \to + \infty lim \frac{# ( A \cap [ 0 , x / c ])}{x} = u \to + \infty lim \frac{# ( A \cap [ 0 , u ])}{u c} = \frac{1}{c} u \to + \infty lim \frac{# ( A \cap [ 0 , u ])}{u} = \frac{1}{c} d (A)$
If $d (A)$ exists, then $d (N ∖ A) = 1 - d (A)$
Not all sets have natural density

Let’s provide some examples:

Arithmetic Progressions

For an arithmetic progression

{n \in Z_{> 0} : n \equiv a (mod q)}

its members can be expressed as $a + n q$ , so its natural density is

d {n \in Z_{> 0} : n \equiv a (mod q)} = x \to + \infty lim \frac{1}{x} (# {a + n q ∣ 0 ⩽ n ⩽ \frac{x - a}{q}}) = x \to + \infty lim \frac{1}{x} ⌊ \frac{x - a}{q} ⌋ = \frac{1}{q} (5a)

where the last step of the limit can be derived from the following inequality

\frac{1}{q} (1 - \frac{a}{x}) = \frac{1}{x} \frac{x - a}{q} ⩽ \frac{1}{x} ⌊ \frac{x - a}{q} ⌋ < \frac{1}{x} (\frac{x - a}{q} + 1) = \frac{1}{q} (1 - \frac{a - q}{x})

Furthermore, we can immediately obtain

d (q Z_{> 0}) = \frac{1}{q} (5b)

Polynomials

If $f [n]$ is an integer-valued polynomial with degree $> 0$ , we point out that the number of its values in the interval $[0, x]$ is $O (x^{1/ d e g f})$ , so the natural density $d = 0$ .

In fact, let $f [n] = a_{0} + a_{1} n + a_{2} n^{2} + a_{3} n^{3} + \dots + a_{k} n^{k}$ , we need to estimate the asymptotic behavior of $# {n ∣ 0 ⩽ f [n] < x}$ when $x \to + \infty$ is sufficiently large. At this point, the dominant term is the one with $n \sim x$ , so as $x \to + \infty$ , $n$ also approaches $+ \infty$ , hence $f [n] \sim a_{k} n^{k}$ . Thus, the solution set of the inequality $0 ⩽ f [n] < x$ asymptotically approaches the solution set of $0 ⩽ a_{k} n^{k} < x$ , i.e., $0 ⩽ n < (x / a_{k})^{1/ k} \sim O (x^{1/ k})$ .

A simple special case is power sequences, particularly perfect squares and perfect cubes, whose natural densities are all $0$ .

Prime Numbers

The distribution of prime numbers is an important topic in number theory. According to the Prime Number Theorem, we know that $π (x) \sim x / lo g x$ , so the natural density of primes is the limit $π (x) / x \to 0$ .

Combinatorial Structures

For a series of mutually disjoint sequences, their natural density is the sum of these sequences’ densities. In particular, for a series of arithmetic progressions with coprime differences, their natural density asymptotically equals the sum of these arithmetic progressions, i.e.,

d (q_{1}, q_{2}, \dots, q_{n} ⋃ {n \in Z_{> 0} ∣ n \equiv a_{k} (mod q_{k})}) = k = 1 \sum n \frac{1}{q _{k}} + higher-order terms, g cd (q_{1}, q_{2}, \dots, q_{n}) = 1 (6)

However, we must point out that the higher-order terms here are not necessarily infinitesimal. In fact, the higher-order terms here are essentially the higher-order terms expanded from the inclusion-exclusion principle.

Analysis of 𝓕

Structure of 𝓕

According to equation $(1)$ , $F_{k}^{(p)} = Z_{> 0} (Z_{⩾ 0} p + k)$ , note that

Proposition

F_{0}^{(p)} = Z_{⩾ 0} p

Note that $1 \in Z_{> 0} \subset Z_{⩾ 0}$ , which is the most important discovery, because this simple fact tells us that the multiplier $Z_{> 0}$ only expands any set. Let $k = 0$ , we have

F_{0}^{(p)} = Z_{> 0} Z_{⩾ 0} p = Z_{⩾ 0} p

This is because the product of positive integers and non-negative integers is still a non-negative integer $Z_{> 0} Z_{⩾ 0} \subset Z_{⩾ 0}$ , and according to our simple observation $1 \in Z_{> 0} \subset Z_{⩾ 0}$ , which provides the conclusion $Z_{> 0} Z_{⩾ 0} \supset Z_{⩾ 0}$ .

Proposition

F_{p}^{(p)} = Z_{> 0} p

In fact, $Z_{⩾ 0} + 1 = Z_{> 0}$ , because

{0, 1, 2, \dots} + 1 = {0 + 1, 1 + 1, 2 + 1, \dots} = {1, 2, 3, \dots}

Therefore

F_{p}^{(p)} = Z_{> 0} (Z_{⩾ 0} p + p) = Z_{> 0} (Z_{⩾ 0} + 1) p = Z_{> 0} Z_{> 0} p = Z_{> 0} p

Here we used $Z_{> 0} Z_{> 0} = Z_{> 0}$ , for the same reason as the above argument.

Proposition

F_{1}^{(p)} = Z_{> 0}

Since $0 \in Z_{⩾ 0}$ , we have

F_{k}^{(p)} = Z_{> 0} (Z_{⩾ 0} p + k) \supset Z_{> 0} k

Therefore $k = 1$ gives $F_{k}^{(p)} \supset Z_{> 0}$ , and since $F_{k}^{(p)}$ is a subset of positive integers, we have $F_{k}^{(p)} = Z_{> 0}$ .

This conclusion is surprising and seems too simple? In fact, the key is that $0 \in Z_{⩾ 0}$ . Indeed, if we consider $X = Z_{> 0} p + k$ and $Y = Z_{> 0} X = Z_{> 0} (Z_{> 0} p + k)$ , when $k = 1$ we have $X = Z_{> 0} p + 1$ , which seems similar to the structure given in Euclid’s proof for the infinitude of primes. In fact, both prime numbers and composite numbers in $X$ are infinite, but the distribution of primes becomes increasingly sparse. Let

π (x; p, k) = # {q \in Primes ∣ q ⩽ x, q \equiv k (mod p)}

By Dirichlet’s theorem, we immediately get

π (x; p, k) \sim \frac{1}{φ ( p )} li (x), x \to + \infty

But we will not analyze further here, because elementary methods are difficult to handle these conclusions, and further analysis requires knowledge of analytic number theory.

In fact, the definition of natural density we provided essentially also requires knowledge of analytic number theory and probabilistic number theory to deepen further.

Based on the above conclusions, we can immediately obtain:

Theorem

If $k ∣ p$ , then

F_{k}^{(p)} = Z_{> 0} k (7a)

independent of $p$ .

Let’s say $p = k t$ , then

n p + k = n (k t + k) = k (n t + 1)

Therefore

F_{k}^{(p)} = {a \cdot k (n t + 1) ∣ a \in Z_{> 0}} = k \cdot {a (n t + 1) ∣ a \in Z_{> 0}}

When $n = 0$ , the above expression gives $F_{k}^{(p)} \supset k Z_{> 0}$ , and the expression itself tells us $F_{k}^{(p)} \subset k Z_{> 0}$ , thus proving the theorem.

Theorem

If $g cd (p, k) = r$ , then

F_{k}^{(p)} = r F_{k / r}^{(p / r)} (7b)

This theorem tells us how to reduce $F_{k}^{(p)}$ , and its proof is simple, just note that

a (n p + k) = a (n p^{'} r + k^{'} r) = r \cdot a (n p^{'} + k^{'})

where $p = p^{'} r$ and $k = k^{'} r$ .

Properties of 𝓕

Proposition

For any $p, k > 0$ , since $n = 0$ is allowed, $n p + k$ includes $k$ , thus

Z_{> 0} k \subset F_{k}^{(p)}

Proposition

If $r = g cd (p, k)$ , for any $a, n$ , $a (n p + k)$ is divisible by $r$ , so

F_{k}^{(p)} \subset r Z_{⩾ 0}

The above two propositions give a range estimation for $F_{k}^{(p)}$ :

Theorem

Z_{> 0} k \subset F_{k}^{(p)} \subset Z_{⩾ 0} g cd (p, k) (8)

Due to $(7b)$ , we only need to study the case where $p, k$ are coprime, in which case

Z_{> 0} k \subset F_{k}^{(p)} \subset Z_{⩾ 0} (8^{'})

This means that the upper bound of the range has lost its meaning (in fact, $Z_{⩾ 0}$ is the domain of our discussion).

Theorem

When $p, k$ are coprime, $r = g cd (p, k) = 1$ , we have

F_{k}^{(p)} = n ⩾ 0 ⋃ (n p + k) Z_{> 0} (9a)

that is, the set of all positive integers that are divisible by some number of the form $n p + k$ . Equivalently, the criterion is

m \in F_{k}^{(p)} ⟺ \exists d ∣ m, d ⩾ k and d \equiv k (mod p) (9b)

This criterion is helpful for programming implementation, because if we directly use $(9a)$ for programming, the resulting array would be unordered and contain duplicate items.

Theorem

$F_{k}^{(p)}$ is closed in a certain sense, i.e., for any $t \in Z_{> 0}$ , if $x \in F_{k}^{(p)}$ , then $t x \in F_{k}^{(p)}$ . However, note that $F_{k}^{(p)}$ is not closed under arbitrary multiplication, thus it doesn’t form a multiplicative semigroup.

Theorem

Due to equation $(8)$ , the natural density of $F_{k}^{(p)}$ is at least $1/ k$ . In particular, if $r = g cd (p, k)$ , then its lower bound of density can be strengthened to $r / k$ , i.e.,

d (F_{k}^{(p)}) ⩾ \frac{r}{k} (10)

But the upper bound of density for $F_{k}^{(p)}$ is difficult to estimate, and more precise values must depend on $p, k$ .

Natural Density of 𝓕

Now we only consider the special case where $p = 10$ . We know, according to equation $(10)$ , that the natural density $d_{k}$ of $F_{k}^{(10)}$ is at least $g cd (10, k) /10$ . Now consider the special values $k = 2, 3, 5, 7$ .

𝑘 = 2

In this case, $d_{k = 2} ⩾ 1/2$ . Note that

F_{2}^{(10)} = 2 F_{1}^{(5)} = 2 Z_{> 0}

where the first equality is due to factoring out the common factor $2 = g cd (10, 2)$ (by Thm. 2), and the second equality is the special case of $k = 1$ (by Prop. 4), whose natural density is $1/2$ .

𝑘 = 3

In this case, $p, k$ are coprime, and the members of $F_{3}^{(10)}$ are multiples of numbers that are congruent to $3$ modulo $10$ , i.e.,

F_{3}^{(10)} = 3 Z_{> 0} \cup 13 Z_{> 0} \cup 23 Z_{> 0} \cup \dots = ℓ = 0 ⋃ \infty (10 ℓ + 3) Z_{> 0}

Its members are

3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 26, 27, 30, 33, 36, \dots

Its natural density appears to be $1/3$ , but in fact this is only a lower bound; the correct density is $1$ , which we will explain shortly.

𝑘 = 5

By a completely similar method, we can immediately obtain that $F_{5}^{(10)} = 5 Z_{> 0}$ consists of multiples of $5$ , whose natural density is naturally $1/5$ .

𝑘 = 7

This case is our starting point, but it is not a special case. Its members are multiples of numbers that are congruent to $7$ modulo $10$ , with a natural density lower bound of obviously $1/7$ , but this is not the precise value of the density. Similar to $k = 3$ , in this case the natural density is still $1$ .

gcd (𝑝, 𝑘) = 1

Theorem

If $g cd (p, k) = 1$ , then the natural density of $F_{k}^{(p)}$ exists and equals $1$ .

To prove this, we will use Thm. 4. According to $(9b)$ , if $m \in F_{k}^{(p)}$ , then $m$ has a factor $q$ such that $q \equiv k (mod p)$ . This tells us that if we define

S = {q \in Primes ∣ q \equiv k (mod p)}

then

{m ∣ m has a prime factor q \in S} \subset F_{k}^{(p)}

We point out that the natural density of the set on the left side is $1$ , therefore the natural density of $F_{k}^{(p)}$ is at least $1$ , and since natural density cannot exceed $1$ , this completes the proof.

The proof of the conclusion

d {m ∣ m has a prime factor q \in S} = 1

relies on analytic number theory, which we will not elaborate on here.

References

Tenenbaum, G. (2022). Introduction à la théorie analytique et probabiliste des nombres. Dunod. [English translation: Thomas, C. B. (Trans.). (2024). Introduction to Analytic and Probabilistic Number Theory. APS; Chinese translation: Chen, H. (Trans.). (2011). 解析与概率数论导引. Higher Education Press.]
Aigner, M., & Ziegler, G. M. (2018). Proofs from THE BOOK (6th ed.). Springer-Verlag. [Chinese translation: Feng, R., et al. (Trans.). (2022). 数学天书中的证明 (6th ed.). Higher Education Press.]

CA77's Site.

Articles

Distribution of Series ℤ[>0] ( ℤ[≥0] 𝑝 + 𝑘 )

Background

Definitions of Related Notations

Natural Density

Arithmetic Progressions

Polynomials

Prime Numbers

Combinatorial Structures

Analysis of 𝓕

Structure of 𝓕

Properties of 𝓕

Natural Density of 𝓕

𝑘 = 2

𝑘 = 3

𝑘 = 5

𝑘 = 7

gcd (𝑝, 𝑘) = 1

References