Bounds for Sets of Remainders

Omkar Baraskar and Ingrid Vukusic^{1} School of Computer Science University of Waterloo Waterloo, ON N2L 3G1 Canada

                 obaraska26@gmail.com
               ingrid.vukusic@york.ac.uk

Abstract

Let s(n) be the number of different remainders n mod k, where 1 ≤ k ≤ ⌊n/2⌋. This rather natural sequence is sequence \underline{A283190} in the OEIS, and although some basic facts are known, surprisingly, it has been barely studied. First, we prove the asymptotic formula s(n) = cn + O(n/(log n log log n)), where c is an explicit constant. Then we focus on the difference between the consecutive terms s(n) and s(n + 1). It turns out that the value can always increase by at most one, but there exist arbitrarily large decreases. We show that the upper bound on the difference is O(log log n). Finally, we consider “iterated remainder sets”. These are related to a problem arising from Pierce expansions, and we prove bounds for the size of these sets as well.

1 Introduction

Let us fix an integer n. Then a natural question is the following: What are the remainders r = n mod k? The sum of such remainders with 1 ≤ k ≤ n was already considered by Lucas [?, p. 373] and more recently in [?, ?, ?]. In the present paper, we are simply interested in the number of distinct remainders. Surprisingly, it seems that this question has been barely studied.

If k > n, then we get r = n for all k. If ⌊n/2⌋ + 1 ≤ k ≤ n, then r = n − k, so in this range we simply get all the integers

between 0 and ⌈n/2⌉ − 1.

Therefore, the interesting cases are where 1 ≤ k ≤ ⌊n/2⌋, and we define the set

S(n) := {n mod k: k ∈ {1, 2, …, ⌊n/2⌋}}.

Note that clearly S(n) ⊆ {0, 1, …, ⌊n/2⌋ − 1}. Now, let us define

s(n) := |S(n)|.

1Author’s current address: Department of Mathematics, University of York, York, North Yorkshire YO10 5GH, United Kingdom. Research supported by NSERC grant 2024-03725.

In other words, s(n) is the number of different values n mod k for 1 ≤ k ≤ ⌊n/2⌋. This is precisely sequence \underline{A283190} in the OEIS (On-Line Encyclopedia of Integer Sequences) [?]. We present the first few numbers of the sequence in Table 1.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ s(n) & 0 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 2 & 3 & 4 & 2 & 3 & 3 & 3 & 4 & 5 & 3 \end{matrix}

Table 1: First eighteen values of s(n).

Although it seems like a natural sequence, it was only entered into the OEIS in 2017 by T. Kerscher. R. Israel then observed that s(n)/n seems to converge to approximately 0.2296. He asked about the actual value of the constant on the StackExchange website [?]. This was answered by the user Empy2 (and added as a comment to the OEIS entry by M. Peake):

lim_{n→∞} \frac{s(n)}{n} = ∑_{p∈ℙ} \frac{1}{p(p + 1)} · ∏_{\begin{matrix}q∈ℙ, \\ q<p \end{matrix}} (1 − \frac{1}{q}) ≈ 0.2296.  (1)

The answer on the StackExchange website also contains an explanation for why this is true. While the argument is relatively simple, we did not find a rigorous proof in print. In this paper, in Section 3, we give a proof of (1), including a bound for the error term.

Then we investigate the differences between consecutive terms of s(n). Looking at the first few values of the sequence s(n), one sees that the values of s(n + 1) compared to s(n) usually either stay the same or increase or decrease by 1. They never seem to increase by more than 1, but sometimes they decrease by 2 or, as it turns out, even more. In Section 4 we show that these differences can get arbitrarily large, while being double logarithmically bounded in terms of n.

In Section 5, we generalize the set S(n) =: S_{1}(n) to “iterated remainder sets” via S_{j+1}(n) := {n mod k: k ∈ S_{j}(n) \ {0}} for j ≥ 1. These sets are related to an older problem arising from Pierce expansions. In several papers [?, ?, ?] the following problem was considered: If we fix a positive integer n, choose another integer 1 ≤ a ≤ n, and repeatedly set a := n mod a, what is the largest number of steps performed before reaching a = 0? This problem remains open. More on this and the relation to our iterated remainder sets in Section 5. In Section 6 we prove some bounds for these sets.

Finally, in Section ?? we pose some open problems.

However, we first present all the main results in the next section.

2 Main results and some lemmas

Let us define the constant from (1), namely

c := ∑_{p} \frac{1}{p(p + 1)} · ∏_{p′<p} (1 − \frac{1}{p′} ) ≈ 0.2296.

In Section 3 we will prove the following asymptotics for s(n).

Theorem 1. We have

s(n) = cn + O (\frac{n}{log n log log n}) .

In particular,

lim_{n→∞} \frac{s(n)}{n} = c.

We believe that our bound for the error term is not sharp. Numerical experiments suggest that O(n^{1/3}) might be closer to the truth; see Section ??. In any case, we know that overall s(n) grows linearly; however, due to the error term, this does not provide much information on the differences s(n + 1) − s(n).

As mentioned in the introduction, looking at the first few values of s(n), it seems that the values of s(n + 1) compared to s(n) usually either stay the same or increase or decrease by 1. It turns out that they never increase by more than 1, but sometimes they do decrease by 2 or even more. For example, s(131) = 33 and s(132) = 30. The first time that the value decreases by 4 happens at n = 17291, where s(17291) = 3975 and s(17292) = 3971. We have searched up to n = 10^{7} and have not found a decrease by more than 4 in this range. However, it turns out that arbitrarily large decreases do exist, and we will provide a construction for such n. On the other hand, we can prove bounds on the decreases in terms of n. In Section 4 we will, in particular, prove the following results.

Theorem 2. For n ≥ 1 we have

s(n) − O(log log n) ≤ s(n + 1) ≤ s(n) + 1.

Moreover,

lim inf_{n→∞} s(n + 1) − s(n) = −∞.

Now, let us define the sets of iterated remainders of n inductively by

S_{0}(n) := {1, 2, …, ⌊n/2⌋} and
S_{j}(n) := {n mod k: k ∈ S_{j−1}(n) \ {0}} for j ≥ 1.

Note that, in particular, S(n) = S_{1}(n). Moreover, analogously to s(n), we define

s_{j}(n) := |S_{j}(n)|.

In Section 6, we will prove the following bounds.

Theorem 3. For j ≥ 0 we have

\frac{1}{(j + 2)!} ≤ lim inf_{n→∞} \frac{s_{j}(n)}{n} ≤ lim sup_{n→∞} \frac{s_{j}(n)}{n} ≤ \frac{1}{j + 2}.

While the bounds are clearly not sharp (for example, set j = 1 and compare to Theorem 1), it seems that for j ≥ 2 there is indeed a gap between the limit inferior and limit superior; see Section ??.

Before moving on, we state two simple lemmas. All results on s(n) will be based on the following equivalence.

Lemma 4. Let r ∈ {0, 1, …, ⌊n/2⌋ − 1}. Then r ∈ S(n) if and only if n − r has a proper divisor k ≥ r + 1.

Proof. First, assume r ∈ S(n). This means that there exist integers k ∈ {1, 2, …, ⌊n/2⌋} and q such that

n = kq + r

and r ≤ k − 1. In other words, k is a divisor of n − r with k ≥ r + 1. Moreover, k ≤ ⌊n/2⌋ implies q ≥ 2, and therefore k is indeed a proper divisor of n − r.

Now assume conversely that n − r has a proper divisor k ≥ r + 1. Then we have

n − r = kq

for some q ≥ 2. This means that r = n mod k. Moreover, q ≥ 2 implies k = (n − r)/q ≤ ⌊n/2⌋, and so by definition r ∈ S(n).

Finally, let us give a slightly more precise statement than S(n) ⊆ {0, 1, … ⌊n/2⌋ − 1}.

Lemma 5. We have S(n) ⊆ {0, 1, …, ⌊(n − 2)/3⌋}.

Proof. Let r ∈ S(n). Then by Lemma 4, the number n − r has a proper divisor k ≥ r + 1. In other words, n − r = kq with q ≥ 2. This implies n − r ≥ (r + 1) · 2, and rewriting the inequality yields n ≥ 3r + 2.

Note that throughout the paper, p will denote a prime. In particular, if we sum or take the union over an index p, the numbers p are implied to be primes.

3 Asymptotics for s(n) (proof of Theorem 1)

In this section, we want to prove that s(n) asymptotically behaves like cn and compute a bound for the error term. We do this with a straightforward sieving argument. In preparation for this, let us define the set of integers that are divisible by p but not by any smaller prime p′ < p:

D_{p} := {m ∈ ℤ: p | m, and p′ ∤ m for every prime p′ < p}.  (2)

As usual, let π(n) denote the number of primes p ≤ n.

The next lemma is standard; we provide a proof for completeness. hii Lemma 6. Let a, t be positive integers and p a prime. Then

|D_{p} ∩ [a + 1, a + t]| = t · \frac{1}{p} · ∏_{p′<p} (1 − \frac{1}{p′} ) + E(a, t, p),

and the error term E(a, t, p) is bounded by

|E(a, t, p)| ≤ 2^{π(p−1)}.

Proof. This follows from a simple inclusion–exclusion argument. Indeed, we have

|D_{p} ∩ [a + 1, a + t]| = (⌊\frac{a + t}{p}⌋ − ⌊\frac{a}{p}⌋) − ∑_{p_{1}<p} (⌊\frac{a + t}{pp_{1}}⌋ − ⌊\frac{a}{pp_{1}} ⌋)

+ ∑_{p_{1}<p_{2}<p} (⌊\frac{a + t}{pp_{1}p_{2}} ⌋ − ⌊\frac{a}{pp_{1}p_{2}} ⌋) − + …

± (⌊\frac{a + t}{p ∏_{p′<p} p′} ⌋ − ⌊\frac{a}{p ∏_{p′<p} p′} ⌋) .

Each difference of the shape ⌊(a + t)/q⌋ − ⌊a/q⌋ is equal to t/q + δ, with some error term δ with |δ| < 1. There are exactly 2^{π(p−1)} such differences. Therefore,

|D_{p} ∩ [a + 1, a + t]| =\frac{t}{p} − ∑_{p_{1}<p} \frac{t}{pp_{1}} + ∑_{p_{1}<p_{2}<p} \frac{t}{pp_{1}p_{2}} − + ⋯ ± \frac{t}{p ∏_{p′<p} p′} + E(a, t, p)

= t · \frac{1}{p} · ∏_{p′<p} (1 − \frac{1}{p′} ) + E(a, t, p),

with |E(a, t, p)| < 2^{π(p−1)}, as desired.

We will also use the next lemma, which is a classical upper bound for the prime counting function [?, Corollary 1].

Lemma 7. For every n ≥ 2 we have

π(n) ≤ 1.3 · \frac{n}{log n}.

Finally, we will use the following simple estimate.

Lemma 8. We have

∑_{p>n} \frac{1}{p^{2}} = O (\frac{1}{n log n}) .

Proof. By the prime number theorem, the k-th p_{k} prime is asymptotically of the size p_{k} ∼ k log k. The lemma follows from a density argument. To be rigorous, we can do the following estimates for sufficiently large n, where C_{1}, C_{2}, C_{3} are some positive constants:

∑_{p>n} \frac{1}{p^{2}} ≤ C_{1} · ∑_{k≥n/ log n} \frac{1}{(k log k)^{2}} ≤ C_{2} · ∫_{n/ log n}^{∞} \frac{1}{(t log t)^{2}} dt

≤ C_{2} · \frac{1}{(log(n/ log n))^{2}} · ∫_{n/ log n}^{∞} \frac{1}{t^{2}} dt

≤ C_{3} · \frac{1}{(log n)^{2}} · \frac{1}{n/ log n} = C_{3} · \frac{1}{n log n}.

Now we are ready to prove the asymptotics for s(n).

Proof of Theorem 1. We want to use Lemma 4 to count the remainders r ∈ S(n)\{0}. Note that n − r having a proper divisor k ≥ r + 1 is equivalent to n − r having a prime factor p ≤ (n−r)/(r+1). Moreover, note that the last inequality is equivalent to r ≤ (n−p)/(p+1). We want to count the remainders r systematically by going through the prime numbers p. Therefore, we define for every n and every prime p < n the set

R_{p}(n) := \{r: 1 ≤ r ≤ \frac{n − p}{p + 1}, p | n − r, and p′ ∤ n − r for every prime p′ < p\} .

Then we have

S(n) \ {0} = ⋃_{p<n} R_{p}(n).

Since all sets in the union are disjoint by construction, we have in particular

s(n) − 1 = |S(n) \ {0}| = ∑_{p<n}|R_{p}(n)|.  (3)

Instead of counting the numbers r ∈ R_{p}(n), we can equivalently count the numbers m = n−r. In other words, if we define

M_{p}(n) := \{m ∈ [n − \frac{n − p}{p + 1}, n − 1] : p | m, and p′ ∤ m for every prime p′ < p\} ,

then we have |R_{p}(n)| = |M_{p}(n)|.

Let X = X(n) be some threshold function with 1 < X(n) < n that we will fix later. Our strategy is to compute

s(n) = 1 + ∑_{p<n}|M_{p}(n)| = ∑_{p<X}|M_{p}(n)| + \underbrace{1 + ∑_{X≤p<n}|M_{p}(n)|}_{=:E_{1}(n)} .  (4)

We do this because on the one hand, if p is small compared to n, we can compute |M_{p}(n)| relatively precisely. On the other hand, if p is sufficiently large, |M_{p}(n)| is small, and we can estimate the error term E_{1}(n) trivially. Let us do the latter first. We have

|E_{1}(n)| = 1 + ∑_{X≤p<n}|M_{p}(n)| ≤ 1 + ∑_{p≥X} \frac{n}{(p + 1)p} ≤ 1 + n · ∑_{p≥X} \frac{1}{p^{2}} = O (\frac{n}{X log X} ) , (5)

where we used Lemma 8 for the last estimate.

In order to compute the main term in (4), for each p < X we apply Lemma 6 with a = n − \frac{n−p}{p+1} − 1 and t = \frac{n−p}{p+1}. This gives us

|M_{p}(n)| = \frac{n − p}{p + 1} · \frac{1}{p} · ∏_{p′<p} (1 − \frac{1}{p′} ) + E_{2}(n, p),

with

|E_{2}(n, p)| ≤ 2^{π(p−1)}.

Now we can write

∑_{p<X}|M_{p}(n)| = ∑_{p<X} \frac{n − p}{p + 1} · \frac{1}{p} · ∏_{p′<p} (1 − \frac{1}{p′} ) + ∑_{p<X} E_{2}(n, p)

= n · ∑_{p<X} \frac{1}{p(p + 1)} · ∏_{p′<p} (1 − \frac{1}{p′} ) \underbrace{− ∑_{p<X} \frac{1}{p + 1} · ∏_{p′<p} (1 − \frac{1}{p′} ) + ∑_{p<X} E_{2}(n, p)}_{=:E_{2}(n)},

with

|E_{2}(n)| ≤ X + ∑_{p<X} 2^{π(p−1)} ≤ X + 2^{π(X)},  (6)

where in the error term we estimated the first sum very crudely by X, and for the second sum we used the definition of π(x).

Finally, recall that

c = ∑_{p} \frac{1}{p(p + 1)} · ∏_{p′<p} (1 − \frac{1}{p′} ) .

Thus, we can write

∑_{p<X}|M_{p}(n)| = cn − \underbrace{n · ∑_{p≥X} \frac{1}{p(p + 1)} · ∏_{p′<p} (1 − \frac{1}{p′} )}_{=:−E_{3}(n)} +E_{2}(n),  (7)

with

|E_{3}(n)| ≤ n · ∑_{p≥X} \frac{1}{p^{2}} = O (\frac{n}{X log X} ) ,  (8)

where we used Lemma 8 for the last estimate.

Overall, we have from (4) and (7) that

s(n) = cn + E_{1}(n) + E_{2}(n) + E_{3}(n).

Using the bounds for the error terms from (5), (6), and (8), and setting X = X(n) = log n, we get

s(n) = cn + O (\frac{n}{X log X} ) + O(X) + O(2^{π(X)})
= cn + O (\frac{n}{log n log log n}) + O(log n) + O(2^{π(log n)}).

The theorem follows upon noting that with Lemma 7 for sufficiently large n we get

2^{π(log n)} ≤ 2^{1.3 log n/ log log n} ≤ n^{1/ log log n} ≤ n^{1/2} = O (\frac{n}{log n log log n}) .

Remark 9. At first glance, the last estimate in the proof above appears quite rough. However, increasing X(n) from log n even to just (log n)^{1+ε} does not work using the same arguments. To improve the bound, one would need to find stronger error bounds.

4 Differences between consecutive terms of s(n) (proof of Theorem 2)

In this section, we try to understand better how s(n) changes as n increases by 1. First, observe the following relation between elements in S(n + 1) and S(n).

Lemma 10. For every n ≥ 1 we have

S(n + 1) \ {0} ⊆ {r + 1: r ∈ S(n)}.

Proof. Let r ∈ S(n + 1) \ {0}. Then by Lemma 4 the integer n + 1 − r has a proper divisor k ≥ r + 1. Now since n − (r − 1) = n + 1 − r has a proper divisor k ≥ r + 1 ≥ r, we have r − 1 ∈ S(n).

From this, we immediately see that the value of s(n) can increase by at most one at a time:

Proposition 11. For every n ≥ 1 we have

s(n + 1) ≤ s(n) + 1.

Proof. We have

s(n + 1) − 1 = |S(n + 1)| − 1 ≤ |S(n + 1) \ {0}| ≤ |S(n)| = s(n),

where we applied Lemma 10 for the last inequality.

Note that 0 = n mod 1 is always in S(n + 1) and recall Lemma 10, and its proof. We can interpret it in the following way: The set S(n + 1) consists precisely of the element 0 and all the elements r + 1 that were “transferred” from S(n) to S(n + 1) by being increased by 1. Thus, to understand the difference s(n + 1) − s(n), we need to understand how many elements r were not transferred. We denote the set of “not transferred elements” by

T (n, n + 1) := {r: r ∈ S(n) and r + 1 ∉ S(n + 1)}.

Then we have

s(n + 1) = s(n) + 1 − |T (n, n + 1)|.  (9)

Next, we characterize the set T (n, n + 1).

Lemma 12. We have r ∈ T (n, n + 1) if and only if r + 1 is the largest proper divisor of n − r.

Proof. This follows directly from Lemma 4: r ∈ S(n) is equivalent to n − r having a proper divisor ≥ r + 1, and r + 1 ∉ S(n + 1) is equivalent to (n + 1) − (r + 1) = n − r not having a proper divisor ≥ r + 2.

To count such occurrences, we will use the following simple lemma.

Lemma 13. Let n, d be positive integers. Then d is the largest proper divisor of n if and only if n/d = p for some prime p and every prime factor of d is ≥ p.

Now, for even n, the situation is rather simple:

Proposition 14. Let n ≥ 2 be even. Then

T (n, n + 1) = \begin{cases}\{(n − 2)/3\}, & if n ≡ 2 (mod 3); \\ ∅, & otherwise. \end{cases}

In particular,

s(n + 1) = \begin{cases}s(n), & if n ≡ 2 (mod 3); \\ s(n) + 1, & otherwise. \end{cases}

Proof. By Lemma 12 we have r ∈ T (n, n + 1) if and only if r + 1 is the largest proper divisor of n − r. By Lemma 13, this is the case if and only if (n − r)/(r + 1) = p for some prime p and every prime factor of r + 1 is ≥ p. Let us find all values of r for which this is the case. Assume first that r is odd. Then (n − r)/(r + 1) = odd/even = p, which is impossible. Now assume that r is even, and we have (n − r)/(r + 1) = even/odd = p. This means that p = 2 and n = 3r + 2. So this happens if and only if n ≡ 2 (mod 3) and r = (n − 2)/3.

The second part of the lemma now follows immediately from formula (9).

For odd n, we will prove that |T (n, n + 1)| is at most double logarithmic in n.

Let us first use Lemmas 12 and 13 to characterize the sets T (n, n + 1) more precisely.

Lemma 15. Assume that n + 1 = p_{1}^{x_{1}} ⋯ p_{ℓ}^{x_{ℓ}} is the prime factorization of n + 1 with p_{1} < ⋯ < p_{ℓ}. Let 1 ≤ r < (n − 2)/3. Then r ∈ T (n, n + 1) if and only if all of the following conditions are satisfied:

(i) r + 1 = p_{I}^{x_{I}} ⋯ p_{ℓ}^{x_{ℓ}} for some index 2 ≤ I ≤ ℓ;

(ii) (n + 1)/(r + 1) − 1 = p_{1}^{x_{1}} ⋯ p_{I−1}^{x_{I−1}} − 1 = p for some prime p;

(iii) p ≤ p_{I}.

Moreover, r = 0 ∈ T (n, n + 1) if and only if n = p_{1}^{x_{1}} ⋯ p_{ℓ}^{x_{ℓ}} − 1 is prime. Finally, if n ≡ 2 (mod 3), then r = (n − 2)/3 ∈ T (n, n + 1).

Proof. By Lemma 12 we have r ∈ T (n, n + 1) if and only if r + 1 is the largest proper divisor of n − r. By Lemma 13 this is equivalent to

\frac{n − r}{r + 1} = \frac{n + 1}{r + 1} − 1 = p  (10)
and every prime factor of r + 1 is at least of size p.  (11)

Let 1 ≤ r < (n − 2)/3 and assume that n + 1 = p_{1}^{x_{1}} ⋯ p_{ℓ}^{x_{ℓ}}. We check that (10) and (11) are equivalent to the three conditions in the statement of the lemma.

Assume first that (10) and (11) hold. Then since r + 1 | n + 1, we have

r + 1 = p_{1}^{y_{1}} ⋯ p_{ℓ}^{y_{ℓ}}, with 0 ≤ y_{i} ≤ x_{i} for 1 ≤ i ≤ ℓ.

Let I be the index such that p_{1} < ⋯ < p_{I−1} < p ≤ p_{I} < ⋯ < p_{ℓ} (where I = 1 is allowed and means that p ≤ p_{1}). Then (11) implies that y_{1} = ⋯ = y_{I−1} = 0. Moreover, for every I ≤ i ≤ ℓ we can write

\frac{n + 1}{r + 1} = p_{i}^{x_{i}−y_{i}} · A = p + 1,

with some integer A ≥ 1. Then p_{I} ≥ p implies x_{i} − y_{i} = 0 for all i = I, …, ℓ, except if p_{i} = 3, x_{i} − y_{i} = 1, A = 1 and p = 2. The exceptional situation is (n + 1)/(r + 1) = 3, which is equivalent to r = (n − 2)/3 and was excluded. In the other situations, we have y_{I} = x_{I}, …, y_{ℓ} = x_{ℓ}, and the three conditions in the lemma are clearly satisfied (the condition I ≥ 2 follows from (n + 1)/(r + 1) = p + 1 > 1).

Conversely, it is clear that the three conditions in the lemma imply (10) and (11).

The statement for r = 0 holds because always 0 ∈ S(n) and by Lemma 4 we have 1 ∈ S(n + 1) if and only if n = (n + 1) − 1 is composite.

Finally, assume r = (n − 2)/3 is an integer. Then n mod (n + 1)/3 = r and so r ∈ S(n). On the other hand, r + 1 > (n − 2)/3 = ⌊(n + 1 − 2)/3⌋ and so by Lemma 5 we have r + 1 ∉ S(n + 1).

Proposition 16. For every odd n ≥ 1 we have

s(n) − s(n + 1) = O(log log n).

Proof. In view of formula (9) it suffices to prove that

|T (n, n + 1) \ {0, (n − 2)/3}| = O(log log n).

In other words, we want to show that there are at most O(log log n) numbers r satisfying the three conditions in Lemma 15. Fix an odd n ≥ 1 and let

n + 1 = p_{1}^{x_{1}} ⋯ p_{ℓ}^{x_{ℓ}}

be the prime factorization of n + 1 with p_{1} < ⋯ < p_{ℓ}. Then by Lemma 15, r + 1 must be of the shape r + 1 = p_{I}^{x_{I}} ⋯ p_{ℓ}^{x_{ℓ}} for some index 2 ≤ I ≤ ℓ. Moreover, for these indices I, we have

p_{I} ≥ p = p_{1}^{x_{1}} ⋯ p_{I−1}^{x_{I−1}} − 1 ≥ p_{2} ⋯ p_{I−1}.

Assume that there are t such numbers r, corresponding to the indices I_{1} < ⋯ < I_{t}. Then we can weaken the above inequality to

p_{I_{j}} ≥ p_{I_{2}}p_{I_{3}} ⋯ p_{I_{j−1}}.

Using this inequality inductively, we get

n = p_{1}^{x_{1}} ⋯ p_{ℓ}^{x_{ℓ}} − 1 ≥ p_{I_{2}}p_{I_{3}} ⋯ p_{I_{t}}
≥ (p_{I_{2}}p_{I_{3}} ⋯ p_{I_{t−1}})^{2} ≥ (p_{I_{2}}p_{I_{3}} ⋯ p_{I_{t−2}})^{4} ≥ ⋯ ≥ p_{I_{2}}^{2^{t−2}} ≥ 3^{2^{t−2}}.

This implies

t − 2 ≤ log_{2} log_{3}(n),

and so t = O(log log n), as desired.

Proposition 17. We have

lim inf_{n→∞} s(n + 1) − s(n) = −∞.

Proof. Let us set

t(n) := |T (n, n + 1)|.

In view of formula (9), our strategy is to use Lemma 15 to recursively construct numbers n^{(1)}, n^{(2)}, … with the properties

• n^{(j)} is prime and

• t(n^{(j)}) ≥ j.

For good intuition, let us set the first three values straight away:

n^{(1)} := 3 = 2^{2} − 1, n^{(2)} := 11 = 2^{2} · 3 − 1, n^{(3)} := 131 = 2^{2} · 3 · 11 − 1.

This works because of Lemma 15 and the following facts: 2^{2} − 1 is prime and 2^{2} − 1 ≥ 3, and 2^{2} · 3 − 1 is prime and 2^{2} · 3 − 1 ≥ 11, and also 2^{2} · 3 · 11 − 1 is prime.

Now assume we have already constructed n^{(j)} for some j ≥ 3. Set

P := ∏_{p≤n^{(j)}} p.

For reasons that will become apparent in (12), we want to choose an integer y with the following properties:

(a) gcd(xP + y, P) = 1 for all integers x. This is equivalent to y ≢ 0 (mod p) for all p | P.

(b) gcd(y(n^{(j)} + 1) − 1, P) = 1. This is equivalent to y(n^{(j)} + 1) ≢ 1 (mod p) for all p | P with p ∤ n^{(j)} + 1.

Overall, we want y to satisfy

y ≢ 0, (n^{(j)} + 1)^{−1} (mod p) for all p | P.

For each p ≥ 3, this is clearly possible, since at most two residue classes need to be avoided. For the case p = 2, note that since n^{(j)} is a prime, n^{(j)} + 1 is even, so p | n^{(j)} + 1 and we only need to avoid y ≡ 0 (mod 2).

Therefore, by the Chinese remainder theorem, there exists an integer 1 ≤ y ≤ P with properties (a) and (b).

We fix such an integer y and consider the arithmetic progression

a_{x} := (n^{(j)} + 1)(xP + y) − 1 = xP (n^{(j)} + 1) + y(n^{(j)} + 1) − 1, x ≥ 1.  (12)

Now our property (b) implies that

gcd(P (n^{(j)} + 1), y(n^{(j)} + 1) − 1) = 1.

Thus, by Dirichlet’s prime number theorem, there exists an integer x ≥ 1 such that a_{x} is a prime. We set

n^{(j+1)} := (n^{(j)} + 1)(xP + y) − 1 = a_{x}.

By construction, n^{(j+1)} is prime, and we finally only need to check that indeed t(n^{(j+1)}) ≥ t(n^{(j)}) + 1 ≥ j + 1.

It is easy to see that by construction n^{(j+1)} ≡ 2 (mod 3) for all j ≥ 2 and n^{(j+1)} is prime, so the special cases from Lemma 15, namely r = 0 and r = (n^{(j+1)} − 2)/3, are always in T (n^{(j+1)}, n^{(j+1)} + 1).

Moreover, let us write n^{(j)} = p_{1}^{x_{1}} ⋯ p_{ℓ}^{x_{ℓ}} − 1 with p_{1} < ⋯ < p_{ℓ}. Then we have n^{(j+1)} = p_{1}^{x_{1}} ⋯ p_{ℓ}^{x_{ℓ}} · Q − 1, where all prime factors in Q = xP + y are larger than p_{ℓ} by property (a) and the definition of P. Thus, if r satisfied the three conditions in Lemma 15 for n^{(j)}, then r′ = (r − 1) · Q + 1 satisfies the three conditions in Lemma 15 for n^{(j+1)}. The increase comes from the fact that now r′ = Q − 1 satisfies the three conditions as well.

Proof of Theorem 2. Combine Propositions 11, 14, 16, and 17.

5 Iterated remainder sets and their relation to the “n mod a problem”

Recall that we defined the sets of iterated remainders of n inductively by

S_{0}(n) := {1, 2, …, ⌊n/2⌋} and
S_{j}(n) := {n mod k: k ∈ S_{j−1}(n) \ {0}} for j ≥ 1.

These sets are related to an older open problem about the length of the Pierce expansion. Shallit [?] first studied the problem, which we state as follows:

Fix a positive integer n and choose another integer 1 ≤ a ≤ n. Set a_{0} := a and a_{j+1} := n mod a_{j} for j ≥ 0 and as long as a_{j} > 0. For example, for (n, a) = (35, 22), we get a_{0} = 22, a_{1} = 13, a_{2} = 9, a_{3} = 8, a_{4} = 3, a_{5} = 2, a_{6} = 1, a_{7} = 0. Now let us define P (n, a) to be the integer t such that a_{t} = 0. So, for example, P (35, 22) = 7. Finally, let us set

P (n) := max_{1≤a≤n} P (n, a).

The problem is to obtain upper and lower bounds for P (n) in terms of n. In particular, experiments suggest that the upper bound should be sublinear; however, this seems to be hard to prove. The best known bounds are due to Chase and Pandey [?], who slightly improved the bounds by Erdős and Shallit [?]: We have

\frac{log n}{log log n} ≪ P (n) ≪ n^{\frac{1}{3} − \frac{2}{177} +ε}  (13)

for sufficiently large n.

This problem is directly related to our sets S_{j}(n) via the following two simple lemmas.

Lemma 18. Let j ≥ 1 and n ≥ 1. Then r ∈ S_{j}(n) if and only if there exists an integer ⌊n/2⌋ + 1 ≤ a ≤ n such that in the above notation a_{j+1} = r.

Proof. This follows directly from the definitions. The index shift comes from the fact that we are assuming ⌊n/2⌋ + 1 ≤ a ≤ n and so a_{1} can be exactly every element from S_{0}(n).

Lemma 19. The following statements are equivalent:

1. P (n) = t;

2. S_{t+1}(n) = {0};

3. |S_{t+1}(n)| = 1 and |S_{t+1+j}(n)| = 0 for all j ≥ 1.

Proof. When computing P (n) = max_{1≤a≤n} P (n, a), we may restrict ourselves to ⌊n/2⌋ + 1 ≤ a ≤ n, since if a < ⌊n/2 + 1⌋, the starting value n − a gives P (n, n − a) = P (n, a) + 1.

Now the equivalences follow from Lemma 18 and the fact that S_{j}(n) = ∅ if and only if S_{j−1} = ∅ or S_{j−1} = {0}.

Remark 20. The known bounds (13) imply that for sufficiently large n, we have |S_{j}(n)| = 0 for all j ≥ n^{1/3}. On the other hand, there exists a constant c such that for all sufficiently large n we have |S_{j}(n)| ≥ 1 for j ≤ c log n/ log log n.

6 Bounds for iterated remainders

Recall that we defined

s_{j}(n) := |S_{j}(n)|.

In this section, we prove upper and lower bounds for s_{j}(n).

We start with a simple upper bound.

Lemma 21. For all j ≥ 0 and n ≥ 1 we have

s_{j}(n) − 1 ≤ max S_{j}(n) ≤ \frac{n}{j + 2}.

Proof. The first inequality is clear since min S_{j}(n) = 0. We show the second inequality by induction. For j = 0 this is clearly satisfied by definition. Now assume that max S_{j}(n) ≤ n/(j + 2) for some j ≥ 0. Then for every r ∈ S_{j+1}(n) there exists a k ∈ S_{j}(n) with k > r such that n = qk + r. By induction hypothesis we have k ≤ n/(j + 2); hence q ≥ j + 2. Now

r + 1 ≤ k = \frac{n − r}{q}

implies

r ≤ \frac{n − q}{q + 1} ≤ \frac{n}{j + 3},

as desired.

Remark 22. The arguments from [?] for the upper bound on P (n) in fact give stronger upper bounds when j is relatively large compared to n. For example, since max S_{j}(n) strictly decreases as j increases, one can show that max S_{j}(n) is roughly bounded by 2\sqrt{n} − j for j > \sqrt{n}. One can do even better (see [?, proof of Theorem 2]), using the fact that the number of divisors of m is O(m^{ε}). It turns out that for j > n^{1/3+ε} we get roughly the upper bound 2n^{2/3+ε} − j · n^{1/3}.

Finally, we prove a lower bound. In particular, we show that the sequence s_{j}(n) grows linearly (even if lim_{n→∞} s_{j}(n)/n might not exist).