cp's OEIS Frontend

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

%I A287862 #11 Sep 03 2017 22:06:14
%S A287862 36,60,108,112,120,180,216,360,540,840,1200,1620,2016,2160,2520,3360,
%T A287862 3780,4800,5040,6480,7560,8400,10080,12600,15120,25200
%N A287862 Numbers n with a record size of the largest Carmichael number that can be generated from them using Erdős's method.
%C A287862 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 A287862 The corresponding largest Carmichael numbers are 63973, 172081, 188461, 278545, 852841, 31146661, 509033161, 416937760921, ...
%H A287862 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 A287862 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 A287862 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 A287862 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 A287862 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]}];
%t A287862 If[c > cmax, cmax = c; AppendTo[a, n]], {n, 1, 1000}]; a
%Y A287862 Cf. A002997, A287840.
%K A287862 nonn,more
%O A287862 1,1
%A A287862 _Amiram Eldar_, Sep 01 2017