# Carmichael numbers with given least prime factor

Jack Brennen jb at brennen.net
Tue Jul 1 11:55:09 CEST 2008

```Maximilian Hasler wrote:
> I have some trouble to find an index entry for this :
> Is the following sequence (or some equivalent variant) present :
>
> A??? Number of 3-factor Carmichael numbers having prime(n) as least factor
>
> (It is known that there is only a finite number of C's with k factors,
> once k-2 factors are given,
> but I don't know if it is straightforward to compute.)
>

To compute this sequence, I think this PARI code works:

tryab() =
{
r=(p*B-p+A*B-B)/(A*B-p*p);
q=(A*r-A+1)/p;
if(q>p&&\
r>q&&\
denominator(q)==1&&\
denominator(r)==1&&\
isprime(q)&&\
isprime(r)&&\
(p*q*r)%(p-1)==1,V=concat(V,[p*q*r]));
return(q>p);
}

try() =
{
V=[];for(A=1,p-1,B=ceil((p^2+1)/A);while(tryab(),B+=1));
print(length(V)," ",p," ",vecsort(V));
}

p=2;while(1,try();p=nextprime(p+1));

That could probably be cleaned up a bit, but it's late
and I'm tired.  :)

The sequence seems to start: 0,1,3,6,0,5,2,2,1,2,7,...

I ran the program for a few minutes, and the largest
Carmichael count I found was for p=2221.  There are
29 three-factor Carmichael numbers with least factor
equal to 2221.

Note that the primes related to the zeroes in this
sequence are in A051663, although there are two problems
with that sequence.  The description is wrong -- it
should probably say "is *no* Carmichael".  Also, the
prime 2 should probably be in the sequence, as there is
no Carmichael number of the form 2qr.

Jack

```