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

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

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

Table of n, a(n) for n=1..52.

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

Cf. A002997.

Sequence in context: A361098 A291713 A370266 * A244326 A357605 A064597

Adjacent sequences: A287837 A287838 A287839 * A287841 A287842 A287843

Keyword

nonn

Author

Amiram Eldar, Sep 01 2017

Status

approved