login
Imprimitive Carmichael numbers: Carmichael numbers m such that if m = p_1 * p_2 * ... *p_k is the prime factorization of m then g(m) = gcd(p_1 - 1, ..., p_k - 1) > sqrt(lambda(m)), where lambda is the Carmichael lambda function (A002322).
5

%I #14 May 09 2021 10:10:46

%S 294409,399001,488881,512461,1152271,1461241,3057601,3828001,4335241,

%T 6189121,6733693,10267951,14676481,17098369,19384289,23382529,

%U 50201089,53711113,56052361,64377991,68154001,79624621,82929001,84350561,96895441,115039081,118901521,133800661

%N Imprimitive Carmichael numbers: Carmichael numbers m such that if m = p_1 * p_2 * ... *p_k is the prime factorization of m then g(m) = gcd(p_1 - 1, ..., p_k - 1) > sqrt(lambda(m)), where lambda is the Carmichael lambda function (A002322).

%C Granville and Pomerance separated the Carmichael numbers into two classes, primitive and imprimitive, according to whether g(m) <= sqrt(lambda(n)) or not.

%C They conjectured that most Carmichael numbers are primitive and most 3-Carmichael numbers (A087788) are imprimitive.

%C Comment from _Jeppe Stig Nielsen_, Apr 21 2021: (Start)

%C In cases n = 1, 3, 5, 7, 8, 10, 14, 15, 19, 20, ..., there exists a primitive Carmichael number in the same "family" (Carmichael numbers that share the ratio (p_1-1):(p_2-1):...:(p_k-1) belong to the same family). However, in the remaining cases, the entire family consists of imprimitive Carmichael numbers.

%C There can be more than one primitive Carmichael number in a family. For example, both Carmichael numbers 5828853661 and 965507554621 are primitive, and are in the family 1:3:6:70. The first imprimitive Carmichael number in the family 1:3:6:70 is a(1639)=59610715093021. (End)

%H Amiram Eldar, <a href="/A328935/b328935.txt">Table of n, a(n) for n = 1..10000</a>

%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.

%F Terms m of A002997 such that A258409(m) > sqrt(A002322(m)).

%t aQ[n_] := Length[(f = FactorInteger[n])] > 2 && Max[f[[;; , 2]]] == 1 && Divisible[n-1, (lambda = LCM @@ (f[[;; , 1]] - 1))] && GCD @@ (f[[;; , 1]] - 1) > Sqrt[lambda]; Select[Range[4*10^6], aQ]

%o (PARI) isA328935(m)=f=factor(m);!(issquarefree(f)&&omega(f)>2)&&return(0);p=f[,1]~;r=apply(x->x-1,p);foreach(r,x,(m-1)%x!=0&&return(0));g=gcd(r);a=r/g;g>lcm(a) \\ p, g, and a are like in Granville & Pomerance, _Jeppe Stig Nielsen_, Apr 21 2021

%Y Cf. A002322, A002997, A087788, A258409, A335584.

%K nonn

%O 1,1

%A _Amiram Eldar_, Oct 31 2019