A328935 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).

294409, 399001, 488881, 512461, 1152271, 1461241, 3057601, 3828001, 4335241, 6189121, 6733693, 10267951, 14676481, 17098369, 19384289, 23382529, 50201089, 53711113, 56052361, 64377991, 68154001, 79624621, 82929001, 84350561, 96895441, 115039081, 118901521, 133800661

Offset: 1

Author

Amiram Eldar, Oct 31 2019

Keywords

• nonn

Comments

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

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

Comment from Jeppe Stig Nielsen, Apr 21 2021: (Start)

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.

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)

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Mathematics of Computation, Vol. 71, No. 238 (2002), pp. 883-908.

Crossrefs

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

Programs

Mathematica

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]

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

Formula

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