Re: Carmichael numbers of order 2
- "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:
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:
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
given in December 2006, Everett Howe posed this "Open Problem":
"What are the first 3 Carmichael numbers of order 2?"
Here is the answer:
- --- In firstname.lastname@example.org,
"David Broadhurst" <d.broadhurst@...> wrote:
> "What are the first 3 Carmichael numbers of order 2?"Richard Finch calls these
"unusually strong Lucas-Carmichael-minus" (uLC-) numbers,
with p^2-1|N-1, for every prime p|N. See:
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
582920080863121 = 41 * 53 * 79 * 103 * 239 * 271 * 509
as a "strong", but not "unusually strong",
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:
making 7 in all, of which only
= 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.