The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A002997 Carmichael numbers: composite numbers n such that a^(n-1) == 1 (mod n) for every a coprime to n. (Formerly M5462) 329
 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS V. Šimerka found the first 7 terms of this sequence 25 years before Carmichael (see the link and also the remark of K. Conrad). - Peter Luschny, Apr 01 2019 n is composite and squarefree and for p prime, p|n => p-1|n-1. An odd composite number n is a pseudoprime to base a iff a^(n-1) == 1 mod n. A Carmichael number is an odd composite number n which is a pseudoprime to base a for every number a prime to n. A composite odd number n is a Carmichael number if and only if n is squarefree and p-1 divides n-1 for every prime p dividing n. (Korselt, 1899) Ghatage and Scott prove using Fermat's little theorem that (a+b)^n == a^n + b^n (mod n) (the freshman's dream) exactly when n is a prime (A000040) or a Carmichael number. - Jonathan Vos Post, Aug 31 2005 Alford et al. have constructed a Carmichael number with 10333229505 prime factors, and have also constructed Carmichael numbers with k prime factors for every k between 3 and 19565220. - Jonathan Vos Post, Apr 01 2012 Thomas Wright proved that for any numbers b and M in N with gcd(b,M) = 1, there are infinitely many Carmichael numbers m such that m = b mod M. - Jonathan Vos Post, Dec 27 2012 Composite numbers n relatively prime to 1^(n-1)+2^(n-1)+...+(n-1)^(n-1). - Thomas Ordowski, Oct 09 2013 Composite numbers n such that A063994(n) = A000010(n). - Thomas Ordowski, Dec 17 2013 Odd composite numbers n such that n divides A002445((n-1)/2). - Robert Israel, Oct 02 2015 If n is a Carmichael number and gcd(b-1,n)=1, then (b^n-1)/(b-1) is a pseudoprime to base b; by Steuerwald's theorem, see the reference in A005935. - Thomas Ordowski, Apr 17 2016 Composite numbers n such that p^n == p (mod n) for every prime p <= A285512(n). - Max Alekseyev and Thomas Ordowski, Apr 20 2017 If a composite m < A285549(n) and p^m == p (mod m) for every prime p <= prime(n), then m is a Carmichael number. - Thomas Ordowski, Apr 23 2017 The sequence of all Carmichael numbers can be defined as follows: a(1) = 561, a(n+1) = smallest composite k > a(n) such that p^k == p (mod k) for every prime p <= n+2. - Thomas Ordowski, Apr 24 2017 An integer m > 1 is a Carmichael number if and only if m is squarefree and each of its prime divisors p satisfies both s_p(m) >= p and s_p(m) == 1 (mod p-1), where s_p(m) is the sum of the base p digits of m. Then m is odd and has at least three prime factors. For each prime factor p, the sharp bound p <= a*sqrt(m) holds with a = sqrt(17/33) = 0.7177.... See Kellner and Sondow 2019. - Bernd C. Kellner and Jonathan Sondow, Mar 03 2019 Carmichael numbers are special polygonal numbers A324973. The rank of the n-th Carmichael number is A324975(n). See Kellner and Sondow 2019. - Jonathan Sondow, Mar 26 2019 An odd composite number m is a Carmichael number iff m divides denominator(Bernoulli(m-1)). The quotient is A324977. See Pomerance, Selfridge, & Wagstaff, p. 1006, and Kellner & Sondow, section on Bernoulli numbers. - Jonathan Sondow, Mar 28 2019 This is setwise difference A324050 \ A008578. Many of the same identities apply also to A324050. - Antti Karttunen, Apr 22 2019 If n is a Carmichael number, then A309132(n) = A326690(n). The proof generalizes that of Theorem in A309132. - Jonathan Sondow, Jul 19 2019 Composite numbers n such that A111076(n)^(n-1) == 1 (mod n). Proof: the multiplicative order of A111076(n) mod n is equal to lambda(n), where lambda(n) = A002322(n), so lambda(n) divides n-1, qed. - Thomas Ordowski, Nov 14 2019 For all positive integers n, n^k - n is divisible by k, for all k>1, iff k is either a Carmichael number or a prime, as is used in the proof by induction for Fermat's Little Theorem. Also related are A182816 and A121707. - Richard R. Forberg, Jul 18 2020 Named by Beeger (1950) after the American mathematician Robert Daniel Carmichael (1879 - 1967). - Amiram Eldar, Dec 04 2020 For ending digit 1,3,5,7,9 through the first 10000 terms, we see 80.3, 4.1, 7.4, 3.8 and 4.3% apportionment respectively. Why the bias towards ending digit "1"? - Bill McEachen, Jul 16 2021 It seems that for any k > 1, the remainders of Carmichael numbers modulo k are biased towards 1. The number of terms congruent to 1 modulo 4, 6, 8, ..., 24 among the first 10000 terms: 9827, 9854, 8652, 8034, 9682, 5685, 6798, 7820, 7880, 3378 and 8518. - Jianing Song, Nov 08 2021 REFERENCES N. G. W. H. Beeger, On composite numbers n for which a^n == 1 (mod n) for every a prime to n, Scripta Mathematica, Vol. 16 (1950), pp. 133-135. A. H. Beiler, Recreations in the Theory of Numbers, Dover Publications, Inc. New York, 1966, Table 18, Page 44. D. M. Burton, Elementary Number Theory, 5th ed., McGraw-Hill, 2002. CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 87. R. K. Guy, Unsolved Problems in Number Theory, A13. O. Ore, Number Theory and Its History, McGraw-Hill, 1948, Reprinted by Dover Publications, 1988, Chapter 14. P. Poulet, Tables des nombres composés vérifiant le théorème du Fermat pour le module 2 jusqu'à 100.000.000, Sphinx (Brussels), 8 (1938), 42-45. W. Sierpiński, A Selection of Problems in the Theory of Numbers. Macmillan, NY, 1964, p. 51. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS N. J. A. Sloane, Table of n, a(n) for n = 1..10000 (from the Pinch web site mentioned below) W. R. Alford, Jon Grantham, Steven Hayman and Andrew Shallue, Constructing Carmichael numbers through improved subset-product algorithms, Mathematics of Computation, Vol. 83, No. 286 (2014), pp. 899-915, arXiv preprint, arXiv:1203.6664v1 [math.NT], Mar 29 2012. W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722. W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16. François Arnault, Thesis François Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, Journal of Symbolic Computation, vol. 20, no 2, Aug. 1995, pp. 151-161. François Arnault, Rabin-Miller primality test: Composite numbers which pass it, Mathematics of Computation, vol. 64, no 209, 1995, pp. 355-361. François Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Mathematics of Computation, vol. 66, no 218, April 1997, pp. 869-881. Joerg Arndt, Matters Computational (The Fxtbook), p. 786. Eric Bach and Rex Fernando, Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test, ISSAC '16: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, July 2016, pp. 47-54, arXiv preprint, arXiv:1512.00444 [math.NT], 2015. Sunghan Bae, Su Hu and Min Sha, On the Carmichael rings, Carmichael ideals and Carmichael polynomials, arXiv:1809.05432 [math.NT], 2018. Jonathan Bayless and Paul Kinlaw, Explicit Bounds for the Sum of Reciprocals of Pseudoprimes and Carmichael Numbers, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.4. Jens Bernheiden, Carmichael numbers (Text in German). John D. Brillhart, N. J. A. Sloane, and J. D. Swift, Correspondence, 1972. Ronald Joseph Burthe, Jr. Upper bounds for least witnesses and generating sets, Acta Arith. 80 (1997), no. 4, 311-326. C. K. Caldwell, The Prime Glossary, Carmichael number. Keith Conrad, Carmichael numbers and Korselt’s criterion, expository paper (2016), 1-3. K. A. Draziotis, V. Martidis and S. Tiganourias, Product Subset Problem: Applications to number theory and cryptography, arXiv:2002.07095 [math.NT], 2020. Harvey Dubner, Carmichael Numbers of the form (6m+1)(12m+1)(18m+1), Journal of Integer Sequences, Vol. 5 (2002) Article 02.2.1. James Emery, Number Theory, 2013. Jan Feitsma and William Galway, Tables of pseudoprimes and related data. Pratibha Ghatage and Brian Scott, Exactly When is (a+b)^n == a^n + b^n (mod n)?, College Mathematics Journal, Vol. 36, No. 4 (Sep 2005), p. 322. Andrew Granville, Papers on Carmichael numbers Andrew Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc., 39 (No. 7, 1992), 696-700. Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2002), no. 238, 883-908. Gerhard Jaeschke, The Carmichael numbers to 10^12, Math. Comp., Vol. 55, No. 191 (1990), pp. 383-389. Eugene Karolinsky and Dmytro Seliutin, Carmichael numbers for GL(m), arXiv:2001.10315 [math.NT], 2020. Bernd C. Kellner, On primary Carmichael numbers, Integers 22 (2022), #A38, 39 pp.; arXiv:1902.11283 [math.NT], 2019. Bernd C. Kellner and Jonathan Sondow, On Carmichael and polygonal numbers, Bernoulli polynomials, and sums of base-p digits, Integers 21 (2021), #A52, 21 pp.; arXiv:1902.10672 [math.NT], 2019. A. Korselt, G. Tarry, I. Franel and G. Vacca, Problème chinois, L'intermédiaire des mathématiciens 6 (1899), 142-144. D. H. Lehmer, Errata for Poulet's table, Math. Comp., 25 (1971), 944-945. 25 944 1971. Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, 16 (2016), #A80. Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013. Romeo Meštrović, On a Congruence Modulo n^3 Involving Two Consecutive Sums of Powers, Journal of Integer Sequences, Vol. 17 (2014), 14.8.4. Yoshio Mimura, Carmichael Numbers up to 10^12. [broken link, WayBackMachine] Math Reference Project, Carmichael Numbers. R. G. E. Pinch, The Carmichael numbers up to 10^18, 2008. R. G. E. Pinch, Carmichael numbers up to 10^15, 10^16, 10^16 to 10^17, 10^17 to 10^18, 10^19, and 10^21 Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Math. Comp., Vol. 35, No. 151 (1980), pp. 1003-1026. Carl Pomerance & N. J. A. Sloane, Correspondence, 1991. Fred Richman, Primality testing with Fermat's little theorem. Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. - From N. J. A. Sloane, Feb 07 2013 Václav Šimerka, Zbytky z arithmetické posloupnosti, (On the remainders of an arithmetic progression), Časopis pro pěstování matematiky a fysiky. 14 (1885), 221-225. Eric Weisstein's World of Mathematics, Carmichael Number, Knoedel Numbers, and Pseudoprime. Wikipedia, Carmichael number. Thomas Wright, Infinitely many Carmichael numbers in arithmetic progressions, Bulletin of the London Mathematical Society, 45 (2013) 943-952, arXiv preprint, arXiv:1212.5850 [math.NT], Dec 2012. FORMULA Sum_{n>=1} 1/a(n) is in the interval (0.004706, 27.8724) (Bayless and Kinlaw, 2017). - Amiram Eldar, Oct 26 2020 MAPLE filter:= proc(n)   local q;   if isprime(n) then return false fi;   if 2 &^ (n-1) mod n <> 1 then return false fi;   if not numtheory:-issqrfree(n) then return false fi;   for q in numtheory:-factorset(n) do     if (n-1) mod (q-1) <> 0 then return false fi   od:   true; end proc: select(filter, [seq(2*k+1, k=1..10^6)]); # Robert Israel, Dec 29 2014 isA002997 := n -> 0 = modp(n-1, numtheory:-lambda(n)) and not isprime(n) and n <> 1: select(isA002997, [\$1..10000]); # Peter Luschny, Jul 21 2019 MATHEMATICA Cases[Range[1, 100000, 2], n_ /; Mod[n, CarmichaelLambda[n]] == 1 && ! PrimeQ[n]] (* Artur Jasinski, Apr 05 2008; minor edit from Zak Seidov, Feb 16 2011 *) PROG (PARI) 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 \\ Charles R Greathouse IV, Jun 10 2011 (PARI) is_A002997(n, F=factor(n)~)={ #F>2 && !foreach(F, f, (n%(f-1)==1 && f==1) || return)} \\ No need to check parity: if efficiency is needed, scan only odd numbers. - M. F. Hasler, Aug 24 2012, edited Mar 24 2022 (Haskell) a002997 n = a002997_list !! (n-1) a002997_list = [x | x <- a024556_list, all (== 0) \$ map ((mod (x - 1)) . (subtract 1)) \$ a027748_row x] -- Reinhard Zumkeller, Apr 12 2012 (Magma) [n: n in [3..53*10^4 by 2] | not IsPrime(n) and n mod CarmichaelLambda(n) eq 1]; // Bruno Berselli, Apr 23 2012 (Sage) def isCarmichael(n):     if n == 1 or is_even(n) or is_prime(n):         return False     factors = factor(n)     for f in factors:         if f > 1: return False         if (n - 1) % (f - 1) != 0:             return False     return True print([n for n in (1..20000) if isCarmichael(n)]) # Peter Luschny, Apr 02 2019 (Python) from itertools import islice from sympy import nextprime, factorint def A002997_gen(): # generator of terms     p, q = 3, 5     while True:         for n in range(p+2, q, 2):             f = factorint(n)             if max(f.values()) == 1 and not any((n-1) % (p-1) for p in f):                 yield n         p, q = q, nextprime(q) A002997_list = list(islice(A002997_gen(), 20)) # Chai Wah Wu, May 11 2022 CROSSREFS Cf. A001567, A002445, A002322, A006931, A024556, A027748, A055553, A064238-A064262, A083737, A087441, A087442, A135717, A141711, A153581, A225498, A285512, A285549, A309132, A324290, A324315, A324316, A324973, A324975, A324977, A326690. Subsequence of A324050. Sequence in context: A218483 A309235 A104016 * A355039 A087788 A173703 Adjacent sequences:  A002994 A002995 A002996 * A002998 A002999 A003000 KEYWORD nonn,nice AUTHOR EXTENSIONS Links for lists of Carmichael numbers updated by Jan Kristian Haugland, Mar 25 2009 and Danny Rorabaugh, May 05 2017 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 28 01:47 EDT 2022. Contains 357063 sequences. (Running on oeis4.)