Problems & Puzzles: Puzzles

Puzzle 100. Digital Prime k-tuplets

For sure you know the concept of Prime k-tuplets, especially after the well known good work of Tony Forbes who maintains the records in his site. There you’ll find not only the records but also the basics concepts needed here.

Let’s summarize the Forbes ideas up to the Quadruplets:

 k Name Structure of the primes 2 Twins p, p+2 3 Triplets p, p+2, p+6 4 Quadruplets p, p+2, p+6, p+8

From these ideas I propose to define the “Digital Prime k-tuplets” the following way:

 K Name Structure of the primes 2 Digital Twins (p,q) d(q)=d(p)+2, for all the corresponding digits (*) 3 Digital Triplets (p, q, r) d(q)=d(p)+2 , d(r)=d(p)+6, idem 4 Digital Quadruplets (p, q, r, s) d(q)=d(p)+2 , d(r)=d(p)+6 & d(s)=d(p)+8, idem

* note:  d(p) is certain digit in p

Here are some examples larger than the trivial ones (3, 5 & 7):

* The smallest “digital prime twins”: {31, 53}
* The smallest “digital prime triplet”: {31, 53, 97}
* The smallest “digital prime quadruplet”:
{1010010011, 3232232233, 7676676677, 9898898899}

* The smallest "palindrome digital prime twins": {131, 353}
* The smallest "palindrome digital prime triplet": {131, 353, 797}

Questions:

1
.     Find the smallest palindrome digital prime quadruplet
2
.     Find a moderate larger (around 100 digits?) palindrome digital prime quadruplet
3.   Find a Titanic palindrome digital prime twin

Solution

Question 1:

Patrick De Geest found (9/8/2000) the smallest palindrome digital prime quadruplet:

p=10010000001110010101010101001110000001001
q=32232222223332232323232323223332222223223
r=76676666667776676767676767667776666667667
s=98898888889998898989898989889998888889889

Question 3:

Not still a titanic one, here is an example of 313 digits large palindromic prime digital twin, found by C. Rivera:

1(0)15012732323721(0)1501 &
3(2)15034954545943(2)1503 are primes

Maybe this shows a way to reach to the titanic asked one...

***

Jim Fougeron has solved absolutely (22/1/2002) the questions 2) & 3):

Puzzle 100 question 2)

Two 101 palindrome digital prime quadruplets (All proven prime)

100000000000000000000001010100011111110011101011101011101011100111111100010101/
00000000000000000000001

322222222222222222222223232322233333332233323233323233323233322333333322232323/
22222222222222222222223

766666666666666666666667676766677777776677767677767677767677766777777766676767/
66666666666666666666667

988888888888888888888889898988899999998899989899989899989899988999999988898989/
88888888888888888888889

100000000000000000000001010110010011000100101111101011111010010001100100110101/
00000000000000000000001

322222222222222222222223232332232233222322323333323233333232232223322322332323/
22222222222222222222223

766666666666666666666667676776676677666766767777767677777676676667766766776767/
66666666666666666666667

988888888888888888888889898998898899888988989999989899999898898889988988998989/
88888888888888888888889

Puzzle 100 question 3)

Titanic palindrome digital prime twin

1 (0)497 135707531 (0)497 1 Proven with N-1 proof (PFGW)

3 (2)497 357929753 (2)497 3 Proven with Primo

The titanic twin was not too hard. I created a program to "build" titanic primorials. The program worked with multiple for loops. The outer loop set the first and last character from 1 to 7, the second loop set the next 496 bytes to characters from 0 to 7, the middle loops worked on 1 pair of characters each. there were 4 "pairs" and 1 non pair. Each of these went from 0 to 7. I then converted these to GMP numbers, and gcd that value with 25000#. If that succeeded, then I added 2 to each digit, converted it to a GMP, and did the gcd again. If that also succeeded, then I output the number. It took about 50 minutes of PII 650 time to run a "range" of 917000 total possible values, which reduced to about 6500 when both numbers were "factored" to p=25000. A pfgw run took about 2 hours of PII 400 time.

The first range found no twins, but found 42 prps of the second number (the number output), I ran the program again with 1003 digit numbers. It created almost the exact same number of candidates (around 6500). This range also produced nothing more than "single" prp's. I then ran the range at 1005 digits, and was surprised to get over 13000 candidates (not sure why). Within this range, I copied the pfgw.log file when pfgw passed the 4500 line mark (there were about 30 prp's in the file). The second or third number of this list ended up having the other "twin" being prime.

The nice thing about this was the first number was of the form 10000....000001, a number which cut my proving time in half. Total time used was probably about equivalent to 5 hours Athlon 750 time. If the first number would not have been of that form, the time would have been about 7 hours (2 titanic ECPP proofs)

For The quadruplets, I spent much more time (since my program did not exit correctly. The first was found after about 44.3 million tests, while the second was found after 45.2 million. The program pushed up to 90 million before this morning (when I woke up and stopped it ;). there were no others found. I think my program had a bug, and always put a '0' '1' '0' in the exact center nut (the value 101010001111111001110101110b is 88.6 million, which is twice too high, damn them bugs :) If the program would have exited when it was supposed to (after the first match), then it would have run about 3 hours. The GMP program did 100% of the work, since it was faster than PFGW at running PRP's at the 100 digit length.

Total coding time was probably less than an hour, done over lunch and a break at work.

***

 Records   |  Conjectures  |  Problems  |  Puzzles