The Prime-Power Map

Steven Business Mathematics Department School of Applied STEM Universitas Prasetiya Mulya South Tangerang 15339 Indonesia

                   steven@pmbs.ac.id

Jonathan Hoseana Department of Mathematics Parahyangan Catholic University Bandung 40141 Indonesia

                 j.hoseana@unpar.ac.id

Abstract

We introduce a modification of Pillai’s prime map: the prime-power map. This map fixes 1, divides its argument by p if it is a prime power p^{k}, and otherwise subtracts from its argument the largest prime power not exceeding it. We study the iteration of this map over the positive integers, developing, firstly, results parallel to those known for the prime map. Subsequently, we compare its dynamical properties to those of a more manageable variant of the map under which any orbit admits an explicit description. Finally, we present some experimental observations, based on which we conjecture that almost every orbit of the prime-power map contains no prime power.

1 Introduction

Let ℙ be the set of primes (\underline{A000040} in the On-Line Encyclopedia of Integer Sequences [10]). In 1930, Pillai [9] introduced the prime map x ↦ x − r(x), where r(x) is the largest element of ℙ ∪ {0, 1} not exceeding x, under whose iteration every positive-integer initial condition is eventually fixed at 0, the only fixed point of the map. Interesting results on the asymptotic behavior of the time steps R(x) it takes for an initial condition x to reach the fixed point were established, before subsequently improved by Luca and Thangadurai [7] in 2009. The latter authors proved that R(x) grows no faster than ln ln x [7, Theorem 1.1], and that for every k ∈ ℕ (ℕ being the set of positive integers), the proportion of initial conditions t ≤ x for which R(t) = k is asymptotic to (ln_{k} x)^{−1}, where the subscript k denotes k-fold self-composition [7, Theorem 1.2].

In this paper we study a modification of the prime map, constructed essentially by letting the role of primes be taken over by prime powers (\underline{A000961}). A prime power, as is well-known, is an integer of the form p^{k}, where p ∈ ℙ and k ∈ ℕ. Letting ℙ^{∗} be the set of prime powers, we define the prime-power map P : ℕ → ℕ by

P (x) := \begin{cases}1, & if x = 1; \\ x − q(x), & if x ∉ ℙ^{∗}; \\ \frac{x}{p}, & if x ∈ ℙ^{∗} is a power p ∈ ℙ, \end{cases}

where q(x) is the largest element of ℙ_{1}^{∗} := ℙ^{∗} ∪ {1} not exceeding x (see Figure 1). By the orbit of an initial condition x ∈ ℕ under P we mean the sequence (x_{n})_{n=1}^{∞} where

x_{1} = x  and  x_{n+1} = P (x_{n}) for every n ∈ ℕ.

Clearly, every orbit under P is decreasing (in the non-strict sense) and eventually reaches the sole fixed point 1 at which it then stabilizes (becomes constant).

In the subdomain ℙ_{1}^{∗} ⊆ ℕ the dynamics of P is predictable; it consists only of divisions by primes and stabilization. In its complement, by contrast, the dynamics is non-trivial and resembles that of Pillai’s prime map. Such hybrid dynamical behavior naturally motivates associating to every initial condition x the time steps

S(x) := min {n ∈ ℕ : x_{n} ∈ ℙ_{1}^{∗}} and T (x) := min {n ∈ ℕ : x_{n} = 1}

at which the orbit of x enters the predictable subdomain ℙ_{1}^{∗}, and at which it reaches 1, respectively. These are referred to as the settling time and transient length of x, respectively. The unboundedness of the transient length function is immediate—the function diverges along the sequence of powers of any given prime—whereas that of the settling time function is less obvious and will be established in this paper. We shall also be interested in the attractor

W (x) := x_{S(x)}

of x, i.e., the element of the predictable subdomain first visited by the orbit of x. The functions T and S defined above constitute our primary object of study. We now describe our main results, along with the structure of this paper. Following this

introduction is Section 2, where we establish a logarithmic upper bound for T (Lemma 2 and

\begin{matrix}0 \\ 50 \\ 100 \\ 150 \\ 200 \\ 250 \\ 0 \\ 20 \\ 40 \\ 60 \\ 80 \\ x \\ P (x) \end{matrix}

Figure 1: The values of P (x) for x ∈ {1, …, 250}.

Theorem 3). Subsequently, we discuss improved versions of Lemma 2, derived from improved versions of Bertrand’s postulate currently known in the literature (Propositions 4 and 6), before we turn our attention to the function S, establishing its unboundedness (Theorem 8) and a double-logarithmic upper bound (Theorem 10); these are analogues of results of Pillai [9, pp. 160–161] and Luca and Thangadurai [7, Theorem 1.1], respectively. Next, we study the densities of some subsets of ℕ induced by P and prove that almost every positive integer is coprime with its image under P, i.e., that the limit of the proportion of such integers is 1 (Theorem 12). At the end of the section, we connect the map P to the representations of integers as sums of prime powers; of note is the discussion on the smallest initial condition having a given settling time (Proposition 15).

The detailed behavior of the functions T and S is difficult to describe explicitly. For a comparison, in Section 3 we introduce a more manageable variant of P: a family of maps P_{p}, under which the analogous functions T_{p} and S_{p} admit explicit descriptions (Theorem 16). We prove that these two functions are asymptotic (Corollary 18), which, together with some experimental observations, suggests that the original functions T and S exhibit an analogous asymptoticity. Motivated by these observations, we conjecture that almost every orbit of the prime-power map contains no prime power (Conjecture 19).

2 Results on the map P

Before entering into our main results, let us state some fundamentals. First, we state the famous Bertrand’s postulate [3, Theorem 418], which will be used frequently.

Lemma 1 (Bertrand’s postulate). For every integer n ≥ 2, there exists a prime p such that n < p < 2n.

We also use standard asymptotic notation that we now recall. Let f(x) and g(x) be positive for all sufficiently large values of x ∈ ℕ. We write f(x) ∼ g(x) to mean f(x) is asymptotic to g(x), i.e., \frac{f(x)}{g(x)} ⟶^{x→∞} 1. In addition, f(x) ≪ g(x) means f(x) is asymptotically bounded above by g(x), i.e., there exist C > 0 and x_{0} ∈ ℕ such that f(x) ≤ C g(x) for every integer x ≥ x_{0}. Finally, f(x) = o(g(x)) means \frac{f(x)}{g(x)} ⟶^{x→∞} 0.

2.1 The transient length function

First, we have

lim sup_{x→∞} T (x) = ∞,

since T diverges along, e.g., the sequence of powers of two (\underline{A000079}). More precisely, if x is a power of two, we have T (x) = log_{2} x + 1. Let us now prove that log_{2} x + 1 is an upper bound for T (see Figure 2) via the following lemma that exploits Bertrand’s postulate.

Lemma 2. For every integer x ≥ 2 we have

P (x) ≤ \frac{x}{2}.

Proof. Let x ≥ 2. If x = p^{k} for some p ∈ ℙ and k ∈ ℕ, then P (x) = \frac{x}{p} ≤ \frac{x}{2}. Otherwise, since Bertrand’s postulate guarantees the existence of a prime between \frac{x}{2} and x, then q(x) ≥ \frac{x}{2}, and hence P (x) ≤ \frac{x}{2}.

Theorem 3. For every x ∈ ℕ we have T (x) ≤ log_{2} x + 1 with equality if and only if x is a power of two.

Proof. By Lemma 2, in the orbit (x_{n})_{n=1}^{∞} of x ∈ ℕ we have

1 = x_{T (x)} ≤ \frac{x_{T (x)−1}}{2} ≤ \frac{x_{T (x)−2}}{2^{2}} ≤ ⋯ ≤ \frac{x_{1}}{2^{T (x)−1}} = \frac{x}{2^{T (x)−1}} ,

which implies the desired inequality. If x is a power of two, we have T (x) = log_{2} x + 1 as previously remarked. Conversely, if T (x) = log_{2} x + 1, then x = 2^{T (x)−1}.

In the literature there have been numerous refinements of Bertrand’s postulate that lead to improved versions of Lemma 2. For instance, the prime number theorem implies that, given any ε > 0, there exists X_{0} ∈ ℕ such that for every integer x ≥ X_{0}, the interval [x − εx, x] contains a prime number [3, Section 22.19], implying that P (x) ≤ εx if x is not a prime power. Therefore, we have the following proposition.

Proposition 4. For every ε > 0 there exists X_{0} ∈ ℕ such that

P (x) ≤ εx  (1)

for every non-prime-power x ≥ X_{0}.

\begin{matrix}0 \\ 50 \\ 100 \\ 150 \\ 200 \\ 250 \\ 0 \\ 2 \\ 4 \\ 6 \\ 8 \\ x \\ T (x) \end{matrix}

Figure 2: The values of T (x) for x ∈ {1, …, 250} and the upper bound provided by Theorem 3.

Notice that, since for every prime power x = p^{k} we have \frac{P (x)}{x} = \frac{1}{p} ≤ \frac{1}{2} with equality if and only if p = 2, there is no ε < \frac{1}{2} such that (1) holds for all sufficiently large x. In this sense, the non-universality of (1)—the fact that it holds only for non-prime-powers—is unavoidable. However, for every ε > 0 one can always choose a sufficiently large X_{1} ∈ ℕ such that (1) holds for all powers of all primes p ≥ X_{1}.

Hoheisel [4], as cited by Luca and Thangadurai [7, Section 2], proved the following development of Bertrand’s postulate.

Lemma 5. There exist θ ∈ (0, 1) and X_{0} ∈ ℕ such that for every x ≥ X_{0} the interval [x − x^{θ}, x] contains a prime number.

This lemma immediately implies the following proposition.

Proposition 6. There exist θ ∈ (0, 1) and X_{0} ∈ ℕ such that

P (x) ≤ x^{θ}

for every non-prime-power x ≥ X_{0}.

Baker et al. [1] have proved the existence of X_{0} ∈ ℕ for which one could take θ = θ_{0} := 0.525.

2.2 The settling time function

In the first half of this subsection we follow the steps of Pillai’s proof [9, pp. 160–161] of the unboundedness of R. In the work cited, Pillai proved that

lim sup_{x→∞} R(x) = ∞

using a well-known result on the unboundedness of gaps between primes, i.e., that for every n ∈ ℕ, none of the n − 1 consecutive positive integers

n! + 2, n! + 3, …, n! + n

is prime, implying the existence of two consecutive primes p_{1} and p_{2} such that p_{2} −p_{1} ≥ n [9, Lemma 1]. Here we first modify this argument to show the unboundedness of gaps between prime powers. Then we use the result to prove that

lim sup_{x→∞} S(x) = ∞.

Lemma 7. For every n ∈ ℕ there exist two consecutive prime powers q_{1} and q_{2} such that q_{2} − q_{1} ≥ n.

Proof. Let n ∈ ℕ. If n = 1, clearly the lemma holds. Now, suppose n ≥ 2. Let p_{1}, …, p_{m}, where m ∈ ℕ, be all prime numbers not exceeding n. For every i ∈ {1, …, m}, define

k_{i} = max{k ∈ ℕ : p_{i}^{k} ≤ n}.

Letting

N := ∏_{i=1}^{m} p_{i}^{k_{i}+1},

we can see that none of the n − 1 consecutive positive integers

N + 2, N + 3, …, N + n

is a prime power. Therefore, letting q_{1} be the largest prime power less than N + 2 and q_{2} be the smallest prime power greater than N + n, we have the lemma.

Theorem 8. We have

lim sup_{x→∞} S(x) = ∞.

Proof. By Lemma 7, for every non-prime-power x ∈ ℕ there exist two consecutive prime powers q_{1} and q_{2} such that q_{2} − q_{1} ≥ x + 1, implying S (q_{1} + x) = S(x) + 1. The theorem follows.

Luca and Thangadurai proved that R(x) ≪ ln ln x [7, Theorem 1.1]. Now, we prove that the same asymptotic upper bound also applies for the settling time function S, following the argument in the work cited. First, we take numbers X_{0} ∈ ℕ and θ ∈ (0, 1) that satisfy Lemma 5 (and hence Proposition 6). Then we have the following lemma.

Lemma 9. Let x ≥ X_{0}, and let (x_{n})_{n=1}^{∞} be the orbit of x. Then for every k ∈ ℕ the following holds:

If x_{k} ≥ X_{0} and S(x) ≥ k + 1, then x_{k+1} ≤ x^{θ^{k}}.

Proof. We use induction on k ∈ ℕ. For k = 1 the statement reads

If x_{1} ≥ X_{0} and S(x) ≥ 2, then x_{2} ≤ x^{θ},

which is true since, if x_{1} ≥ X_{0} and S(x) ≥ 2, the latter implying that x_{1} is not a prime power, then

x_{2} = P (x_{1}) ≤ x_{1}^{θ} = x^{θ},

by Proposition 6.

Now let k ≥ 2, and suppose the statement holds for k − 1 replacing k. Suppose x_{k} ≥ X_{0} and S(x) ≥ k + 1. The former implies that x_{k−1} ≥ X_{0} since x_{k−1} ≥ x_{k}, while the latter implies that S(x) ≥ k and that x_{k} is not a prime power. Therefore, our inductive hypothesis gives x_{k} ≤ x^{θ^{k−1}}, and so by Proposition 6,

x_{k+1} = P (x_{k}) ≤ x_{k}^{θ} ≤ (x^{θ^{k−1}})^{θ} = x^{θ^{k}},

completing the induction.

Theorem 10. We have

S(x) ≪ ln ln x.

Proof. Define X′_{0} := max {X_{0}, e}. Let x ≥ X′_{0}, and let (x_{n})_{n=1}^{∞} be the orbit of x. Define

k := min{S(x), ℓ} − 1 ∈ ℕ_{0}, where ℓ := max {λ ∈ ℕ : x_{λ} ≥ X′_{0}} ,

the existence of ℓ being guaranteed by the fact that x_{1} = x ≥ X′_{0} > 1.

By the definition of k we have that k ≤ S(x) − 1 and k ≤ ℓ − 1 (i.e., k + 1 ≤ ℓ), implying S(x) ≥ k + 1 and x_{k} ≥ x_{k+1} ≥ x_{ℓ} ≥ X′_{0} ≥ X_{0}, respectively. Then we have the inequality

x_{k+1} ≤ x^{θ^{k}},

which is trivially true if k = 0 and implied by Lemma 9 if k ≥ 1. This inequality, together with the fact that x_{k+1} ≥ X′_{0}, implies

X′_{0} ≤ x^{θ^{k}}.

Taking logarithms twice gives

ln ln X′_{0} ≤ k ln θ + ln ln x.

Since X′_{0} ≥ e, the left-hand side is non-negative, and hence so is the right-hand side, i.e.,

k ≤ \frac{ln ln x}{ln \frac{1}{θ}}.

Letting m := max {S(1), …, S (X′_{0})}, by the definitions of k and ℓ we have

S(x) ≤ k + 1 + m ≤ \frac{ln ln x}{ln \frac{1}{θ}} + 1 + m ≪ ln ln x,

proving the theorem.

2.3 Densities of subsets of ℕ induced by P

Let us now discuss the densities of some positive integer sets induced by P, for which the following standard terminology [8, 11] is used. Given a subset A ⊆ ℕ. For every x ∈ ℕ, we define

d_{x}(A) := \frac{|A ∩ \{1, …, x\}|}{x}.

The (natural) density of A is the limit

d(A) := lim_{x→∞} d_{x}(A),

if it exists. If d(A) = 0, we say that A is sparse. If d(A) = 1, we say that A has full density. If d(A) = 1 and a statement P(x) holds for every x ∈ A, we say that P(x) holds for almost every x ∈ ℕ.

It is fairly well-known that the sets ℙ and ℙ^{∗} are both sparse. This can be deduced by considering the prime and prime power counting functions

π(x) := |ℙ ∩ {1, …, ⌊x⌋}| and Π(x) := |ℙ^{∗} ∩ {1, …, ⌊x⌋}|

defined for real numbers x > 0. Clearly, π(x) ≤ Π(x) for every x > 0. The prime number theorem [3, page 10] gives the asymptotic

π(x) ∼ \frac{x}{ln x},

from which it follows that ℙ is sparse. Moreover, since

Π(x) − π(x) = ∑_{j=2}^{⌊log_{2} x⌋} π (x^{\frac{1}{j}} ) ≪ \frac{x^{\frac{1}{2}}}{ln x^{\frac{1}{2}}} (⌊log_{2} x⌋ − 1) ≪ x^{\frac{1}{2}} ,

then Π(x) ∼ π(x), implying that ℙ^{∗} is also sparse. (In fact, this holds more generally [6].) Letting ℕ_{≥k} be the set of positive integers greater than or equal to k ∈ ℕ, we have the following immediate consequences.

(i) The set T^{−1} (ℕ_{≥3}) has full density because T^{−1}({1}) = {1} and T^{−1}({2}) = ℙ ∪ {q + 1 : q ∈ ℙ^{∗}} are both sparse.

(ii) The set S^{−1} (ℕ_{≥2}) has full density because S^{−1}({1}) = ℙ_{1}^{∗} is sparse.

(iii) The set {x ∈ ℕ : P (x) ≤ x^{θ_{0}}} has full density, and, consequently, the set {x ∈ ℕ : P (x) ≤ εx} has full density for every ε > 0.

The last one follows from Propositions 4 and 6.

Every x ∈ ℕ_{≥2}\ℙ and its image under the prime map is coprime; for if they have a prime common divisor then it must divide r(x), and so must equal to r(x), implying that x ≥ 2r(x) which contradicts Bertrand’s postulate. Under the prime-power map, however, the analogue does not hold. Indeed, the number 34 ∈ ℕ_{≥2}\ℙ^{∗} and its image P (34) = 2 are not coprime. Nonetheless, we shall now prove that x and P (x) are coprime for almost every x ∈ ℕ. For this purpose, we define

𝔾 := {x ∈ ℕ : gcd(x, P (x)) > 1} ,

and we choose numbers X_{1} ∈ ℕ and θ ∈ (0, 1) such that for every x ≥ X_{1} the interval [x, x + x^{θ}] contains a prime number [1]. Our aim is to show that d(𝔾) = 0 via the following lemma.

Lemma 11. For every prime power p^{k} ≥ X_{1}, where p ∈ ℙ and k ∈ ℕ, we have

|(𝔾 ∩ q^{−1} ({p^{k}})) \ℙ^{∗}| ≤ p^{kθ−1}.

Proof. Let p^{k} ≥ X_{1} be a prime power, where p ∈ ℙ and k ∈ ℕ. For every x ∈ (𝔾 ∩ q^{−1} ({p^{k}})) \ℙ^{∗} we have that x ∉ ℙ^{∗} is a preimage of p^{k} under q satisfying

1 < gcd(x, P (x)) = gcd (x, x − p^{k}) = gcd (x, p^{k}) ,

so x is a multiple of p, and that x ∈ (p^{k}, p^{k} + p^{kθ}]. Therefore, the number of elements of (𝔾 ∩ q^{−1} ({p^{k}})) \ℙ^{∗} is bounded above by the number of multiples of p in the interval (p^{k}, p^{k} + p^{kθ}], namely

|\{p^{k} + p, …, p ⌊\frac{p^{k} + p^{kθ}}{p} ⌋\}| = \frac{p ⌊\frac{p^{k}+p^{kθ}}{p} ⌋ − p^{k}}{p} ≤ p^{kθ−1},

proving the lemma.

Theorem 12. The set 𝔾 is sparse.

Proof. Since

d(𝔾) = d (𝔾 ∩ ℙ^{∗}) + d (𝔾\ℙ^{∗})

and d (𝔾 ∩ ℙ^{∗}) = 0, it suffices to prove that d (𝔾\ℙ^{∗}) = 0.

Notice that for every x ∈ ℕ we have

d_{x} (𝔾\ℙ^{∗}) = \frac{|(𝔾\ℙ^{∗}) ∩ \{1, …, x\}|}{x} ≤ \frac{1}{x} ∑_{1≤p^{k}≤x} |(𝔾 ∩ q^{−1} (\{p^{k}\})) \ℙ^{∗}| ,

where the summation is taken over all prime powers p^{k} ∈ {1, …, x}. Now, the last expression is equal to

\frac{1}{x} ∑_{1≤p≤x} ∑_{k=1}^{⌊log_{p} x⌋} |(𝔾 ∩ q^{−1} (\{p^{k}\})) \ℙ^{∗}| ,

where the outer summation is taken over all primes p ∈ {1, …, x}. By Lemma 11, this expression is asymptotically bounded above by

\frac{1}{x} ∑_{X_{1}≤p≤x} ∑_{k=1}^{⌊log_{p} x⌋} p^{kθ−1},

where the outer summation is taken over all primes p ∈ {X_{1}, …, x}. This expression is bounded above by

\frac{1}{x} ∑_{j=2}^{x} ∑_{k=1}^{⌊log_{j} x⌋} j^{kθ−1} = \frac{1}{x} ∑_{j=2}^{x} \frac{j^{θ−1} ((j^{θ})^{⌊log_{j} x⌋} − 1)}{j^{θ} − 1} ∼ \frac{1}{x^{1−θ}} ∑_{j=2}^{x} \frac{1}{j} ≤ \frac{ln x}{x^{1−θ}} .

Since θ ∈ (0, 1), the last expression vanishes as x → ∞, so we have proved the theorem.

2.4 Connection to prime-power representations

As the prime map is closely connected to prime representations [9, page 159], so is the prime-power map to prime-power representations of positive integers. More precisely, every initial condition x ∈ ℕ is associated with, besides its orbit, the sequence (q (x_{n}))_{n=1}^{S(x)} which gives a way to express x as the sum of elements of ℙ_{1}^{∗}:

x = x_{1}
= q (x_{1}) + x_{2}
= q (x_{1}) + q (x_{2}) + x_{3}
= ⋯
= q (x_{1}) + q (x_{2}) + ⋯ + q (x_{S(x)−1}) + x_{S(x)}
= q (x_{1}) + q (x_{2}) + ⋯ + q (x_{S(x)−1}) + q (x_{S(x)}) .  (2)

Here we have that

q (x_{1}) > q (x_{2}) > ⋯ > q (x_{S(x)}) ,

which follows from the next two lemmas.

Lemma 13. For every x, y ∈ ℕ, if x ≤ y then q(x) ≤ q(y).

Proof. This is straightforward by contradiction.

Lemma 14. For every initial condition x ∈ ℕ, the sequence (q (x_{n}))_{n=1}^{S(x)} is strictly decreasing.

Proof. Let x ∈ ℕ. If S(x) = 1 then there is nothing to prove. Otherwise, we have q (x_{1}) ≥ q (x_{2}) ≥ ⋯ ≥ q (x_{S(x)}) by Lemma 13. Suppose for a contradiction that there exists n ∈ {1, …, S(x) − 1} such that q (x_{n}) = q (x_{n+1}). Then

2q (x_{n}) = q (x_{n}) + q (x_{n+1}) = (x_{n} − x_{n+1}) + (x_{n+1} − x_{n+2}) ≤ x_{n}.

But between q (x_{n}) and 2q (x_{n}) there is a prime by Bertrand’s postulate, contradicting the definition of q (x_{n}).

Clearly, there could be many ways to represent x ∈ ℕ as the sum of elements of ℙ_{1}^{∗}. The one given by (2) is the result of applying the greedy algorithm: for each n ∈ {1, …, S(x)}, one chooses the largest element q (x_{n}) of ℙ_{1}^{∗} not exceeding x_{n}. As in the case of the prime map [9, 7], a question one could ask is, for every s ∈ ℕ, what is the smallest positive integer which is expressed by the greedy algorithm as the sum of exactly s elements of ℙ_{1}^{∗}? These are precisely the numbers ξ_{s} := min S^{−1}({s}) for every s ∈ ℕ, recently submitted to the OEIS [10] as sequence \underline{A336825} (an analogue to the Pillai sequence \underline{A066352}). The values of ξ_{1}, ξ_{2}, ξ_{3}, and ξ_{4} are

1 = 1, 6 = 5 + 1, 95 = 89 + 5 + 1, and 360748 = 360653 + 89 + 5 + 1,

respectively. Anyone attempting to compute the subsequent values should take into consideration the following facts.

Proposition 15.

(i) For every s ∈ ℕ we have P (ξ_{s+1}) = ξ_{s}.

(ii) For every s ∈ ℕ we have ξ_{s+1} = min P^{−1} ({ξ_{s}}).

(iii) For every integer s ≥ 3, the number ξ_{s} is not a prime power.

(iv) We have

\frac{ξ_{s+1}}{ξ_{s}} , \frac{q (ξ_{s+1})}{q (ξ_{s})} ⟶^{x→∞} ∞.

Proof. First, we prove (i). Let s ∈ ℕ. Since S (ξ_{s+1}) = s + 1, then S (P (ξ_{s+1})) = s, so ξ_{s} ≤ P (ξ_{s+1}). To prove that ξ_{s} = P (ξ_{s+1}), suppose for a contradiction that ξ_{s} < P (ξ_{s+1}). Then,

q (ξ_{s+1}) < q (ξ_{s+1}) + ξ_{s} < q (ξ_{s+1}) + P (ξ_{s+1}) = ξ_{s+1}.

Since q (ξ_{s+1}) is the largest prime power not exceeding ξ_{s+1}, this implies that q (ξ_{s+1}) + ξ_{s} is not a prime power, and that q (ξ_{s+1}) is also the largest prime power not exceeding q (ξ_{s+1})+ξ_{s}. The latter implies that

P (q (ξ_{s+1}) + ξ_{s}) = (q (ξ_{s+1}) + ξ_{s}) − q (ξ_{s+1}) = ξ_{s},

so q (ξ_{s+1}) + ξ_{s} is a positive integer less than ξ_{s+1} having settling time

S (q (ξ_{s+1}) + ξ_{s}) = S (ξ_{s}) + 1 = s + 1,

contradicting the definition of ξ_{s+1}.

Both (ii) and (iii) are immediate consequences of (i). To prove (iv), notice that, by Proposition 6, there exists θ ∈ (0, 1) such that

ξ_{s} = P (ξ_{s+1}) ≤ ξ_{s+1}^{θ},  i.e.,  \frac{ξ_{s+1}}{ξ_{s}} ≥ ξ_{s+1}^{1−θ},

for all sufficiently large values of s. This implies

\frac{ξ_{s+1}}{ξ_{s}} ⟶^{s→∞} ∞ and \frac{q (ξ_{s+1})}{q (ξ_{s})} = \frac{ξ_{s+1} − ξ_{s}}{ξ_{s} − ξ_{s−1}} = \frac{\frac{ξ_{s+1}}{ξ_{s}} − 1}{1 − _{\frac{1}{( \frac{ξs}{ξ_{s−1}} )}}} ⟶^{s→∞} ∞,

as desired.

Part (i) of Proposition 15 also means that for every s ∈ ℕ we have ξ_{s+1} = ξ_{s} + q_{1}, where (q_{1}, q_{2}) is the first pair of consecutive prime powers with q_{2} − q_{1} ≥ ξ_{s} + 1. Therefore, to compute ξ_{5} one must find the first pair of consecutive prime powers differing by at least 360749.

3 The family of maps P_{p}

The unpredictability of the functions T and S largely originates from the fact that the prime number p acting at each iteration of P is not fixed. Take as an initial condition, for instance, x_{1} = 35. At the first iteration, which produces x_{2} = P (35) = 35 − 2^{5} = 3, the acting prime is 2. However, at the second, which produces x_{3} = P (3) = \frac{3}{3} = 1, the acting prime is 3. In order to eliminate this unpredictability, and for a comparison, let us now consider a modification of the map P constructed by fixing the acting prime. This consists in a oneparameter family of maps P_{p}, where p ∈ ℙ. As we shall see, all orbits of P_{p} are predictable via the base-p representations of the iterates (Lemma 17), and hence so are their transient lengths and settling times (Theorem 16).

3.1 The maps P_{p}

Fix a prime p ∈ ℙ. Define the map P_{p} : ℕ → ℕ by

P_{p}(x) := \begin{cases}x, & if 1 ≤ x ≤ p − 1; \\ x − q_{p}(x), & if x is not a power of p; \\ \frac{x}{p}, & if x is a power of p, \end{cases}  (3)

where q_{p}(x) is the largest power of p not exceeding x. Notice that this map has p−1 distinct fixed points: 1, …, p − 1.

As in the original map, the orbit of x ∈ ℕ under the map P_{p} : ℕ → ℕ is the sequence (x_{n})_{n=1}^{∞} where

x_{1} = x  and  x_{n+1} = P_{p} (x_{n}) for every n ∈ ℕ.

The transient length and limit of x under P_{p} are the positive integers

T_{p}(x) := min{n ∈ ℕ : x_{n} ∈ {1, …, p − 1}} and L_{p}(x) := x_{T_{p}(x)},

respectively. Equivalently, L_{p}(x) = lim_{n→∞} x_{n}, and T_{p}(x) is the index of the first term in the orbit having value L_{p}(x). One immediately sees that T_{p} is unbounded since it diverges along, e.g., the sequence of powers of p. The settling time and the attractor of x under P_{p} are the positive integers

S_{p}(x) := min{n ∈ ℕ : x_{n} ∈ {1, …, p − 1} ∪ {p^{k} : k ∈ ℕ}} and W_{p}(x) := x_{S_{p}(x)},

respectively.

Our aim is to derive explicit formulae for T_{p}(x), L_{p}(x), S_{p}(x), and W_{p}(x) in terms of p and x. This is achieved using some number-theoretic tools [3, 5]. First, the p-adic valuation [3, page 562] of x is the non-negative integer

ν_{p}(x) := max {m ∈ ℕ_{0} : p^{m} | x} ,

i.e., the exponent of the largest power of p which divides x. Moreover, we let x mod p denote the remainder upon dividing x by p [5, page 71], σ_{p}(x) the sum of the coefficients in the base-p representation [5, Section 2.2] of x, and

σ_{p}^{∗}(x) := σ_{p}(x) − (x mod p).

The formulae are given by the following theorem.

Theorem 16. Let p ∈ ℙ. For every x ∈ ℕ we have

T_{p}(x) = \begin{cases}σ_{p}^{∗}(x) + ν_{p}(x), & if p | x; \\ σ_{p}^{∗}(x) + 1, & otherwise, \end{cases}

L_{p}(x) = \begin{cases}1, & if p | x; \\ x mod p, & otherwise, \end{cases}

S_{p}(x) = \begin{cases}σ_{p}^{∗}(x), & if p | x; \\ σ_{p}^{∗}(x) + 1, & otherwise, \end{cases}

W_{p}(x) = \begin{cases}p^{ν_{p}(x)}, & if p | x; \\ x mod p, & otherwise. \end{cases}

ℕ ℕ Ω_{p} Ω_{p} P_{p} \overline{P}_{p} Ψ_{p}^{−1} Ψ_{p}

Figure 3: The commutative diagram representing the conjugation \overline{P}_{p} = Ψ_{p} ∘ P_{p} ∘ Ψ_{p}^{−1}.

To prove this theorem, we first study the structure of the orbits of the map P_{p}. We do this by looking at how the base-p representation of x changes under an application of P_{p}. More formally, we study the conjugate map \overline{P}_{p} := Ψ_{p} ∘ P_{p} ∘ Ψ_{p}^{−1}, where Ψ_{p} is the bijection associating to every positive integer the infinite sequence whose terms are the coefficients a_{0}, …, a_{k} ∈ ℤ_{p}, where a_{k} ≠ 0 and k ∈ ℕ_{0}, in its base-p representation ∑_{i=0}^{k} a_{i}p^{i} followed by infinitely many zeros denoted using the standard notation \overline{0} (e.g., Ψ_{2}(6) = (0, 1, 1, \overline{0})), as a self-map on the space Ω_{p} of all such sequences (see Figure 3). The action of the map \overline{P}_{p} is described by the following lemma.

Lemma 17. The image of (a_{0}, …, a_{k}, \overline{0}) ∈ Ω_{p}, where a_{k} ≠ 0 and k ∈ ℕ_{0}, under \overline{P}_{p} is given by

\overline{P}_{p} (a_{0}, …, a_{k}, \overline{0}) = \begin{cases}(a_{0}, …, a_{k}, \overline{0}) , & if k = 0; \\ (a_{1}, …, a_{k}, \overline{0}) , & if k ≥ 1 and a_{0} = ⋯ = a_{k−1} = 0 and a_{k} = 1; \\ (a_{0}, …, a_{k} − 1, \overline{0}) , & otherwise. \end{cases}

(4)

Proof. Let x := Ψ_{p}^{−1} (a_{0}, …, a_{k}, \overline{0}) ∈ ℕ. This means that ∑_{i=0}^{k} a_{i}p^{i} is the base-p representation of x.

(i) If k = 0 then 1 ≤ x ≤ p − 1, so P_{p}(x) = x. In other words, \overline{P}_{p} (a_{0}, …, a_{k}, \overline{0}) = (a_{0}, …, a_{k}, \overline{0}).

(ii) Suppose k ≥ 1, a_{0} = a_{1} = ⋯ = a_{k−1} = 0, and a_{k} = 1. Then x = p^{k} ≥ p, so P_{p}(x) =

\frac{x}{p} = p^{k−1}. In other words, \overline{P}_{p}(\underbrace{0, …, 0}_{k}, 1, \overline{0}) = (\underbrace{0, …, 0}_{k−1}, 1, \overline{0}), i.e., \overline{P}_{p} (a_{0}, …, a_{k}, \overline{0}) =

(a_{1}, …, a_{k}, \overline{0}).

(iii) Suppose k ≥ 1, and suppose at least one of the following is not true: a_{0} = ⋯ = a_{k−1} = 0 and a_{k} = 1. Then, x is not a power of p; for otherwise, since x > p^{k}, we must have that x = p^{ℓ} for some integer ℓ > k, meaning that p^{ℓ} is the unique base-p representation of x, in which the leading coefficient is 1 and all the other coefficients are 0, contradicting our supposition. Since p^{k} is the largest power of p not exceeding x, then P_{p}(x) = x − p^{k} = ∑_{i=0}^{k−1} a_{i}p^{i} + (a_{k} − 1) p^{k}. In other words, \overline{P}_{p} (a_{0}, …, a_{k}, \overline{0}) = (a_{0}, …, a_{k} − 1, \overline{0}).

For every x ∈ ℕ, Lemma 17 gives a complete description of the orbit of Ψ_{p}(x) under \overline{P}_{p}, and hence that of the orbit of x under P_{p}. For instance, a complete description of the orbit of 108 under P_{2},

108 ↦ 44 ↦ 12 ↦ 4 ↦ 2 ↦ 1,

can be obtained from the fact that Ψ_{2}(108) = (0, 0, 1, 1, 0, 1, 1, \overline{0}) and, under \overline{P}_{2},

(0, 0, 1, 1, 0, 1, 1, \overline{0}) ↦ (0, 0, 1, 1, 0, 1, \overline{0}) ↦ (0, 0, 1, 1, \overline{0}) ↦ (0, 0, 1, \overline{0}) ↦ (0, 1, \overline{0}) ↦ (1, \overline{0}) .

Now, let α = (a_{k}, …, a_{0}). Based on the definitions of the analogues under P_{p}, the transient length, limit, settling time, and attractor of α under \overline{P}_{p} are

\overline{T}_{p}(α) = min\{n ∈ ℕ : only the first term of α_{n} is non-zero\},
\overline{L}_{p}(α) = α_{\overline{T}_{p}(α)},
\overline{S}_{p}(α) = min\{n ∈ ℕ : α_{n} ∈ \{(\underbrace{0, 0, …, 0}_{t}, 1, \overline{0}) : t ∈ ℕ_{0}\} ∪ \{(1, \overline{0}), …, (p − 1, \overline{0})\}\},
\overline{W}_{p}(α) = α_{\overline{S}_{p}(α)},

respectively, where (α_{n})_{n=1}^{∞} is the orbit of α under \overline{P}_{p}, which is determined by

α_{1} = α  and  α_{n+1} = \overline{P}_{p} (α_{n}) for every n ∈ ℕ.

Proof of Theorem 16. Proving Theorem 16 is equivalent to proving that

\overline{T}_{p}(α) = \begin{cases}ν_{p} (Ψ_{p}^{−1}(α)) + a_{k} + ⋯ + a_{1}, & if a_{0} = 0; \\ 1 + a_{k} + ⋯ + a_{1}, & if a_{0} ≥ 1, \end{cases}

\overline{L}_{p}(α) = \begin{cases}(1, \overline{0}) , & if a_{0} = 0; \\ (a_{0}, \overline{0}) , & if a_{0} ≥ 1, \end{cases}

\overline{S}_{p}(α) = \begin{cases}a_{k} + ⋯ + a_{1}, & if a_{0} = 0; \\ 1 + a_{k} + ⋯ + a_{1}, & if a_{0} ≥ 1, \end{cases}

\overline{W}_{p}(α) = \begin{cases}(\underbrace{0, 0, …, 0}_{ν_{p}(Ψ_{p}^{−1}(α))}, 1, \overline{0}), & if a_{0} = 0; \\ (a_{0}, \overline{0}) , & if a_{0} ≥ 1. \end{cases}

We consider each of the two cases.

Case 1: a_{0} ≥ 1. If k = 0, then the orbit of α = (a_{0}, \overline{0}) is constant, so \overline{L}_{p}(α) = \overline{W}_{p}(α) = (a_{0}, \overline{0}) and \overline{T}_{p}(α) = \overline{S}_{p}(α) = 1, obeying the desired formulae. Now suppose k ≥ 1. Since a_{0} ≥ 1, then each iteration is prescribed by the last branch in (4). Since

α_{1} = (a_{0}, …, a_{k}, \overline{0}) ,

then

α_{1+a_{k}} = \overline{P} _{p}^{a_{k}} (α_{1}) = (a_{0}, …, a_{k−1}, \overline{0}) .

Continuing this, we have, for every j ∈ {k − 1, …, 1},

α_{1+a_{k}+···+a_{j}} = \overline{P} _{p}^{a_{j}} (α_{1+a_{k}+···+a_{j+1}}) = (a_{0}, …, a_{j−1}, \overline{0}) ,

which means that

\overline{T}_{p}(α) = \overline{S}_{p}(α) = 1 + a_{k} + ⋯ + a_{1} and \overline{L}_{p}(α) = \overline{W}_{p}(α) = (a_{0}, \overline{0}) ,

as desired.

Case 2: a_{0} = 0. In this case, k ≥ 1. Let t := ν_{p} (Ψ_{p}^{−1}(α)). Then a_{0} = ⋯ = a_{t−1} = 0 and a_{t} ≥ 1, so

α_{1} = (\underbrace{0, …, 0}_{t}, a_{t}, …, a_{k}, \overline{0}).

By the last branch in (4), we have

α_{1+a_{k}} = \overline{P} _{p}^{a_{k}} (α_{1}) = (\underbrace{0, …, 0}_{t}, a_{t}, …, a_{k−1}, \overline{0}),

and, for every j ∈ {k − 1, …, t + 1},

α_{1+a_{k}+···+a_{j}} = \overline{P} _{p}^{a_{j}} (α_{1+a_{k}+···+a_{j+1}}) = (\underbrace{0, …, 0}_{t}, a_{t}, …, a_{j−1}, \overline{0}).

Next,

α_{a_{k}+···+a_{t}} = \overline{P} _{p}^{a_{t}−1} (α_{1+a_{k}+···+a_{t+1}}) = (\underbrace{0, …, 0}_{t}, 1, \overline{0}).

At this point we have proved that

\overline{S}_{p}(α) = a_{k} + ⋯ + a_{1} and \overline{W}_{p}(α) = (\underbrace{0, …, 0}_{t}, 1, \overline{0}) = (\underbrace{0, 0, …, 0}_{ν_{p}(Ψ_{p}^{−1}(α))}, 1, \overline{0}).

Finally, the dynamics concludes with t iterations prescribed by the second branch in (4):

α_{a_{k}+···+a_{t}+t} = \overline{P} _{p}^{t} (α_{a_{k}+···+a_{t}}) = (1, \overline{0}) .

Therefore,

\overline{T}_{p}(α) = t + a_{k} + ⋯ + a_{1} = ν_{p} (Ψ_{k}^{−1}(α)) + a_{k} + ⋯ + a_{1} and \overline{L}_{p}(α) = (1, \overline{0}) ,

as desired. □

0 2 4 6 8 2 4 6 8 ln x T̂(x), T̂_{2}(x) T̂_{2} ; T̂  ^{0 2 4 6 8 2 4 6 ln x Ŝ(x), Ŝ_{2}(x) Ŝ_{2} ; Ŝ}

Figure 4: Plots of T̂(x) and T̂_{2}(x) versus ln x (left) and Ŝ(x) and Ŝ_{2}(x) versus ln x (right) for x ∈ {1, …, 1 · 10^{4}}.

3.2 A comparison of P_{p} and P

Let p ∈ ℙ. For every x ∈ ℕ, let

T̂_{p}(x) := \frac{1}{x} ∑_{t=1}^{x} T_{p}(t)  and  Ŝ_{p}(x) := \frac{1}{x} ∑_{t=1}^{x} S_{p}(t)

be the x-th Cesáro mean of the sequences (T_{p}(x))_{x=1}^{∞} and (S_{p}(x))_{x=1}^{∞}, respectively. From Theorem 16, noticing that

\frac{|\{t ≤ x : p | t\}|}{x} = \frac{1}{x} ⌊\frac{x}{p}⌋ ∼ \frac{1}{p}

and

\frac{1}{x} ∑_{t=1}^{x} ν_{p}(t) = \frac{1}{x} ∑_{t=1}^{⌊log_{p} x⌋} ⌊\frac{x}{p^{t}} ⌋ ∼ ∑_{t=1}^{⌊log_{p} x⌋} \frac{1}{p^{t}} ∼ \frac{1}{p − 1}

and applying

\frac{1}{x} ∑_{t=1}^{x} σ_{p}(t) ∼ \frac{(p − 1) ln x}{2 ln p}

[2, Theorem 1], one proves the following corollary.

Corollary 18. We have

T̂_{p}(x) ∼ Ŝ_{p}(x) ∼ \frac{(p − 1) ln x}{2 ln p}.

1 1.2 1.4 1.6 1.8 2 2.2 1.5 2 2.5 3 Ŝ(x) T̂(x)

Figure 5: Plot of T̂(x) versus Ŝ(x) for x ∈ {1, …, 1 · 10^{5}}.

Thus, the growths of T̂_{p}(x) and Ŝ_{p}(x) with x are both logarithmic. By contrast, letting

T̂(x) := \frac{1}{x} ∑_{t=1}^{x} T (t)  and  Ŝ(x) := \frac{1}{x} ∑_{t=1}^{x} S(t),

from Theorems 3 and 10 we know that the former grows at most logarithmically, and the latter at most double-logarithmically. In fact, Figure 4 suggests that both quantities grow at most double-logarithmically; in particular,

T̂(x) ≪ ln ln x.

This is confirmed by Figure 5 which suggests the existence of λ ≥ 1 such that

\frac{T̂(x)}{Ŝ(x)} ∼ λ.  (5)

Now, since

(T̂ − Ŝ) (x) = \frac{1}{x} ∑_{t=1}^{x}(T − S)(t)

= \frac{1}{x} ∑_{u=0}^{max_{1≤t≤x}(T −S)(t)} u |(T − S)^{−1}(\{u\}) ∩ \{1, …, x\}|

= ∑_{u=1}^{max_{1≤t≤x}(T −S)(t)} u d_{x} ((T − S)^{−1}({u}))

≤ d_{x} ((T − S)^{−1}(ℕ)) ( max_{1≤t≤x}(T − S)(t))^{2} ,

10 12 14 −0.33 −0.32 −0.31 −0.3 ln x ln (d_{x} (W^{−1} (ℕ_{≥2})))  ^{0 2 · 10^{5} 4 · 10^{5} 6 · 10^{5} 8 · 10^{5} 1 · 10^{6} 0.72 0.73 0.74 x d_{x} (W^{−1} (ℕ_{≥2}))}

Figure 6: Plot of d_{x} (W^{−1} (ℕ_{≥2})) versus x for x ∈ {5 · 10^{4}, …, 1 · 10^{6}} in log-log scale (left) together with the least-squares line determined using its values for x ∈ {6 · 10^{5}, …, 1 · 10^{6}} which has slope α ≈ −0.006 and ordinate intercept β ≈ −0.243, and in linear-linear scale (right) together with the curve e^{β}x^{α}.

then we have (T̂ − Ŝ) (x) ⟶^{x→∞} 0 if d_{x} ((T − S)^{−1}(ℕ)) = d_{x} (W^{−1} (ℕ_{≥2})) decays algebraically to zero as x → ∞. An extensive dataset provides an evidence for the latter (Figure 6), leading to the following conjecture.

Conjecture 19. There exist c ∈ (0, 1) and α ∈ (−10^{−2}, −10^{−3}) such that

d_{x} (W^{−1} (ℕ_{≥2})) ∼ cx^{α} as x → ∞.

In particular, almost every orbit of P contains no prime power.

Notice that if this conjecture holds, then so does (5) with λ = 1.

References

[1] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes, II, Proc. Lond. Math. Soc. (3) 83 (2001), 532–562.

[2] L. E. Bush, An asymptotic formula for the average sum of the digits of integers, Amer. Math. Monthly 47 (1940), 154–156.

[3] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6^{th} edition, Oxford University Press, 2008.

[4] G. Hoheisel, Primzahlprobleme in der Analysis, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin 33 (1930), 3–11.

[5] T. Koshy, Elementary Number Theory with Applications, 2^{nd} edition, Elsevier, 2007.

[6] P. Leonetti and S. Tringali, On small sets of integers, Ramanujan J., to appear.

    Available at https://arxiv.org/abs/1905.08075.

[7] F. Luca and R. Thangadurai, On an arithmetic function considered by Pillai, J. Théor. Nombres Bordeaux 21 (2009), 693–699.

[8] M. D. Nasso and R. Jin, Abstract densities and ideals of sets, Acta Arith. 185 (2018), 301–313.

[9] S. S. Pillai, On an arithmetic function concerning primes, Annamalai University Journal 1 (1930), 159–167.

[10] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2020.

[11] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge University Press, 1995.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11A41, 37P99. Keywords: prime, prime power, prime gap.

(Concerned with sequences \underline{A000040}, \underline{A000079}, \underline{A000961}, \underline{A066352}, and \underline{A336825}.)

Received October 12 2020; revised versions received December 28 2020; January 6 2021. Published in Journal of Integer Sequences, January 24 2021.

Return to Journal of Integer Sequences home page.