OFFSET
1,1
COMMENTS
Erdős showed in 1956 how to construct Carmichael numbers from a given number n (typically with many divisors). Given a number n, let P be the set of primes p such that (p-1)|n but p is not a factor of n. Let c be a product of a subset of P with at least 3 elements. If c == 1 (mod n) then c is a Carmichael number.
Numbers with only one generated Carmichael number: 48, 80, 224, 252, 324, 468, 528, 560, 594, 780, 972, 1104, 1232, 1368, 1536, 1848, 2024, ...
LINKS
Paul Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), pp. 201-206.
Andrew Granville, Primality testing and Carmichael numbers, Notices of the American Mathematical Society, Vol. 39 No. 6 (1992), pp. 696-700.
Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Mathematics of Computation, Vol. 71, No. 238 (2002), pp. 883-908.
EXAMPLE
The set of primes for n = 36 is P={5, 7, 13, 19, 37}. Two subsets, {7, 13, 19} and {7, 13, 19, 37} have c == 1 (mod n): c = 7*13*19 = 1729 and c = 7*13*19*37 = 63973. 36 is the first number that generates Carmichael numbers thus a(1)=36.
MATHEMATICA
a = {}; Do[p = Select[Divisors[n] + 1, PrimeQ]; pr = Times @@ p; pr = pr/GCD[n, pr]; ps = Divisors[pr]; c = 0; Do[p1 = FactorInteger[ps[[j]]][[;; , 1]]; If[Length[p1] < 3, Continue[]]; c1 = Times @@ p1; If[Mod[c1, n] == 1, c++], {j, 1, Length[ps]}]; If[c > 0, AppendTo[a, n]], {n, 1, 1000}]; a
CROSSREFS
KEYWORD
nonn
AUTHOR
Amiram Eldar, Sep 01 2017
STATUS
approved