Linear Recurrences of Order at Most Two in Small Divisors

A. Anas Chentouf Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 USA

                       chentouf@mit.edu

Abstract

Given a positive integer n, the small divisors of n are defined as the positive divisors that do not exceed \sqrt{n}. Iannucci previously classified all n for which the small divisors of n form an arithmetic progression. In this paper, we classify all n for which the small divisors of n form a linear recurrence of order at most two.

1 Introduction

As usual, we say that a nonzero integer m divides another integer n whenever the quotient \frac{n}{m} is itself an integer. When this occurs, we use the conventional notation m | n. Moreover, a nontrivial divisor of a natural number n is a divisor other than 1 and n (if such a divisor exists).

Consider a positive integer n, and let S_{n} be the set of small divisors of n, that is,

S_{n} := \{d : 1 ≤ d ≤ \sqrt{n} ∧ d | n\}.  (1)

Large divisors, associated with L_{n}, are defined with the inequality reversed. Iannucci’s work classified all n for which the ordered elements of S_{n} form an arithmetic progression. For brevity, we let s(n) = |S_{n}|. Moreover, for any tuple (u, v, a, b) ∈ ℤ^{4}, there is an integral linear recurrence of order at most two, (d_{i})_{i=1}^{∞}, given by

d_{i} = \begin{cases}u, & if i = 1; \\ v, & if i = 2; \\ ad_{i−1} + bd_{i−2}, & if i ≥ 3. \end{cases}  (2)

This recurrence is usually abbreviated as U(u, v, a, b). The choice of beginning the index at 1, rather than 0, is due to the context of working with divisors.

As usual, we let τ(n) denote the number of positive divisors of n, that is,

τ(n) = ∑_{d|n} 1.

Since there is a “coupling” between small and large divisors of n, linking d and \frac{n}{d}, we easily relate τ(n) to s(n) as follows:

τ(n) = \begin{cases}2s(n) − 1, & if n is a perfect square; \\ 2s(n), & otherwise. \end{cases}  (3)

In this paper, we classify all values of n ∈ ℕ such that the ordered elements of S_{n} form an integral linear recurrence (d_{i})_{i=1}^{s(n)} of order at most two. A number n that satisfies this property is called a recurrent number.

Example 1. Notice that 60 is a recurrent number since the elements of S_{60} = {1, 2, 3, 4, 5, 6} satisfy the recurrence d_{i} = 2d_{i−1}−d_{i−2}. On the other hand, a simple computation or computer search would show that the smallest non-recurrent number is 36, as S_{36} = {1, 2, 3, 4, 6} does not satisfy a linear recurrence of order at most two.

Since 1 is the smallest divisor of n, we have d_{1} = 1. To be able to easily determine whether S_{n} forms a linear recurrence, we impose the condition that s(n) ≥ 5, although we revisit the cases s(n) ≤ 4 at the end of the paper. Furthermore, since the smallest nontrivial divisor of any natural number is prime, we assign d_{2} = p throughout the paper. We also let U(1, p, a, b) be the linear recurrence which produces the divisors of some recurrent number n. Notice that simply knowing p, a, b allows us to determine all elements in S_{n} whenever n is recurrent.

\begin{matrix}d_{1} & 1 \\ d_{2} & p \\ d_{3} & ap + b \\ d_{4} & (a^{2} + b)p + ab \\ d_{5} & (a^{3} + 2ab)p + b(a^{2} + b) \end{matrix}  (4)

Table 1: First 5 values of (d_{i})_{i=1}^{s(n)} in terms of a, b, p.

1p p^{2} ; \begin{matrix}p^{3} \\ q \end{matrix} ; q \begin{matrix}p^{2} \\ pq \\ r \end{matrix}

Figure 1: The above tree represents the possible “configurations” of the first four divisors of a natural number n ≥ 1, where p < q < r are distinct primes. For example, this says that the first divisor must be 1, the second divisor must be some prime p, and the third divisor can either be p^{2} or a second prime q, etc … Our proof makes use of this “tree” approach in determining the divisors d_{i}.

2 Preliminary results

Proposition 2. Let a, b, n be positive integers such that a ≤ b. If ab | n, then a ∈ S_{n}.

Proof. Since ab | n, it follows that a is a divisor of n. Moreover, we get that ab ≤ n. However, a^{2} ≤ ab ≤ n, and hence a ≤ \sqrt{n}.

Theorem 3. Given a recurrent number n associated with U(1, p, a, b), at least one of the following statements is true:

1. gcd(a, b) = 1.

2. All nontrivial elements of S_{n} are divisible by p.

3. a = 0.

Proof. Suppose gcd(a, b) ≠ 1, so some prime divides both a and b.

If p | gcd(a, b), then we see that all nontrivial elements in S_{n} are divisible by p, so the second possibility holds. If p ∤ gcd (a, b), then we obtain that gcd (a, b)|ap + b = d_{3}, so gcd (a, b) is some prime q according to Figure 1, and d_{3} = q. Similarly, q | d_{4} and thus aq + bp = d_{4} must be pq. From ap + b = q and aq + bp = bp, we get a(p^{2} − q) = 0, hence a = 0.

Proposition 4. If all nontrivial elements of S_{n} are divisible by some prime p, then n = p^{k} or n = p^{k}q for some prime q > p^{k}.

Proof. We proceed by considering two cases.

Case I: If all nontrivial divisors of n are divisible by p, then n = p^{k} for some k ≥ 1.

Case II: Assume that n has a divisor d > \sqrt{n} that is not divisible by p.

If d is composite, then one of its prime divisors must be less than or equal to \sqrt{d} < \sqrt{n}, and must hence be divisible by p. This contradicts our assumption, and d must thus be some prime q.

We now prove uniqueness. If there exists another prime r in the interval (\sqrt{n}, n) that divides n, then qr must divide n but qr > \sqrt{n} · \sqrt{n} = n, another contradiction.

Hence, q is the sole divisor of n that is not divisible by p, and thus we have n = p^{k}q.

Proposition 5. In a recurrent number n, if S_{n} satisfies a recurrence U(1, p, 0, b) (i.e. , a = 0), then exactly one of the following possibilities holds, where p, q, r are primes and k ∈ ℕ:

1. n = p^{k}.

2. n = p^{k}q for p^{k} < q.

3. n = pq^{k} for p < q.

4. n = pq^{k}r for p < q < pq^{k} < r.

Proof. If a = 0, then S_{n} forms a bifurcated series with d_{i} = bd_{i−2}, but taking i = 3 requires that d_{3} = b must be either p^{2} or q (for a prime q > p). The former gives rise to S_{n} = {1, p, p^{2}, …, p^{k}}, while the latter implies that S_{n} = {1, p, q, pq, q^{2}, …, pq^{k}} or {1, p, q, pq, q^{2}, …, q^{k}}, depending on parity. Identical to the proof of Proposition 4, there is at most one prime divisor greater than \sqrt{n} that divides n, and hence the possibilities follow directly.

3 The case gcd(a, b) = 1

We now turn our attention to the major case where gcd(a, b) = 1. We also assume, henceforth, that n has at least two distinct small prime factors—otherwise we are simply in the second and third cases of Theorem 3. In particular, ab ≠ 0 since if one of the numbers is zero, then the other cannot have absolute value 1, as negative numbers do not appear in S_{n} and no number appears twice in the sequence of small divisors.

Lemma 6. For all small divisors d_{i} of a recurrent number we have gcd(b, d_{i}) = 1.

Proof. Suppose that q | gcd(b, d_{i}) for some prime q and some index i. Notice that this i ≠ 1. Similarly, if i = 2, then p | b and inductively, all small divisors are divisible by p which contradicts the assumption of having two distinct small prime factors.

Suppose i ≥ 3. Since d_{i} = ad_{i−1} + bd_{i−2}, we have q | ad_{i−1}. The coprimality of a and b implies that q | d_{i−1}. We can inductively show that smaller divisors, including d_{1} = 1, are divisible by q, which is absurd. Hence the coprimality follows.

Corollary 7. For all i such that d_{i}, d_{i+1} are small divisors of a recurrent number, we have gcd(d_{i}, d_{i+1}) = 1.

Proof. We proceed by induction. The base case clearly holds. For the inductive step, observe that

gcd (d_{i}, d_{i+1}) = gcd (d_{i}, ad_{i} + bd_{i−1}) = gcd (d_{i}, bd_{i−1}).

The inductive hypothesis implies that gcd (d_{i}, d_{i−1}) = 1, while Lemma 6 implies that gcd (d_{i}, b) = 1, and hence the coprimality follows.

As a direct consequence of this, we conclude that d_{3} cannot be p^{2} in a recurrent number, and hence d_{3} must be prime. Henceforth, we set d_{3} = q.

Lemma 8. All configurations of the first four nontrivial divisors (d_{2}, d_{3}, d_{4}, d_{5}) except possibly (p, q, p^{2}, r), (p, q, r, p^{2}), and (p, q, r, s), where p, q, r, s are distinct primes, are impossible in a recurrent number.

Proof. We have already determined d_{2}, d_{3}. Now, d_{4} can be p^{2}, q^{2}, pq, or r (where r is another prime). By Corollary 7, d_{4} cannot be pq or q^{2}. Hence, we have either d_{4} = p^{2} or d_{4} = r.

If d_{4} = p^{2}, then we can similarly see that the possibilities for the next divisor d_{5} are p^{3}, q^{2}, pq, r for a prime r. However, Corollary 7 once again implies that p^{3}, pq are impossible. If d_{5} = q^{2}, then since d_{5} = ap^{2} + bq we would get that q | ap^{2}, and so, q | a. Yet, since q = ap + b, q | a would imply that q | b and thus contradicts Lemma 6. Hence, d_{5} ought to be another prime, r.

If d_{4} = r, then we see that our possibilities for the next divisor d_{5} are p^{2}, pq, s, for a new prime s. A reasoning similar to above shows that q ∤ d_{5}, so the only possibilities left are those of d_{5} = p^{2} and d_{5} = s.

Lemma 9. The only pair (u, x) ∈ ℕ × ℕ_{≥2} that satisfies

−ux^{5} + (u + 3)x^{4} − \frac{2u + 3}{u}x^{3} + \frac{3u + 1}{u^{2}}x^{2} − \frac{2}{u^{2}} x + \frac{1}{u^{2}} ≥ x^{2} + 1

is (1, 2).

Proof. Define

P (x) := −ux^{5} + (u + 3)x^{4} − \frac{2u + 3}{u}x^{3} + \frac{3u + 1}{u^{2}}x^{2} − \frac{2}{u^{2}} x + \frac{1}{u^{2}} − (x^{2} + 1).

Notice that

P′(x) = −5ux^{4} + 4(u + 3)x^{3} − \frac{3(2u + 3)}{u}x^{2} + \frac{2(3u + 1)}{u^{2}}x − \frac{2}{u^{2}} − 2x

= −5ux^{4} + 4(u + 3)x^{3} − \frac{3(2u + 3)}{u}x^{2} + \frac{−2u^{2} + 6u + 2}{u^{2}}x − \frac{2}{u^{2}} .

For u ≥ 4 and x ≥ 2 we have

5ux^{4} ≥ 10ux^{3} ≥ 4(u + 3)x^{3},

and in addition, we have −\frac{3(2u+3)}{u}x^{2}, \frac{−2u^{2}+6u+2}{u^{2}}x, −\frac{2}{u^{2}} are each negative. Notice that P′(x) is negative. Hence, for u ≥ 4, the function P (x) is strictly decreasing in the interval [2, ∞). Moreover, it is easy to check that P (2) < 0. Hence, it suffices to simply consider u ∈ {1, 2, 3}. One may easily check that the only possible value is u = 1. Another simple computation reveals that the inequality only holds for x = 2.

Theorem 10. The only recurrent number with configuration (d_{2}, d_{3}, d_{4}, d_{5}) = (p, q, p^{2}, r) is 60.

Proof. In this case, we have

p^{2} = d_{4} = aq + bp = a(ap + b) + bp.  (5)

Since p | ab and p ∤ b by Lemma 6, we have p | a. Let a = kp for some integer k. We can rewrite (5) as

k^{2}p^{2} + b(k + 1) = p,

which is equivalent to

b = \frac{p(1 − k^{2}p)}{k + 1}.

However, since we know that p ∤ b, we obtain that p | k + 1. In other words, there exists a positive integer u such that k + 1 = up. From here, we are able to express a, b in terms of u, p, and use that to obtain r in terms of u, p only. We end up obtaining

a = up^{2} − p,

b = \frac{1 − p}{u} − up^{3} + 2p^{2},

and

r = ap^{2} + bq = −up^{5} + (u + 3)p^{4} − \frac{2u + 3}{u}p^{3} + \frac{3u + 1}{u^{2}}p^{2} − \frac{2}{u^{2}} p + \frac{1}{u^{2}} .

Since r = d_{5} ≥ d_{4} + 1 = p^{2} + 1, Lemma 9 gives that (u, p) = (1, 2) and substituting reveals a = 2, b = −1. Hence the first five divisors would be 1, 2, 3, 4, 5. This reduces to the case of an arithmetic sequence with common difference 1, which, using the results of Iannucci [1, Lemma 2], implies that s(n) = 5 or s(n) = 6. If s(n) = 5, we have n ≥ lcm(1, 2, 3, 4, 5) = 60, but 6 is a small divisor that does not appear in S_{n}, a contradiction. When s(n) = 6, we see that n is a multiple of 60. However, if n ≥ 180 then 12 ≤ \sqrt{n} does not appear in the list of small divisors, contradicting the recurrency. Clearly, n = 120 is not recurrent neither as 8 ∉ {1, 2, 3, 4, 5, 6}. Hence, the only solution is S_{n} = {1, 2, 3, 4, 5, 6} for when n = 60, which is indeed recurrent.

Corollary 11. For an initial configuration (p, q, r, p^{2}) in a recurrent number, we have that p | d_{j} if and only if j ≡ 2 (mod 3).

Proof. Firstly, the statement holds for d_{2} = p. Since p^{2} = d_{5} = (a^{3} + 2ab)p + b(a^{2} + b), Lemma 6 implies that p | (a^{2} + b). Hence,

d_{i+3} = ad_{i+2} + bd_{i+1} = a(ad_{i+1} + bd_{i}) + bd_{i+1} = (a^{2} + b)d_{i+1} + abd_{i}.

Lemma 6 once again gives us that p | d_{i+3} if and only if p | d_{i}, which is the inductive step.

Theorem 12. The configuration of divisors (p, q, r, p^{2}) cannot occur in a recurrent number.

Proof. Assume otherwise, that is, there exists a recurrent number n of this configuration. We prove, by induction, that s(n) ≥ 3i + 2 for all i ∈ ℕ, which is absurd.

The base case is already assumed. Assume that s(n) ≥ 3i + 2 for some i ∈ ℕ. By Corollary 11, p ∤ d_{3i}d_{3i+1} and since gcd(d_{3i}, d_{3i+1}) = 1 by Corollary 7, we have p^{2}d_{3i}d_{3i+1} divides n. By Proposition 2, pd_{3i} is a small divisor. We consider two cases.

Case I: pd_{3i} = d_{3i+2}. Hence, we obtain that d_{3i} | ad_{3i+1}, and by Corollary 7, we obtain that d_{3i} | a. Observe that the sequence (d_{i} mod a) takes values congruent to 1, p, b, bp, b^{2}, …, and thus, d_{3i} divides an element of the form b^{k}p where k ∈ ℕ. However, Corollary 11 and Lemma 6 yield

gcd(p, d_{3i+1}) = 1 = gcd(b, d_{3i+1}),

which is a contradiction.

Case II: pd_{3i} > d_{3i+2}, hence, pd_{3i} ≥ d_{3i+5} by Corollary 11. Therefore, s(n) ≥ 3i + 5, and the induction is complete.

Lemma 13. In a recurrent number of configuration (p, q, r, s), the small divisors d_{i}, d_{i+2} are coprime.

Proof. Assume a prime t divides gcd (d_{i}, d_{i+2}). Thus t | ad_{i+1}. Clearly, t ∤ d_{i+1} by Lemma 7, and therefore, t | a. As such, the sequence (d_{i} mod t) takes values congruent to 1, p, b, bp, b^{2}, … and hence t | b^{k}p for some k ≥ 0. Yet Lemma 6 implies that gcd (b, t) = 1, hence t | p and so t = p. However, this would imply that t | r = (a^{2} + b)p + ab, which is a contradiction as p < r are distinct primes.

Theorem 14. The configuration of divisors (p, q, r, s) cannot occur in a recurrent number.

Proof. Assume that the configuration does occur in some recurrent number n. Since pq < pr are both small by Proposition (2), there exist at least three small divisors that are multiples of p. Let d_{j} = pv be the greatest small divisor that is divisible by p. In particular, v > p. By Lemma 13, p ∤ d_{j−2}d_{j−1}, and we conclude that d_{j−2}d_{j−1}pv | n, so Proposition 2 implies that pd_{j−2} ∈ S_{n}. Moreover, pd_{j−2} ≠ d_{j} by Lemma 13, and so pd_{j−2} > d_{j} is a small divisor greater than d_{j}, a contradiction.

4 Concluding remarks

In conclusion, imposing the condition s(n) ≥ 5 returns certain infinite families of recurrent integers n with at most 3 distinct prime divisors, in addition to the sole “sporadic” case of 60. We now revisit the condition we imposed and relax it to find all recurrent numbers by relating s(n) to τ(n) using Equation (3).

(i) s(n) = 1. Hence, τ(n) ∈ {1, 2}. That is, n = 1 or n = p for some prime p, and in both cases, n is vacuously recurrent.

(ii) s(n) = 2. Thus, τ(n) ∈ {3, 4}, and we have the possibilities that n = p^{2}, p^{3}, or pq for primes p < q. In all cases, n is vacuously recurrent.

(iii) s(n) = 3. This implies τ(n) ∈ {5, 6}, and hence the possibilities are n = p^{4}, n = p^{5}, n = p^{2}q, or n = pq^{2} for primes p < q. These are again vacuously recurrent.

(iv) s(n) = 4. Consequently, τ(n) ∈ {7, 8}.

(I) If τ(n) = 7, we get that n = p^{6} and S_{n} = {1, p, p^{2}, p^{3}} indeed forms a linear recurrence of order at most two.

(II) If τ(n) = 8, the possibilities are p^{7}, p^{3}q, pq^{3}, and pqr for primes p < q < r.

i. n = p^{7}: Here n is recurrent by the aforementioned geometric recurrences. ii. n = p^{3}q: Here Lemma 7 implies that the only possibility is S_{n} = {1, p, q, p^{2}}. Setting up a linear system of equations to solve for a, b, we deduce that it is both necessary and sufficient for \frac{q−p}{p^{2}−q} to be an integer for primes p < q < p^{2}. Based on numerical evidence, we conjecture that this occurs for infinitely many pairs of primes (p, q), but we defer analyzing this conjecture to another time.

iii. n = pq^{3} : Clearly, we have S_{n} = {1, p, q, pq}, but this is not possible by

Lemma 7. iv. n = pqr : If pq < r, then S_{n} = {1, p, q, pq} and the same argument above holds. If pq > r, then S_{n} = {1, p, q, r}. Setting up a linear system of equations, we see that it is both necessary and sufficient for \frac{pq−r}{p^{2}−q} to be an integer.

We summarize our findings in the following result.

Theorem 15. All recurrent numbers n fall into one of the following categories.

1. n = p^{k}, for some prime p and a natural number k, hence S_{n} = \{1, p, …, p^{⌊ \frac{k}{2} ⌋}\}.

2. n = p^{k}q, for some primes p, q and a natural number k, such that q > p^{k}. Hence, S_{n} = {1, p, …, p^{k}}.

3. n = pq^{k}, for some primes p < q and k an odd (resp. , even) natural number with S_{n} = \{1, p, q, pq, q^{2}, …, pq^{\frac{k−1}{2}} \} (resp. , S_{n} = \{1, p, q, pq, q^{2}, …, q^{\frac{k}{2}} \}).

4. n = pq^{k}r, for some primes p, q, r and a natural number k such that p < q and r > pq^{k}. Hence, S_{n} = {1, p, q, pq, …, pq^{k}}.

5. n = 60, with S_{n} = {1, 2, 3, 4, 5, 6}.

6. n = p^{3}q for some primes p, q such that p < q < p^{2} and p^{2} − q | q − p. Hence, S_{n} = {1, p, q, p^{2}}.

7. n = pqr, for some primes p, q, r such that p < q < r and p^{2} − q | pq − r. Hence, S_{n} = {1, p, q, r}.

Notice that S_{n} may contain an arbitrarily long subset of divisors that form a second-order linear recurrence, without all of S_{n} forming such a recurrence. Consider numbers of the form pq^{k}r^{2} where p < q < r are primes and k ∈ ℕ such that pq^{k} < r. If r is large enough, we see that the divisors 1, p, q, pq, q^{2}, … may form an arbitrarily long linear recurrence that is interrupted by r, but n is not itself recurrent.

Finally, we briefly study the analytic distribution of recurrent numbers. Define f(x) to be the number of recurrent integers in the interval [1, x]. The fact that recurrent numbers have at most 3 distinct prime divisors implies that they have null density among the natural numbers. For k ∈ ℕ, let π_{k}(x) be the number of integers in [1, x] having exactly k distinct prime factors. Hardy and Ramanujan [2, Lemma A, p. 265] showed that there exist constants A, B such that

π_{k}(x) < \frac{Ax(log log x + B)^{k−1}}{(k − 1)! log x} .

In fact, Landau [3] proved that that

π_{k}(x) ∼ \frac{x(log log x)^{k−1}}{(k − 1)! log x} .

Since f(x) ≤ π_{1}(x) + π_{2}(x) + π_{3}(x), we obtain that there exists some constant C such that for all x ≥ 1,

f(x) ≤ C(\frac{x}{log x} + \frac{x log log x}{log x} + \frac{x(log log x)^{2}}{2 log x} ).

Chu previously extended the results of Iannucci by classifying all natural numbers whose large divisors [4] or nontrivial, small divisors [5] form an arithmetic progression. Based on our results, the interested reader may naturally ask whether the aforementioned results can be generalized from the case of arithmetic progressions to that of linear recurrences of order at most two.

5 Acknowledgment

I would like to thank Professor Haynes Miller for his feedback and support, and Murilo Corato Zanarella for guidance in dealing with the analytic distributions. I would also like to thank Abdeljalil Hezouat for his comments, and the anonymous referee for their helpful suggestions.

References

[1] D. E. Iannucci, When the small divisors of a natural number are in arithmetic progression, Integers 18 (2018), Paper #A77.

[2] S. Ramanujan, Collected Papers of Srinivasa Ramanujan, American Mathematical Soc., 2000.

[3] E. Landau, Handbuch der Lehre von der Vorteilung der Primzahlen, B. G. Teubner, 1909.

[4] H. V. Chu, When the large divisors of a natural number are in arithmetic progression, J. Integer Sequences 23 (2020), Article 20.6.1.

[5] H. V. Chu, When the nontrivial, small divisors of a natural number are in arithmetic progression, preprint, 2020. Available at http://arxiv.org/abs/2001.08634.

2020 Mathematics Subject Classification: Primary 11B37. Keywords: divisor, linear recurrence.

(Concerned with sequence \underline{A346447}.)

Received August 17 2021; revised versions received August 18 2021; October 31 2021; December 31 2021. Published in Journal of Integer Sequences, January 2 2022.

Return to Journal of Integer Sequences home page.