A002071 Number of pairs of consecutive integers x, x+1 such that all prime factors of both x and x+1 are at most the n-th prime.

1, 4, 10, 23, 40, 68, 108, 167, 241, 345, 482, 653, 869, 1153, 1502, 1930, 2454, 3106, 3896

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more

Comments

Størmer's theorem proves that a(n) is finite. - Charles R Greathouse IV, Feb 19 2013

Also: Number of positive integers x such that x(x+1) is prime(n)-smooth. - M. F. Hasler, Jan 16 2015

Also: Row lengths of A138180; partial sums of A145604. - M. F. Hasler, Jan 16 2015

On an effective abc conjecture (c < rad(abc)^2), we have that a(20)-a(33) is (4839, 6040, 7441, 9179, 11134, 13374, 16167, 19507, 23367, 27949, 33233, 39283, 46166, 54150). - Lucas A. Brown, Oct 16 2022

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Lucas A. Brown, stormer.py.
• E. F. Ecklund and R. B. Eggleton, Prime factors of consecutive integers, Amer. Math. Monthly, 79 (1972), 1082-1089.
• D. Eppstein, Smooth pairs.
• D. Eppstein, Python program
• D. H. Lehmer, On a problem of Størmer, Ill. J. Math., 8 (1964), 57-69.
• C. Stormer, Quelques théorèmes sur l'équation de Pell x^2 - Dy^2 = +-1 et leurs applications, Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv (1897). Kl. I (2).
• Wikipedia, Størmer's theorem
• OEIS Index entries for sequences related to the abc conjecture

Crossrefs

Cf. A002072, A145604, A145605, A145606.

Cf. A138180 (triangle of x values for each n).

Cf. A085152, A085153.

Cf. A285283 (equivalent for x^2 + 1). - Tomohiro Yamada, Apr 22 2017

Programs

Mathematica

(* This program needs x maxima taken from A002072. *) xMaxima = A002072;
smoothNumbers[p_, max_] := Module[{a, aa, k, pp, iter}, k = PrimePi[p]; aa = Array[a, k]; pp = Prime[Range[k]]; iter = Table[{a[j], 0, PowerExpand @ Log[pp[[j]], max/Times @@ (Take[pp, j-1]^Take[aa, j-1])]}, {j, 1, k}]; Table[Times @@ (pp^aa), Sequence @@ iter // Evaluate] // Flatten // Sort]; a[n_] := Module[{sn, cnt}, sn = smoothNumbers[Prime[n], xMaxima[[n]]+1]; cnt = 0; Do[If[sn[[i]]+1 == sn[[i+1]], cnt++], {i, 1, Length[sn]-1}]; cnt]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 16}] (* Jean-François Alcover, Nov 10 2016 *)
A002072 = {1, 8, 80, 4374, 9800, 123200, 336140, 11859210, 11859210};
Table[Length[Select[Table[Max[FactorInteger[x], FactorInteger[x + 1]], {x, A002072[[n]]}], # <= Prime[n] &]], {n, 7}] (* Robert Price, Oct 29 2018 *)

PARI

A002071(n)=[1,4,10,23,40,68,108,167,241,345,482,653,869,1153,1502][n] \\ "practical" solution. - M. F. Hasler, Jan 16 2015

PARI

A002071(n,b=A002072,c=1,p=prime(n))={for(k=2,b(n),vecmax(factor(k++,p)[,1])<=p && vecmax(factor(k--+(k<2),p)[,1])<=p && c++); c} \\ b can be any upper bound for A002072, e.g., n->10^n should work, too. - M. F. Hasler, Jan 16 2015

Formula

a(n) <= (2^n-1)*(prime(n)+1)/2 is implicit in Lehmer 1964. - Charles R Greathouse IV, Feb 19 2013

Extensions

Better description and more terms from David Eppstein, Mar 23 2007

a(16) from Jean-François Alcover, Nov 10 2016

a(17)-a(18) from Lucas A. Brown, Aug 23 2020

a(19) from Lucas A. Brown, Oct 16 2022