cp's OEIS Frontend

A006931 Least Carmichael number with n prime factors, or 0 if no such number exists.

%I A006931 M5463 #50 Feb 16 2025 08:32:31
%S A006931 561,41041,825265,321197185,5394826801,232250619601,9746347772161,
%T A006931 1436697831295441,60977817398996785,7156857700403137441,
%U A006931 1791562810662585767521,87674969936234821377601,6553130926752006031481761,1590231231043178376951698401
%N A006931 Least Carmichael number with n prime factors, or 0 if no such number exists.
%C A006931 Alford, Grantham, Hayman, & Shallue construct large Carmichael numbers, finding upper bounds for a(3)-a(19565220) and a(10333229505). - _Charles R Greathouse IV_, May 30 2013
%D A006931 J.-P. Delahaye, Merveilleux nombres premiers ("Amazing primes"), p. 269, Pour la Science, Paris 2000.
%D A006931 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006931 David W. Wilson, <a href="/A006931/b006931.txt">Table of n, a(n) for n = 3..35</a>
%H A006931 W. R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue, <a href="http://arxiv.org/abs/1203.6664">Constructing Carmichael numbers through improved subset-product algorithms</a>, arXiv:1203.6664 [math.NT], 2012-2013.
%H A006931 R. G. E. Pinch, <a href="https://doi.org/10.1090/S0025-5718-1993-1202611-7">The Carmichael numbers up to 10^15</a>, Math. Comp. 61 (1993), no. 203, 381-391.
%H A006931 R. G. E. Pinch, <a href="https://arxiv.org/abs/math/0504119">The Carmichael numbers up to 10^17</a>, arXiv:math/0504119 [math.NT], 2005.
%H A006931 R. G. E. Pinch, <a href="http://arXiv.org/abs/math/0604376">The Carmichael numbers up to 10^18</a>, arXiv:math/0604376 [math.NT], 2006.
%H A006931 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CarmichaelNumber.html">Carmichael Number</a>
%H A006931 <a href="/index/Ca#Carmichael">Index entries for sequences related to Carmichael numbers.</a>
%t A006931 (* Program not suitable to compute more than a few terms *)
%t A006931 A2997 = Select[Range[1, 10^6, 2], CompositeQ[#] && Mod[#, CarmichaelLambda[#] ] == 1&];
%t A006931 (First /@ Split[Sort[{PrimeOmega[#], #}& /@ A2997], #1[[1]] == #2[[1]]&])[[All, 2]] (* _Jean-François Alcover_, Sep 11 2018 *)
%o A006931 (PARI) Korselt(n,f=factor(n))=for(i=1,#f[,1],if(f[i,2]>1||(n-1)%(f[i,1]-1),return(0)));1
%o A006931 a(n)=my(p=2,f);forprime(q=3,default(primelimit),forstep(k=p+2,q-2,2,f=factor(k);if(vecmax(f[,2])==1 && #f[,2]==n && Korselt(k,f), return(k)));p=q)
%o A006931 \\ _Charles R Greathouse IV_, Apr 25 2012
%o A006931 (PARI)
%o A006931 carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, lo, k) = my(list=List()); my(hi=sqrtnint(B\m, k)); if(lo > hi, return(list)); if(k==1, lo=max(lo, ceil(A/m)); my(t=lift(1/Mod(m,l))); while(t < lo, t += l); forstep(p=t, hi, l, if(isprime(p), my(n=m*p); if((n-1)%(p-1) == 0, listput(list, n)))), forprime(p=lo, hi, if(gcd(m, p-1) == 1, list=concat(list, f(m*p, lcm(l, p-1), p+1, k-1))))); list); vecsort(Vec(f(1, 1, 3, k)));
%o A006931 a(n) = if(n < 3, return()); my(x=vecprod(primes(n+1))\2,y=2*x); while(1, my(v=carmichael(x,y,n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ _Daniel Suteu_, Feb 24 2023
%Y A006931 Cf. A002997, A135717, A135719, A135720, A135721.
%Y A006931 Cf. A087788, A141711, A074379, A112428, A112429, A112430, A112431, A112432.
%K A006931 nonn
%O A006931 3,1
%A A006931 _N. J. A. Sloane_ and _Richard Pinch_
%E A006931 Corrected by _Lekraj Beedassy_, Dec 31 2002
%E A006931 More terms from _Ralf Stephan_, from the Pinch paper, Apr 16 2005
%E A006931 Edited by _N. J. A. Sloane_, May 16 2008 at the suggestion of _R. J. Mathar_.
%E A006931 Escape clause added by _Jianing Song_, Dec 12 2021