Richard Pinch - cp's OEIS frontend

A047713 Euler-Jacobi pseudoprimes: 2^((n-1)/2) == (2 / n) mod n, where (2 / n) is a Jacobi symbol.

561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, 12801, 15841, 16705, 18705, 25761, 29341, 30121, 33153, 34945, 41041, 42799, 46657, 49141, 52633, 62745, 65281, 74665, 75361, 80581, 85489, 87249, 88357, 90751, 104653

Offset: 1

N. J. A. Sloane, Richard Pinch and Robert G. Wilson v

Odd composite numbers n such that 2^((n-1)/2) == (-1)^((n^2-1)/8) mod n. - Thomas Ordowski, Dec 21 2013

Most terms are congruent to 1 mod 8 (cf. A006971). Among the first 1000 terms, the number of terms congruent to 1, 3, 5 and 7 mod 8 are 764, 47, 125 and 64, respectively. - Jianing Song, Sep 05 2018

R. K. Guy, Unsolved Problems in Number Theory, A12.
H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, Vol. 57, Birkhauser, Boston, 1985.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes the subsequence A006971).

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.
Eric Weisstein's World of Mathematics, Pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A002997, A001567, A048950.

Terms in this sequence satisfying certain congruence: A270698 (congruent to 1 mod 4), A270697 (congruent to 3 mod 4), A006971 (congruent to +-1 mod 8), A244628 (congruent to 3 mod 8), A244626 (congruent to 5 mod 8).

Select[ Range[ 3, 105000, 2 ], Mod[ 2^((# - 1)/2) - JacobiSymbol[ 2, # ], # ] == 0 && ! PrimeQ[ # ] & ]

is(n)=n%2 && Mod(2,n)^(n\2)==kronecker(2,n) && !isprime(n) \\ Charles R Greathouse IV, Dec 20 2013

Corrected by Eric W. Weisstein; more terms from David W. Wilson

A007011 a(n) = smallest pseudoprime to base 2 with n prime factors.

Original entry on oeis.org

341, 561, 11305, 825265, 45593065, 370851481, 38504389105, 7550611589521, 277960972890601, 32918038719446881, 1730865304568301265, 606395069520916762801, 59989606772480422038001, 6149883077429715389052001, 540513705778955131306570201, 35237869211718889547310642241

Offset: 2

Richard Pinch

Smallest composite number m with n prime factors such that 2^(m-1)-1 is divisible by m.

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

Daniel Suteu, Table of n, a(n) for n = 2..34
R. Pinch, Pseudoprimes up to 10^13, Proceedings ANTS-IV, 4th Algorithmic Number Theory Symposium, Leiden, 2000. Springer Lecture Notes in Computer Science 1838 (2000) 459--474.
Index entries for sequences related to pseudoprimes

Cf. A007535.

fermat_psp(A, B, k, base) = A=max(A, vecprod(primes(k))); (f(m, l, lo, k) = my(list=List()); my(hi=sqrtnint(B\m, k)); if(lo > hi, return(list)); if(k==1, forstep(p=lift(1/Mod(m, l)), hi, l, if(isprimepower(p) && gcd(m*base, p) == 1, my(n=m*p); if(n >= A && (n-1) % znorder(Mod(base, p)) == 0, listput(list, n)))), forprime(p=lo, hi, base%p == 0 && next; my(z=znorder(Mod(base, p))); gcd(m,z) == 1 || next; my(q=p, v=m*p); while(v <= B, list=concat(list, f(v, lcm(l, z), p+1, k-1)); q *= p; Mod(base, q)^z == 1 || break; v *= p))); list); vecsort(Set(f(1, 1, 2, k)));
a(n) = if(n < 2, return()); my(x=vecprod(primes(n)), y=2*x); while(1, my(v=fermat_psp(x, y, n, 2)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ Daniel Suteu, Mar 04 2023

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007

A006971 Composite numbers k such that k == +-1 (mod 8) and 2^((k-1)/2) == 1 (mod k).

Original entry on oeis.org

561, 1105, 1729, 1905, 2047, 2465, 4033, 4681, 6601, 8321, 8481, 10585, 12801, 15841, 16705, 18705, 25761, 30121, 33153, 34945, 41041, 42799, 46657, 52633, 62745, 65281, 74665, 75361, 85489, 87249, 90751, 113201, 115921, 126217, 129921, 130561, 149281, 158369

Offset: 1

Richard Pinch

nonn

Previous name was "Terms of A047713 that are congruent to +-1 mod 8".

Complement of (A244626 union A244628) with respect to A047713. - Jianing Song, Sep 18 2018

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section A12, pp. 44-50.
Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, Vol. 57, Birkhäuser, Boston, 1985.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..828 from Jianing Song using data from A047713)

Subsequence of A001567 and A047713.

Cf. A244626, A244628, A270697, A270698.

Select[Range[10^5], MemberQ[{1, 7}, Mod[#, 8]] && CompositeQ[#] && PowerMod[2, (# - 1)/2, #] == 1 &] (* Amiram Eldar, Nov 06 2023 *)

This sequence appeared as M5461 in Sloane-Plouffe (1995), but was later mistakenly declared to be an erroneous form of A047713. Thanks to Jianing Song for providing the correct definition. - N. J. A. Sloane, Sep 17 2018

Formal definition by Jianing Song, Sep 18 2018

A006972 Lucas-Carmichael numbers: squarefree composite numbers k such that p | k => p+1 | k+1.

Original entry on oeis.org

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, 104663, 117215, 120581, 147455, 152279, 155819, 162687, 191807, 194327, 196559, 214199

Offset: 1

Richard Pinch and Jeffrey Shallit

nonn

Wright proves that this sequence is infinite (Main Theorem 2). - Charles R Greathouse IV, Nov 03 2015
Conjecture: if k = p*q*r, p = a*d - 1, q = b*d - 1, r = c*d - 1 are distinct odd primes, with d = gcd(p + 1, q + 1, r + 1) and a*b*c*d divides k + 1, then k is a Lucas-Carmichael number. - Davide Rotondo, Dec 23 2020
A composite k is a Lucas-Carmichael number if and only if k | A322702(k+1). - Thomas Ordowski, May 06 2021

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 399, p. 89, Ellipses, Paris 2008.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Donovan Johnson, Table of n, a(n) for n = 1..10000 (first 550 terms from Paolo P. Lava)
Ed Copeland and Brady Haran, Something special about 399, Numberphile video (2015).
Sridhar Tamilvanan and Subramani Muthukrishnan, On Lucas-Carmichael Integer, arXiv:2311.08012 [math.NT], 2023.
Daniel Suteu, Table of n, a(n) for terms a(n) < 10^15.
Samuel S. Wagstaff, Jr., Ramanujan's Taxicab Number and its Ilk, Purdue Univ. (2024). See p. 2.
Wikipedia, Lucas-Carmichael number
Thomas Wright, There are infinitely many elliptic Carmichael numbers
Thomas Wright, There are infinitely many elliptic Carmichael numbers, arXiv:1609.00231 [math.NT], 2016.
Index entries for sequences related to Carmichael numbers.

Intersection of A024556 and A056729.
Cf. A216925, A216926, A216927, A217002, A217003, A217091 (terms having 3, 4, 5, 6, 7 and 8 factors).
Cf. A216929, A322702.

with(numtheory):
a:= proc(n) option remember; local k; for k from 1+
     `if`(n=1, 3, a(n-1)) while isprime(k) or not issqrfree(k)
       or add(irem(k+1,i+1), i=factorset(k))>0 do od; k
    end:
seq(a(n), n=1..15);  # Alois P. Heinz, Apr 05 2018

Select[ Range[ 2, 10^6 ], !PrimeQ[ # ] && Union[ Transpose[ FactorInteger[ # ] ][ [ 2 ] ] ] == {1} && Union[ Mod[ # + 1, Transpose[ FactorInteger[ # ] ][ [ 1 ] ] + 1 ] ] == {0} & ]

is(n)=my(f=factor(n));for(i=1,#f[,1],if((n+1)%(f[i,1]+1) || f[i,2]>1, return(0)));#f[,1]>1 \\ Charles R Greathouse IV, Sep 23 2012

lucas_carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, lo, k) = my(list=List()); my(hi=min(sqrtint(B+1)-1, 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); f(1, 1, 3, k);
upto(n) = my(list=List()); for(k=3, oo, if(vecprod(primes(k+1))\2 > n, break); list=concat(list, lucas_carmichael(1, n, k))); vecsort(Vec(list)); \\ Daniel Suteu, Dec 01 2023

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

Original entry on oeis.org

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

A006970 Euler pseudoprimes: composite numbers n such that 2^((n-1)/2) == +-1 (mod n).

Original entry on oeis.org

341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, 10261, 10585, 12801, 15709, 15841, 16705, 18705, 25761, 29341, 30121, 31621, 33153, 34945, 41041, 42799

Offset: 1

N. J. A. Sloane, Robert G. Wilson v, Richard Pinch

Pseudoprimes for the primality test from [Schick]: n odd is probably prime if (n-1) | A003558((n-1)/2). (Succeeds for 99.9975% of odd natural numbers less than 10^8.) - Jonathan Skowera, Jun 29 2013

Equivalently, these are composites n such that ((n-1)/2)^((n-1)/2) == +-1 (mod n). - Thomas Ordowski, Nov 28 2023

R. K. Guy, Unsolved Problems in Number Theory, A12.
C. Schick, Weiche Primzahlen und das 257-Eck, 2008, pages 140-146.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1231 from T. D. Noe)
Eric Weisstein's World of Mathematics, Euler Pseudoprime.
Index entries for sequences related to pseudoprimes

ok[?PrimeQ] = False; ok[n] := (p = PowerMod[2, (n - 1)/2, n]; p == Mod[1, n] || p == Mod[-1, n]); Select[2 Range[22000] + 1, ok] (* Jean-François Alcover, Apr 06 2011 *)

isok(n) = {if (!isprime(n) && (n%2), npm = Mod(2, n)^((n-1)/2); if ((npm == Mod(1,n)) || (npm == Mod(-1,n)), print1(n, ", ")););} \\ Michel Marcus, Sep 12 2015

a(15) corrected (to 10261 from 10241) by Faron Moller (fm(AT)csd.uu.se)

Name edited by Thomas Ordowski, Nov 28 2023

cp's OEIS Frontend

User: Richard Pinch

A047713 Euler-Jacobi pseudoprimes: 2^((n-1)/2) == (2 / n) mod n, where (2 / n) is a Jacobi symbol.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A007011 a(n) = smallest pseudoprime to base 2 with n prime factors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A006971 Composite numbers k such that k == +-1 (mod 8) and 2^((k-1)/2) == 1 (mod k).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A006972 Lucas-Carmichael numbers: squarefree composite numbers k such that p | k => p+1 | k+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

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

A006970 Euler pseudoprimes: composite numbers n such that 2^((n-1)/2) == +-1 (mod n).

Views

Author

Keywords

Comments

References

Links

Programs

Mathematica

PARI

Extensions