login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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: A160063 A260927 A291713 * A244326 A064597 A119850

Adjacent sequences:  A287837 A287838 A287839 * A287841 A287842 A287843

KEYWORD

nonn

AUTHOR

Amiram Eldar, Sep 01 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 14 19:48 EDT 2020. Contains 335729 sequences. (Running on oeis4.)