A135720 -id:A135720 - cp's OEIS frontend

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

561, 41041, 825265, 321197185, 5394826801, 232250619601, 9746347772161, 1436697831295441, 60977817398996785, 7156857700403137441, 1791562810662585767521, 87674969936234821377601, 6553130926752006031481761, 1590231231043178376951698401

Offset: 3

N. J. A. Sloane and Richard Pinch

nonn

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

J.-P. Delahaye, Merveilleux nombres premiers ("Amazing primes"), p. 269, Pour la Science, Paris 2000.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

David W. Wilson, Table of n, a(n) for n = 3..35
W. R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue, Constructing Carmichael numbers through improved subset-product algorithms, arXiv:1203.6664 [math.NT], 2012-2013.
R. G. E. Pinch, The Carmichael numbers up to 10^15, Math. Comp. 61 (1993), no. 203, 381-391.
R. G. E. Pinch, The Carmichael numbers up to 10^17, arXiv:math/0504119 [math.NT], 2005.
R. G. E. Pinch, The Carmichael numbers up to 10^18, arXiv:math/0604376 [math.NT], 2006.
Eric Weisstein's World of Mathematics, Carmichael Number
Index entries for sequences related to Carmichael numbers.

Cf. A002997, A135717, A135719, A135720, A135721.

Cf. A087788, A141711, A074379, A112428, A112429, A112430, A112431, A112432.

(* Program not suitable to compute more than a few terms *)
A2997 = Select[Range[1, 10^6, 2], CompositeQ[#] && Mod[#, CarmichaelLambda[#] ] == 1&];
(First /@ Split[Sort[{PrimeOmega[#], #}& /@ A2997], #1[[1]] == #2[[1]]&])[[All, 2]] (* Jean-François Alcover, Sep 11 2018 *)

Korselt(n,f=factor(n))=for(i=1,#f[,1],if(f[i,2]>1||(n-1)%(f[i,1]-1),return(0)));1
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)
\\ Charles R Greathouse IV, Apr 25 2012

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)));
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

Corrected by Lekraj Beedassy, Dec 31 2002
More terms from Ralf Stephan, from the Pinch paper, Apr 16 2005
Edited by N. J. A. Sloane, May 16 2008 at the suggestion of R. J. Mathar.
Escape clause added by Jianing Song, Dec 12 2021

A083876 Least pseudoprime to base 2 through base prime(n).

Original entry on oeis.org

341, 1105, 1729, 29341, 29341, 162401, 252601, 252601, 252601, 252601, 252601, 252601, 1152271, 2508013, 2508013, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 6733693, 6733693, 6733693

Offset: 1

Robert G. Wilson v, May 06 2003

nonn

Records: 341, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, .... - Robert G. Wilson v, May 11 2012
Conjecture: for n > 1, a(n) is the smallest Carmichael number k with lpf(k) > prime(n). It seems that such Carmichael numbers have exactly three prime factors. - Thomas Ordowski, Apr 18 2017
The conjecture is true if a(n) < A285549(n) for all n > 1. It holds for all a(n) < 2^64. - Max Alekseyev and Thomas Ordowski, Mar 13 2018
If prime(n) < m < a(n), then m is prime if and only if p^(m-1) == 1 (mod m) for every prime p <= prime(n). - Thomas Ordowski, Mar 05 2018
By this conjecture in the second comment, a(n) <= A135720(n+1), with equality for n > 1 iff a(n) < a(n+1), namely for n = 2, 3, 5, 6, 12, 13, 15, 25, 28, 29, ... For such n, a(n) gives all terms of A300629 > 561. - Thomas Ordowski, Mar 10 2018

Giovanni Resta, Table of n, a(n) for n = 1..1000 (first 100 terms from Robert G. Wilson v)

Cf. A002997, A001567, A052155, A083737, A087788, A083739, A135720, A141768, A250199, A271221, A285549, A300629.

k = 4; Do[l = Table[ Prime[i], {i, 1, n}]; While[ PrimeQ[k] || Union[PowerMod[l, k - 1, k]] != {1}, k++ ]; Print[k], {n, 1, 29}]

isps(k, n) = {if (isprime(k), return (0)); my(nbok = 0); for (b=2, prime(n), if (Mod(b, k)^(k-1) == 1, nbok++, break)); if (nbok==prime(n)-1, return (1));}
a(n) = {my(k=2); while (!isps(k, n), k++); return (k);} \\ Michel Marcus, Apr 27 2018

A135721 a(n) is the smallest Carmichael number (A002997) divisible by the n-th prime, or 0 if no such number exists.

Original entry on oeis.org

561, 1105, 1729, 561, 1105, 561, 1729, 6601, 2465, 2821, 29341, 6601, 334153, 62745, 2433601, 74165065, 29341, 8911, 10024561, 10585, 2508013, 55462177, 62745, 46657, 101101, 52633, 84350561, 188461, 278545, 1152271, 18307381, 410041, 2628073, 12261061, 838201

Offset: 2

Artur Jasinski, Nov 25 2007

nonn

			561 is the first Carmichael number and its prime factors are 3, 11, 17 (2nd, 5th and 7th primes), so a(2), a(5) and a(7) are equal to 561. - _Michel Marcus_, Nov 07 2013

Amiram Eldar, Table of n, a(n) for n = 2..10001 (calculated using data from Claude Goutier; terms 2..1000 from Donovan Johnson)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
Gérard P. Michon, Carmichael Multiples of Odd Primes.
Index entries for sequences related to Carmichael numbers.

Cf. A002997, A135717, A006931, A135719, A135720.

c = Cases[Range[1, 10000000, 2], n_ /; Mod[n, CarmichaelLambda@ n] == 1 && ! PrimeQ@ n]; Table[First@ Select[c, Mod[#, Prime@ n] == 0 &], {n, 2, 16}] (* Michael De Vlieger, Aug 28 2015, after Artur Jasinski at A002997 *)

Korselt(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1||(n-1)%(f[i, 1]-1), return(0))); 1
isA002997(n)=n%2 && !isprime(n) && Korselt(n) && n>1
a(n) = my(pn=prime(n),cn = 31*pn); until (isA002997(cn+=2*pn),); cn; \\ Michel Marcus, Nov 07 2013, improved by M. F. Hasler, Apr 14 2015

Korselt(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1||(n-1)%(f[i, 1]-1), return(0))); 1
a(n,p=prime(n))=my(m=lift(Mod(1/p,p-1)),c=max(m,33)*p,mp=m*p); while(!isprime(c) && !Korselt(c), c+=mp); c \\ Charles R Greathouse IV, Apr 15 2015

More terms from Michel Marcus, Nov 07 2013

Escape clause added by Jianing Song, Dec 12 2021

A300629 a(1) = 561; a(n+1) = smallest Fermat pseudoprime to all natural bases up to lpf(a(n)).

Original entry on oeis.org

561, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, 413138881, 2301745249, 2438403661, 5255104513, 5781222721, 8251854001, 12173703001, 13946829751, 15906120889, 23224518901, 31876135201, 51436355851, 57274147841, 58094662081

Offset: 1

Thomas Ordowski, Mar 10 2018

nonn

It is sufficient to consider only prime bases: a(n+1) is the least composite number k such that p^(k-1) == 1 (mod k) for every prime p <= lpf(a(n)), with a(1) = 561.
Conjecture: a(n+1) is the smallest Carmichael number k such that lpf(k) > lpf(a(n)), with a(1) = 561. It seems that such Carmichael numbers have exactly three prime factors.
The above conjecture is true if A083876(n) < A285549(n) for all n > 1, but has not been proven; there is no counterexample up to a(n) < 2^64. - Max Alekseyev and Thomas Ordowski, Mar 13 2018
Carl Pomerance (in a letter to the author) wrote, Mar 13 2018: (Start)
Assuming a strong form of the prime k-tuples conjecture, if there are no small counterexamples, there are likely to be none.
Here's why.
Assuming prime k-tuples, there are infinitely many Carmichael numbers of the form (6k+1)(12k+1)(18k+1), where each factor is prime. And from Bateman-Horn, these are fairly thickly distributed. There are other even better triples such as (60k+41)(90k+61)(150k+101), where "better" means the least prime factor is not so far below the cube root.
So, to get into the sequence, a number needs to be a Fermat pseudoprime for every base up to nearly the cube root.
However, it's a theorem that a sufficiently large number with this property must be a Carmichael number. (End)
Theorem: if lpf(a(n)) < m < a(n), then m is prime if and only if p^(m-1) == 1 (mod m) for every prime p <= lpf(a(n)). - Thomas Ordowski, Mar 13 2018
lpf(a(n)) are listed in A300748. - Max Alekseyev, Mar 13 2018
For m > 1, A135720(m) >= A083876(m-1), with equality iff lpf(a(n)) = prime(m); by this conjecture in the second comment. - Thomas Ordowski, Mar 13 2018

Max Alekseyev, Table of n, a(n) for n = 1..138

Cf. A002997, A020639, A083876, A271221, A285549, A300748.

Subsequence of A087788 and of A135720.

A141705 a(n) is the least Carmichael number of the form prime(n)prime(n')prime(n") with n < n' < n", or 0 if no such number exists.

Original entry on oeis.org

0, 561, 1105, 1729, 0, 29341, 162401, 334153, 1615681, 3581761, 399001, 294409, 252601, 1152271, 104569501, 2508013, 178837201, 6189121, 10267951, 10024561, 14469841, 4461725581, 985052881, 19384289, 23382529, 3828001, 90698401

Offset: 1

M. F. Hasler, Jul 03 2008

nonn

Primes for which there are no such numbers (i.e. prime(n) such that a(n)=0) are given in A051663. Sequence A135720 is similar, but without restriction to 3-factor Carmichael numbers.

			a(1)=0 since there is no Carmichael number having prime(1)=2 as factor.
a(2)=561 since this is the smallest Carmichael number of the form pqr with prime r>q>p=prime(2)=3.
a(5)=0 since there is no Carmichael number of the form pqr with prime r>q>p=prime(5)=11.

Amiram Eldar, Table of n, a(n) for n = 1..10000
OEIS index entries for Carmichael numbers

Cf. A002997, A051663, A135720, A141702-A141706.

A141705(n) = { /* based on code by J.Brennen (jb AT brennen.net) */ local( V=[], B, p=prime(n), q, r); for( A=1, p-1, B=ceil((p^2+1)/A); while( 1, r=(p*B-p+A*B-B)/(A*B-p*p); q=(A*r-A+1)/p; q<=p && break; denominator(q)==1 && denominator(r)==1 && r>q && isprime(q) && isprime(r) && (p*q*r)%(p-1)==1 && V=concat(V,[p*q*r]); B++ )); if( V, vecmin( V )); }

A141706 a(n) is the largest Carmichael number of the form prime(n)prime(n')prime(n") with n < n' < n", or 0 if no such number exists.

Original entry on oeis.org

0, 561, 10585, 52633, 0, 530881, 7207201, 1024651, 1615681, 5444489, 471905281, 36765901, 2489462641, 564651361, 958762729, 17316001, 178837201, 1574601601, 7991602081, 597717121, 962442001, 4461725581, 167385219121, 43286923681

Offset: 1

M. F. Hasler, Jul 03 2008

nonn

Primes for which there are no such numbers (i.e. prime(n) such that a(n)=0) are given in A051663.

			a(1)=0 since there is no Carmichael number having prime(1)=2 as factor.
a(2)=561 since this is the largest (since only) Carmichael number of the form pqr with prime r>q>p=prime(2)=3.
a(5)=0 since there is no Carmichael number of the form pqr with prime r>q>p=prime(5)=11.

Amiram Eldar, Table of n, a(n) for n = 1..10000
OEIS index entries for Carmichael numbers

Cf. A002997, A051663, A135720, A141702-A141705.

A141706(n) = { /* based on code by J.Brennen (jb AT brennen.net) */ local( V=[], B, p=prime(n), q, r); for( A=1, p-1, B=ceil((p^2+1)/A); while( 1, r=(p*B-p+A*B-B)/(A*B-p*p); q=(A*r-A+1)/p; q<=p && break; denominator(q)==1 && denominator(r)==1 && r>q && isprime(q) && isprime(r) && (p*q*r)%(p-1)==1 && V=concat(V,[p*q*r]); B++ )); if( V, vecmax( V ))}

A300748 Least prime divisor of A300629(n).

Original entry on oeis.org

3, 5, 7, 13, 17, 41, 43, 53, 101, 109, 113, 151, 211, 281, 307, 331, 337, 461, 617, 727, 739, 827, 1033, 1301, 1481, 1531, 1723, 1901, 2161, 2351, 2381, 2633, 2647, 2801, 3371, 3931, 4933, 5653, 5743, 6791, 6917, 7561, 8059, 9521, 10369, 11503, 11551, 12161, 17579, 17839, 18433, 20593, 21061, 23581, 26731, 30241

Offset: 1

Max Alekseyev, Mar 11 2018

nonn

For m > 2, A135720(m) = A083876(m-1) if and only if a(n) = prime(m).

Max Alekseyev, Table of n, a(n) for n = 1..138

Cf. A002997, A020639, A083876, A285549, A300629.

a(n) = A020639(A300629(n)).

A321790 a(n) is the smallest base a > 2 such that a^(k-1) != 1 (mod k), where k = A001567(n), the n-th Fermat pseudoprime to base 2.

Original entry on oeis.org

3, 3, 3, 5, 3, 7, 3, 3, 5, 5, 7, 3, 3, 3, 3, 3, 3, 7, 3, 3, 3, 7, 3, 5, 3, 3, 3, 3, 3, 3, 3, 7, 3, 3, 5, 3, 3, 3, 3, 13, 3, 3, 3, 3, 5, 3, 3, 3, 3, 7, 3, 3, 13, 5, 3, 7, 3, 3, 3, 3, 3, 7, 3, 3, 3, 3, 3, 11, 3, 5, 5, 3, 3, 3, 5, 5, 3, 5, 7, 5, 5, 3, 13, 3, 3

Offset: 1

Thomas Ordowski, Nov 19 2018

nonn

a(n) <= A177415(n).
Each a(n) is an odd prime.
If k = A001567(n) is a Carmichael number, then a(n) = lpf(k).
Conjecture: if k = A001567(n) is semiprime, then a(n) < lpf(k).
The smallest numbers k = A001567(n) such that a(n) = prime(m) for m > 1 are 341, 1105, 1729, 75361, 29341, 162401, 334153, ... See A135720 > 561.
The smallest such semiprimes are 341, 2701, ?, 721801, ... Cf. A285549.

			The first Fermat pseudoprime to base 2 is 341, and 341 is not a Fermat pseudoprime to base 3, so a(1) = 3.

Cf. A001567, A002997, A083876, A135720, A177415, A214305, A285549.

A141710 is a subsequence.

a[p_] := Module[{m=3}, While[Mod[m^(p-1), p] == 1, m++]; m]; psp = Select[Range[3, 1000000, 2], CompositeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &]; Map[a, psp] (* Amiram Eldar, Nov 19 2018 *)

More terms from Amiram Eldar, Nov 19 2018

A380979 Composites that cause a witness to be added to a set of Fermat witnesses: a(n) is the smallest composite number that is not guaranteed composite using Fermat's Little Theorem by the witness A380978(i) for any i < n.

Original entry on oeis.org

4, 341, 1105, 1729, 29341, 75361, 162401, 252601, 294409, 334153, 399001, 1152271, 1615681, 2508013, 3581761, 3828001, 6189121, 6733693, 10024561, 10267951, 14469841, 17098369, 17236801, 19384289, 23382529, 29111881, 34657141, 53711113, 64377991, 79411201, 79624621

Offset: 1

Jan Kostanjevec, Feb 10 2025

nonn

A380978(n) is defined as the minimal Fermat witness that guarantees the compositeness of a(n). See the Weisstein link for details of the guarantee -- the option that uses a property derived from Fermat's little theorem.

To what extent does this differ from A135720 sorted? - Peter Munn, Mar 12 2025

			a(1) = 4, since 4 is the smallest composite number and we need to add a witness to the empty set to guarantee its compositeness. 2 is the minimal Fermat witness for the compositeness of 4, so the set of witnesses becomes {2}.
a(2) = 341, since 341 is the smallest composite number that requires a witness other than 2, namely 3.
a(3) = 1105, since 1105 is the smallest composite number that requires a witness other than 2 and 3, namely 5.

Eric Weisstein's World of Mathematics, Compositeness Certificate
Index entries for sequences related to pseudoprimes

Cf. A001567, A002997, A006945, A098654, A135720, A380978 (new minimal Fermat witness).

More terms from Jinyuan Wang, Mar 05 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A083876 Least pseudoprime to base 2 through base prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A135721 a(n) is the smallest Carmichael number (A002997) divisible by the n-th prime, or 0 if no such number exists.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A300629 a(1) = 561; a(n+1) = smallest Fermat pseudoprime to all natural bases up to lpf(a(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

A141705 a(n) is the least Carmichael number of the form prime(n)*prime(n')*prime(n") with n < n' < n", or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A141706 a(n) is the largest Carmichael number of the form prime(n)*prime(n')*prime(n") with n < n' < n", or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A300748 Least prime divisor of A300629(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A321790 a(n) is the smallest base a > 2 such that a^(k-1) != 1 (mod k), where k = A001567(n), the n-th Fermat pseudoprime to base 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A141705 a(n) is the least Carmichael number of the form prime(n)prime(n')prime(n") with n < n' < n", or 0 if no such number exists.

A141706 a(n) is the largest Carmichael number of the form prime(n)prime(n')prime(n") with n < n' < n", or 0 if no such number exists.