

A287840


Numbers that generate Carmichael numbers using Erdős's method.


5



36, 48, 60, 72, 80, 108, 112, 120, 144, 180, 198, 216, 224, 240, 252, 288, 300, 324, 336, 360, 396, 420, 432, 468, 480, 504, 528, 540, 560, 576, 594, 600, 612, 630, 648, 660, 672, 720, 756, 768, 780, 792, 810, 828, 840, 864, 900, 936, 960, 972, 990, 1008
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 (p1)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

Table of n, a(n) for n=1..52.
Paul Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), pp. 201206.
Andrew Granville, Primality testing and Carmichael numbers, Notices of the American Mathematical Society, Vol. 39 No. 6 (1992), pp. 696700.
Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Mathematics of Computation, Vol. 71, No. 238 (2002), pp. 883908.


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

Cf. A002997.
Sequence in context: A160063 A260927 A291713 * A244326 A064597 A119850
Adjacent sequences: A287837 A287838 A287839 * A287841 A287842 A287843


KEYWORD

nonn


AUTHOR

Amiram Eldar, Sep 01 2017


STATUS

approved



