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

*** Records   |  Conjectures  |  Problems  |  Puzzles 