

A287862


Numbers n with a record size of the largest Carmichael number that can be generated from them using Erdős's method.


1



36, 60, 108, 112, 120, 180, 216, 360, 540, 840, 1200, 1620, 2016, 2160, 2520, 3360, 3780, 4800, 5040, 6480, 7560, 8400, 10080, 12600, 15120, 25200
(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.
The corresponding largest Carmichael numbers are 63973, 172081, 188461, 278545, 852841, 31146661, 509033161, 416937760921, ...


LINKS



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 = {}; cmax = 0; 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 = Max[c, c1]], {j, 1, Length[ps]}];
If[c > cmax, cmax = c; AppendTo[a, n]], {n, 1, 1000}]; a


CROSSREFS



KEYWORD

nonn,more


AUTHOR



STATUS

approved



