cp's OEIS Frontend

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.

%I A002071 M3386 N1366 #81 Oct 17 2022 01:57:43
%S A002071 1,4,10,23,40,68,108,167,241,345,482,653,869,1153,1502,1930,2454,3106,
%T A002071 3896
%N 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.
%C A002071 Størmer's theorem proves that a(n) is finite. - _Charles R Greathouse IV_, Feb 19 2013
%C A002071 Also: Number of positive integers x such that x(x+1) is prime(n)-smooth. - _M. F. Hasler_, Jan 16 2015
%C A002071 Also: Row lengths of A138180; partial sums of A145604. - _M. F. Hasler_, Jan 16 2015
%C A002071 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
%D A002071 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002071 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002071 Lucas A. Brown, <a href="https://github.com/lucasaugustus/oeis/blob/main/stormer.py">stormer.py</a>.
%H A002071 E. F. Ecklund and R. B. Eggleton, <a href="http://www.jstor.org/stable/2317422">Prime factors of consecutive integers</a>, Amer. Math. Monthly, 79 (1972), 1082-1089.
%H A002071 D. Eppstein, <a href="https://11011110.github.io/blog/2007/03/23/smooth-pairs.html">Smooth pairs</a>.
%H A002071 D. Eppstein, <a href="https://11011110.github.io/blog/2007/03/19/strmers-algorithm.html">Python program</a>
%H A002071 D. H. Lehmer, <a href="http://projecteuclid.org/euclid.ijm/1256067456">On a problem of Størmer</a>, Ill. J. Math., 8 (1964), 57-69.
%H A002071 C. Stormer, <a href="https://archive.org/stream/skrifterudgivnea1897chri#page/n81/mode/2up">Quelques théorèmes sur l'équation de Pell x^2 - Dy^2 = +-1 et leurs applications</a>, Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv (1897). Kl. I (2).
%H A002071 Wikipedia, <a href="http://en.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem">Størmer's theorem</a>
%H A002071 <a href="/index/Ab#abc">OEIS Index entries for sequences related to the abc conjecture</a>
%F A002071 a(n) <= (2^n-1)*(prime(n)+1)/2 is implicit in Lehmer 1964. - _Charles R Greathouse IV_, Feb 19 2013
%t A002071 (* This program needs x maxima taken from A002072. *) xMaxima = A002072;
%t A002071 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 *)
%t A002071 A002072 = {1, 8, 80, 4374, 9800, 123200, 336140, 11859210, 11859210};
%t A002071 Table[Length[Select[Table[Max[FactorInteger[x], FactorInteger[x + 1]], {x, A002072[[n]]}], # <= Prime[n] &]], {n, 7}] (* _Robert Price_, Oct 29 2018 *)
%o A002071 (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
%o A002071 (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
%Y A002071 Cf. A002072, A145604, A145605, A145606.
%Y A002071 Cf. A138180 (triangle of x values for each n).
%Y A002071 Cf. A085152, A085153.
%Y A002071 Cf. A285283 (equivalent for x^2 + 1). - _Tomohiro Yamada_, Apr 22 2017
%K A002071 nonn,nice,hard,more
%O A002071 1,2
%A A002071 _N. J. A. Sloane_
%E A002071 Better description and more terms from _David Eppstein_, Mar 23 2007
%E A002071 a(16) from _Jean-François Alcover_, Nov 10 2016
%E A002071 a(17)-a(18) from _Lucas A. Brown_, Aug 23 2020
%E A002071 a(19) from _Lucas A. Brown_, Oct 16 2022