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,1

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.

Formula

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

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]

Prog

(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

Crossrefs

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

Sequence in context: A354440 A224973 A328664 * A335584 A182206 A178997

Adjacent sequences: A328932 A328933 A328934 * A328936 A328937 A328938

Keyword

nonn

Author

Amiram Eldar, Oct 31 2019

Status

approved