# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a002997
Showing 1-1 of 1
%I A002997 M5462 #418 Sep 15 2024 20:24:34
%S A002997 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,
%T A002997 52633,62745,63973,75361,101101,115921,126217,162401,172081,188461,
%U A002997 252601,278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,530881,552721
%N A002997 Carmichael numbers: composite numbers k such that a^(k-1) == 1 (mod k) for every a coprime to k.
%C A002997 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
%C A002997 k is composite and squarefree and for p prime, p|k => p-1|k-1.
%C A002997 An odd composite number k is a pseudoprime to base a iff a^(k-1) == 1 (mod k). A Carmichael number is an odd composite number k which is a pseudoprime to base a for every number a prime to k.
%C A002997 A composite odd number k is a Carmichael number if and only if k is squarefree and p-1 divides k-1 for every prime p dividing k. (Korselt, 1899)
%C A002997 Ghatage and Scott prove using Fermat's little theorem that (a+b)^k == a^k + b^k (mod k) (the freshman's dream) exactly when k is a prime (A000040) or a Carmichael number. - _Jonathan Vos Post_, Aug 31 2005
%C A002997 Alford et al. have constructed a Carmichael number with 10333229505 prime factors, and have also constructed Carmichael numbers with m prime factors for every m between 3 and 19565220. - _Jonathan Vos Post_, Apr 01 2012
%C A002997 Thomas Wright proved that for any numbers b and M in N with gcd(b,M) = 1, there are infinitely many Carmichael numbers k such that k == b (mod M). - _Jonathan Vos Post_, Dec 27 2012
%C A002997 Composite numbers k relatively prime to 1^(k-1) + 2^(k-1) + ... + (k-1)^(k-1). - _Thomas Ordowski_, Oct 09 2013
%C A002997 Composite numbers k such that A063994(k) = A000010(k). - _Thomas Ordowski_, Dec 17 2013
%C A002997 Odd composite numbers k such that k divides A002445((k-1)/2). - _Robert Israel_, Oct 02 2015
%C A002997 If k is a Carmichael number and gcd(b-1,k)=1, then (b^k-1)/(b-1) is a pseudoprime to base b by Steuerwald's theorem; see the reference in A005935. - _Thomas Ordowski_, Apr 17 2016
%C A002997 Composite numbers k such that p^k == p (mod k) for every prime p <= A285512(k). - _Max Alekseyev_ and _Thomas Ordowski_, Apr 20 2017
%C A002997 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
%C A002997 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
%C A002997 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
%C A002997 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
%C A002997 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
%C A002997 This is setwise difference A324050 \ A008578. Many of the same identities apply also to A324050. - _Antti Karttunen_, Apr 22 2019
%C A002997 If k is a Carmichael number, then A309132(k) = A326690(k). The proof generalizes that of Theorem in A309132. - _Jonathan Sondow_, Jul 19 2019
%C A002997 Composite numbers k such that A111076(k)^(k-1) == 1 (mod k). Proof: the multiplicative order of A111076(k) mod k is equal to lambda(k), where lambda(k) = A002322(k), so lambda(k) divides k-1, qed. - _Thomas Ordowski_, Nov 14 2019
%C A002997 For all positive integers m, m^k - m 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
%C A002997 From _Amiram Eldar_, Dec 04 2020, Apr 21 2024: (Start)
%C A002997 Ore (1948) called these numbers "Numbers with the Fermat property", or, for short, "F numbers".
%C A002997 Also called "absolute pseudoprimes". According to Erdős (1949) this term was coined by D. H. Lehmer.
%C A002997 Named by Beeger (1950) after the American mathematician Robert Daniel Carmichael (1879 - 1967). (End)
%C A002997 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
%C A002997 It seems that for any m > 1, the remainders of Carmichael numbers modulo m 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
%C A002997 Alford, Granville and Pomerance conjectured in their 1994 paper that a statement analogous to Bertrand's Postulate could be applied to Carmichael numbers. This has now been proved by Daniel Larsen, see link below. - _David James Sycamore_, Jan 17 2023
%D A002997 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.
%D A002997 Albert H. Beiler, Recreations in the Theory of Numbers, Dover Publications, Inc. New York, 1966, Table 18, Page 44.
%D A002997 David M. Burton, Elementary Number Theory, 5th ed., McGraw-Hill, 2002.
%D A002997 CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 87.
%D A002997 Richard K. Guy, Unsolved Problems in Number Theory, A13.
%D A002997 Øystein Ore, Number Theory and Its History, McGraw-Hill, 1948, Reprinted by Dover Publications, 1988, Chapter 14.
%D A002997 Paul 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.
%D A002997 Wacław Sierpiński, A Selection of Problems in the Theory of Numbers. Macmillan, NY, 1964, p. 51.
%D A002997 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A002997 David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See entry 561 at p. 157.
%H A002997 N. J. A. Sloane, Table of n, a(n) for n = 1..10000 (from the Pinch web site mentioned below)
%H A002997 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.
%H A002997 W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722.
%H A002997 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.
%H A002997 François Arnault, Thesis.
%H A002997 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.
%H A002997 François Arnault, Rabin-Miller primality test: Composite numbers which pass it, Mathematics of Computation, vol. 64, no 209, 1995, pp. 355-361.
%H A002997 François Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Mathematics of Computation, vol. 66, no 218, April 1997, pp. 869-881.
%H A002997 Joerg Arndt, Matters Computational (The Fxtbook), p. 786.
%H A002997 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.
%H A002997 Sunghan Bae, Su Hu, and Min Sha, On the Carmichael rings, Carmichael ideals and Carmichael polynomials, arXiv:1809.05432 [math.NT], 2018.
%H A002997 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.
%H A002997 Jens Bernheiden, Carmichael numbers (Text in German).
%H A002997 John D. Brillhart, N. J. A. Sloane, and J. D. Swift, Correspondence, 1972.
%H A002997 Ronald Joseph Burthe, Jr. Upper bounds for least witnesses and generating sets, Acta Arith. 80 (1997), no. 4, 311-326.
%H A002997 C. K. Caldwell, The Prime Glossary, Carmichael number.
%H A002997 R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232-238.
%H A002997 Keith Conrad, Carmichael numbers and Korselt's criterion, expository paper (2016), 1-3.
%H A002997 K. A. Draziotis, V. Martidis, and S. Tiganourias, Product Subset Problem: Applications to number theory and cryptography, arXiv:2002.07095 [math.NT], 2020. See also Chapter 5, Analysis, Cryptography and Information Science, World Scientific (2023), p. 108.
%H A002997 Harvey Dubner, Carmichael Numbers of the form (6m+1)(12m+1)(18m+1), Journal of Integer Sequences, Vol. 5 (2002) Article 02.2.1.
%H A002997 James Emery, Number Theory, 2013. [Broken link]
%H A002997 Paul Erdős, On the converse of Fermat's theorem, The American Mathematical Monthly, Vol. 56, No. 9 (1949), pp. 623-624; alternative link.
%H A002997 Jan Feitsma and William Galway, Tables of pseudoprimes and related data.
%H A002997 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.
%H A002997 Claude Goutier, Compressed text file carm10e22.7z containing all the Carmichael numbers up to 10^22. [Local copy, with permission. This is a very large file.]
%H A002997 Andrew Granville, Papers on Carmichael numbers.
%H A002997 Andrew Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc., 39 (No. 7, 1992), 696-700.
%H A002997 Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2002), no. 238, 883-908.
%H A002997 Gerhard Jaeschke, The Carmichael numbers to 10^12, Math. Comp., Vol. 55, No. 191 (1990), pp. 383-389.
%H A002997 Eugene Karolinsky and Dmytro Seliutin, Carmichael numbers for GL(m), arXiv:2001.10315 [math.NT], 2020.
%H A002997 Bernd C. Kellner, On primary Carmichael numbers, Integers 22 (2022), #A38, 39 pp.; arXiv:1902.11283 [math.NT], 2019.
%H A002997 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.
%H A002997 Paul Kinlaw, The reciprocal sums of pseudoprimes and Carmichael numbers, Mathematics of Computation (2023).
%H A002997 A. Korselt, G. Tarry, I. Franel, and G. Vacca, Problème chinois, L'intermédiaire des mathématiciens 6 (1899), 142-144.
%H A002997 Daniel Larsen, Bertrand's Postulate for Carmichael Numbers, arXiv:2111.06963 [math.NT], 2021.
%H A002997 D. H. Lehmer, Errata for Poulet's table, Math. Comp., 25 (1971), 944-945. 25 944 1971.
%H A002997 Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, 16 (2016), #A80.
%H A002997 Renaud Lifchitz, A generalization of the Korselt's criterion - Nested Carmichael numbers.
%H A002997 Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.
%H A002997 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.
%H A002997 Yoshio Mimura, Carmichael Numbers up to 10^12. [broken link, WayBackMachine]
%H A002997 Math Reference Project, Carmichael Numbers.
%H A002997 R. G. E. Pinch, The Carmichael numbers up to 10^18, 2008.
%H A002997 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.
%H A002997 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.
%H A002997 Carl Pomerance and N. J. A. Sloane, Correspondence, 1991.
%H A002997 Fred Richman, Primality testing with Fermat's little theorem.
%H A002997 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
%H A002997 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.
%H A002997 Eric Weisstein's World of Mathematics, Carmichael Number, Knoedel Numbers, and Pseudoprime.
%H A002997 Wikipedia, Carmichael number.
%H A002997 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.
%H A002997 Index entries for sequences related to Carmichael numbers.
%F A002997 Sum_{n>=1} 1/a(n) is in the interval (0.004706, 27.8724) (Bayless and Kinlaw, 2017). The upper bound was reduced to 0.0058 by Kinlaw (2023). - _Amiram Eldar_, Oct 26 2020, Feb 24 2024
%p A002997 filter:= proc(n)
%p A002997 local q;
%p A002997 if isprime(n) then return false fi;
%p A002997 if 2 &^ (n-1) mod n <> 1 then return false fi;
%p A002997 if not numtheory:-issqrfree(n) then return false fi;
%p A002997 for q in numtheory:-factorset(n) do
%p A002997 if (n-1) mod (q-1) <> 0 then return false fi
%p A002997 od:
%p A002997 true;
%p A002997 end proc:
%p A002997 select(filter, [seq(2*k+1,k=1..10^6)]); # _Robert Israel_, Dec 29 2014
%p A002997 isA002997 := n -> 0 = modp(n-1, numtheory:-lambda(n)) and not isprime(n) and n <> 1:
%p A002997 select(isA002997, [$1..10000]); # _Peter Luschny_, Jul 21 2019
%t A002997 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 *)
%t A002997 Select[Range[1,600001,2],CompositeQ[#]&&Mod[#,CarmichaelLambda[#]]==1&] (* _Harvey P. Dale_, Jul 08 2023 *)
%o A002997 (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
%o A002997 isA002997(n)=n%2 && !isprime(n) && Korselt(n) && n>1 \\ _Charles R Greathouse IV_, Jun 10 2011
%o A002997 (PARI) is_A002997(n, F=factor(n)~)={ #F>2 && !foreach(F,f,(n%(f[1]-1)==1 && f[2]==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
%o A002997 (Haskell)
%o A002997 a002997 n = a002997_list !! (n-1)
%o A002997 a002997_list = [x | x <- a024556_list,
%o A002997 all (== 0) $ map ((mod (x - 1)) . (subtract 1)) $ a027748_row x]
%o A002997 -- _Reinhard Zumkeller_, Apr 12 2012
%o A002997 (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
%o A002997 (Sage)
%o A002997 def isCarmichael(n):
%o A002997 if n == 1 or is_even(n) or is_prime(n):
%o A002997 return False
%o A002997 factors = factor(n)
%o A002997 for f in factors:
%o A002997 if f[1] > 1: return False
%o A002997 if (n - 1) % (f[0] - 1) != 0:
%o A002997 return False
%o A002997 return True
%o A002997 print([n for n in (1..20000) if isCarmichael(n)]) # _Peter Luschny_, Apr 02 2019
%o A002997 (Python)
%o A002997 from itertools import islice
%o A002997 from sympy import nextprime, factorint
%o A002997 def A002997_gen(): # generator of terms
%o A002997 p, q = 3, 5
%o A002997 while True:
%o A002997 for n in range(p+2,q,2):
%o A002997 f = factorint(n)
%o A002997 if max(f.values()) == 1 and not any((n-1) % (p-1) for p in f):
%o A002997 yield n
%o A002997 p, q = q, nextprime(q)
%o A002997 A002997_list = list(islice(A002997_gen(),20)) # _Chai Wah Wu_, May 11 2022
%Y A002997 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.
%Y A002997 Subsequence of A324050.
%K A002997 nonn,nice
%O A002997 1,1
%A A002997 _N. J. A. Sloane_
%E A002997 Links for lists of Carmichael numbers updated by _Jan Kristian Haugland_, Mar 25 2009 and _Danny Rorabaugh_, May 05 2017
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE