|
| |
|
|
A002997
|
|
Carmichael numbers: composite numbers n such that a^(n-1) == 1 (mod n) for every a coprime to n.
(Formerly M5462)
|
|
337
|
|
|
|
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
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
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
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
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
|
|
|
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
|
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.
A. Korselt, G. Tarry, I. Franel and G. Vacca, Problème chinois, L'intermédiaire des mathématiciens 6 (1899), 142-144.
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.
|
|
|
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:
|
|
|
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 *)
Select[Range[1, 600001, 2], CompositeQ[#]&&Mod[#, CarmichaelLambda[#]]==1&] (* Harvey P. Dale, Jul 08 2023 *)
|
|
|
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
(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
(Haskell)
a002997 n = a002997_list !! (n-1)
a002997_list = [x | x <- a024556_list,
all (== 0) $ map ((mod (x - 1)) . (subtract 1)) $ a027748_row x]
(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] > 1: return False
if (n - 1) % (f[0] - 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)
|
|
|
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.
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
