- "I was lazy and did not use binary indexing for products of primes."

Yes, I used long long int (8bytes) to store the residue (L<2^63), and int (4

bytes) to store the offset of the prime divisors (there were 26 primes in P

so it was enough).

Searching for Carmichael number of order 3 would be very hard:

by the following quick code:

generatesmooth(n)=T=1;forprime(p=2,n,q=p;while(q*p<=n,q*=p);T*=q);return(T)

this is generating super smooth numbers, but for example for n=1000 this is

giving only P(3,T)~225 numbers

, the last 3 of them in order what I have found are:

153572717

217815289

264982051

So there are very few larger primes in P(3,T) set. Say there are another 25,

then the expected number of solutions are

2^250/eulerphi(generatesmooth(1000))=3*10^(-357), and it would require about

2^200 multiplications/divisions (using man-in-the middle algorithm #P=25,

#Q=200). Obviously using smaller n gives larger but still very small

probability to find a 3 order number. So we have to increase the value of n:

For example: L=generatesmooth(20000) gives P(L,3)>30000 primes and this

means that it generates many Carmichael numbers of order 3:

2^30000/eulerphi(L)>>1. But to find even one solution using this L value is

still very hard.

[Non-text portions of this message have been removed] - In a talk

http://alumnus.caltech.edu/%7Ehowever/talks/FortCollins.pdf

given in December 2006, Everett Howe posed this "Open Problem":

"What are the first 3 Carmichael numbers of order 2?"

Here is the answer:

443372888629441

39671149333495681

842526563598720001

David Broadhurst - --- In primenumbers@yahoogroups.com,

"David Broadhurst" <d.broadhurst@...> wrote:

> "What are the first 3 Carmichael numbers of order 2?"

Richard Finch calls these

>

> 443372888629441

> 39671149333495681

> 842526563598720001

"unusually strong Lucas-Carmichael-minus" (uLC-) numbers,

with p^2-1|N-1, for every prime p|N. See:

http://www.chalcedon.demon.co.uk/rgep/p20.pdf

I found the third of these by mining Richard's file of

Carmichael numbers between 10^17 than 10^18.

The first two had already been noted in

http://www.chalcedon.demon.co.uk/rgep/cartable.html

Richard classified

582920080863121 = 41 * 53 * 79 * 103 * 239 * 271 * 509

as a "strong", but not "unusually strong",

Lucas-Carmichael-minus number

since in this case both p-1 and p+1

divide N-1, for each prime p|N, but p^2-1

does not divide N-1 in the cases p = 79, 239, 271,

where p^2 = 1 mod 2^5

whilst N = 17 mod 2^5.

If we ask merely that p-1 and (p+1)/2 divide N-1,

then the following 3 numbers also occur, for N < 10^18:

28295303263921

894221105778001

2013745337604001

making 7 in all, of which only

842526563598720001

= 17 * 61 * 71 * 89 * 197 * 311 * 769 * 2729

occurs for 10^18 > N > 10^17.

Finally, I remark that Richard found precisely one

"unusually strong Lucas-Carmichael-plus" (uLC+) number,

with p^2-1|N+1, for prime p|N and N < 10^13, namely

79397009999 = 23 * 29 * 41 * 43 * 251 * 269.

David