Problems & Puzzles:
Problems
Problem 33. The extreme
prime triplets
The structure of these triplets were discovered by Chris
Nash related to certain questions about the Carmichael numbers. But in
order to avoid unnecessary repetitions please see the details of the origin of
these prime triplets at the Conjecture
19.
Now the problem is to get larger and larger primes p such that p^2+p-1
and (p^3+p^2-p+1)/2 are also primes.
Specially for larger numbers, and in order to
facilitate the rigorous primality test step, Chris Nash has
suggested that is better (but not strictly necessary) that p to be of the following forms: or
P=k*p#+1 or P=k*p#-1. Why? "if P PLUS 1 can be factored, the primes are ...
provable... since q+1 = P(P+1) and r-1 =(P+1)^2. (P-1)/2..." A
similar reasoning can be done if p MINUS 1 can be factored or, at least
factored enough.
Just to pose an interesting starting point, try to get a larger triplet
than this one I got recently (31/05/2000) in no more than 12 hours of
search for the proper k given the primorial 419# as a fixed quantity:
P = 1820095*(419#)-1 (is strong-pseudo-prime, 176 digits )
q = p^2+p-1 (is strong-pseudo-prime, 351 digits)
r = (p^3+p^2-p+1)/2 (is strong-pseudo-prime, 526 digits)
This prime triplet provides a Carmichael number C3=P*q*r
having 1051 digits.
Challenge:
Get larger extreme triplets
Solution
Chris Nash has produced (9/6/2000) a larger
extreme triplet with P=70522*499#+1. Twenty four hours later Michael
Bell sent a little bit large one extreme triplet, in this case, with
P=2924634*500#+1. Michael says that the C3 produced with his P
prime has 1276 digits.
***
Michael Bell wrote the 12/06/2000:
"Hi, It didn't take as long as I thought it might, I've found
6 p's that give C3's of over 2000 digits, the largest being: p=9896514*
800#+1 which is 337 digits and gives a C3 of 2020 digits"
and again, the 16/06/200:
"...due to an
incredible amount of luck, I will: If p=70778*1000#+1 (421 digits), then
we produce a 2521 digit C3. I found this while doing a quick test on
some new sieving code that should allow me to go to a p of at least 600
digits - who knows, maybe further if I get this lucky again!"
One more email arrived the 19/06/2000:
"Well - despite (slightly) faulty sieving code
(it handled the case when r has 3 factors
incorrectly), I've found a huge C3 of 3661 digits! p=5927222*1450#+1 has
611 digits (although, due to the bug, this may not be the lowest for
k*1450#+1 form)
The sieve code is now fixed and faster, so even larger cases
should be possible (though maybe not right now, this one took nearly 3
days). Many thanks go to Chris Nash who has been very helpful,
giving me loads of pointers on how to write the sieve program, and also
for pfgw (without which I don't think I would even have attempted
a p that big)".
***
Phil Carmody wrote (Jan, 2007):
I found the following maximal 3-carmichaels back in April 2004, but
forgot to
tell anyone!
3 components and carmichael number length enclosed below:
> 6038310301574*1996995^250+1
> (6038310301574*1996995^250+1)^2+(6038310301574*1996995^250+1)-1
>
((6038310301574*1996995^250+1)^3+(6038310301574*1996995^250+1)^2-(6038310301
> 574*1996995^250+1)+1)/2
1588, 3176, 4764 = 9527
> 22853927331996*1996995^250+1
> (22853927331996*1996995^250+1)^2+(22853927331996*1996995^250+1)-1
>
((22853927331996*1996995^250+1)^3+(22853927331996*1996995^250+1)^2-(22853927
> 331996*1996995^250+1)+1)/2
1589, 3177, 4766 = 9531
> 51108475458474*1996995^250+1
> (51108475458474*1996995^250+1)^2+(51108475458474*1996995^250+1)-1
>
((51108475458474*1996995^250+1)^3+(51108475458474*1996995^250+1)^2-(51108475
> 458474*1996995^250+1)+1)/2
>
> 54863435130068*1996995^250+1
> (54863435130068*1996995^250+1)^2+(54863435130068*1996995^250+1)-1
>
((54863435130068*1996995^250+1)^3+(54863435130068*1996995^250+1)^2-(54863435
> 130068*1996995^250+1)+1)/2
>
> 60220696088452*1996995^250+1
> (60220696088452*1996995^250+1)^2+(60220696088452*1996995^250+1)-1
>
((60220696088452*1996995^250+1)^3+(60220696088452*1996995^250+1)^2-(60220696
> 088452*1996995^250+1)+1)/2
all 1589, 3178, 4767 = 9533
> 65506387867086*1996995^250+1
> (65506387867086*1996995^250+1)^2+(65506387867086*1996995^250+1)-1
>
((65506387867086*1996995^250+1)^3+(65506387867086*1996995^250+1)^2-(65506387
> 867086*1996995^250+1)+1)/2
1589, 3178, 4767 = 9534
***
|