|
%I #13 Sep 03 2017 22:05:57
%S 36,120,180,240,360,540,720,1080,1200,1260,1680,2160,2520,3780,5040,
%T 7560,10080,15120,25200
%N Numbers n with a record number of Carmichael numbers that can be generated from them using Erdős's method.
%C 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.
%C The corresponding number of generated Carmichael numbers are 2, 3, 4, 8, 11, 16, 26, 30, 36, 57, 79, 204, 466, 610, 7253, 9778, 58058, 1244090, 5963529.
%H Paul Erdős, <a href="https://renyi.hu/~p_erdos/1956-10.pdf">On pseudoprimes and Carmichael numbers</a>, Publ. Math. Debrecen 4 (1956), pp. 201-206.
%H Andrew Granville, <a href="http://www.dms.umontreal.ca/~andrew/PDF/Notices1.pdf">Primality testing and Carmichael numbers</a>, Notices of the American Mathematical Society, Vol. 39 No. 6 (1992), pp. 696-700.
%H Andrew Granville and Carl Pomerance, <a href="https://doi.org/10.1090/S0025-5718-01-01355-2">Two contradictory conjectures concerning Carmichael numbers</a>, Mathematics of Computation, Vol. 71, No. 238 (2002), pp. 883-908.
%e 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.
%t 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++], {j, 1, Length[ps]}];
%t If[c > cmax, cmax = c; AppendTo[a, n]], {n, 1, 1000}]; a
%Y Cf. A002997, A287840.
%K nonn,more
%O 1,1
%A _Amiram Eldar_, Sep 01 2017
|
