Arithmetic Functions that Remain Constant on Runs of Consecutive Integers

Noah Lebowitz-Lockard and Joseph Vandehey Department of Mathematics University of Texas at Tyler Tyler, TX 75799 USA

                 nlebowitzlockard@uttyler.edu
                     jvandehey@uttyler.edu

Abstract We bound from above the length of the longest sequence of consecutive numbers less than or equal to x with the same number of divisors. We also bound the length of the longest sequence of consecutive numbers less than or equal to x for which the number of divisors is decreasing. Finally, we consider variants of this problem such as the corresponding sequences for the sum-of-proper-divisors function and the Carmichael function. In particular, we show that it is impossible for the sum-of-proper-divisors function to be equal on six consecutive integers.

1 Introduction

Let d(n) be the number of divisors of n. In 1952, Erdős and Mirsky [4] defined the function F (x) as the largest number k for which there exists some n ≤ x − k such that d(n + 1) = d(n + 2) = ⋯ = d(n + k). Unfortunately, they did not obtain any non-trivial bounds.

Over the years, multiple people have investigated whether d(n) = d(n + k) for infinitely many values of n for a given k. Spiro [18] proved this statement for k = 5040. Heath-Brown [11] then solved the k = 1 case. Finally, Pinner [15] showed that d(n) = d(n + k) has infinitely many solutions for all k. (For further discussion of this problem, see Guy [9, §B18]. For bounds on the number of solutions to the equation d(n) = d(n + 1) with n ≤ x, see Erdős, Pomerance, and Sárközy [5] and Hildebrand [12].)

Schinzel’s hypothesis H implies that d(n + 1) = d(n + 2) = ⋯ = d(n + k) has infinitely many solutions for all k. However, there is no unconditional proof of this result. Last year, Letsko found a solution to this equation with k = 20, which implies that F (x) ≥ 20 for all sufficiently large x. (For examples of runs of integers with the same number of divisors, see \underline{A006558}.)

Spătaru [17] recently made the first substantial improvement on Erdős and Mirsky’s original question. (From here on, log_{k} is the kth iterate of the logarithm.)

Theorem 1. As x → ∞, we have

F (x) = exp(O(\sqrt[3]{log x log_{2} x})).

In this note, we derive an alternate proof of Theorem 1, which we independently obtained before Spătaru [17] appeared in print. Later on, we derive a substantially stronger conditional bound.

We also consider a related function. Let G(x) be the largest k for which the inequality d(n + 1) ≥ d(n + 2) ≥ ⋯ ≥ d(n + k) holds for some n ≤ x − k. (The bounds we obtain also hold for increasing, decreasing, and non-decreasing sequences.) We modify Spătaru’s proof to bound G(x) as well.

Theorem 2. We have

G(x) = exp(O(\sqrt{log x log_{2} x})).

We can generalize these functions. For a given arithmetic function f, let F_{f}(x) (resp., G_{f}(x)) be the largest k for which f(n+1), f(n+2), …, f(n+k) is constant (resp., decreasing). Note that F_{f}(x) ≤ G_{f}(x) for all f, x. Pollack, Pomerance, and Treviño [16] showed that F_{φ}(x) ∼ log_{3} x/ log_{6} x, where φ is the totient function. (For recent research on the equation φ(n) = φ(n + 1), see Bayless and Kinlaw [2] or Kinlaw, Kobayashi, and Pomerance [13]. Though Erdős [3] conjectured that φ(n + 1) = φ(n + 2) = ⋯ = φ(n + k) has infinitely many solutions for all k, the only known solution to φ(n + 1) = φ(n + 2) = φ(n + 3) is n = 5185 [14]. For the non-consecutive case, see Tao [19].)

Let ω(n) (resp., Ω(n)) be the number of distinct (resp., not necessarily distinct) prime factors of n. Erdős, Pomerance, and Sárközy [6, Thm. 5] proved that

F_{ω}(x) ≤ exp((1/\sqrt{2} + o(1))\sqrt{log x log_{2} x})

and

F_{Ω}(x) ≤ exp((\sqrt{log 2} + o(1))\sqrt{log x})

using a variation of the arguments that we use here. They also bounded the largest k for which there exists a number n ≤ x − k such that ω(n + 1), , …, ω(n + k) (resp., Ω(n + 1), …, Ω(n + k)) are all distinct.

Erdős [3] also conjectured that F_{σ}(x) → ∞ as x → ∞ as well, where σ is the sum-of-divisors function. A slight modification to Pollack et al.’s argument implies that F_{σ}(x) ≪ log_{3} x/ log_{6} x. Weingartner [21] proved that σ(n) = σ(n+k) has infinitely many solutions for all even k, conditional on Schinzel’s hypothesis H. He also showed that if k ≤ 10^{10^{7}} is even, then σ(n) = σ(n + k) has infinitely many solutions unconditionally. (For further discussion of the equation σ(n) = σ(n + 1), see Guy [9, §B13].) By modifying our proof of Theorem 1, we derive an alternate proof of the following result.

Theorem 3. We have

F_{σ}(x) = exp(O(\sqrt{log x log_{2} x})).

Let s be the sum-of-proper-divisors function. Surprisingly, we can prove a much stronger upper bound on F_{s}(x).

Theorem 4. For all x, we have F_{s}(x) ≤ 5. In other words, the equation s(n+1) = s(n+2) = ⋯ = s(n + 6) has no solutions.

Though we are unaware of any papers on the equation s(n) = s(n + 1), there is a MathOverflow post [8] on this problem. Frank asked whether n = 2 is the only solution to s(n) = s(n + 1). Poonen then responded that there are no other solutions up to 10^{16}. (Note that s(n) = s(n + 1) is equivalent to the statement σ(n) + σ(1) = σ(n + 1). Guy [9, §B15] discusses the more general equation σ(m) + σ(n) = σ(m + n).)

Finally, we prove the following upper bound for the Carmichael λ function. We define λ(n) as the smallest integer m such that a^{m} ≡ 1 (mod n) for all a coprime to n.

Theorem 5. We have F_{λ}(x) ≪ (log x log_{2} x)^{2}.

2 The divisor function

In this section, we prove our main result. From here on, we let v_{p}(m) be the order of p in m, i.e., the largest a for which p^{a}|m. For a given x, let k = F (x) and K = log k/ log 2. By assumption, there exists some n ≤ x − k such that d(n + 1) = d(n + 2) = ⋯ = d(n + k). Let D = d(n + i) for all i ≤ k. Spătaru [17] proved the following result.

Lemma 6. The number D is a multiple of every prime ≤ K.

Using the prime factorization of D, we can bound F (x) from above.

Proof of Theorem 1. Recall that we wish to show that as x → ∞, we have

F (x) = exp(O(\sqrt[3]{log x log_{2} x})).

We may assume that k > exp(C\sqrt[3]{log x log_{2} x}) for some positive constant C.

Fix ϵ < 1 − (log 2/ log 3) and let S be the set of primes in ((1 − ϵ)K, K]. Let q_{1}, q_{2}, and q_{3} be three distinct elements of S. For all i, we have q_{1}q_{2}q_{3}|d(n + i) by Lemma 6. Because d(p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}) = (a_{1} + 1) ⋯ (a_{r} + 1), there are three possibilities:

1. We have v_{p}(n + i) = aq_{1}q_{2}q_{3} − 1 for some prime p and positive a,

2. We have v_{p_{1}}(n + i) = a_{1}q_{1}q_{2} − 1 and v_{p_{2}}(n + i) = a_{2}q_{3} − 1 for some prime p_{1}, p_{2} and positive a_{1}, a_{2},

3. We have v_{p_{j}}(n + i) = a_{j}q_{j} − 1 for all j ≤ 3, where each p_{j} is prime and each a_{j} is positive.

Suppose n + i satisfies Condition (1) for some q_{1}, q_{2}, q_{3} ∈ S. Then, we can bound p from above. In this case, we have

x ≥ p^{aq_{1}q_{2}q_{3}−1}
≥ 2^{q_{1}q_{2}q_{3}−1}
≥ 2^{(1−ϵ)^{3}K^{3}−1}
≥ 2^{((1−ϵ)C/ log 2)^{3} log x log_{2} x−1}
≥ x^{(1+o(1))((1−ϵ)C)^{3}/(log 2)^{2} log_{2} x}.

However, this is impossible for x sufficiently large. Therefore, n + i does not satisfy (1) for q_{1}, q_{2}, q_{3} ∈ S.

Let r = #S. Fix i ≤ k. Because n + i does not satisfy (1), it is possible to partition S into two disjoint subsets S_{1} and S_{2} with the following properties. Let S_{1} = {q_{1}, q_{2}, …, q_{#S_{1}}} and S_{2} = {q_{#S_{1}+1}, …, q_{r}}. We may write

∏_{j=1}^{⌊#S_{1}/2⌋} p_{j}^{a_{j}q_{2j−1}q_{2j}−1} ∏_{j=#S_{1}+1}^{r} p_{j}^{a_{j}q_{j}−1}|n + i,

where each p_{j} is prime and each a_{j} is a positive integer. Note that each exponent is ≥ ⌊(1 − ϵ)K⌋ − 1 and that there are at least r/2 distinct prime factors in the product above. Hence, n + i ≥ (p_{i,1}p_{i,2} ⋯ p_{i,⌊r/2⌋})^{⌊(1−ϵ)K⌋−1} for some primes p_{i,1}, p_{i,2}, …, p_{i,⌊r/2⌋}.

From here on, we assume that n + i and n + j are both odd. We can show that p_{i,a} ≠ p_{j,b} for all a and b. For every odd prime p, we have

p^{⌊(1−ϵ)K⌋−1} ≥ 3^{(((1−ϵ)/ log 2) log k)−2} = (1/9)k^{(1−ϵ)(log 3)/ log 2}.

However, this quantity is greater than k when k is sufficiently large. So, p^{⌊(1−ϵ)K⌋−1} cannot divide both n + i and n + j for distinct i and j.

If we multiply all of these n + i together, we obtain a multiple of

( ∏_{\begin{matrix}i:n+i is odd \\ m≤r/2 \end{matrix}} p_{i,m})^{⌊(1−ϵ)K⌋−1}.

Let p_{m} be the mth prime and let

θ(x) = ∑_{p≤x} log p.

De la Vallée Poussin [20, p. 54] showed that |π(x)−Li(x)| and |θ(x)−x| are both O(x exp(−c\sqrt{log x})) for some positive constant c. Therefore,

x^{k} > (n + 1)(n + 2) ⋯ (n + k) ≥ (p_{1}p_{2} ⋯ p_{C_{1}rk})^{⌊(1−ϵ)K⌋−1} = exp ((C_{2} + o(1))rkK log(rk))

for some positive constants C_{1}, C_{2}. So, we have

rkK log(rk) ≪ log(x^{k}) = k log x,

which implies that

rK log(rk) ≪ log x.

Recall that K ≍ log k and r ≍ log k/ log log k. Therefore, we have

k = exp(O(\sqrt[3]{log x log log x})).

3 Decreasing sequences

Rather than considering sequences for which d(n + i) is constant, we can consider sequences for which it is increasing or decreasing. Pollack et al. found a precise asymptotic formula for the analogous problem for the totient function.

Theorem 7 ([16, Thm. 1.5]). The largest k for which there exists some n ≤ x − k such that φ(n + 1) ≥ φ(n + 2) ≥ ⋯ ≥ φ(n + k) is asymptotic to log_{3} x/ log_{6} x.

We modify their argument to obtain an upper bound for the divisor function. To do so, we make use of the following result of Spătaru.

Lemma 8 ([17, Lemma 4.2]). Let n be an integer with smallest prime factor p. Then,

\frac{log n}{log p} ≥ ∑_{q}(q − 1)v_{q}(d(n)).

Rather than using this lemma directly, we rewrite the righthand side using the following result.

Corollary 9. For all m, we have

∑_{q}(q − 1)v_{q}(m) ≥ \frac{log m}{log 2}.

Proof. By definition, m is the product of q^{v_{q}(m)} over all q. Therefore, we have

log m = ∑_{q}(log q)v_{q}(m),

which implies that

\frac{1}{log m} ∑_{q}(q − 1)v_{q}(m) = (∑_{q}(q − 1)v_{q}(m))(∑_{q}(log q)v_{q}(m))^{−1}.

Let

M = min_{q|m}(\frac{q − 1}{log q}).

Then, we have

∑_{q}(q − 1)v_{q}(m) ≥ ∑_{q} M(log q)v_{q}(m) = M ∑_{q}(log q)v_{q}(m),

giving us

\frac{1}{log m} ∑_{q}(q − 1)v_{q}(m) ≥ M ≥ \frac{1}{log 2}.

Recall that G(x) is the largest k for which there exists some n ≤ x − k such that d(n + 1) ≥ d(n + 2) ≥ ⋯ ≥ d(n + k).

Proof of Theorem 2. A classic theorem [10, Thm. 317] states that there exists some m ≤ k/2 such that

d(m) = 2^{(1+o(1)) log(k/2)/ log_{2}(k/2)} = 2^{(1+o(1)) log k/ log_{2} k}.

Let n + k = am + b with 0 < b < m. Note that k − b > k/2 because m ≤ k/2. Consider the subsequence n+1, n+2, …, n+(k−b). By assumption, m|n+(k−b). So d(m) ≤ d(n+k−b), which implies that d(m) ≤ d(n + i) for all i ≤ k − b. So,

d(n + i) ≥ exp((log 2 + o(1))\frac{log k}{log_{2} k} )

for all i ≤ k − b.

Spătaru [17, §4] also observed that in a sequence of k − b consecutive numbers, at least one of those numbers consists entirely of prime factors p satisfying log p ≫ log(k−b) ≫ log k. Select i ≤ k − b so that n + i satisfies this property. The previous lemma and corollary imply that

\frac{log x}{log k} ≥ \frac{log(n + i)}{log k} ≫ ∑_{q}(q − 1)v_{q}(d(n + i)) ≫ log d(n + i) ≫ \frac{log k}{log_{2} k} .

From this inequality, we obtain (log k)^{2}/ log_{2} k ≪ log x, giving us our desired bound.

The function G(x) has a much stronger conditional bound. Suppose the sequence n + 1, n + 2, …, n + k contains two primes n + i, n + j > 3. Then, d(n + i) = d(n + j) = 2, but d(n + k) > 2 for every k ∈ (i, j) with n + k composite. Therefore, G(x) is at most as large as the largest gap between two consecutive primes ≤ x. Cramér’s conjecture states that this gap is O((log x)^{2}). Assuming this conjecture, G(x) = O((log x)^{2}) as well. (Unfortunately, the best unconditional upper bound on the gap between two consecutive primes ≤ x is x^{0.525+o(1)} [1]. The best lower bound is ≫ log x log_{2} x log_{4} x/ log_{3} x [7].)

4 Sums of divisors

Let F_{σ}(x) be the largest k for which there exists some n ≤ x − k such that σ(n + 1) = σ(n + 2) = ⋯ = σ(n + k). By modifying the techniques of Section 2, we bound F_{σ}(x) from above. Let T = σ(n + 1) = ⋯ = σ(n + k). Once again, we let K = log k/ log 2.

Lemma 10. We have

T ≥ ∏_{p≤K}(2^{p} − 1).

Proof. Let p ≤ K. Because 2^{p} ≤ k, there exists some i ≤ k such that n + i ≡ 2^{p−1} (mod 2^{p}). For this particular i, we have σ(2^{p−1}) = 2^{p} − 1|σ(n + i). Therefore, 2^{p} − 1|T as well. In particular, 2^{p} − 1|T for all p ≤ K. However, if p and q are distinct primes, then 2^{p} − 1 and 2^{q} − 1 are relatively prime. Therefore, T is a multiple of

∏_{p≤K}(2^{p} − 1).

Proof of Theorem 3. By the previous lemma, there exists a constant C such that

T ≥ ∏_{p≤K} C^{p} = exp((log C) ∑_{p≤K} p) = exp((1 + o(1))\frac{log C}{2} \frac{K^{2}}{log K} ).

However, Mertens’ theorem implies that T = σ(n + i) ≪ x log log x. Hence,

\frac{K^{2}}{log K} ≪ log T ≪ log x,

which implies that

log k ≪ K ≪ \sqrt{log x log_{2} x}.

If we replace σ with the sum-of-proper-divisors function s(n), we get a completely different result. To prove this result, we use the following fact about σ.

Lemma 11. The quantity σ(n) is odd if and only if n = m^{2} or n = 2m^{2} for some m.

Proof. Suppose σ(n) is odd. By definition,

σ(n) = ∏_{p}(1 + p + p^{2} + ⋯ + p^{v_{p}(n)}).

] If p and v_{p}(n) are both odd, then 1 + p + p^{2} + ⋯ + p^{v_{p}(n)} is even because it is the sum of an even number of odd terms. Because σ(n) is odd, v_{p}(n) must be even for all odd p. So, n = m^{2} or 2m^{2}, depending on the parity of v_{2}(n).

We now prove the converse. If v_{p}(n) is even for all odd p, then

∏_{p>2}(1 + p + ⋯ + p^{v_{p}(n)})

is odd. In addition, 1+2+⋯+2^{v_{2}(n)} is always odd because every term except 1 is even.

Proof of Theorem 4. Suppose that s(n + 1) = s(n + 2) = ⋯ = s(n + 6) for some integer n. Let S = s(n + i) for all i ≤ 6. Suppose S is even. Choose i ≤ 2 so that n + i is odd. Because s(n + i) is even, we have that σ(n + i) is odd, which implies that n + i is a square. By a similar argument, the number n + i + 2 is also a square, which is impossible. Therefore, S is odd.

The sequence n + 1, n + 2, …, n + 6 contains three even numbers m, m + 2, and m + 4. Because s(m), s(m + 2), and s(m + 4) are odd, the numbers σ(m), σ(m + 2), and σ(m + 4) must all be odd as well. There are two possibilities. Either two elements of {m, m+2, m+4} are squares or two of them are double a square. However, the difference between two positive squares cannot be 2 or 4. If two elements of {m, m + 2, m + 4} have the form 2r^{2} for some r, then two elements of {m/2, (m/2) + 1, (m/2) + 2} are squares. But the difference between two positive squares cannot be 1 or 2, giving us a contradiction.

5 The Carmichael function

Let λ be the Carmichael function. Though λ is an arithmetic function, it is neither additive nor multiplicative. Instead, for a given number n = p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}, we have

λ(n) = lcm(λ(p_{1}^{a_{1}}), …, λ(p_{r}^{a_{r}})).

Let p^{a} be a prime power. Then,

λ(p^{a}) = \begin{cases}φ(p^{a})/2, & if p = 2 and a ≥ 3; \\ φ(p^{a}), & otherwise. \end{cases}

We prove an upper bound on F_{λ} in a matter analogous to our previous functions.

Proof of Theorem 5. Let L = λ(n + 1) = ⋯ = λ(n + k). We bound L from above. For each prime p, there exists an i ≤ k such that p^{⌊log k/ log p⌋}|n + i. For this i, we have

p^{⌊log k/ log p⌋−1}|λ(n + i) = L.

Hence, we have

L ≥ \frac{1}{2} ∏_{p≤\sqrt{k}} p^{⌊ \frac{log k}{log p} ⌋−1} ≫ ∏_{p≤\sqrt{k}} p^{\frac{log k}{log p} −2} = ∏_{p≤\sqrt{k}} \frac{k}{p^{2}} .

We now bound the numerator and denominator in our product. We have

∏_{p≤\sqrt{k}} k = k^{π(\sqrt{k})} = exp((log k)π(\sqrt{k})) = exp(2\sqrt{k} + (4 + o(1))\frac{\sqrt{k}}{log k} )

and

∏_{p≤\sqrt{k}} p^{2} = exp(2 ∑_{p≤\sqrt{k}} log p) ≤ exp(2\sqrt{k} + o(\frac{\sqrt{k}}{log k} )).

Therefore, we have

L ≥ exp((4 + o(1))\frac{\sqrt{k}}{log k} ).

However, we have L ≤ x because λ(n + i) ≤ n + i for all i. So, \sqrt{k}/ log k ≪ log x, which implies that k ≪ (log x log_{2} x)^{2}.

References

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

[2] J. Bayless and P. Kinlaw, Consecutive coincidences of Euler’s function, Int. J. Number Theory 12 (2016), 1011–1026.

[3] P. Erdős, Some remarks on Euler’s ϕ function and some related problems, Bull. Amer. Math. Soc. 51 (1945), 540–544.

[4] P. Erdős and L. Mirsky, The distribution of values of the divisor function d(n), Proc. Lond. Math. Soc. 1 (1952), 257–271.

[5] P. Erdős, C. Pomerance, and A. Sárközy, On locally repeated values of certain arithmetic functions, III, Proc. Amer. Math. Soc. 101 (1987), 1–7.

[6] P. Erdős, C. Pomerance, and A. Sárközy, On locally repeated values of certain arithmetic functions, IV, Ramanujan J. 1 (1997), 227–241.

[7] K. Ford, B. Green, S. Konyagin, J. Maynard, and T. Tao, Long gaps between primes, J. Amer. Math. Soc. 31 (2018), 65–105.

[8] A. Frank, Are there pairs of consecutive integers with the same sum of factors?,

https://mathoverflow.net/q/14459.

[9] R. K. Guy, Unsolved Problems in Number Theory, 2nd ed., Springer-Verlag, 1994.

[10] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008.

[11] D. R. Heath-Brown, The divisor function at consecutive integers, Mathematika 31 (1984), 141–149.

[12] A. Hildebrand, The divisor function at consecutive integers, Pacific J. Math. 129 (1987), 307–319.

[13] P. Kinlaw, M. Kobayashi, and C. Pomerance, On the equation φ(n) = φ(n + 1), Acta Arith. 196 (2020), 69–92.

[14] M. Lal and P. Gillard, On the equation ϕ(n) = ϕ(n + k), Math. Comp. 26 (1972), 579–583.

[15] C. G. Pinner, Repeated values of the divisor function, Q. J. Math. 48 (1997), 499–502.

[16] P. Pollack, C. Pomerance, and E. Treviño, Sets of monotonicity for Euler’s totient function, Ramanujan J. 30 (2013), 379–398.

[17] V.-T. Spătaru, Runs of consecutive integers having the same number of divisors, PUMP J. Undergrad. Res. 6 (2023), 96–101.

[18] C. A. Spiro, The Frequency with Which an Integral-Valued, Prime-Independent, Multiplicative or Additive Function of n Divides a Polynomial Function of n, University of Illinois at Urbana-Champaign, PhD Dissertation (1981).

[19] T. Tao, Monotone non-decreasing sequences of the Euler totient function, arxiv preprint arXiv:2309.02325 [math.NT], 2023. Available at https://arxiv.org/abs/2309.02325.

[20] C.-J. de la Vallée Poussin, Sur la fonction ζ(s) de Riemann et le nombre des nombre premiers inferieurs á une limite donnée, Mem. Couronnés de l’Acad. Roy. Sci. Bruxelles 59 (1899), 1–74.

[21] A. Weingartner, On the solutions of σ(n) = σ(n + k), J. Integer Sequences 14 (2011), Article 11.5.5.

2020 Mathematics Subject Classification: Primary 11A25, Secondary 11N64. Keywords: arithmetic function, divisor function, sum-of-proper-divisors function.

(Concerned with sequence \underline{A006558}.)

Received February 24 2023; revised versions received April 13 2023; September 12 2023. Published in Journal of Integer Sequences, October 3 2023.

Return to Journal of Integer Sequences home page.