Consecutive Integers Divisible by a Power of their Largest Prime Factor

Jean-Marie De Koninck Dép. de mathématiques et de statistique Université Laval Québec, G1V 0A6 Canada

                      jmdk@mat.ulaval.ca

Matthieu Moineau École des mines de Nancy Université de Lorraine 54042 Nancy Cedex France

               matthieu.moineau@mines-nancy.org

Abstract We construct families of consecutive polynomials with integer coefficients that allow for the discovery of consecutive integers divisible by a power of their largest prime factor.

1 Introduction

Let P (n) stand for the largest prime factor of an integer n ≥ 2 and set P (1) = 1. Given an arbitrary positive integer ℓ and k distinct primes p_{0}, p_{1}, …, p_{k−1}, the Chinese remainder theorem guarantees the existence of infinitely many integers n such that p_{i}^{ℓ} | n + i for i = 0, 1, …, k − 1. However, this theorem does not guarantee that such integers n will also have the property that P (n + i) = p_{i} for i = 0, 1, …, k − 1, although such is the case in some particular instances. For example when ℓ = 2, k = 3 and n = 1 294 298, we indeed have

1 294 298 = 2 · 61 · 103^{2},
1 294 299 = 3^{4} · 19 · 29^{2},
1 294 300 = 2^{2} · 5^{2} · 7 · 43^{2}.

In fact, one can show that the above number n is the smallest positive integer with that property. This motivates the following definitions. Given fixed integers k ≥ 2 and ℓ ≥ 2, set

E_{k,ℓ} := {n ∈ ℕ : P (n + i)^{ℓ} | n + i for each i = 0, 1, …, k − 1}
E_{k,ℓ}(x) := #{n ≤ x : n ∈ E_{k,ℓ}}.

Many elements of E_{2,2}, E_{2,3}, E_{2,4}, E_{2,5} and E_{3,2} are given in the 2009 book of the first author [2], whereas no elements of the sets E_{3,3}, E_{2,6} and E_{4,2} were known at that time. But, in 2014, Burcsi and Gévay (private communication), found the 77-digit number n_{0} which satisfies

n_{0} − 1 = 2^{7} · 53 · 4253 · 27631 · 27953 · 1546327 · 2535271
·17603683 · 1472289739 · 16476952799^{3},
n_{0} = 3^{6} · 19 · 37 · 787 · 711163 · 2181919 · 137861107
·318818473 · 937617607 · 7323090133^{3},
n_{0} + 1 = 2 · 12899 · 133451 · 421607 · 2198029 · 8046041
·19854409 · 555329197 · 32953905599^{3},

thereby establishing that n_{0} −1 ∈ E_{3,3}. Perhaps, this number is the smallest element of E_{3,3}, but this has not been shown.

Even though no elements of E_{k,ℓ} for k ≥ 4 and ℓ ≥ 2 are known, it seems reasonable to conjecture that, given any fixed integers k ≥ 2 and ℓ ≥ 2, the corresponding set E_{k,ℓ} is infinite.

The fact that #E_{k,ℓ} = ∞ is certainly true in the particular case k = ℓ = 2, as it is an immediate consequence of the fact that the Fermat-Pell equation a^{2} − 2b^{2} = 1 has infinitely many integer solutions (a, b), thereby also ensuring that E_{2,2}(x) ≫ log x. However, E_{2,2}(x) can be proved to be much larger. Indeed, De Koninck, Doyon, and Luca [3] focused their attention on the size of E_{2,2}(x) and proved that

x^{1/4}/ log x ≪ E_{2,2}(x) ≪ x exp\{−c\sqrt{2 log x log log x}\},

where c = 25/24 ≈ 1.042. Note that de la Bretèche and Drappeau [5] have recently showed that one can choose c = 4/\sqrt{5} ≈ 1.789, whereas, as we will see in Section 9, one can expect that the true order of E_{2,2}(x) is x exp\{−(1 + o(1))2\sqrt{2 log x log log x}\} as x → ∞.

At this point, we introduce additional notation. Given k integers ℓ_{0}, ℓ_{1}, …, ℓ_{k−1}, each ≥ 2, consider the set

F (ℓ_{0}, ℓ_{1}, …, ℓ_{k−1}) := {n ∈ ℕ : P (n + i)^{ℓ_{i}} | n + i for i = 0, 1, …, k − 1},

so that in particular E_{k,ℓ} = F (\underbrace{ℓ, …, ℓ}_{k}). Also, for each integer ℓ ≥ 2, we set G_{ℓ} := \{n ∈ ℕ :

P (n)^{ℓ} | n} and G_{ℓ}(x) := #{n ≤ x : n ∈ G_{ℓ}}.

Most likely, each set F (ℓ_{0}, ℓ_{1}, …, ℓ_{k−1}) is infinite, but besides the set F (2, 2), no such statement has been proved.

Here, we first show that if we assume that there exist infinitely many primes of the form 9k^{2} + 6k + 2 (respectively 4k^{2} + 2k + 1), then the set F (3, 2) (respectively F (4, 2)) is infinite. We then explore some identities involving consecutive polynomials whose algebraic structure provides the potential for revealing infinitely many members of E_{k,ℓ} for any given pair of integers k ≥ 2, ℓ ≥ 2 and of F (ℓ_{0}, ℓ_{1}, …, ℓ_{k−1}) for any given k-tuple of integers ℓ_{0} ≥ 2, ℓ_{1} ≥ 2, …, ℓ_{k−1} ≥ 2.

2 Preliminary results and conjectures

2.1 Friable numbers and the Dickman function

For 2 ≤ y ≤ x, the function Ψ(x, y) := #{n ≤ x : P (n) ≤ y}, which counts the number of “y-friable” or “y-smooth” numbers not exceeding x, has been studied extensively. In particular, it is known (see for instance Hildebrand and Tenenbaum [7]), that, given ε > 0 and setting u = log x/ log y,

Ψ(x, y) = xρ(u) (1 + O_{ε} (\frac{log(u + 1)}{log y}))

uniformly for x ≥ 3, exp\{(log log x)^{\frac{5}{3} +ε}\} ≤ y ≤ x, where ρ(u) stands for the Dickman function defined for 0 ≤ u ≤ 1 by ρ(u) = 1 and for u > 1 by the differential equation uρ′(u) = −ρ(u − 1). It can also be shown (see for instance Corollary 9.18 in the book of De Koninck and Luca [4]) that

ρ(u) = exp{−u(log u + log log u − 1 + o(1))} (u → ∞),

indicating that ρ(u) decreases very rapidly as u → ∞. In fact the following table provides the approximate values of ρ(u) for u = 1, 2, …, 7.

\begin{matrix}u & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ ρ(u) & 1.0 & 0.3068 & 0.0486 & 0.00491 & 0.000354 & 0.0000196 & 0.00000087 \end{matrix}

Table 1

Related to the above is the difficult problem of estimating the number of friable (or smooth) values of polynomials. To do so, given a polynomial f ∈ ℤ[x] with positive leading coefficient, we set

Ψ(f; x, y) := #{n ≤ x : P (f(n)) ≤ y}.

Now, given k irreducible polynomials f_{1}, …, f_{k} ∈ ℤ[x], consider the polyonimal f(t) := f_{1}(t) ⋯ f_{k}(t). Then, as stated by Martin [10], if we assume that the multiplicative properties of the various f_{i}(n) are independent of one another, we are led to the probabilistic prediction that

Ψ(f; x, y) ∼ x ∏_{i=1}^{k} ρ (\frac{log f_{i}(x)}{log y})  (x → ∞).  (1)

As we will later see in Section 9, this probabilistic relation will prove useful in estimating the expected size of the smallest elements of the various sets E_{k,ℓ}.

2.2 Estimates for the size of G_{ℓ}(x)

It was established by Ivić and Pomerance [9] that

G_{2}(x) = x exp\{−(1 + o(1))\sqrt{2 log x log log x}\} (x → ∞).  (2)

Observe that a more explicit expression for the right hand side of (2) was later obtained by Ivić [8]. Now, the technique used in [9] can be used to establish a more general result, namely that, for any fixed integer ℓ ≥ 2,

G_{ℓ}(x) = x exp\{−(1 + o(1))\sqrt{2(ℓ − 1) log x log log x}\} (x → ∞).  (3)

2.3 The Bunyakovsky conjecture

As we will see in the next section, there is an unexpected connection between the size of the sets F (3, 2) and F (4, 2) and a particular case of an old conjecture of Bunyakovsky [1], which essentially says that any irreducible polynomial with no fixed prime divisor contains infinitely many prime values.

Conjecture A (Bunyakovsky). Let f ∈ ℤ[x] be an irreducible polynomial of positive degree and with positive leading coefficient such that the greatest common divisor of f(1), f(2), f(3), … is 1. Then there exist infinitely many values of n for which f(n) is prime.

In trying to prove that F (4, 2) is infinite and as will be seen in Section 3, it would be helpful if we could say that there are infinitely many primes p such that P (p^{2} + 1) < p. However, no such claim has been proved, so far. Interestingly, although one can easily show that the sequence (n^{2} + 1)_{n≥1} is such that P (n^{2} + 1) < n for infinitely many integers n (simply consider the subsequence n = 2m^{2}, m = 1, 2, …, for which n^{2} + 1 = 4m^{4} + 1 = (2m^{2} +2m+1)(2m^{2} −2m+1), and observe that 5 | 2m^{2} +2m+1 provided m ≡ 1, 3 (mod 5), in which case P (2m^{2} + 2m + 1) < n, whereas P (2m^{2} − 2m + 1) < n for all m), it seems to be much more difficult to prove that P (p^{2} + 1) < p for infinitely many primes p. However, if Conjecture A is true, this will indeed be the case.

3 On the infinitude of the sets F (3, 2) and F (4, 2)

Using a computer one can check that the smallest four elements of F (3, 2) are 8, 6 859, 12 167 and 101 250, whereas the smallest four elements of F (4, 2) are 101 250, 11 859 210, 23 049 600 and 32 580 250. Further calculations seem to indicate that the two sets F (3, 2) and F (4, 2) are indeed infinite. However, no such claim has yet been proved. Nevertheless, we can prove the following.

Theorem 1. Assuming that Conjecture A is true, then each of the sets F (3, 2) and F (4, 2) is infinite.

Proof. First consider the identity

(2m^{3} + 1)^{2} − 1 = 4m^{3}(m + 1)(m^{2} − m + 1) (m = 1, 2, …).  (4)

It is clear that if m = p, a prime, and if the largest prime factor of p^{2} − p + 1 is less than p, then it follows from (4) that n = 4p^{3}(p^{3} + 1) ∈ F (3, 2). Now, assuming Conjecture A, there exist infinitely many positive integers k such that 9k^{2} + 6k + 2 is prime. For each such k, write p = 9k^{2} + 6k + 2, in which case p − 1 = (3k + 1)^{2}. Since p ≡ 2 (mod 3), we have that p + (3k + 1) ≡ 0 (mod 3). We may thus write

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

Clearly p − (3k + 1) < p. On the other hand,

\frac{p + (3k + 1)}{3} = \frac{1}{3}(p + \sqrt{p − 1}) < p,

thereby implying that P (p^{2} − p + 1) < p, thus completing the proof of the first assertion of the theorem.

Using a similar argument, one can show that F (4, 2) is infinite. Indeed, first observe that for every prime p,

(2p^{4} − 1)^{2} − 1 = 4p^{4}(p + 1)(p − 1)(p^{2} + 1).  (5)

Assuming Conjecture A, there exist infinitely many integers k such that 4k^{2}+2k+1 is prime. For each such k, write

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

in which case we have p^{2} + 1 = 2(4k^{2} + 1)(2k^{2} + 2k + 1). Now clearly, 4k^{2} + 1 < p and 2k^{2} + 2k + 1 < p, implying that P (p^{2} + 1) < p for each prime p ≥ 3, thereby implying that if we set n = (2p^{4} − 1)^{2} − 1 as p runs through the primes of the form (6), it follows that P (n)^{4} | n and P (n + 1)^{2} | n, and therefore that n ∈ F (4, 2) for infinitely integers n, thereby establishing the second assertion of the theorem.

4 Searching for elements of E_{3,2}

In order to generate elements of E_{3,2}, one can use a computer to find all the members of that set say with fifteen digits or less, thus obtaining the 60 numbers

1 294 298, 9 841 094, 158 385 500, 1 947 793 550, 5 833 093 013, 11 587 121 710, 20 944 167 840, 22 979 821 310, 24 604 784 814, 267 631 935 500, 290 672 026 412, 956 544 588 350, 987 988 937 343, 2 399 283 556 900, 2 816 075 601 855, 4 174 608 151 758, 4 322 550 249 043, 6 789 218 799 999, 10 617 595 679 778, 16 036 630 184 409, 22 869 997 335 620, 23 153 476 981 634, 23 480 833 955 320, 23 614 828 289 298, 24 126 198 551 098, 24 694 738 692 960, 31 456 704 045 166, 51 739 297 269 174, 52 898 121 606 525, 58 983 108 265 025, 71 709 481 909 254, 85 685 045 024 449, 113 707 706 201 375, 121 263 390 681 828, 122 169 948 877 430, 131 369 477 978 033, 133 959 037 005 774, 173 673 369 470 573, 176 664 623 046 273, 182 814 446 304 023, 209 744 971 905 458, 233 128 603 089 248, 237 464 160 321 408, 255 379 708 116 026, 280 778 107 745 620, 295 087 727 328 448, 313 232 585 684 886, 329 032 104 424 099, 360 853 931 895 982, 366 044 187 876 124, 467 683 999 401 022, 472 490 089 634 815, 480 138 936 005 168, 508 162 109 136 976, 593 047 972 159 008, 628 665 479 832 194, 638 506 456 514 625, 660 115 890 581 849, 906 165 826 118 135, 931 393 753 411 195.

The above list can be generated in a few hours using a powerful computer. However, in order to generate say thousands of members of E_{3,2}, one needs another approach. One efficient way is to identify polynomials f(x), g(x) and h(x) with squared factors and such that g(x) = f(x) + 1 and h(x) = f(x) + 2, with the hope that adequate choices of x will reveal members of E_{3,2}. Our first choice for such consecutive polynomials is given by

f(x) = x^{2}(2x^{3} + 5x^{2} − 5),
g(x) = f(x) + 1 = (x^{2} + x − 1)^{2}(2x + 1),  (7)
h(x) = f(x) + 2 = (x + 1)^{2}(2x^{3} + x^{2} − 4x + 2).

Setting x = 3802 reveals the three consecutive 19-digit integers

1 589 922 788 612 140 124 = 2^{2} · 59 · 61 · 71 · 239 · 1801 · 1901^{2},
1 589 922 788 612 140 125 = 3^{2} · 5^{3} · 11^{2} · 13^{2} · 151^{2} · 1741^{2},
1 589 922 788 612 140 126 = 2 · 103 · 701 · 809 · 941 · 3803^{2}.

As x runs through positive integers up to 2 000 000, we thus find a total of 33 members of E_{3,2}; much work for little outcome. Other approaches can be more fruitful. Indeed, first consider the system

f(x) = (2x^{2} + 1)^{2}(x − 1)(x + 1),
g(x) = f(x) + 1 = x^{2}(4x^{4} − 3),  (8)
h(x) = f(x) + 2 = (2x^{2} − 1)^{2}(x^{2} + 1).

With x = 5087, we find the somewhat larger 23-digit numbers

69 315 509 064 481 032 011 329 = 2^{6} · 3^{7} · 53 · 53 · 2543 · 1916857^{2},
69 315 509 064 481 032 011 330 = 11 · 71 · 769 · 1163 · 1321 · 2903 · 5087^{2},
69 315 509 064 481 032 011 331 = 2 · 5 · 7^{2} · 17 · 29^{2} · 167^{2} · 181 · 44273^{2}.

However, letting x run up to 2 000 000 reveals 252 elements of E_{3,2}, a score better than the one obtained through system (7). Many more elements of E_{3,2} can be obtained with a small modification to system (8). Indeed, in (8), replacing x^{2} by x, we find the new system

g(x) − 1 = (2x + 1)^{2}(x − 1),
g(x) = x(4x^{2} − 3),  (9)
g(x) + 1 = (2x − 1)^{2}(x + 1).

Although at first sight, system (9) appears to be useless in the quest to find elements of E_{3,2}, observe that since mP (m) ∈ G_{2} for each integer m ≥ 2, if we substitute x = mP (m) in system (9) and let m run up to 2 000 000, we find 261 elements of E_{3,2} and running m up to 30 000 000, we find 4 473 elements of E_{3,2}. One reason for the numerous elements of E_{3,2} found using system (9) is that the polynomials involved are of degree 3 while those in systems (7) and (8) are of degree 5 and 6 respectively. Remark 2. It has recently come to the attention of the authors that in 1986 Hildebrand [6] also came up with system (9) but for a different purpose and in a different context.

5 Searching for elements of F (2, ℓ, 2)

Consider the consecutive polynomials

g(x) − 1 = 2(x + 1)^{2}(24x^{3} + 12x^{2} + 2x − 1),
g(x) = (2x + 1)^{3}(6x^{2} + 6x − 1),  (10)
g(x) + 1 = 2x^{2}(24x^{3} + 60x^{2} + 50x + 15).

This set up is of particular interest because it allows for a rapid search for elements in F (2, 3, 2). For instance, using a computer and letting x run through the primes p, we find that the prime p = 6 158 923 yields the 36-digit number n_{1} which is such that

n_{1} − 1 = 2^{5} · 139 · 331 · 1627 · 3457 · 73019 · 296729 · 1539731^{2},
n_{1} = 3^{3} · 11 · 137 · 40433 · 3735181 · 4105949^{3},
n_{1} + 1 = 2 · 17 · 23 · 463 · 107251 · 433259 · 666529 · 6158923^{2}.

Many other elements of F (2, 3, 2) can also be obtained from the polynomials in (10).

A smaller element of F (2, 3, 2) can be obtained by considering another configuration of the same kind but with greater symmetry, namely

g(x) − 1 = (2x + 1)^{2}(12x^{3} − 12x^{2} + 4x − 1),
g(x) = 4x^{3}(12x^{2} − 5),  (11)
g(x) + 1 = (2x − 1)^{2}(12x^{3} + 12x^{2} + 4x + 1).

This scenario allows us to find the 34-digit number n_{2} ∈ F (2, 3, 2) which is such that

n_{2} − 1 = 3^{3} · 17 · 113 · 239 · 12829 · 13679 · 321109 · 1242121^{2},
n_{2} = 2^{2} · 24121 · 32203 · 53629 · 1863181^{3},
n_{2} + 1 = 7211 · 17977 · 689237 · 868691 · 3726361^{2}.

Remark 3. The fact that the numbers n_{1} and n_{2} are large is in part due to the fact that they each are solutions of a system of polynomials with a very specific algebraic structure. Therefore, one will not be surprised to learn that smaller elements of F (2, 3, 2) do exist. For instance, a judicious computer search reveals that the much smaller 16 and 20 digit numbers 3 858 290 162 662 516 and 67 500 618 671 796 179 920 are both elements of F (2, 3, 2).

The three polynomials given in (11) can also be put to good use to find an element of F (2, 6, 2). Indeed by considering positive integers r of the form r = mP (m), that is members of G_{2}, we automatically get that r^{3} ∈ G_{6}, implying that if 2r −1 =: p and (2r +1)/3 =: q are both primes and if the three conditions P (12r^{3}−12r^{2}+4r−1) < q, P (12r^{3}+12r^{2}+4r+1) < p and P (12r^{2} − 5) < P (m) are simultaneously satisfied, then we are guaranteed that the number 4r^{3}(12r^{2} − 5) − 1 belongs to F (2, 6, 2). In fact by choosing m = 79 311 205, that is r = 5 · 17 · 933 073^{2} and thus substituting the value x = 74 003 143 982 965 in (11), we find the 72-digit integer n which satisfies

n = 3^{4} · 3171439637 · 5982121049 · 91023709109 · 312912616603 · 49335429321977^{2},
n + 1 = 2^{2} · 5^{4} · 7^{2} · 17^{3} · 43 · 223 · 599 · 3607 · 66977 · 227089 · 851231 · 933073^{6},
n + 2 = 121327 · 13747920817 · 49470595193983 · 58937287195613 · 148006287965929^{2}.

Of course, this also reveals a number in F (2, 5, 2) and in F (2, 4, 2). However, for the same reason as the one mentioned in Remark 3, smaller elements of F (2, 5, 2) and F (2, 4, 2) most certainly exist.

6 Elements of E_{3,3}

In the hope of finding elements of E_{3,3} using consecutive polynomials, one might search for three consecutive polynomials f(x)−1, f(x), f(x)+1 which are respectively divisible by, say, (2x−1)^{3}, x^{3}, (2x+1)^{3}. If this is possible, then, since the original polynomials only differ by a constant, they must share the same derivative f′(x). But then, clearly, (2x−1)^{2}, x^{2}, (2x+1)^{2} are three factors of f′(x). This means that assuming that f(x) is of degree 7, then we must have that for some constant a ∈ ℕ,

f(x) = ∫ a · (2x − 1)^{2} · x^{2} · (2x + 1)^{2} dx = ∫ ax^{2}(4x^{2} − 1)^{2} dx.

It turns out that, by choosing a = 105, we find the three consecutive polynomials

f(x) − 1 = (2x − 1)^{3}(30x^{4} + 45x^{3} + 24x^{2} + 6x + 1),
f(x) = x^{3}(240x^{4} − 168x^{2} + 35),  (12)
f(x) + 1 = (2x + 1)^{3}(30x^{4} − 45x^{3} + 24x^{2} − 6x + 1),

which certainly have the potential of revealing several elements of E_{3,3}. In fact, setting x = 39 682 272 446 in (12), we find the 77-digit number n_{1} which is such that

n_{1} − 1 = 3^{3} · 137 · 251 · 49253 · 6892241 · 1400173417 · 1749071927 · 2602138829 · 26454848297^{3},
n_{1} = 2^{3} · 1162 · 31 · 3301 · 92639 · 376627 · 474994139 · 573384841 · 5057839271 · 19841136223^{3},
n_{1} + 1 = 13 · 23 · 41 · 61^{3} · 233 · 3767 · 9551 · 977719 · 5076637 · 367839041 · 396464197 · 1301058113^{3},

so that n_{1} − 1 ∈ E_{3,3}. Observe that although n_{1} is larger than the number n_{0} appearing in Section 1, it has the same number of digits. Similarly, setting x = 39 874 762 919 in (12), we find another 77-digit number belonging to E_{3,3}. Many more can be obtained with larger values of x.

7 The particular case E_{2,ℓ}

Given an integer ℓ ≥ 2, are there two consecutive polynomials that can help one find positive integers n such that P (n)^{ℓ} | n and P (n + 1)^{ℓ} | n + 1 ? The answer is “yes” and an explicit answer is given by the following result.

Theorem 4. Let ℓ ≥ 2 be a fixed integer. Then, there exist g_{1}(x), g_{2}(x) ∈ ℤ[x] each of degree ℓ − 1 such that

x^{ℓ} · g_{1}(x) + (−1)^{ℓ} = (x − 1)^{ℓ} · g_{2}(x).  (13)

Proof. First observe that, using repeated integration by parts one easily obtains that

∫_{0}^{1} t^{r}(t − 1)^{r} dt = (−1)^{r} \frac{r! · r!}{(2r + 1)!} = (−1)^{r} C  (r = 1, 2, …)  (14)

where C = \frac{r! · r!}{(2r + 1)!}.

In order to prove (13), we first consider the case ℓ even and set r = ℓ − 1. Computing the primitive of the function x^{r}(x − 1)^{r}, that is

g(x) := ∫_{0}^{x} \frac{1}{C} t^{r}(t − 1)^{r} dt,  (15)

we obtain, since r is odd,

g(x) = ∫_{0}^{x} \frac{1}{C} t^{r} (t^{r} − \binom{r}{1}t^{r−1} + \binom{r}{2}t^{r−2} − ⋯ + \binom{r}{r − 1}t − 1) dt
= ∫_{0}^{x} \frac{1}{C} (t^{2r} − \binom{r}{1}t^{2r−1} + \binom{r}{2}t^{2r−2} − ⋯ + \binom{r}{r − 1}t^{r+1} − t^{r}) dt
= \frac{1}{C} (\frac{x^{2r+1}}{2r + 1} − \binom{r}{1}\frac{x^{2r}}{2r} + \binom{r}{2}\frac{x^{2r−1}}{2r − 1} − ⋯ + \binom{r}{r − 1}\frac{x^{r+2}}{r + 2} − \frac{x^{r+1}}{r + 1})
= x^{r+1} \{\frac{1}{C} (\frac{x^{r}}{2r + 1} − \binom{r}{1}\frac{x^{r−1}}{2r} + \binom{r}{2}\frac{x^{r−2}}{2r − 1} − ⋯ + \binom{r}{r − 1}\frac{x}{r + 2} − \frac{1}{r + 1})\}
= x^{r+1}g_{1}(x),  (16)

which corresponds to the first term on the left hand side of (13). Setting

h(x) := g(x) + 1,  (17)

it follows from (16) and (14) that

h(1) = g(1) + 1 = ∫_{0}^{1} \frac{1}{C} t^{r}(t − 1)^{r} dt + 1 = \frac{1}{C} (−1)^{r} C + 1 = −1 + 1 = 0,

thereby implying that x − 1 is a factor of h(x). In order to complete the proof of (13), it is sufficient to prove that (x − 1)^{ℓ−1} = (x − 1)^{r} is a factor of the derivative of h(x). But recalling the definitions of g and h given by (15) and (17), it follows that

h′(x) = g′(x) = x^{r}(x − 1)^{r},

thereby implying that (x − 1)^{r} is indeed a factor of h′(x) as requested.

The case ℓ odd can be treated in a similar manner.

Since, as mentioned in Section 1, no elements of E_{2,6} have been previously discovered, let us illustrate the above method in the case ℓ = 6. Applying Theorem 4, we find the two consecutive polynomials

g(x) = x^{6}(252x^{5} − 1386x^{4} + 3080x^{3} − 3465x^{2} + 1980x − 462),
g(x) + 1 = (x − 1)^{6}(252x^{5} + 126x^{4} + 56x^{3} + 21x^{2} + 6x + 1).

Choosing x = 20 905 825 364, we obtain the 116-digit integer n which satisfies

n = 2^{13} · 5 · 83 · 22157 · 127139 · 12177577 · 17565259 · 372289003
1659308773 · 3257215037 · 5226456341^{6},
n + 1 = 569 · 32939 · 122489 · 146359 · 50300881 · 919974911
4166729363 · 15532846993 · 20905825363^{6}.

Choosing x = 86 459 129 774, we find another element of E_{2,6}, this time with 123 digits.

8 Consecutive polynomials generating elements of the sets E_{k,ℓ}

In the previous sections, we were successful in generating two or three consecutive integer coefficient polynomials each divisible by a power of some linear polynomial. We will now show that this can be done for an arbitrarily long sequence of consecutive polynomials each divisible by the ℓ-th power of some linear polynomial.

Theorem 5. Given fixed integers k ≥ 2 and ℓ ≥ 2, there exist k consecutive polynomials L_{i}(x) ∈ ℤ[x], i = 0, 1, …, k − 1, that is L_{i+1}(x) − L_{i}(x) = 1 for i = 0, 1, …, k − 2, such that each L_{i}(x) is divisible by the ℓ-th power of some linear polynomial.

Proof. We only give the proof in the case ℓ = 2 and arbitrary k ≥ 2, the general case being similar. Our proof is constructive. First, choose k − 1 linear polynomials c_{i}x + d_{i}, where c_{i}, d_{i} ∈ ℚ and c_{i} > 0 for i = 1, …, k − 1, in such a way that the k linear polynomials x, c_{1}x+d_{1}, …, c_{k−1}x+d_{k−1} are pairwise linearly independent over ℚ. We shall first construct k consecutive polynomials Q_{i}(x) with rational coefficients, namely

Q_{0}(x) = x^{2} ∑_{r=0}^{2k−1} a_{r}x^{r},  Q_{i}(x) = (c_{i}x + d_{i})^{2} ∑_{r=0}^{2k−1} b_{i,r}x^{r}  (i = 1, …, k − 1),  (18)

where each Q_{i}(x) ∈ ℚ[x] and Q_{i}(x) = Q_{0}(x) + i for i = 1, …, k − 1.

In order for the equation Q_{1}(x) = Q_{0}(x) + 1 to hold for all x, that is for the equation

(c_{1}x + d_{1})^{2}(b_{1,0} + b_{1,1}x + ⋯ + b_{1,2k−1}x^{2k−1}) = 1 + a_{0}x^{2} + a_{1}x^{3} + ⋯ + a_{2k−1}x^{2k+1} (19)

to hold, we need to equate the respective coefficients of x^{r}, r = 0, 1, …, 2k +1, on both sides of the above identity. Equating the coefficients of x^{0} and of x^{1}, we find

d_{1}^{2}b_{1,0} = 1  and  d_{1}^{2}b_{1,1} + 2c_{1}d_{1}b_{1,0} = 0,

which allows us to express the values of b_{1,0} and b_{1,1} in terms of c_{1} and d_{1}. Equating the coefficients of x^{2}, x^{3}, …, x^{2k+1} on both sides of (19), we find that

a_{0} = d_{1}^{2}b_{1,2} + 2c_{1}d_{1}b_{1,1} + c_{1}^{2}b_{1,0},
a_{1} = d_{1}^{2}b_{1,3} + 2c_{1}d_{1}b_{1,2} + c_{1}^{2}b_{1,1},
⋮
a_{2k−3} = d_{1}^{2}b_{1,2k−1} + 2c_{1}d_{1}b_{1,2k−2} + c_{1}^{2}b_{1,2k−3},
a_{2k−2} =  2c_{1}d_{1}b_{1,2k−1} + c_{1}^{2}b_{1,2k−2},
a_{2k−1} =  c_{1}^{2}b_{1,2k−1}.

We then move to equation Q_{2}(x) = Q_{0}(x) + 2 and again equate coefficients. Equating the coefficients of x^{0} and of x^{1}, we find

d_{2}^{2}b_{2,0} = 2  and  d_{2}^{2}b_{2,1} + 2c_{2}d_{2}b_{2,0} = 0,

which allows us to express b_{2,0} and b_{2,1} in terms of c_{2} and d_{2}. Equating the coefficients of x^{2}, x^{3}, …, x^{2k+1}, we find that

a_{0} = d_{2}^{2}b_{2,2} + 2c_{2}d_{2}b_{2,1} + c_{2}^{2}b_{2,0},
a_{1} = d_{2}^{2}b_{2,3} + 2c_{2}d_{2}b_{2,2} + c_{2}^{2}b_{2,1},
⋮
a_{2k−3} = d_{2}^{2}b_{1,2k−1} + 2c_{2}d_{2}b_{2,2k−2} + c_{2}^{2}b_{2,2k−3},
a_{2k−2} =  2c_{2}d_{2}b_{2,2k−1} + c_{2}^{2}b_{2,2k−2},
a_{2k−1} =  c_{2}^{2}b_{2,2k−1}.

Similarly, we construct k − 3 other systems each with 2k equations. Then, from these k − 1 systems, we see that

a_{0} = d_{1}^{2}b_{1,2}+2c_{1}d_{1}b_{1,1}+c_{1}^{2}b_{1,0} = d_{2}^{2}b_{2,2}+2c_{2}d_{2}b_{2,1}+c_{2}^{2}b_{2,0} = ⋯ = d_{2}^{2}b_{k−1,2}+2c_{2}d_{2}b_{k−1,1}+c_{2}^{2}b_{k−1,0}

and obtain analogous identities for a_{1}, a_{2}, …, a_{2k−1}. Hence, recalling that c_{1}, …, c_{k−1} and d_{1}, …, d_{k−1} are given, in all we obtain 2k(k − 2) equations involving a total of 2(k − 1)^{2} unknowns, namely b_{i,j} where 1 ≤ i ≤ k − 1 and 2 ≤ j ≤ 2k − 1. To summarize, we have constructed a system of 2k^{2} − 4k linear equations involving 2k^{2} − 4k + 2 unknowns. This means that if we fix any two of these unknowns, we will obtain a unique solution for the set of b_{i,j}’s.

Finally, having obtained the values of b_{i,j} for 1 ≤ i ≤ k − 1 and 2 ≤ j ≤ 2k − 1, we can use any of the k − 1 systems of equations to determine the unique values of a_{0}, a_{1}, …, a_{2k−1}.

Moreover, since all of the above equations are linear and involve rational coefficients, the coefficients a_{r} are also rational. Let us then write each a_{r} as

a_{r} = \frac{p_{r}}{q_{r}} where p_{r}, q_{r} ∈ ℤ, (p_{r}, q_{r}) = 1, q_{r} > 0 and set D := lcm[q_{1}, …, q_{r}]

and consider the polynomials

L_{i}(x) := Q_{i}(D x) (i = 0, …, k − 1).

We then have

L_{0}(x) = Q_{0}(Dx) = D^{2} x^{2} ∑_{r=0}^{2k−1} a_{r}D^{r} · x^{r} = D · x^{2} ∑_{r=0}^{2k−1} D · a_{r} · (Dx)^{r}.

By the nature of D, the coefficients of L_{0}(x)/x^{2} are therefore all integers. This implies that each of the polynomials L_{0}(x), …, L_{k−1}(x) has integer coefficients. Moreover, these polynomials are clearly consecutive. We have thus created an infinite family of consecutive polynomials each with a squared factor, as required.

Example. In the case (k, ℓ) = (4, 2), the above construction yields the four consecutive polynomials

L_{0}(x) = x^{2}(17220 + a − 5b + (815440 + 52a − 248b)x + (14339520 + 1108a − 4916b)x^{2}
+(120865536 + 12384a − 48624b)x^{3} + (494346240 + 76608a − 234432b)x^{4}

+(789626880 + 248832a − 324864b)x^{5} + (331776a + 1327104b)x^{6} + 3981312bx^{7})

and L_{1}(x), L_{2}(x) and L_{3}(x) whose squared factors are (6x + 1)^{2}, (8x + 1)^{2} and (12x + 1)^{2}, respectively. We have thus constructed infinitely many such quadruples with parameters a and b. Choosing a = b = 0 allows for the more simple quadruple

L_{0}(x) = x^{2}(17220 + 815440x + 14339520x^{2} + 120865536x^{3} + 494346240x^{4} + 789626880x^{5})
L_{1}(x) = L_{0}(x) + 1 = (1 + 6x)^{2}(1 − 12x + 17328x^{2} + 607936x^{3} + 6420480x^{4} + 21934080x^{5})
L_{2}(x) = L_{0}(x) + 2 = 2(1 + 8x)^{2}(1 − 16x + 8802x^{2} + 267912x^{3} + 2319840x^{4} + 6168960x^{5})
L_{3}(x) = L_{0}(x) + 3 = (1 + 12x)^{2}(3 − 72x + 18516x^{2} + 381424x^{3} + 2519040x^{4} + 5483520x^{5})

Using the method of proof of Theorem 5, the following result also holds.

Theorem 6. Given arbitrary integers ℓ_{i} ≥ 2, i = 0, 1, …, k − 1, there exist k consecutive polynomials L_{0}(x), L_{1}(x), …, L_{k−1}(x) ∈ ℤ[x] such that each L_{i}(x), i = 0, 1, …, k − 1, is divisible by the ℓ_{i}-th power of some linear polynomial.

Proof. We only provide a sketch of the proof. The idea is to let s := ℓ_{0} + ⋯ + ℓ_{k−1}, to set

Q_{0}(x) := x^{ℓ_{0}} ∑_{r=0}^{s−ℓ_{0}−1} a_{r}x^{r} and Q_{i}(x) := (c_{i}x + d_{i})^{ℓ_{i}} ∑_{r=0}^{s−ℓ_{i}−1} b_{i,r}x^{r} for i = 1, …, k − 1

and then to search for the coefficients a_{r} ∈ ℚ and b_{i,r} ∈ ℚ in the same manner as we did in the proof of Theorem 5. This allows us to obtain k consecutive polynomials Q_{0}(x), Q_{1}(x), …, Q_{k−1}(x) ∈ ℚ[x] with the property that Q_{0}(x) is divisible by x^{ℓ_{0}} whereas each Q_{i}(x), for i = 1, …, k − 1, is divisible by the ℓ_{i}-th power of a linear polynomial c_{i}x + d_{i} with c_{i}, d_{i} ∈ ℚ, c_{i} > 0. Using these k polynomials with rational coefficients, we proceed as in the proof of Theorem 5 and obtain k consecutive polynomials L_{0}(x), L_{1}(x), …, L_{k−1}(x) ∈ ℤ[x] with the same properties.

Remark 7. It follows from Theorems 5 and 6 that if Martin’s probabilistic prediction (1) is true, then each one of the sets E_{k,ℓ} and F (ℓ_{0}, ℓ_{1}, …, ℓ_{k−1}) is infinite.

9 Final remarks and heuristics

Let us now examine the expected size of the smallest elements of E_{k,ℓ}.

A consequence of estimate (3) is that the probability that a given large integer n is such that P (n)^{ℓ} divides n is approximately 1/e^{\sqrt{2(ℓ−1) log n log log n}}.

On the other hand, given an arbitrary integer k ≥ 2, it is reasonable to assume that P (n), P (n + 1), …, P (n + k − 1) are independent events and therefore to conclude that the probability that P (n + i)^{ℓ} | n + i for i = 0, 1, …, k − 1 is around 1/e^{k\sqrt{2(ℓ−1) log n log log n}}.

Using this approach, one can expect the smallest element of E_{3,3} to have around 82 digits (that is, roughly the size of the numbers n_{0} and n_{1} obtained in Sections 1 and 6, respectively) and that the smallest element of E_{4,2} to have around 71 digits.

On the other hand, in line with our algebraic approach, the following system (similar to the one displayed in Section 8, but with smaller coefficients for each of the four degree 5 polynomials) clearly has the potential of generating infinitely many elements of E_{4,2}:

f(x) = 4x^{2}(184896x^{5} + 292320x^{4} + 172500x^{3} + 46500x^{2} + 5501x + 195),
f(x) + 1 = (2x + 1)^{2}(184896x^{5} + 107424x^{4} + 18852x^{3} + 792x^{2} − 4x + 1),
f(x) + 2 = 2(4x + 1)^{2}(23112x^{5} + 24984x^{4} + 7626x^{3} + 438x^{2} − 8x + 1),
f(x) + 3 = (6x + 1)^{2}(20544x^{5} + 25632x^{4} + 10052x^{3} + 1104x^{2} − 36x + 3).

Unfortunately, in order to find a number n_{1} ∈ E_{4,2} using the above four polynomials, one would need much computer time since, in light of the conjectured estimate (1) and of Table 1, one can expect, as x runs through the positive integers, that the probability that each of the above degree 5 co-factors has its largest prime factor smaller than the largest prime factor of their respective squared factors is smaller than ρ(5) ≈ 0.000354, implying that the smallest integer x meeting these four requirements would be larger than 1/ρ(5)^{4} > 10^{14} and therefore that

n_{1} = f(x) > 4 · x^{2} · 184896 · x^{5} > 739584 · (10^{14})^{7} > 10^{103}.

Of course, one could perhaps come up with a smaller element of E_{4,2} using a totally new approach.

Finally, if Martin’s probabilistic estimate (1) could be proved, not only would each set E_{k,ℓ} be infinite (as already mentioned in Remark 7), but one could hope to find the approximate size of E_{k,ℓ}(x).

10 Acknowledgment

The authors would like to thank the referee for pointing out a previous result of Hildebrand (see Remark 2). The first author was supported in part by a grant from NSERC.

References

[1] V. Bunyakovsky, Nouveaux théorèmes relatifs à la distinction des nombres premiers et à la décomposition des entiers en facteurs, Mém. Acad. Sc. St. Pétersbourg 6 (1857), 305–329.

[2] J.-M. De Koninck, Those Fascinating Numbers, American Mathematical Society, 2009.

[3] J.-M. De Koninck, N. Doyon, and F. Luca, Consecutive integers divisible by the square of their largest prime factors, J. Comb. Number Theory 5 (2013), 81–93.

[4] J.-M. De Koninck and F. Luca, Analytic Number Theory: Exploring the Anatomy of Integers, Graduate Studies in Mathematics, Vol. 134, American Mathematical Society, 2012.

[5] R. de la Bretèche et S. Drappeau, Majoration du nombre de valeurs friables d’un polynôme, preprint.

[6] A. Hildebrand, On consecutive values of the Liouville function, Enseign. Math. (2) 32 (1986), 219–226.

[7] A. Hildebrand and G. Tenenbaum, Integers without large prime factors, Journal de Théorie des Nombres de Bordeaux 5 (1993), 411–484.

[8] A. Ivić, On certain large additive functions, in Gábor Halász, László Lovász, Miklós Simonovits and Vera T. Sós, eds., Paul Erdős and his Mathematics I, Bolyai Society Mathematical Studies, Vol. 11, Springer-Verlag, 2002, pp. 319–331.

[9] A. Ivić and C. Pomerance, Estimates for certain sums involving the largest prime factor of an integer, in Topics in Classical Number Theory, Vol. I, II (Budapest, 1981), Colloq. Math. Soc. János Bolyai 34, North-Holland, 1984, pp. 769–789.

[10] G. Martin, An asymptotic formula for the number of smooth values of a polynomial, J. Number Theory 93 (2002), 108–182.

2010 Mathematics Subject Classification: Primary 11N25; Secondary 11N32. Keywords: largest prime factor.

Received June 6 2018; revised version received October 15 2018. Published in Journal of Integer Sequences, December 6 2018.

Return to Journal of Integer Sequences home page.