cp's OEIS Frontend

A002072 a(n) = smallest number m such that for all k > m, either k or k+1 has a prime factor > prime(n).

%I A002072 M4560 N1942 #80 Mar 02 2025 22:57:07
%S A002072 1,8,80,4374,9800,123200,336140,11859210,11859210,177182720,
%T A002072 1611308699,3463199999,63927525375,421138799639,1109496723125,
%U A002072 1453579866024,20628591204480,31887350832896,31887350832896,119089041053696,2286831727304144,9591468737351909375,9591468737351909375,9591468737351909375,9591468737351909375,9591468737351909375,19316158377073923834000
%N A002072 a(n) = smallest number m such that for all k > m, either k or k+1 has a prime factor > prime(n).
%C A002072 An effective abc conjecture (c < rad(abc)^2) would imply that a(27) = a(28) = ... = a(32), and a(33) = 124225935845233319439173. - _Lucas A. Brown_, Sep 20 2020
%D A002072 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002072 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002072 Lucas A. Brown, <a href="https://github.com/lucasaugustus/oeis/blob/main/stormer.py">Python program</a>.
%H A002072 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 A002072 D. H. Lehmer, <a href="http://projecteuclid.org/euclid.ijm/1256067456">On a problem of Størmer</a>, Ill. J. Math., 8 (1964), 57-79.
%H A002072 Don Reble, <a href="/A002072/a002072.py.txt">Python program</a>
%H A002072 Jim White, <a href="https://11011110.github.io/blog/2007/03/23/smooth-pairs.html">Results to P = 127</a>
%H A002072 Wikipedia, <a href="http://en.wikipedia.org/wiki/Stormer%27s_theorem">Størmer's theorem</a>
%F A002072 a(n) < 10^n/n except for n=4. (Conjectured, from experimental data.) - _M. F. Hasler_, Jan 16 2015
%e A002072 a(1) = 1 since for any number k greater than 1, it is impossible that k and k+1 both are powers of 2, so at least one of them has a prime factor > 2. (For m = 0 this would not hold for k = 1, k+1 = 2.)
%e A002072 a(2) = 8 since for any larger k, we cannot have k and k+1 both 3-smooth (cf. A003586).
%e A002072 31887350832897 = 3^9*7*37*41^2*61^2, 31887350832896 = 2^8*13*19*23*29^4*31, this number appears twice because there is no pair of numbers with max. factor = 67 that is larger than this number.
%t A002072 smoothNumbers[p_?PrimeQ, max_Integer] := 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}]; Sort[Flatten[Table[Times @@ (pp^aa), Evaluate[ Sequence @@ iter]]]]]; a[n_] := Module[{sn = smoothNumbers[Prime[n], Ceiling[2000 + 10^n/n]], pos}, pos = Position[Differences[sn], 1][[-1, 1]]; sn[[pos]]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 12}] (* _Jean-François Alcover_, Nov 17 2016, after _M. F. Hasler_'s observation *)
%o A002072 (PARI) A002072(n, a=[1, 8, 80, 4374, 9800, 123200, 336140, 11859210, 11859210, 177182720, 1611308699, 3463199999, 63927525375, 421138799639, 1109496723125, 1453579866024])=a[n] \\ "practical" solution for use in other sequences, easily extended to more values. - _M. F. Hasler_, Jan 16 2015
%o A002072 (PARI) A2072=List(1); A002072(n)={while(#A2072<n, A2072_extend()); A2072[n]}
%o A002072 isSmooth(n, p) = !(n=factor(n,p+1)~) || n[1, #n] <= p
%o A002072 A2072_extend()={ local(best = A2072[#A2072]); my(P = prime(#A2072+1), check(x, sol = (x-1)\2) = sol > best && isSmooth(sol, P) && isSmooth(sol+1, P) && best=sol, p=primes([1, P])); for(i=1, 2^#p, i==2 && next; my(qq = 2*vecprod(vecextract(p,i-1)), qn = [qq, sqrtint(qq), 0, 1], cf = [1,0,0,1], xi, aa, x0, x1, y0, y1); until(x0, aa = (qn[2]+qn[3])\qn[4]; qn[3] = aa*qn[4] - qn[3]; qn[4] = (qn[1] - qn[3]^2) \ qn[4]; cf = [aa*cf[1]+cf[3], aa*cf[2]+cf[4], cf[1], cf[2]]; cf[1]^2 - qq*cf[2]^2 == 1 && [x0,x1, y0,y1] = [x1, cf[1], y1, cf[2]] ); isSmooth(y0, P) || next; check(xi = x0); check(x1); for (i=3, max(P\/2, 3), [x0, x1] = [x1, x1 * xi * 2 - x0]; check(x1)))/*for i*/; listput(A2072, best) } \\ Following Don Reble's Python program. - _M. F. Hasler_, Mar 01 2025
%Y A002072 Cf. A002071, A003032, A003033, A122463, A145606, A175607.
%Y A002072 Equals A117581(n) - 1.
%K A002072 nonn,nice,hard
%O A002072 1,2
%A A002072 _N. J. A. Sloane_
%E A002072 More terms from _Don Reble_, Jan 11 2005
%E A002072 a(18)-a(26) from _Fred Schneider_, Sep 09 2006
%E A002072 Corrected and extended by _Andrey V. Kulsha_, Aug 10 2011, according to Jim White's computations.