On the Erdős-Sloane and Shifted Sloane Persistence Problems

Gabriel Bonuccelli, Lucas Colucci, and Edson de Faria^{1} Instituto de Matemática e Estatística Universidade de São Paulo São Paulo Brazil

                     gabrielbhl@ime.usp.br
                      lcolucci@ime.usp.br
                       edson@ime.usp.br

Abstract In this paper, we investigate two variations on the so-called persistence problem of Sloane: the shifted version, which was introduced by Wagstaff; and the nonzero version, proposed by Erdős. We explore connections between these problems and a recent conjecture of de Faria and Tresser regarding equidistribution of the digits of some integer sequences and a natural generalization of it.

1 Introduction

In 1973, Sloane [9] proposed the following question: given a positive integer n, multiply all its digits together to get a new number, and keep repeating this operation until a single-digit number is obtained. The number of operations needed is called the persistence of n. Is it true that there is an absolute constant C(b) (depending solely on the base b in which the numbers are written) such that the persistence of every positive integer is bounded by C(b)? Despite many computational searches, heuristic arguments and related conjectures in favor of a positive answer, no proof or disproof of this conjecture has been found so far.

1This work has been supported by “Projeto Temático Dinâmica em Baixas Dimensões” FAPESP Grant 2016/25053-8.

Many variants of Sloane’s problem have been considered as well. The famous book of Guy [5] mentions that Erdős introduced the version of the Sloane problem wherein only the nonzero digits of a number are multiplied in each iteration, which we call the Erdős-Sloane problem. Another variant was raised by Diamond and Reidpath [3], where instead of the usual base b, numbers are taken to the so-called factorial base. Less related variations include the additive persistence (when the digits are summed up instead of multiplied) [7] or versions where even more general functions of the digits are considered [1, 6].

In this paper, we will be concerned with the Erdős-Sloane version and the shifted Sloane problem, introduced by Wagstaff [10], which consists in shifting all the digits of the number by a fixed positive integer before multiplying them.

2 Definitions and notation

For integers t ≥ 0 and b ≥ 2, the t-shifted Sloane map in base b is the map S_{t,b} that takes a nonnegative integer n = ∑_{i=0}^{k} d_{i}b^{i} (as usual, 0 ≤ d_{i} ≤ k − 1 for all i and d_{k} > 0) to the integer S_{t,b}(n) = ∏_{i=0}^{k}(d_{i} + t). This function was introduced (in the special case b = 10) by Wagstaff [10], motivated by a question of Erdős and Kiss. Note that t = 0 corresponds to the map that we iterate in the original persistence problem. Furthermore, the Erdős-Sloane map in base b, denoted by S_{b}^{∗}, is the map that sends n = ∑_{i=0}^{k} d_{i}b^{i} to S_{b}^{∗}(n) = ∏_{0≤i≤k,d_{i}≠0} d_{i}. The set of nonnegative integers is denoted by ℕ. We use the notation f^{k}(n) to denote the k-th iterate of a map f on the point n, i.e., f^{0}(n) = n and f^{k}(n) = f(f^{k−1}(n)) for every k ≥ 1, and we let Per(f) denote the set of periodic points of f. Finally, for 0 ≤ d ≤ b − 1 and an integer n, we let #d(n)_{b} denote the number of digits d in the expansion of n in base b (e.g., #2(100_{10})_{3} = 1, since 100_{10} = 10201_{3}), and #(n)_{b} denote the number of digits of the base-b expansion of n. The subscripts b will be omitted when clear from the context.

We are interested in the dynamics of S_{t,b} and S_{b}^{∗}. Contrarily to the original problem (t = 0) and to S_{b}^{∗}, for t ≥ 1 it is not even clear that every n reaches a fixed point or a cycle of S_{t,b}. If it does, the smallest number of iterations to reach it will be called, as usual, the persistence of n, and it will be denoted, respectively, by ν_{t,b}(n) and ν_{b}^{∗}(n) (we set those values to ∞ in case the corresponding sequence of iterates diverges). Even the basic question of whether ν_{t,b}(n) is finite for every n is not so readily answered for many values of t and b, and it is open for most of them. On the other hand, it is easy to see that S_{b,b}(n) > n holds for every b and n, so ν_{t,b}(n) = ∞ for every n whenever t ≥ b. Thus, from now on, we will assume that t ≤ b − 1 unless stated otherwise.

3 Questions

For every b ≥ 2 and 0 ≤ t ≤ b−1, one defines the t-shifted Sloane problem in base b as in the previous section. We will refer to this problem as the (t, b) problem for short. Furthermore, for every b ≥ 2, we may consider the Erdős-Sloane problem in base b, and, similarly, we will refer to this problem as the (∗, b) problem.

For each of the (t, b) and (∗, b) problems, there are different questions one may ask about the corresponding iterating map f = S_{t,b} (or f = S_{b}^{∗}).

1. The most basic question is the following: let A_{f} denote the set of nonnegative integers n such that the sequence of iterates (f^{k}(n))_{k≥0} stabilizes (i.e., reaches either a cycle or a fixed point of f). What can be said about A_{f}? It is trivial that A_{f} = ℕ in the original problem (t = 0) and in the Erdős-Sloane problem. We will prove (Theorem 7) that A_{f} = ℕ for t = 1 and b ≥ 2 as well (extending a result of Wagstaff [10]). Furthermore, we will prove that some natural conjectures on the equidistribution of digits of some sequences imply that A_{f} = ℕ for some pairs (t, b) and that ℕ − A_{f} contains all sufficiently large integers for other pairs (t, b), but our results do not cover all the range of (t, b) (Theorems 15, 17, 19, 20 and 23).

2. In case A_{f} = ℕ, i.e., every n ∈ ℕ stabilizes under iteration by f, is there a universal constant that bounds the persistence of all numbers, that is, is there C such that ν_{t,b}(n) ≤ C (or ν_{b}^{∗}(n) ≤ C) for every n ∈ ℕ? Note that the positive answer to the question for t = 0 is the original Sloane conjecture. Perhaps surprisingly, we prove that the equidistribution conjectures imply a negative answer for t = 1 and for the Erdős-Sloane problem, which shows a pronounced difference in the behaviors of the (0, b) problem and the (1, b) and (∗, b) problems (Theorems 5, 6, 10 and 13).

3. Still assuming A_{f} = ℕ, we know that every integer n reaches either a fixed point or a cycle of f. What are the cycles and the fixed points of f? Besides the trivial cases (0, b) and (∗, b), we are able to describe them precisely in the case t = 1 for any b ≥ 3 (Theorem 7).

4. Finally, the most detailed question we deal with is the following: for a cycle (or fixed point) C of f, which integers n tend to an element of C under iteration by f? That is, what are the backward orbits of each cycle C? We can answer this question precisely only in the case t = 1 and b = 3 (Theorem 8).

4 Equidistribution of digits in products of primes

If an integer n contains a digit zero in its base-b expansion, then S_{0,b}(n) = 0; otherwise, it is a product of positive digits in base b, i.e., the integers from 1 to b − 1. This simple fact implies that almost all integers have persistence equal to one, in the sense that the number of integers up to N having this property is asymptotically equal to N when N → ∞. Furthermore, it implies that, when considering the dynamics of S_{0,b} (or S_{b}^{∗}), it is frequently enough to deal with products of integers less than b, i.e., products of power of primes smaller than b. Similarly, for S_{t,b}, it is enough to consider products of integers between t and t+b−1. Based on strong computational evidence and heuristic models, de Faria and Tresser [2] proposed a conjecture that states, in particular, that some sequences of this kind of numbers have a very regular asymptotic distribution of digits. Before stating their conjecture, we introduce one more definition: given ε > 0, a number n, and a base b, we say that the digits of n are ε-equidistributed (in base b) if, for every digit d ∈ \{0, …, b − 1\}, we have |\frac{#d(n)_{b}}{#(n)_{b}} − \frac{1}{b}| < ε.

Conjecture 1 (de Faria, Tresser [2]). Given an integer q > 1, a finite set of primes F that does not contain all the primes dividing q, and a positive integer a, let (N_{i})_{i≥0} be a sequence of integers such that N_{0} = a and, for every k ≥ 0, N_{k+1} = N_{k} · p_{k}, where p_{k} ∈ F. Then the digits {0, …, q −1} are asymptotically equidistributed when n → ∞ in the base-q expansion of the N_{i}. That is, given ε > 0, there is n_{0} such that N_{n} is ε-equidistributed in base q for every n ≥ n_{0}.

This form of the conjecture stems from an earlier one that arose in discussions between C. Tresser and G. Hentchel [2, p. 381]. Remark 2. The full version of Conjecture 1 also states that the equidistribution holds for blocks of consecutive digits of any length l > 0, i.e., given a block of l digits, its proportion in the base-q expansion of the numbers in the sequences (N_{i})_{i≥0} is asymptotically equal to \frac{1}{q^{l}}.

Remark 3. Although Conjecture 1 seems very natural, even its simplest instances are not known to be true. For instance, it is not known whether the sequence (2^{n})_{n≥0} is asymptotically equidistributed in base 3. Indeed, even the old conjecture of Erdős [4] that states that all but finitely many terms of this sequence contain a digit two in its ternary expansion is still open.

Although Conjecture 1 is enough to prove results in base 3 (and, in some cases, base 4), for larger bases one needs a uniform, or “multidimensional” generalized version, which we now state.

Conjecture 4 (Uniform generalization of Conjecture 1). Let q > 1 be an integer, F = {p_{1}, …, p_{k}} be a finite set of primes that does not contain all the primes dividing q, and a be a positive integer. Then, for every ε > 0, there exists N such that a ∏_{i=1}^{k} p_{i}^{α_{i}} is ε-equidistributed in base q whenever α_{i} ≥ N for some i ∈ {1, …, k}.

5 Main results

5.1 Erdős-Sloane problem

First, we consider the Erdős-Sloane version. It is trivial that the only periodic points of the Erdős-Sloane map in base b are the fixed points 1, 2, …, b − 1. As for the persistence of a number, we prove that Conjectures 1 and 4 imply that the analog of Sloane’s conjecture does not hold in this context.

Theorem 5. Conjecture 1 implies that for both S_{3}^{∗} and S_{4}^{∗}, there are integers with arbitrarily large persistence. Moreover, Conjecture 4 implies the same result for S_{b}^{∗}, for every b ≥ 5.

Proof. We divide the proof into three cases: b = 3, b = 4 and b ≥ 5.

(i) Base 3

Let f denote S_{3}^{∗} for ease of notation. Taking q = 3, F = {2} and a = 1 in Conjecture 1, we get the following statement: for every ε > 0, there is N such that the proportion of digits d (d = 0, 1, 2) in 2^{n} is in (1/3 − ε, 1/3 + ε) whenever n ≥ N.

Take ε = 1/6. There is N such that the proportion of digits d (d = 0, 1, 2) in 2^{n} is in (1/6, 1/2) whenever n ≥ N. Take m such that m(1/6)^{t−1}(log_{3} 2)^{t−1} ≥ max{N, 3} and consider the integer n = 2^{m}. We claim that ν_{3}^{∗}(n) ≥ t.

As m = m(1/6)^{0}(log_{3} 2)^{0} ≥ max{N, 3}, we know that 2^{m} has at least 1/6 of its digits equal to 2. Thus, f(m) = 2^{m_{1}}, where m_{1} ≥ (1/6) log_{3} 2^{m} = m(1/6) log_{3} 2. As m(1/6) log_{3} 2 ≥ max{N, 3}, we know that the persistence of m is at least two and that 2^{m_{1}} has at least 1/6 of its digits equal to 2. Thus, f(f(2^{m})) = f(2^{m_{1}}) = 2^{m_{2}}, where m_{2} ≥ 2^{m(1/6)^{2}(log_{3} 2)^{2}}. Inductively, we get that f^{t−1}(2^{m}) = 2^{m_{t−1}}, where m_{t−1} ≥ 2^{m(1/6)^{t−1}(log_{3} 2)^{t−1}} ≥ 3: indeed, if f^{i}(2^{m}) = 2^{m_{i}} with m_{i} ≥ m(1/6)^{i}(log_{3} 2)^{i}, we have that f^{i}(2^{m}) is ε-equidistributed, since m(1/6)^{i}(log_{3} 2)^{i} ≥ N, and then at least 1/6 of its digits are equal to 2. This implies that f^{i+1}(2^{m}) = 2^{m_{i+1}}, where m_{i+1} ≥ (1/6) log_{3} f^{i}(2^{m}) ≥ m(1/6)^{i+1}(log_{3} 2)^{i+1}, and completes the induction. Hence, f^{t−1}(2^{m}) ≥ 2^{m(1/6)^{t−1}(log_{3} 2)^{t−1}} ≥ 3, which means that n = 2^{m} has persistence at least t.

(ii) Base 4

In this case, we apply Conjecture 1 twice, with q = 4, F = 3, a = 1; and q = 4, F = 3, a = 2, respectively, to get that for every ε > 0 there is N such that 3^{m} and 2 · 3^{m} are ε-equidistributed whenever m ≥ N. Noting that, for every a and b, we have f(2^{a} · 3^{b}) is either equal to f(3^{b}) or f(2 · 3^{b}) and applying the same argument as in item (i) with ε = 1/8, one can show that ν_{4}^{∗}(3^{m}) ≥ t if m(1/8)^{t−1}(log_{3} 4)^{t−1} ≥ max{N, 4}.

(iii) Larger bases

For b ≥ 5, let F be the set of primes smaller than b and F_{r} = F − {r}. We apply Conjecture 4 for each prime divisor r of b and each proper divisor d of b, with F_{r} being the set of primes considered, q = b and a = d. Note that, by Bertrand’s postulate (which states that, for every n > 1, there is a prime p such that n < p < 2n), there is some prime q such that (b − 1)/2 < q < b, which means that q does not divide b. Taking the maximum of the N given in each application of the conjecture with a fixed ε > 0, we get the following statement: for every ε > 0, there is N such that d ∏_{p_{i}∈F_{r}} p_{i}^{α_{i}} is ε-equidistributed whenever α_{i} ≥ N for some i ∈ {1, …, k}, where d is a proper divisor of b and r is a prime divisor of b. Moreover, note that, for every n, one has f(bn) = f(n), since the expansion of bn and n in base b differ only by one digit 0.

We claim that ν ∗_{b} (n) ≥ t, where n = (∏_{p_{i}∈F, p_{i}∤b} p_{i})^{m} and m satisfies the inequality m(1/(2b))^{t−1}(log_{b} 2)^{t−1} ≥ max{N, b}, where N is the integer given by the applications of Conjecture 4 as above with ε = 1/(2b). As m ≥ N, n is ε-equidistributed, whence, using a rough bound (∏_{p_{i}∈F, p_{i}∤b} p_{i})^{m} ≥ 2^{m}, we have f(n) = ∏_{p_{i}≤b prime} p_{i}^{β_{i}}, with β_{i} ≥ (1/b − ε)#(n)_{b} ≥ (1/(2b))(log_{b} 2)m. The fact that f(ba) = f(a) for every a implies that f(f(n)) = f(d ∏_{p_{i}∈F_{r}} p_{i}^{α_{i}}) for some proper divisor d of b and some prime r dividing b. As α_{i} ≥ β_{i} for every p_{i} that does not divide b (because no power of p_{i} can be factored out into powers or divisors of b), we have α_{i} ≥ (1/(2b))(log_{b} 2)m ≥ N for some i ∈ {1, …, k}. Then the number d ∏_{1≤i≤k} p_{i}^{α_{i}} is ε-equidistributed, and hence we have

f(f(n)) = ∏_{p_{i}≤b prime} p_{i}^{β′_{i}}

with

β′_{i} ≥ (1/(2b))#(d ∏_{1≤i≤k} p_{i}^{α_{i}})_{b} ≥ (1/(2b))(log_{b} 2)α_{i} ≥ (1/(2b))^{2}(log_{b} 2)^{2} · m

for every i, and the argument can be repeated. Inductively, the exponents of the p_{i} in f^{t−1}(n) are at least (1/(2b))^{t−1}(log_{b} 2)^{t−1} · m. In particular, we have

f^{t−1}(n) ≥ 2^{(1/(2b))^{t−1}(log_{b} 2)^{t−1}·m} ≥ 2^{b} ≥ b^{2}.

By the choice of m, this number is at least b, so n has persistence at least t.

In other words, assuming Conjectures 1 and 4, Theorem 5 states that lim sup_{n→∞} ν_{b}^{∗}(n) = ∞ for every b ≥ 3. Our next result gives an estimate on this number which is sharp up to a constant factor.

Theorem 6. For each base b ≥ 3, we have

lim sup_{n→∞} \frac{ν_{b}^{∗}(n)}{log log n} ≤ \frac{1}{log (α^{−1})},  (1)

where α = log_{b} (b − 1). Moreover, if Conjecture 4 holds, then we have

lim sup_{n→∞} \frac{ν_{b}^{∗}(n)}{log log n} ≥ \frac{1}{log (β^{−1})},  (2)

where β = \frac{log_{b} 2}{2b}.

Proof. For ease of notation, let us denote by f the Erdős-Sloane map S_{b}^{∗} in base b. The proof is naturally divided into two parts.

(i) Upper bound. Given n > b, let us denote by k_{j} (j = 0, 1, …) the number of digits of f^{j}(n) in base b. Note that k_{j} ≤ 1 + log_{b} f^{j}(n) for all j. Since each digit in the base-b expansion of f^{j}(n) is at most b − 1, we have f^{j+1}(n) ≤ (b − 1)^{k_{j}}. Therefore, for all j ≥ 0 we get

k_{j+1} ≤ 1 + k_{j} log_{b} (b − 1) = 1 + αk_{j}.

By induction, it follows that for all j ≥ 1 we have

k_{j} ≤ α^{j}k_{0} + (1 + α + α^{2} + ⋯ + α^{j−1}) < α^{j}k_{0} + \frac{1}{1 − α}.  (3)

Since α < 1, the first term in the right-hand side of (3) goes to zero as j → ∞. Thus, let j_{0} be the smallest natural number such that α^{j_{0}}k_{0} < 1. An easy calculation shows that

j_{0} = ⌈\begin{matrix}log & b & k_{0} \\ log & b & (α^{−1}) \end{matrix}⌉ ,

and since k_{0} ≤ 1 + log_{b} n ≤ 2 log_{b} n when n ≥ b, it follows that

j_{0} ≤ \frac{log_{b} log_{b} n}{log_{b} (α^{−1})} + (1 + \frac{log_{b} 2}{log_{b} (α^{−1})}) .

But now note that k_{j_{0}} ≤ D, where D = 1 + ⌈(1 + α)^{−1}⌉. Hence, defining

M = max {ν_{b}^{∗}(m) : m has at most D digits in base b} < ∞,

we see that ν_{b}^{∗}(f^{j_{0}}(n)) ≤ M. Since we clearly have ν_{b}^{∗}(n) = j_{0} + ν_{b}^{∗}(f^{j_{0}}(n)), it follows that

ν_{b}^{∗}(n) ≤ \frac{log_{b} log_{b} n}{log_{b} (α^{−1})} + (1 + M + \frac{log_{b} 2}{log_{b} (α^{−1})})
= \frac{log log_{b} n}{log (α^{−1})} + (1 + M + \frac{log_{b} 2}{log_{b} (α^{−1})}) .

Dividing both sides of this inequality by log log n and taking the lim sup as n → ∞, we get (1) as desired.

(ii) Lower bound. Here we shall use one of the ideas used in the proof of Theorem 5. For each natural number t, let us consider n_{t} = (∏_{p_{i} prime, p_{i}<b, p_{i}∤b} p_{i})^{m_{t}}, where m_{t} is the smallest positive integer such that

m_{t} (\frac{1}{2b})^{t−1} (log_{b} 2)^{t−1} ≥ C = max\{b, N\},

and where N is given by Conjecture 4 taking ε = \frac{1}{2b}. As we saw in the proof of Theorem 5, we have ν_{b}^{∗}(n_{t}) ≥ t. Now, by the very definition of m_{t}, we know that

(m_{t} − 1) (\frac{1}{2b})^{t−1} (log_{b} 2)^{t−1} < C.

Taking logarithms (to base b) on both sides of this inequality and solving for t, we get

t > \begin{matrix}log & b & (m_{t} − 1) \\ log & b & (β^{−1}) \end{matrix} + 1 − \frac{log_{b} C}{log_{b} (β^{−1})},

where β = \frac{log_{b} 2}{2b}. Note that log_{b} (m_{t} − 1) > log_{b} m_{t}−log_{b} 2 (because m_{t} > 2). Moreover, again from the definition of m_{t}, we have

log_{b} m_{t} = log_{b} log_{b} n_{t} − log_{b} log_{b} ( ∏_{1≤i≤k} p_{i}) .

Putting all these facts together, we deduce that

ν_{b}^{∗}(n_{t}) > log_{b} log_{b} n_{t} ; log_{b} (β^{−1}) + K
= log log_{b} n_{t} ; log (β^{−1}) + K,  (4)

where K is a constant, namely

K = 1 − \frac{1}{log_{b} (β^{−1})} log_{b} (2C log_{b} ( ∏_{1≤i≤k} p_{i})) .

Thus, the inequalities in (4) divided by log log n_{t}, letting t → ∞, imply that

lim sup_{t→∞} \frac{ν_{b}^{∗}(n_{t})}{log log n_{t}} ≥ \frac{1}{log (β^{−1})},

and this obviously implies (2).

5.2 1-shifted problem

In this section, we generalize a result of Wagstaff [10] for base 10, showing that for any base b, every positive integer n reaches reach a fixed point or a cycle under iteration by S_{1,b}.

Theorem 7. Let b ≥ 2. Then, for every positive integer n, the iterates of S_{1,b} starting at n reach one of the following cycles:

(10_{2}),  if b = 2;
(2, …, b − 1, 10_{b}) or (1(b − 2)_{b}),  if b ≥ 3.

Proof. For ease of notation, let f denote S_{1,b} in this proof. First of all, notice that the theorem is trivial for b = 2, since in this case f(n) is a power of 2 for every n, and then f^{2}(n) = 10_{2}, which is the only fixed point of f. From this point on, we assume that b ≥ 3.

Assume first that n is of the form db^{k}−1, where 2 ≤ d ≤ b (i.e., all the digits of n, possibly with the exception of the leading digit, are equal to b − 1; the leading digit of n is d − 1; and n has exactly k digits). In this case, f(n) = db^{k−1} = n + 1, and 2 ≤ f(f(n)) ≤ b = 10_{b}, so this number belongs to the cycle (2, 3, …, 10_{b}).

If n is not of the form above, let n = (d_{k}d_{k−1} ⋯ d_{0})_{b} be the representation of n in base b, and let j be the biggest index i such that i < k and d_{i} < b − 1. We can bound f(n) from above by (d_{k} +1)(d_{j} +1)b^{k−1}, which can be written as d_{k}b^{k} +d_{j}b^{k−1}+b^{k−1}(1+d_{k}(d_{j} −(b−1))).

On the other hand, we have that n = ∑_{i=0}^{k} d_{i}b^{i} ≥ d_{k}b^{k} + d_{j}b^{k+1}. If the term

b^{k−1}(1 + d_{k}(d_{j} − (b − 1)))

is negative, we have f(n) < n. As d_{j} ≤ b − 2, this term is nonnegative only if d_{j} = b − 2 and d_{k} = 1. In this case, the bound for f(n) becomes equal to db^{k} + (b − 2)b^{k−1}. Furthermore, if j < k − 1, then the lower bound on n can be strengthened to

n ≥ b^{k} + (b − 1)b^{k+1} + (b − 2)b^{j}

and hence f(n) < n. So we must have j = k − 1 to have f(n) ≥ n. Also, if any digit of n other than d_{k} and d_{k−1} is not zero, we have n > db^{k} +(b−2)b^{k−1} ≥ f(n). Therefore, f(n) < n unless n is of the form 1(b − 2)000 ⋯ 0_{b} = b^{k} + (b − 2)b^{k−1}. In this case, f(n) = 2(b − 1), which implies that f(n) < n unless k = 1, which corresponds to the fixed point n = 1(b−2)_{b}. This proves that f either reaches the fixed point 1(b − 2)_{b} or keeps decreasing until it enters the cycle (2, 3, …, 10_{2}).

In the case b = 3, we are able to tell which integers reach the fixed point and which integers reach the cycle. Namely, we have the following result.

Theorem 8. For every n ≥ 1, the sequence (S_{1,3}^{k}(n))_{k≥1} reaches the cycle (2, 10_{3}) if and only if either n or 2^{#1(n)_{3}} lacks the digit 1 in its ternary expansion; otherwise, it reaches (11_{3}).

Proof. Once more, let f denote S_{1,3}. The result is clear for n ∈ {1, 2, 10_{3}, 11_{3}}. Let n ≥ 12_{3}. Notice that f(n) = 2^{#1(n)}3^{#2(n)}, so f(n) ends in #2(n) zeros in base 3, and hence f(f(n)) = f(2^{#1(n)}).

If #1(n) = 0, then f(f(n)) = f(1) = 2. Also, if #1(2^{#1(n)}) = 0, then f^{3}(n) = f(f(2^{#1(n)})) = f(2^{#1(2^{#1(n)})}) = f(1) = 2.

On the other hand, assume that both #1(n) and #1(2^{#1(n)}) are positive. We will prove by induction on n (over those values such that #1(n) > 0 and 2^{#1(n)} > 0) that, in this case, (f^{k}(n))_{k≥1} reaches the cycle (11_{3}).

The result if trivial if n ≤ 11_{3}. If n > 11_{3}, then f(f(n)) = f(2^{#1(n))}). As 2^{#1(n)} < n, we can use the induction hypothesis to prove that n reaches (11_{3}) if we have #1(2^{#1(n)}) > 0 and #1(2^{#1(2^{#1(n)})}) > 0. The first inequality is just part of the condition on n; the second comes from the fact that #1(2^{#1(n)}) is even (an even number must have an even number of digits 1 in its ternary expansion), and hence 2^{#1(2^{#1(n)})} is a power of four, and so it ends with a digit 1.

Remark 9. By Conjecture 1, the number of n such that #1(2^{n})_{3} = 0 is finite. A result of Narkiewicz [8] says that the number of n up to N with this property is bounded by 1.62N^{log_{3} 2}, so in particular their density in the set of positive integers is zero (this fact also follows from a more general result of de Faria and Tresser [2, Corollary 3.7]).

As for persistence, similarly as in Theorem 5, we prove that Conjectures 1 and 4 imply that there are integers of arbitrarily large persistence for S_{1,b}.

Theorem 10. Conjecture 1 implies that there are integers of arbitrarily large persistence for the 1-shifted problem in base 3 and 4, and Conjecture 4 implies the same result for bases greater than 4.

Proof. We split the proof into three cases:

(i) Base 3

Put f = S_{1,3}. Conjecture 1 implies the following: for every ε > 0, there exists N such that 2^{m} is ε-equidistributed whenever m ≥ N. To construct a number of persistence greater than t, notice that, if a number a has exactly x digits 1 in its ternary expansion, then f^{2}(a) = f(2^{x}). Take ε = 1/6 and let N be the integer given by Conjecture 1 for this value of ε. Let m be such that m(1/6)^{t−1}(log_{3} 2)^{t−1} ≥ max{N, 3}.

We claim that the number n = 2^{m} has persistence larger than t. Let us denote, for i ≥ 1 by a_{i} and b_{i}, respectively, the numbers defined inductively in the following way: 2^{m} has a_{1} digits 1 and b_{1} digits 2 in its ternary expansion, and f(2^{a_{i}}) = 2^{a_{i+1}} · 3^{b_{i+1}} for every i ≥ 1. As m ≥ N, 2^{m} is ε-equidistributed, so we have a_{1} ≥ (1/6)(log_{3} 2)m. This implies that f^{2}(2^{m}) = f(2^{a_{1}} · 3^{b_{1}}) = f(2^{a_{1}}) = 2^{a_{2}} · 3^{b_{2}}. As a_{1} ≥ (1/6) log_{3} 2 · m ≥ N, the number 2^{a_{1}} is ε-equidistributed, and this in turn implies that a_{2} ≥ (1/6) log_{3}(2) · a_{1} ≥ (1/6)^{2}(log_{3} 2)^{2}m. Inductively, we have that f^{t−1}(2^{m}) = 2^{a_{t−1}} · 3^{b_{t−1}} where a_{t−1} ≥ (1/6)^{t−1}(log_{3} 2)^{t−1}m ≥ 3, which implies that n = 2^{m} has persistence at least t, since Theorem 7 shows that the elements of the cycle and the fixed point of f have at most two digits.

(ii) Base 4

We consider the number n = 3^{m}, where m(1/8)^{t−1}(log_{4} 3)^{t−1} ≥ max{M, 4}, where M is the maximum of the N obtained applying Conjecture 1 with (q, F, a) = (4, {3}, 1) and (q, F, a) = (4, {3}, 2), in both cases with ε = 1/8, and the proof of item (i) applies.

(iii) Larger bases

Finally, for b ≥ 5, let F be the set of primes smaller than b and F_{r} = F − {r}. We apply Conjecture 4 for each prime divisor r of b and each proper divisor d of b, with F_{r} being the set of primes considered, q = b and a = d. Note that, by Bertrand’s postulate (which states that, for every n > 1, there is a prime p such that n < p < 2n), there is some prime s such that (b − 1)/2 < s < b. In particular, s does not divide b (so that F_{r} is nonempty for every prime r dividing b). Taking the maximum of the N given in each application of the conjecture with a fixed ε > 0, we get the following statement: for every ε > 0, there is N such that d ∏_{p_{i}∈F_{r}} p_{i}^{α_{i}} is ε-equidistributed whenever α_{i} ≥ N for some i ∈ {1, …, k}, where d is a proper divisor of b and r is a prime divisor of b. Moreover, note that, for every n, one has f(bn) = f(n), since the expansion of bn and n in base b differ only by one digit 0.

We claim that ν_{1,b}(n) ≥ t, where n = (∏_{p_{i}∈F, p_{i}∤b} p_{i})^{m} and m satisfies the inequality m(1/(2b))^{t−1}(log_{b} 2)^{t−1} ≥ max{N, b}, where N is the integer given by the applications of Conjecture 4 as above with ε = 1/(2b). As m ≥ N, n is ε-equidistributed, whence, using a rough bound (∏_{p_{i}∈F, p_{i}∤b} p_{i})^{m} ≥ 2^{m}, we have f(n) = ∏_{p_{i}≤b prime} p_{i}^{β_{i}}, with β_{i} ≥ (1/b − ε)#(n)_{b} ≥ (1/(2b))(log_{b} 2)m. The fact that f(ba) = f(a) for every a implies that f(f(n)) = f(d ∏_{p_{i}∈F_{r}} p_{i}^{α_{i}}) for some proper divisor d of b and some prime r dividing b. As α_{i} = β_{i} for every p_{i} that does not divide b (because no power of p_{i} can be factored out into powers or divisors of b), we have α_{i} ≥ (1/(2b))(log_{b} 2)m ≥ N for some i ∈ {1, …, k}. Then the number

d ∏_{1≤i≤k} p_{i}^{α_{i}}

is ε-equidistributed, and hence we have f(f(n)) = ∏_{p_{i}≤b prime} p_{i}^{β′_{i}} with

β′_{i} ≥ (1/(2b))#(d ∏_{1≤i≤k} p_{i}^{α_{i}})_{b} ≥ (1/(2b))(log_{b} 2)α_{i} ≥ (1/(2b))^{2}(log_{b} 2)^{2} · m

for every i, and the argument can be repeated. Inductively, the exponents of the p_{i} in f^{t−1}(n) are at least (1/(2b))^{t−1}(log_{b} 2)^{t−1} · m. In particular,

f^{t−1}(n) ≥ 2^{(1/(2b))^{t−1}(log_{b} 2)^{t−1}·m} ≥ 2^{b} ≥ b^{2}.

Again, as the elements of the cycle and the fixed point of f have at most two digits, this implies that n has persistence at least t.

An alternative proof of Theorem 10 in the case b = 3 would be to find an infinite sequence (a_{n})_{n≥0} such that 2^{a_{n}} has a_{n−1} digits 1 in base 3 for every n ≥ 1. In this case, the integer 2^{a_{n}} would have persistence equal to n plus the persistence of 2^{a_{0}}. The existence of such a sequence is a straightforward consequence of Conjecture 1, but we conjecture it independently, as it may be much simpler to prove than the full statement of the original conjecture. A computational search shows that the initial terms of such a sequence could be

2, 4, 8, 24, 96, 350, 1580, 7520, 35600, 168980,

since 2^{168980} has 35600 digits 1, 2^{35600} has 7520 digits 1, and so on, and 2^{2} is a fixed point of S_{1,3}. In fact, there is some computational evidence in favor of the following stronger conjecture, which assures that one can find such a sequence starting from any sufficiently large even number:

Conjecture 11. There is N such that, for every n > N, there is m such that 2^{2m} has exactly 2n digits 1 in base 3.

Remark 12. Conjecture 11 is equivalent to the assertion that the subsequence of terms of even order of \underline{A036461} contains all sufficiently large even numbers.

Just as we did for the Erdős-Sloane persistence, we can estimate the maximal growth of ν_{1,b}(n) as a function of n from above (unconditionally) and from below (using Conjecture 4 as in Theorem 10). More precisely, we have the result stated below. In its proof, we shall use the following evident fact. If F is any finite non-empty set and ϕ : F → F is a self-map, then every x ∈ F is eventually mapped to a (fixed or) periodic point under ϕ, and the number of iterates that it takes for x to reach the periodic cycle is obviously bounded by the cardinality of F.

Theorem 13. For each base b ≥ 3, we have

lim sup_{n→∞} \frac{ν_{1,b}(n)}{log log n} ≤ \frac{2}{log (α^{−1})},  (5)

where α = log_{b} (b − 1). Moreover, if Conjecture 4 holds, then we have

lim sup_{n→∞} \frac{ν_{1,b}(n)}{log log n} ≥ \frac{1}{log (β^{−1})},  (6)

where β = \frac{log_{b} 2}{2b}.

Proof. Let us write f = S_{1,b} in this proof. We treat the upper and lower estimates separately.

(i) Upper bound. Given n > b, write n = (d_{1}d_{2} ⋯ d_{k})_{b} (where k ≤ 1 + log_{b} n; note that this notation differs from the one in section 2) and let ℓ ≤ k be the number of digits d_{i} that are equal to b − 1. Then f(n) = b^{ℓ} · P, where P = ∏_{d_{i}≤b−2}(1 + d_{i}). This in turn implies that f^{2}(n) = f(P). But the number of digits of P in base b is at most

1 + log_{b} P = 1 + ∑_{d_{i}≤b−2} log_{b} (1 + d_{i}) ≤ 1 + (k − ℓ)α ≤ 1 + kα,

where α = log_{b} (b − 1) < 1. Hence we have

f^{2}(n) = f(P) ≤ b^{1+kα} ≤ b^{1+(1+log_{b} n)α} = b^{1+α}n^{α}.

By induction, it follows that

f^{2j} ≤ (b^{1+α})^{1+α+α^{2}+···+α^{j−1}} n^{α^{j}} < b^{(1+α)/(1−α)}n^{α^{j}}, ∀j ≥ 1.

Let j_{0} be the smallest natural number such that n^{α^{j_{0}}} < 2, i.e.,

j_{0} = ⌈\frac{log log n − log log 2}{log (α^{−1})}⌉ .  (7)

Then we have f^{2j_{0}}(n) ∈ A = {1, 2, …, M}, where M = ⌈2b^{(1+α)/(1−α)}⌉. We claim that A is f^{2}-invariant, i.e., f^{2}(A) ⊆ A. Indeed, if a ∈ A then

f^{2}(a) ≤ b^{1+α}a^{α} ≤ b^{1+α}M^{α} ≤ b^{1+α} (2b^{(1+α)/(1−α)})^{α} = 2^{α}b^{(1+α)/(1−α)} < M,

and so f^{2}(a) ∈ A as claimed. But now, by the simple remark preceding the statement of this theorem, every a ∈ A is eventually periodic, and if m ∈ ℕ is the smallest number such that f^{2m}(a) ∈ Per(f^{2}) ⊆ Per(f), then m ≤ |A| = M. Summarizing, we have proved that, starting from n > b: (i) after 2j_{0} iterates under f, we reach some a_{0} ∈ A; (ii) after j_{1} ≤ 2M further iterates, we reach a periodic cycle, i.e., f^{j_{1}}(a_{0}) ∈ Per(f). Therefore we have ν_{1,b}(n) ≤ 2j_{0} + 2M, and from (7) we deduce that

ν_{1,b}(n) ≤ 2 (\frac{log log n − log log 2}{log (α^{−1})}) + 2(M + 1).

This shows that

lim sup_{n→∞} \frac{ν_{1,b}(n)}{log log n} ≤ \frac{2}{log (α^{−1})}.

and this is precisely (5).

(ii) Lower bound. Here we proceed just as in the proof of the lower bound in Theorem 10. Once again, for each natural number t we consider n_{t} = (∏_{p_{i} prime, p_{i}<b, p_{i}∤b} p_{i})^{m_{t}}, where m_{t} is the smallest positive integer such that

m_{t} (\frac{1}{2b})^{t−1} (log_{b} 2)^{t−1} ≥ C = max\{b, N\},

and where N is given by Conjecture 4 taking ε = \frac{1}{2b}. Then, as we saw in the proof of Theorem 10, the 1-shifted persistence of n_{t} is at least t, and the same computations performed in the proof of Theorem 6 yield

ν_{1,b}(n_{t}) ≥ t > log_{b} log_{b} n_{t} ; log_{b} (β^{−1}) + K = log log_{b} n_{t} ; log (β^{−1}) + K,  (8)

for some constant K. Dividing the resulting inequality in (8) by log log n_{t} and letting t → ∞, we arrive at (6) as desired.

5.3 2-shifted problem

In this section, we show that Conjectures 1 and 4 imply that every integer reaches a cycle or a fixed point under iteration by S_{2,b}. Before stating the result precisely, we start with a lemma.

Lemma 14. Let b ≥ 5 be a positive integer. Then

1. (b + 1)!^{\frac{log_{b} (b+1)}{b}} < b;

2. (b + 1)^{log_{b}(b−1)} < b;

3. (b + 1)^{2 log_{b}(b−2)+log_{b}(b+1)} < b^{3}.

Proof. Taking logarithms and rearranging terms, the first inequality is equivalent to

b(log b)^{2} − log(b + 1)! · log(b + 1) > 0.  (9)

We will use the following well-known upper bound for n!, valid for all positive integers n:

n! ≤ e (\frac{n}{e})^{n} \sqrt{n}.

Applying this bound to the left-hand side of inequality (9), we get

b(log b)^{2} − log(b + 1)! · log(b + 1)

≥ b(log b)^{2} − (b + 1)(log(b + 1))^{2} + b log(b + 1) − \frac{(log(b + 1))^{2}}{2} .

By the mean value theorem, b(log b)^{2} − (b + 1)(log(b + 1))^{2} = −g′(c) for some c ∈ (b, b + 1), where g(x) = x(log x)^{2}. As g′(x) = (log x)^{2} + 2 log x is increasing, we get that b(log b)^{2} − (b + 1)(log(b + 1))^{2} ≥ −(log(b + 1))^{2} − 2 log(b + 1). This implies that

b(log b)^{2} − log(b + 1)! · log(b + 1) ≥ b log(b + 1) − \frac{3(log(b + 1))^{2}}{2} − 2 log(b + 1).

Let h(b) = b log(b + 1) − \frac{3(log(b+1))^{2}}{2} − 2(log(b + 1)). It is readily checked that h(5) > 0. Moreover, h′(b) = \frac{(b−2)(log(b+1)+1)}{b+1} > 0 for every b > 2. This implies that h(b) > 0 for all b ≥ 5 and concludes the proof of the first item.

The inequality of the second item is equivalent, taking logarithms and rearranging terms, to

\frac{log(b − 1)}{log b} < \frac{log b}{log(b + 1)}.  (10)

Inequality (10) is a straightforward consequence of the fact that f(x) = \frac{log x}{log(x+1)} is increasing

for x > 1, which follows immediately from f′(x) = \frac{(x+1) log(x+1)−x log x}{x(x+1)(log(x+1))^{2}}.

Finally, the third inequality is equivalent to

log(b + 1)(2 log(b − 2) + log(b + 1)) < 3(log b)^{2}.  (11)

This can be proved using that log is a concave function and applying Jensen’s inequality to 2 log(b − 2) + log(b + 1):

2 log(b − 2) + log(b + 1) < 3 log(b − 1).

The left-hand side of (11) is, then, smaller than 3 log(b−1) log(b+1). Inequality (10) implies that this is less than 3(log b)^{2} and concludes the proof.

Theorem 15. Conjecture 1 (resp., Conjecture 4) implies that for every n ≥ 1, the iterates of S_{2,3}(n) (resp., S_{2,b}(n), for b ≥ 4) reach a cycle or a fixed point.

Proof. We will prove the result for b = 3, b = 4 and b ≥ 5 separately. In any case, to show that the sequence of iterates starting at any positive integer stabilizes, we will prove the following stronger statement: there exist integers N_{0} and k and a constant 0 < c_{b} < 1 (which depends only on b) such that, for every n ≥ N_{0}, S_{2,b}^{j}(n) ≤ n^{c_{b}} (or, equivalently, S_{2,b}^{j}(n) ≤ C · n^{c′_{b}} for some constant C independent of n and 0 < c′_{b} < 1) for some 1 ≤ j ≤ k. In the cases b = 3, b = 4 and b ≥ 5, we will prove this statement with k = 4, k = 3 and k = 2, respectively.

(i) Base 3

First, put f = S_{2,3} to simplify the notation. We will use the following instance of Conjecture 1, which corresponds to q = 3, F = {2} and a = 1: for every ε > 0, there exists N such that 2^{t} is ε-equidistributed in base 3 whenever t ≥ N.

Let a_{0}, b_{0}, c_{0} denote, respectively, #0(n), #1(n), #2(n); and, for k ≥ 1, define

a_{k} = #0(2^{b_{k−2}+a_{k−1}+2c_{k−1}})
b_{k} = #1(2^{b_{k−2}+a_{k−1}+2c_{k−1}})
c_{k} = #2(2^{b_{k−2}+a_{k−1}+2c_{k−1}}),

where we put b_{−1} = 0. With this notation, we have

f^{k}(n) = 2^{b_{k−2}+a_{k−1}+2c_{k−1}} · 3^{b_{k−1}}

for every k ≥ 1.

Let us write α = log_{3} 2 ≈ 0.631. Moreover, fix ε = 0.001 and write δ = 1/3 − ε. Let N be such that 2^{t} is ε-equidistributed in base 3 for every t ≥ N.

For any integer n, we have f(n) = 2^{a_{0}+2c_{0}} · 3^{b_{0}} and f^{2}(n) = 2^{b_{0}}f(2^{a_{0}+2c_{0}}).

Let n ≥ 3^{3M} be an integer, where M ≥ N/(δα)^{2}. We know that a_{0} + b_{0} + c_{0} ≥ log_{3} n ≥ 3M. This implies that either b_{0} ≥ 2M or a_{0} + c_{0} ≥ M.

Suppose first that a_{0} + c_{0} < M. Then b_{0} ≥ 2M, and using the trivial bound f(m) ≤ 4^{log_{3} m+1}, which holds for every m since each of the at most log_{3} m + 1 digits of m is mapped to a factor 2, 3 or 4 in f(m), we get, using that 3^{a_{0}+b_{0}+c_{0}−1} ≤ n ≤ 3^{a_{0}+b_{0}+c_{0}}, that

\frac{f^{2}(n)}{n} ≤ \frac{2^{b_{0}}f(2^{a_{0}+2c_{0}})}{3^{a_{0}+b_{0}+c_{0}−1}}

≤ \frac{2^{b_{0}} · 4^{log_{3}(2^{a_{0}+2c_{0}})+1}}{3^{a_{0}+b_{0}+c_{0}−1}}

= c · 3^{(α−1)b_{0}+(2α^{2}−1)a_{0}+(4α^{2}−1)c_{0}}

≤ c · (3^{b_{0}})^{α−1+(4α^{2}−1)/2}

≤ c · (\frac{n}{3^{M}} )^{α−1+(4α^{2}−1)/2} ,

for some positive constant c, since 1 − 2α^{2}, 1 − α > 0 and 1 − 4α^{2} < 0. As α − 1 + (4α^{2} − 1)/2 < 0, this concludes the proof in this case.

From now on, we may assume that a_{0} + c_{0} ≥ M. As M ≥ N/(δα)^{2} ≥ N, we know that 2^{a_{0}+2c_{0}} is ε-equidistributed, i.e., a_{1}, b_{1}, c_{1} belong to ((1/3 − ε)α(a_{0} + 2c_{0}), (1/3 + ε)α(a_{0} + 2c_{0})). In particular, writing β for 1/3 + ε, we have that a_{1}, b_{1}, c_{1} are bounded from above by

βα(a_{0} + 2c_{0}).

As f^{2}(n) = 2^{b_{0}+a_{1}+2c_{1}} · 3^{b_{1}}, we have f^{3}(n) = 2^{b_{1}}f(2^{b_{0}+a_{1}+2c_{1}}). As a_{1} ≥ δα(a_{0} + 2c_{0}) ≥ δαM ≥ N, the number 2^{b_{0}+a_{1}+2c_{1}} is ε-equidistributed, i.e., the quantities a_{2}, b_{2}, c_{2} belong to the interval ((1/3 − ε)α(b_{0} + a_{1} + 2c_{1}), (1/3 + ε)α(b_{0} + a_{1} + 2c_{1})), and hence are bounded from above by

βα(b_{0} + a_{1} + 2c_{1}) ≤ βα(b_{0} + 3βα(a_{0} + 2c_{0}))
= 3β^{2}α^{2}(a_{0} + 2c_{0}) + βαb_{0}.

On the other hand, the numbers a_{2}, b_{2}, c_{2} are greater than δα(b_{0} +a_{1} +2c_{1}) > δ^{2}α^{2}(a_{0} + 2c_{0}) ≥ N, so 2^{a_{2}+2c_{2}+b_{1}} is ε-equidistributed. This implies that

a_{3}, b_{3}, c_{3} ≤ βα(b_{1} + a_{2} + 2c_{2})
≤ βα(βα(a_{0} + 2c_{0}) + 9β^{2}α^{2}(a_{0} + 2c_{0}) + 3βαb_{0})
= β^{2}α^{2}(1 + 9βα)(a_{0} + 2c_{0}) + 3β^{2}α^{2}b_{0}.

Together, these estimates imply that

α(b_{2} + a_{3} + 2c_{3}) + b_{3} ≤ α(3β^{2}α^{2}(a_{0} + 2c_{0}) + βαb_{0})+
(3α + 1)(β^{2}α^{2}(1 + 9βα)(a_{0} + 2c_{0}) + 3β^{2}α^{2}b_{0})

= β^{2}α^{2}(3α + (3α + 1)(1 + 9βα))(a_{0} + 2c_{0}) + βα^{2}(1 + 3(3α + 1)β)b_{0}.

Finally, this bound implies that

\frac{f^{4}(n)}{n} = \frac{2^{b_{2}+a_{3}+2c_{3}} · 3^{b_{3}}}{3^{a_{0}+b_{0}+c_{0}−1}}

≤ 3 · \frac{3^{α(b_{2}+a_{3}+2c_{3})+b_{3}}}{3^{a_{0}+b_{0}+c_{0}}}

≤ 3 · \frac{3^{β^{2}α^{2}(3α+(3α+1)(1+9βα))(a_{0}+2c_{0})+βα^{2}(1+3(3α+1)β)b_{0}}}{3^{a_{0}+b_{0}+c_{0}}}

= 3 · 3^{(β^{2}α^{2}(3α+(3α+1)(1+9βα))−1)a_{0}+(βα^{2}(1+3(3α+1)β)−1)b_{0}+(2β^{2}α^{2}(3α+(3α+1)(1+9βα))−1)c_{0}}.

This gives the result, since β^{2}α^{2}(3α+(3α+1)(1+9βα)) < \frac{1}{2} and βα^{2}(1+3(3α+1)β) < 1.

(ii) Base 4

We now consider base 4. As usual, put f = S_{2,4} to ease the notation. We will prove the following: for every sufficiently large integer n, one of the numbers f(n), f^{2}(n), f^{3}(n) is at most cn^{c_{b}} for some c > 0 and 0 < c_{b} < 1. We will apply Conjecture 4 twice, with q = 4, F = {3, 5}, a = 1 and q = 4, F = {3, 5}, a = 2 to get the following statement: for every ε > 0, there is N such that 3^{x} ·5^{y} and 2·3^{x} ·5^{y} are ε-equidistributed whenever x ≥ N or y ≥ N.

For any integer n, if we put a_{0} = #0(n), b_{0} = #1(n), c_{0} = #2(n) and d_{0} = #3(n), we have f(n) = 4^{⌊a_{0}/2⌋+c_{0}} · 2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}} and f^{2}(n) = 2^{⌊a_{0}/2⌋+c_{0}} · f(2^{a_{0}′} · 3^{b_{0}} · 5^{d_{0}}), where x′ denotes the remainder of the integer x modulo 2.

Let ε = 0.001 and let n ≥ 4^{4M} be an integer, where M ≥ N/(2(1/4 − ε) log_{4} 3). We know that a_{0} +b_{0} +c_{0} +d_{0} ≥ log_{4} n ≥ 4M. This implies that either b_{0} ≥ M, or d_{0} ≥ M, or a_{0} + c_{0} ≥ 2M.

Suppose first that b_{0} < M and d_{0} < M. Then a_{0} + c_{0} ≥ 2M, and using the trivial bound f(m) ≤ 5^{log_{4} m+1}, which holds for every m since each of the at most log_{4} m + 1 digits of m is mapped to a factor 2, 3, 4, or 5 in f(m), we get that

\frac{f^{2}(n)}{n} ≤ \frac{2^{⌊a_{0}/2⌋+c_{0}} · f(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}})}{4^{a_{0}+b_{0}+c_{0}+d_{0}−1}}

≤ 4 · \frac{2^{a_{0}/2+c_{0}} · 5^{log_{4}(2·3^{b_{0}}·5^{d_{0}})+1}}{4^{a_{0}+b_{0}+c_{0}+d_{0}}}

= c · 4^{−3a_{0}/4−c_{0}/2+(log_{4} 5 log_{4} 3−1)b_{0}+((log_{4} 5)^{2}−1)d_{0}}

≤ c(M) · (4^{a_{0}+c_{0}})^{−1/2}

≤ c(M) · (\frac{n}{4^{2M}} )^{−1/2} ,

where c(M) is some constant dependent on M only. This proves the claim in the first case.

From now on, we assume that b_{0} ≥ M or d_{0} ≥ M. As M ≥ N/(2(1/4 − ε) log_{4} 3) ≥ N, we know that 2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}} is ε-equidistributed, i.e., #d(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}) belongs to the interval ((1/4 − ε) log_{4}(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}), (1/4 + ε) log_{4}(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}})), for d = 0, 1, 2, 3. Put a_{1} = #0(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}), b_{1} = #1(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}), c_{1} = #2(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}), and d_{1} = #3(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}). In particular, a_{1}, b_{1}, c_{1} and d_{1} are bounded from above by (1/4 + ε) log_{4}(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}) ≤ (1/4 + 2ε) log_{4}(3^{b_{0}} · 5^{d_{0}}) ≤ βα(b_{0} + d_{0}) for M large enough (namely, for (1/4 + ε) log_{4}(2 · 3^{M} · 5^{M}) ≤ (1/4 + 2ε) log_{4}(3^{M} · 5^{M}) to hold), writing β for 1/4 + 2ε and α for log_{4} 5.

We have

f^{2}(n) = 2^{⌊a_{0}/2⌋+c_{0}} · f(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}) = 2^{⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1}} · 3^{b_{1}} · 5^{d_{1}},

and then

f^{3}(n) = f(2^{⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1}} ·3^{b_{1}} ·5^{d_{1}}) = 2^{⌊(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})/2⌋}f(2^{(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})′} ·3^{b_{1}} ·5^{d_{1}}).

Putting a_{2} = #0(2^{(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})′} · 3^{b_{1}} · 5^{d_{1}}), b_{2} = #1(2^{(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})′} · 3^{b_{1}} · 5^{d_{1}}), c_{2} = #2(2^{(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})′} · 3^{b_{1}} · 5^{d_{1}}), and d_{2} = #3(2^{(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})′} · 3^{b_{1}} · 5^{d_{1}}), we have

f^{3}(n) ≤ 2^{a_{0}/4+c_{0}/2+a_{1}/2+c_{1}+a_{2}+2c_{2}} · 3^{b_{2}} · 5^{d_{2}}.  (12)

As b_{1} ≥ (1/4 − ε) log_{4}(2^{a′_{0}} · 3^{b_{0}} · 5^{d_{0}}) ≥ (1/4 − ε) log_{4}(3^{b_{0}} · 5^{d_{0}}) ≥ 2M(1/4 − ε) log_{4} 3 ≥ N, the number 2^{(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})′} · 3^{b_{1}} · 5^{d_{1}} is ε-equidistributed, i.e., a_{2}, b_{2}, c_{2} and d_{2} belong to ((1/4 − ε) log_{4}(2^{(⌊a_{0}/2⌋+c_{+}a_{1}+2c_{1})′} · 3^{b_{1}} · 5^{d_{1}}), (1/4 + ε) log_{4}(2^{(⌊a_{0}/2⌋+c_{+}a_{1}+2c_{1})′} · 3^{b_{1}} · 5^{d_{1}})).

This implies that a_{2}, b_{2}, c_{2} and d_{2} can be bounded from above by the following expression: (1/4+ε) log_{4}(2^{(⌊a_{0}/2⌋+c_{0}+a_{1}+2c_{1})′} ·3^{b_{1}} ·5^{d_{1}}) ≤ (1/4+2ε)α(b_{1} +d_{1}) ≤ 2β^{2}α^{2}(b_{0} +d_{0}). Plugging these estimates for a_{1}, …, d_{1}, a_{2}, …, d_{2} in (12), we get that

\frac{f^{3}(n)}{n} ≤ \frac{4^{a_{0}/8+c_{0}/4+(3/4αβ+3α^{2}β^{2}+4α^{3}β^{2})(b_{0}+d_{0})}}{4^{a_{0}+b_{0}+c_{0}+d_{0}−1}}
= 4 · 4^{−7a_{0}/8−3c_{0}/4+(3/4αβ+3α^{2}β^{2}+4α^{3}β^{2}−1)(b_{0}+d_{0})}
≤ 4 · n^{θ},

for some 0 < θ < 1 since 3αβ/4 + 3α^{2}β^{2} + 4α^{3}β^{2} < 1.

(iii) Larger bases

Finally, we prove the result for b ≥ 5. Let f denote S_{2,b}. We will prove that either f(n) ≤ c · n^{c_{b}} or f^{2}(n) ≤ c · n^{c_{b}} if n is large enough, for some c > 0 and 0 < c_{b} < 1.

We start applying Conjecture 4 a few times: for every prime p dividing b and for every proper divisor d of b (i.e., a divisor which is less than b, including 1), we apply it for q = b, a = d, F_{p} = {r prime : r ≤ b+1, r ≠ p}. Taking the maximum of the N obtained by each application of the conjecture, we get the following statement: for every ε > 0, there is N such that, for every proper divisor d of b and every prime divisor p of b, the number d ∏_{q_{i}∈F_{p}} q_{i}^{a_{i}} is ε-equidistributed if any of the a_{i} is at least N.

Let ε > 0 be such that (b + 1)!^{(log_{b}(b+1))(1/b+ε)} < b. Such an ε exists by the first item of Lemma 14 and by the fact that lim_{ε→0^{+}}(b+1)!^{ε log_{b}(b+1)} = 1. Moreover, let n ≥ b^{4M}, with M ≥ N, where N is as in the paragraph above. For i ∈ {0, …, b−1}, let n_{i} denote the number of digits i in the base-b expansion of n. We know that ∑_{i=0}^{b−1} n_{i} ≥ log_{b} n ≥ 4M.

By the definition of f, we have f(n) = ∏_{i=0}^{b−1}(i + 2)^{n_{i}}. We may rewrite this number as b^{t} · d · ∏_{q_{i}∈F_{p}} q_{i}^{α_{i}}, where t ≥ 0 is an integer, d is a proper divisor of b and p is a prime divisor of b. In particular, we have f(f(n)) = 2^{t}f(d · ∏_{q_{i}∈F_{p}} q_{i}^{α_{i}}). Note that we have t ≥ n_{b−2}, since all the n_{b−2} powers of b are factored out to the term b^{t}.

Suppose first that n_{b−1} ≥ M or n_{b−3} ≥ M. Then the number d · ∏_{q_{i}∈F_{p}} q_{i}^{α_{i}} is εequidistributed, since no prime factor from b + 1 or b − 1 is factored out in b^{t} or d in the product b^{t} · d · ∏_{q_{i}∈F_{p}} q_{i}^{α_{i}}, as b is coprime with b − 1 and b + 1, and hence α_{i} ≥ max{n_{b−3}, n_{b−1}} ≥ M for some i. The number of occurrences of every digit from 0 to b − 1 in f(n) belongs, then, to the interval ((1/b − ε) log_{b}(d · ∏_{q_{i}∈F_{p}} q_{i}^{α_{i}}), (1/b + ε) log_{b}(d · ∏_{q_{i}∈F_{p}} q_{i}^{α_{i}})). This implies that

f^{2}(n) ≤ 2^{t} · (2 ⋯ (b + 1))^{(1/b+ε) log_{b}(d·∏_{q_{i}∈Fp} q_{i}^{α_{i}})}

= 2^{t} · (b + 1)!^{(1/b+ε) log_{b}( \frac{1}{b^{t}} ∏_{i=0}^{b−1}(i+2)^{n_{i}})}

= (\frac{2}{(b + 1)!^{(1/b+ε)}} )^{t} · (b + 1)!^{(1/b+ε) ∑_{i=0}^{b−1} n_{i} log_{b}(i+2)}

≤ 1 · (b + 1)!^{(1/b+ε) log_{b}(b+1) ∑_{i=0}^{b−1} n_{i}}

≤ b^{c_{b} ∑_{i=0}^{b−1} n_{i}} = c · n^{c_{b}}

for some c > 0, 0 < c_{b} < 1, where the last inequality comes from the choice of ε.

Suppose now, on the other hand, that n_{b−1} < M and n_{b−3} < M. First, if n_{b−2} < M, as M ≤ log_{b}(n)/4 and ∑_{i=0}^{b−1} n_{i} ≤ log_{b} n, we have ∑_{i=0}^{b−4} n_{i} ≥ log_{b}(n)/4. Then

\frac{f(n)}{n} = \frac{∏_{i=0}^{b−1}(i + 2)^{n_{i}}}{b^{∑_{i=0}^{n−1} −1}}

≤ b · (\frac{b − 1}{b})^{∑_{i=0}^{b−3} n_{i}} (\frac{b + 1}{b})^{n_{b−1}}

≤ b · (\frac{b^{2} − 1}{b^{2}})^{log_{b}(n)/4}

= b · n^{log_{b}(^{\frac{b^{2}−1}{b^{2}}} )/4}, as desired, since log_{b} (\frac{b^{2}−1}{b^{2}}) < 0.

Finally, if n_{b−1}, n_{b−3} < M ≤ log_{b}(n)/4 and n_{b−2} ≤ M, then, applying the trivial bound f(m) ≤ (b + 1)^{1+log_{b} m} and noting that t ≥ n_{b−2} and ∑_{i=0}^{n−4} n_{i} + n_{b−2} ≥ log_{b}(n)/2, we get

\frac{f^{2}(n)}{n} ≤ \frac{2^{t} · f(d · ∏_{q_{i}∈F_{p}} q_{i}^{α_{i}})}{b^{∑_{i=0}^{b−1} n_{i}−1}}

≤ \frac{2^{t} · (b + 1)^{1+log_{b}(d·∏_{q_{i}∈Fp} q_{i}^{α_{i}})}}{b^{∑_{i=0}^{b−1} n_{i}−1}}

= \frac{2^{t} · (b + 1)^{1+log_{b}((∏_{i=0}^{b−1}(i+2)^{n_{i}})/b^{t})}}{b^{∑_{i=0}^{b−1} n_{i}−1}}

≤ b(b + 1) · (\frac{2}{b + 1})^{t} · (\frac{(b + 1)^{log_{b}(b−2)}}{b} )^{∑_{i=0}^{b−4} n_{i}} · (\frac{b + 1}{b})^{n_{b−2}}

· (\frac{(b + 1)^{log_{b}(b−1)}}{b} )^{n_{b−3}} · (\frac{(b + 1)^{log_{b}(b+1)}}{b} )^{n_{b−1}}

≤ b(b + 1) · (\frac{2}{b})^{n_{b−2}} · (\frac{(b + 1)^{log_{b}(b−2)}}{b} )^{∑_{i=0}^{b−4} n_{i}} · (\frac{(b + 1)^{log_{b}(b−1)}}{b} )^{n_{b−3}}

· (\frac{(b + 1)^{log_{b}(b+1)}}{b} )^{n_{b−1}} .

By the second item of Lemma 14, \frac{(b+1)^{log_{b}(b−1)}}{b} < 1. This inequality, together with the simple fact that (b + 1)^{log_{b}(b−2)} ≥ 2 for b ≥ 4, implies

\frac{f^{2}(n)}{n} ≤ b(b + 1) · (\frac{(b + 1)^{log_{b}(b−2)}}{b} )^{n_{b−2}+∑_{i=0}^{b−4} n_{i}} · (\frac{(b + 1)^{log_{b}(b+1)}}{b} )^{n_{b−1}}

≤ b(b + 1) (\frac{(b + 1)^{2 log_{b}(b−2)+log_{b}(b+1)}}{b^{3}} )^{log_{b}(n)/4} ,

where we used that n_{b−2}+∑_{i=0}^{b−4} ≥ log_{b}(n)/2 and n_{b−1} ≤ log_{b}(n)/4 in the last inequality. This completes the proof, since, by the third item of Lemma 14, the expression raised to log_{b} n in the last line above is smaller than 1, whence \frac{f^{2}(n)}{n} is bounded by b(b+1)·n^{γ} for some γ < 0.

Remark 16. The proof of Theorem 15 gives that S_{2,b}(n) ≤ n^{γ} for some γ < 1 if n is large enough. As in Theorem 13, this implies that the persistence of every number n under S_{2,b} is at most c log log n for some constant c. It is not hard to see that, as before, there is some sequence of integers for which this is sharp up to a constant factor (i.e., there exists an increasing sequence (n_{k})_{k≥1} of integers such that the persistence of n_{k} is at least c′ log log n_{k} for some c′ > 0 and every k).

5.4 The (4, 5) problem diverges

Using a proof similar to the proof of Theorem 15, one can show that the sequence of iterates of both S_{3,4} and S_{3,5} starting from every integer stabilizes (indeed, one can again prove that, in case f = S_{3,4} or f = S_{3,5}, for every sufficiently large n, f^{j}(n) ≤ n for some j ∈ {1, 2, 3, 4}). On the other hand, our next result shows that, assuming Conjecture 4, S_{4,5} is the smallest instance where the opposite behavior occurs, namely the sequence of iterates starting from every sufficiently large integer diverges.

Theorem 17. Conjecture 4 implies the following: there is an integer n_{0} such that, for every n ≥ n_{0}, the sequence of iterates (S_{4,5}^{k}(n))_{k≥0} diverges to infinity.

Proof. Put f = S_{4,5}. We will prove the following statement which obviously implies the theorem: there is n_{0} such that, for every n ≥ n_{0}, f^{5}(n) > n.

We apply Conjecture 4 for q = 5, a = 1 and F = {2, 3, 7} to get the following statement: for every ε > 0, there is N such that 2^{x} · 3^{y} · 7^{z} is ε-equidistributed whenever one of x, y, z is at least N. In particular, the number 4^{x} · 6^{y} · 7^{z} · 8^{w} is equidistributed whenever one of x, y, z and w is at least N.

Take ε = 0.001, put δ = 1/5 − ε and let n ≥ 5^{4M+M^{2}}, with Mδ^{3}(log_{5} 4)^{3} ≥ N, where N is the integer given by the application of Conjecture 4 as in the paragraph above with this value of ε; and M is large enough as for the last inequality in (13) to hold.

Let a_{0}, …, e_{0} denote, respectively, #0(n), …, #4(n); and, for k ≥ 1, let a_{k}, …, e_{k} denote, respectively, #0(4^{b_{k−2}+a_{k−1}} · 6^{c_{k−1}} · 7^{d_{k−1}} · 8^{e_{k−1}}), …, #4(4^{b_{k−2}+a_{k−1}} · 6^{c_{k−1}} · 7^{d_{k−1}} · 8^{e_{k−1}}), where we put b_{−1} = 0. With this notation, we have

f^{k}(n) = 4^{b_{k−2}+a_{k−1}} · 5^{b_{k−1}} · 6^{c_{k−1}} · 7^{d_{k−1}} · 8^{e_{k−1}}

for every k ≥ 1.

Assume first that one of a_{0}, c_{0}, d_{0}, e_{0} is at least M. As M ≥ N/δ^{3}(log_{5} 4)^{3} > N, this implies that 4^{a_{0}} · 6^{c_{0}} · 7^{d_{0}} · 8^{e_{0}} is ε-equidistributed. In particular, we have

a_{1}, …, e_{1} ≥ δ log_{5}(4^{a_{0}} · 6^{c_{0}} · 7^{d_{0}} · 8^{e_{0}})
= δ(a_{0} log_{5} 4 + c_{0} log_{5} 6 + d_{0} log_{5} 7 + e_{0} log_{5} 8).

In turn, as a_{1}, …, e_{1} ≥ δ(a_{0} +c_{0} +d_{0} +e_{0}) log_{5} 4 > N, this implies that 4^{b_{0}+a_{1}} ·6^{c_{1}} ·7^{d_{1}} ·8^{e_{1}} is ε-equidistributed, so

a_{2}, …, e_{2} ≥ δ log_{5}(4^{b_{0}+a_{1}} · 6^{c_{1}} · 7^{d_{1}} · 8^{e_{1}})
= δ((b_{0} + a_{1}) log_{5} 4 + c_{1} log_{5} 6 + d_{1} log_{5} 7 + e_{1} log_{5} 8)
= δ log_{5} 4 · b_{0} + δ^{2} log_{5} 1344(a_{0} log_{5} 4 + c_{0} log_{5} 6 + d_{0} log_{5} 7 + e_{0} log_{5} 8).

As the choice of M guarantees that the a_{2}, …, e_{2} and a_{3}, …, b_{3} are greater than N, the same reasoning can be applied two more times to get that

a_{3}, …, e_{3} ≥ δ log_{5}(4^{b_{1}+a_{2}} · 6^{c_{2}} · 7^{d_{2}} · 8^{e_{2}})
= δ((b_{1} + a_{2}) log_{5} 4 + c_{2} log_{5} 6 + d_{2} log_{5} 7 + e_{2} log_{5} 8)
≥ δ^{2} log_{5} 1344 log_{5} 4 · b_{0}
+ δ^{2}(log_{5} 4 + δ(log_{5} 1344)^{2})(a_{0} log_{5} 4 + c_{0} log_{5} 6 + d_{0} log_{5} 7 + e_{0} log_{5} 8)

and

a_{4}, …, e_{4} ≥ δ log_{5}(4^{b_{2}+a_{3}} · 6^{c_{3}} · 7^{d_{3}} · 8^{e_{3}})
= δ((b_{2} + a_{3}) log_{5} 4 + c_{3} log_{5} 6 + d_{3} log_{5} 7 + e_{3} log_{5} 8)
≥ δ^{2}((log_{5} 4)^{2} + δ log_{5} 4(log_{5} 1344)^{2})b_{0}
+ δ^{3} log_{5} 1344(2 log_{5} 4 + δ(log_{5} 1344)^{2})·
· (a_{0} log_{5} 4 + c_{0} log_{5} 6 + d_{0} log_{5} 7 + e_{0} log_{5} 8).

Finally, this implies that

\frac{f^{5}(n)}{n} > \frac{4^{b_{3}+a_{4}} · 5^{b_{4}} · 6^{c_{4}} · 7^{d_{4}} · 8^{e_{4}}}{5^{a_{0}+b_{0}+c_{0}+d_{0}+e_{0}}}

≥ (\frac{4^{δ^{2} log_{5} 4(log_{5} 4+δ(log_{5} 1344)^{2})} · 6720^{δ^{3} log_{5} 4 log_{5} 1344(2 log_{5} 4+δ(log_{5} 1344)^{2})}}{5} )^{a_{0}+c_{0}+d_{0}+e_{0}} ·

· (\frac{4^{δ^{2} log_{5} 1344 log_{5} 4} · 6720^{δ^{2} log_{5} 4(log_{5} 4+δ(log_{5} 1344)^{2})}}{5} )^{b_{0}}

> 1,

as a straightforward computation shows that each of the expressions inside the parenthesis are greater than 1 (indeed, the first and the second expression are greater than 1.14 and 1.06, respectively).

Suppose now, on the other hand, that each of a_{0}, c_{0}, d_{0}, e_{0} is less than M. This implies that b_{0} > M^{2} > N, which in turn implies that 4^{b_{0}+a_{1}} ·6^{c_{1}} ·7^{d_{1}} ·8^{e_{1}} is ε-equidistributed. Hence, we have a_{2}, ⋯, e_{2} ≥ δ log_{5}(4^{b_{0}+a_{1}} · 6^{c_{1}} · 7^{d_{2}} · 8^{e_{1}}) ≥ (δ log_{5} 4)b_{0} > N. Again, this implies that 4^{b_{1}+a_{2}} · 6^{c_{2}} · 7^{d_{2}} · 8^{e_{2}} is ε-equidistributed and

a_{3}, …, e_{3} ≥ δ log_{5}(4^{b_{1}+a_{2}} · 6^{c_{2}} · 7^{d_{2}} · 8^{e_{2}}) ≥ δ^{2} log_{5} 4 log_{5} 1344 · b_{0} > N.

Finally, this implies that

a_{4}, …, e_{4} ≥ δ log_{5}(4^{b_{2}+a_{3}} · 6^{c_{3}} · 7^{d_{3}} · 8^{e_{3}}) ≥ δ^{2} log_{5} 4(log_{5} 4 + δ(log_{5} 1344)^{2})b_{0},

and then

\frac{f^{5}(n)}{n} > \frac{4^{b_{3}+a_{4}} · 5^{b_{4}} · 6^{c_{4}} · 7^{d_{4}} · 8^{e_{4}}}{5^{a_{0}+b_{0}+c_{0}+d_{0}+e_{0}}}

> (\frac{4^{δ^{2} log_{5} 4 log_{5} 1344} · 6720^{δ^{2} log_{5} 4(log_{5} 4+δ(log_{5} 1344)^{2})}}{5} )^{b_{0}} · (\frac{1}{5})^{4M}

≥ (\frac{4^{δ^{2} log_{5} 4 log_{5} 1344} · 6720^{δ^{2} log_{5} 4(log_{5} 4+δ(log_{5} 1344)^{2})}}{5} )^{M^{2}} · (\frac{1}{5})^{4M}

> 1,  (13)

for large M, as the expression being raised to M^{2} is greater than 1 (approximately 1.06).

5.5 Larger t and b

In this section, we consider the behavior of the t-shifted problem in base b when t is bounded by a function of b. As one would expect, the equidistribution conjectures imply that, if b is very large compared to t, then the sequence of iterates starting from any integer stabilizes in the t-shifted problem in base b. One the other hand, if t is very close to b, then almost no sequence stabilizes. Our next results give some estimates on the ranges of t and b (both for small and large b) where each of those behaviors appear. Again, we start with a technical lemma.

Lemma 18. Let t and b be positive integers such that b ≥ 5 and t ≤ b/4. Then

(i) b^{log_{b}(t)−1} · \frac{(b+t−1)^{log_{b}(b+t−1)}}{b} < 1;

(ii) (\frac{(b+t−1)!}{(t−1)!})^{\frac{1}{b} log_{b}(b+t−1)} < b.

Proof. (i) The inequality is equivalent, applying logarithms, to

log b · log t + (log(b + t − 1))^{2} < 2(log b)^{2}.  (14)

The left-hand side of (14) is increasing with t, so bounded from above by log b·log(b/4)+ (log(5b/4))^{2}. Expanding this expression, we get

2(log b)^{2} + log(25/64) log b + (log(5/4))^{2},

which is smaller than 2(log b)^{2} whenever b ≥ e^{− log(5/4)^{2}/ log(25/64)} ≈ 1.05.

(ii) The inequality is equivalent, taking logarithms twice, to

log log(b + t − 1) + log log (\frac{(b + t − 1)!}{(t − 1)!}) < log b + 2 log log b.  (15)

By the inequality of arithmetic and geometric means, we have that

\frac{(b + t − 1)!}{(t − 1)!} = t(t + 1) ⋯ (b + t − 1)

≤ (\frac{t + (t + 1) + ⋯ + (b + t − 1)}{b})^{b}

= (\frac{b + 2t − 1}{2})^{b}

< (\frac{3b}{4})^{b} ,

as t ≤ b/4.

We also have b + t − 1 < 5b/4. Plugging these two estimates on the left-hand side of (15) and using that log log x is a concave and increasing function on its domain, we get that

log log(b + t − 1) + log log (\frac{(b + t − 1)!}{(t − 1)!}) < log log(5b/4) + log log(3b/4)^{b}

= log b + log log(5b/4) + log log(3b/4)

< log b + 2 log log (\frac{5b/4 + 3b/4}{2})

= log b + 2 log log b.

Theorem 19. Conjecture 4 implies the following: for every prime number b ≥ 5 and t ≤ b/4, the sequence of iterates (S_{t,b}^{k}(n))_{k≥1} stabilizes for every positive integer n.

Proof. The proof follows the ideas of the proof of Theorem 15. Let t and b be integers such that 3 ≤ t ≤ b/4 (the cases t = 1 and t = 2 were covered by Theorems 7 and 15, respectively). Again, we will prove that, for every sufficiently large integer n, either f(n) ≤ n^{c_{b}} or f^{2}(n) ≤ n^{c_{b}}, where f = S_{t,b} and 0 < c_{b} < 1.

We apply Conjecture 4 with q = b, a = 1, F = {p prime : p ≤ b+t−1, p ≠ b} to get the following statement: for every ε > 0, there is N such that the number ∏_{p_{i} prime:p_{i}≤b+t−1, p_{i}≠b} p_{i}^{a_{i}} is ε-equidistributed if any of the a_{i} is at least N. Taking the maximum of the N obtained by each application of the conjecture, we get the following statement: for every ε > 0, there is N such that, for every proper divisor d of b and every prime divisor p of b, the number d ∏_{q_{i} prime,q_{i}≤b+t−1,q_{i}≠p} q_{i}^{a_{i}} is ε-equidistributed if any of the a_{i} is at least N.

Let ε > 0 be so small as to satisfy

\frac{1}{b} · (\frac{(b + t − 1)!}{(t − 1)!})^{( \frac{1}{b} +ε) log_{b}(b+t−1)} < 1,

which is possible by the second item of Lemma 18. Moreover, let n ≥ b^{2(b−1)M}, with M ≥ N, where N is as in the paragraph above. For i ∈ {0, …, b − 1}, let n_{i} denote the number of digits i in the base-b expansion of n. We know that ∑_{i=0}^{b−1} n_{i} ≥ log_{b} n ≥ 2(b − 1)M. This implies that either n_{i} ≥ M for some i ≠ b − t or n_{b−t} ≥ (b − 1)M.

By the definition of f, we have f(n) = ∏_{i=0}^{b−1}(i + t)^{n_{i}}, where n_{i} is the number of digits i of n in base b. Note that ∏_{i=0}^{b−1}(i + t)^{n_{i}} = b^{n_{b−t}} · ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}, and that b does not divide the second product. Then we have f^{2}(n) = t^{n_{b−t}} · f(∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}})

Suppose first that n_{i} ≥ M for some i ≠ b−t. This implies that the number ∏_{i=0,i≠b−t}^{b−1}(i+ t)^{n_{i}} is ε-equidistributed, i.e., the number of occurrences of every digit from 0 to b−1 belongs to the interval ((1/b − ε) log_{b}(∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}), (1/b + ε) log_{b}(∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}})). Hence, as n ≥ b^{∑_{i=0}^{b−1} n_{i}−1}, it follows that

\frac{f^{2}(n)}{n} ≤ \frac{1}{n} · t^{n_{b−t}} · (t ⋯ (t + b − 1))^{( \frac{1}{b} +ε) log_{b}(∏_{i=0,i≠b−t}^{b−1}(i+t)^{n_{i}})}

= \frac{1}{n} · b^{n_{b−t} log_{b} t} · (\frac{(b + t − 1)!}{(t − 1)!})^{( \frac{1}{b} +ε) ∑_{i=0,i≠b−t}^{b−1} n_{i}(log_{b}(i+t))}

≤ \frac{1}{n} · b^{n_{b−t} log_{b} t} ((\frac{(b + t − 1)!}{(t − 1)!})^{( \frac{1}{b} +ε) log_{b}(b+t−1)})^{∑_{i=0,i≠b−t}^{b−1} n_{i}}

≤ b · (b^{log_{b} t−1})^{n_{b−t}} (\frac{1}{b} · (\frac{(b + t − 1)!}{(t − 1)!})^{( \frac{1}{b} +ε) log_{b}(b+t−1)})^{∑_{i=0,i≠b−t}^{b−1} n_{i}} .  (16)

The choice of ε implies that the expression inside the second parenthesis in the last line of (16) is b^{γ} for some γ < 0, which completes the proof of this case, as log_{b}(t) − 1 < 0 and then (16) is bounded from above by b · b^{γ′ ∑_{i=0}^{b−1} n_{i}} ≤ b · n^{γ′} for some γ′ < 0.

Suppose now, on the other hand, that n_{i} < M for every i ≠ b − t. This implies, as ∑_{i=0}^{b−1} n_{i} ≥ 2(b − 1)M, that n_{b−t} ≥ (b − 1)M ≥ ∑_{i=0,i≠b−t}^{b−1} n_{i}, and hence n_{b−t} ≥ log_{b}(n)/2 ≥ ∑_{i=0,i≠b−t}^{b−1} n_{i}. Applying a trivial bound f(m) ≤ (b + t − 1)^{1+log_{b} m}, we get that

\frac{f^{2}(n)}{n} = \frac{1}{n} · t^{n_{b−t}}f ( ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}})

≤ \frac{1}{n} · b^{n_{b−t} log_{b} t} · (b + t − 1)^{1+∑_{i=0}^{b−1} log_{b}(i+t)n_{i}}

≤ 2b^{2} · b^{(log_{b} t−1)n_{b−t}} · (\frac{(b + t − 1)^{log_{b}(b+t−1)}}{b} )^{∑_{i=0,i≠b−t}^{b−1} n_{i}}

≤ 2b^{2} · (b^{log_{b}(t)−1} · \frac{(b + t − 1)^{log_{b}(b+t−1)}}{b} )^{log_{b}(n)/2}

= 2b^{2} · n^{γ}, where, by the first item of Lemma 18, b^{log_{b}(t)−1} · \frac{(b+t−1)^{log_{b}(b+t−1)}}{b} < 1, whence γ < 0. This concludes the proof.

The estimates in the proof of Theorem 19 can be applied asymptotically in b (instead of for every b ≥ 4) using Stirling’s formula (instead of a precise inequality for every n) to improve the constant 1/4 in to approximately 0.316 for large b. Namely, the following result, whose proof is very similar to the proof of Theorem 19 and will be omitted, holds:

Theorem 20. Conjecture 4 implies the following: let c_{0} be the solution of 2 log(1 + c) + c log(1 + 1/c) = 1 in the interval (0, 1) (c_{0} ≈ 0.315999). Then, for every c ≤ c_{0}, there is b_{0} with the following property: for every prime number b ≥ b_{0} and t ≤ cb, the sequence of iterates (S_{t,b}^{k}(n))_{k≥1} stabilizes for every positive integer n.

Remark 21. What we stated in Remark 16 holds for Theorems 19 and 20 as well, i.e., persistence is bounded by c log log n for every n and some c, and there is an increasing sequence of integers (n_{k})_{k≥1} with persistence at least c′ log log n_{k} for some c′ > 0 and every k.

On the other end of the spectrum, we have a divergence result, which we state now, after a technical lemma.

Lemma 22. Let c_{0} be the solution 2 log c + log(c + 1) + c log(1 + 1/c) = 1 in the interval (0, 1) (c_{0} ≈ 0.865722). Then, for every c > c_{0}, there is b_{0} with the following property: Let t and b be integers, with b ≥ b_{0} and t ≥ cb. If we put δ = 1/b − 1/b^{2}, then the following inequalities hold:

(i) (\frac{(t−1+b)!}{(t−1)!})^{δ log_{b} t} > b;

(ii) t^{δ log_{b} t} · (\frac{(t−1+b)!}{(t−1)!})^{(b−2)δ^{2}(log_{b} t)^{2}} > b.

Proof. We will prove that the logarithm to base b of the two expressions on the left-hand sides of i) and ii) are greater than 1 for large b. For that purpose, we use the following logarithmic form of the well-known Stirling approximation:

log n! = n log n − n + O(log n).

(i) We have

log_{b} (\frac{(t − 1 + b)!}{(t − 1)!})^{δ log_{b} t} =
= δ \frac{log t}{(log b)^{2}} · ((t − 1 + b) log(t − 1 + b) − (t − 1) log(t − 1)
− b + O(log b))
= δ \frac{log t}{(log b)^{2}} · (b log(t − 1 + b) + (t − 1) log(1 + b/(t − 1))
− b + O(log b))

≥ δ \frac{log cb}{(log b)^{2}} · (b log((c + 1)b) + cb log(1 + 1/c) − b + O(log b))

≥ δb (1 + \frac{log c + log(c + 1) + c log(1 + 1/c) − 1}{log b} + O (\frac{1}{b log b}))

≥ 1 + \frac{log c + log(c + 1) + c log(1 + 1/c) − 1}{log b} + O (\frac{1}{b}) ,

since δb = 1 − 1/b. This expression is greater than 1 for large b as we have log c + log(c + 1) + c log(1 + 1/c) − 1 > log c_{0} + log(c_{0} + 1) + c_{0} log(1 + 1/c_{0}) − 1 > 2 log c_{0} + log(c_{0} + 1) + c_{0} log(1 + 1/c_{0}) − 1 = 0.

(ii) We apply the bound obtained in the first part of the proof to get

log_{b} (t^{δ log_{b} t} · (\frac{(t − 1 + b)!}{(t − 1)!})^{(b−2)δ^{2}(log_{b} t)^{2}})

= δ (\frac{log t}{log b})^{2} + (b − 2)δ \frac{log t}{log b} log_{b} (\frac{(t − 1 + b)!}{(t − 1)!})^{δ log_{b} t}

≥ (\frac{1}{b} − \frac{1}{b^{2}} ) (1 + \frac{log c}{log b})^{2} + (1 − \frac{2}{b}) (1 + \frac{1}{b}) (1 + \frac{log c}{log b}) ·

· (1 + \frac{log c + log(c + 1) + c log(1 + 1/c) − 1}{log b} + O (\frac{1}{b}))

= 1 + \frac{2 log c + log(c + 1) + c log(1 + 1/c) − 1}{log b} + O (\frac{1}{b}) ,

which is greater than 1 for large b since 2 log c + log(c + 1) + c log(1 + 1/c) − 1 > 2 log c_{0} + log(c_{0} + 1) + c_{0} log(1 + 1/c_{0}) − 1 = 0.

Theorem 23. Conjecture 4 implies the following: let c_{0} be the solution 2 log c + log(c + 1) + c log(1 + 1/c) = 1 in the interval (0, 1) (c_{0} ≈ 0.865722). Then, for every c > c_{0}, there exists b_{0} with the following property: for every prime number b ≥ b_{0} and positive integer t ≥ cb, the sequence of iterates (S_{t,b}^{k}(n))_{k≥1} diverges for every sufficiently large integer n.

Proof. Fix c > c_{0}. Let b_{0} be the integer given by Lemma 22 for this c, and let t, b be integers such that t ≥ cb and b ≥ b_{0}.

We apply Conjecture 4 with q = b, a = 1, F = {p prime : p ≤ b+t−1, p ≠ b} to get the following statement: for every ε > 0, there is N such that the number ∏_{p_{i} prime:p_{i}≤b+t−1, p_{i}≠b} p_{i}^{a_{i}} is ε-equidistributed if any of the a_{i} is at least N.

Put f = S_{t,b}. We can write f(n) = ∏_{i=0}^{b−1}(i + t)^{n_{i}} = b^{n_{b−t}} · ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}. As b is a prime number, b ∤ ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}, and then f^{2}(n) = t^{n_{b−t}} · f(∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}).

Let n′_{i} denote the number of digits i in ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}. Then we may rewrite f^{2}(n) = t^{n_{b−t}} · ∏_{i=0}^{b−1}(i + t)^{n′_{i}} = b^{n′_{b−t}} · t^{n_{b−t}} · ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n′_{i}}.

Let ε = 1/b^{2} and put δ = 1/b − ε. Let M ≥ N/(δ log_{b} 2), where N is the integer given by the application of Conjecture 4 as above with ε = 1/b^{2}, and M is large enough as to satisfy that (17) is greater than 1. Let n ≥ b^{(b−1)M+M^{2}} be an integer. We will prove that f^{3}(n) > n, which implies that the sequence of iterates of f starting from any integer at least b^{(b−1)M+M^{2}} diverges.

Either n_{i} ≥ M for some i ≠ b − t or n_{b−t} ≥ M^{2} ≥ M ≥ N. In the first case, this implies that n′_{i} ≥ δ log_{b}(∏_{i=0,i≠b−t}^{b−1}(i+t)^{n_{i}}) ≥ (δ log_{b} 2) ∑_{i=0,i≠b−t}^{b−1} n_{i} ≥ (δ log_{b} 2)M ≥ N. In any case, the number t^{n_{b−t}}·∏_{i=0,i≠b−t}(i+t)^{n′_{i}} is ε-equidistributed. This means that every digit from 0 to b−1 appears at least δ log_{b}(t^{n_{b−t}} ·∏_{i=0,i≠b−t}(i+t)^{n′_{i}}) = δ(n_{b−t} log_{b} t+∑_{i=0,i=b−t}^{b−1} n′_{i} log_{b}(i+t)) times in this number, and hence

f^{3}(n) = f(b^{n′_{b−t}} · t^{n_{b−t}} · ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n′_{i}})

= t^{n′_{b−t}} · f(t^{n_{b−t}} · ∏_{i=0,i≠b−t}^{b−1}(i + t)^{n′_{i}})

≥ t^{n′_{b−t}}(t(t + 1) ⋯ (b + t − 1))^{δ(n_{b−t} log_{b} t+∑_{i=0,i≠b−t}^{b−1} n′_{i} log_{b}(i+t))}

≥ t^{n′_{b−t}} · (\frac{(t − 1 + b)!}{(t − 1)!})^{δ(n_{b−t}+∑_{i=0,i≠b−t}^{b−1} n′_{i}) log_{b} t} .  (16)

Suppose first that n_{i} ≥ M for some i ≠ b−t. Then ∏_{i=0,i≠b−t}^{b−1}(i+t)^{n_{i}} is ε-equidistributed, which implies that n′_{i} ≥ δ log_{b}(∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}) ≥ δ log_{b} t ∑_{i=0,i≠b−t}^{b−1} n_{i} for every 1 ≤ i ≤ b − 1. In this case, bound (16) implies, together with Lemma 22, that

f^{3}(n) ≥ (t^{δ log_{b} t} · (\frac{(t − 1 + b)!}{(t − 1)!})^{(b−2)δ^{2}(log_{b} t)^{2}})^{∑_{i=0,i≠b−t}^{b−1} n_{i}} · (\frac{(t − 1 + b)!}{(t − 1)!})^{(δ log_{b} t)n_{b−t}}
> b^{∑_{i=0,i≠b−t}^{b−1} n_{i}+n_{b−t}}
≥ n.

Finally, if n_{i} < M for every i ≠ b − t, then n_{b−t} ≥ M^{2}. Moreover, we have n′_{i} ≤ log_{b}(∏_{i=0,i≠b−t}^{b−1}(i + t)^{n_{i}}) < b log_{b}(2b)M for every 0 ≤ i ≤ b − 1, and then, using (16), we get that

\frac{f^{3}(n)}{n} ≥ \frac{1}{n} · t^{n′_{b−t}} · (\frac{(t − 1 + b)!}{(t − 1)!})^{δ(n_{b−t}+∑_{i=0,i≠b−t}^{b−1} n′_{i}) log_{b} t}

≥ \frac{1}{n} · (\frac{(t − 1 + b)!}{(t − 1)!})^{(δ log_{b} t)n_{b−t}}

> (\frac{1}{b} · (\frac{(t − 1 + b)!}{(t − 1)!})^{δ log_{b} t})^{n_{b−t}} · b^{− ∑_{i=0,i≠b−t}^{b−1} n_{i}}

≥ (\frac{1}{b} · (\frac{(t − 1 + b)!}{(t − 1)!})^{δ log_{b} t})^{M^{2}} · b^{−bM}  (17)

> 1,

if M is large enough (since, by Lemma 22, the base of M^{2} in the last line of (17) is greater than 1). This concludes the proof.

Remark 24. As we saw before (in Theorems 19 and 20), if one applies bounds for n! that hold for every n instead of the asymptotic Stirling formula, it is possible to get a result of the following form, with c being a constant greater than c_{0} in Theorem 23: let b ≥ 7 be a prime and t ≥ cb. Conjecture 4 implies that, for every sufficiently large integer n, the sequence of iterates (S_{t,b}^{k}(n))_{k≥1} diverges to infinity.

6 Concluding remarks

As we made clear from the beginning, most of the main results in the present paper (Theorems 5, 10, 15, 17, 19 and 23) are conditional on the validity of Conjecture 1 or 4. There is ample experimental evidence in favor of Conjecture 1, and further support would be provided if one could prove our main results unconditionally. Conversely, of course, if any one of these unconditional statements were proved to be false, then Conjecture 1 (or 4) would have to be false. However, given the computational evidence and robust heuristics available [2], we feel confident that Conjectures 1 and 4 must be true.

7 Acknowledgments

We wish to thank the referee for several remarks and suggestions that led to a considerable improvement of our exposition.

References

[1] A. F. Beardon, Sums of squares of digits, Math. Gaz. 82 (1998), 379–388.

[2] E. de Faria and C. Tresser, On Sloane’s persistence problem, Exp. Math. 23 (2014), 363–382.

[3] M. R. Diamond and D. D. Reidpath, A counterexample to conjectures by Sloane and Erdős concerning the persistence of numbers, J. Recreat. Math. 29 (1998), 89–92.

[4] P. Erdős, Some unconventional problems in number theory, Math. Mag. 52 (1979), 67–70.

[5] R. K. Guy, Unsolved Problems in Number Theory, Vol. 1, Springer Science & Business Media, 2013.

[6] A. M. Herzberg and M. R. Murty, Some remarks on iterated maps of natural numbers, Resonance 19 (2014), 1038–1046.

[7] H. J. Hinden, The additive persistence of a number, J. Recreat. Math. 7 (1974), 134–135.

[8] W. Narkiewicz, A note on a paper of H. Gupta concerning powers of two and three, Publikacije Elektrotehničkog fakulteta. Serija Matematika i fizika 678/715 (1980), 173– 174.

[9] N. J. A. Sloane, The persistence of a number, J. Recreat. Math. 6 (1973), 97–98.

[10] S. S. Wagstaff, Iterating the product of shifted digits, Fibonacci Quart. 19 (1981), 340– 347.

2010 Mathematics Subject Classification: Primary 11A63; Secondary 11A67. Keywords: persistence of a number, Sloane’s conjecture, products of digits, shifted Sloane problem, equidistribution of digits.

(Concerned with sequences \underline{A031346}, \underline{A036461}, \underline{A335808}, \underline{A335824}.)

Received September 1 2020; revised versions received October 14 2020; October 16 2020; October 18 2020. Published in Journal of Integer Sequences, October 18 2020.

Return to Journal of Integer Sequences home page.