Problems & Puzzles: Puzzles
Puzzle 192. Reversible & Digit Complementary Prime Pairs (*)
Two numbers (A,B) are said to be a 'Digit Complementary Prime Pair' (DCPP from now on) if:
Heinz example for K=4 digits in A & B:
A = 4721
If we rule an additional condition for A & B, to be a reversible prime pair, Heinz provide the following example:
A = 3467
This is the kind of numbers we will ask for in this puzzle: DCCP & reversible
Find the smallest K digits example for:
Sudipta Das and Jens Kruse Andersen got both the same solution for K=50 & K=500. Jens Kruse Andersen got the solution for K=1000. Here are the solutions:
This is the approach by Andersen:
I assume the "smallest" solution means the smaller of the two primes is as small as possible. Then it must have the decimal form A=10...0D0...09 where the number D (not a digit) is centered, digit complementary with itself, and as small as possible.
My algorithm: Test all D from 0 to the first solution, i.e. the first time both A and B=reverse(A) are primes. I wrote a C program with the Miracle big integer library. When the first half of D's digits are chosen, the other half is given. A and therefore D always has an even number of digits for the solutions asked. I computed A and B and first trial factored them in parallel: Test if a prime divides any of them, then try the next prime. This prevents "wasted" time on one number when the other has a small factor. If no factor below 65536 is found, I make a single probabilistic test on A, and then B if A is a probable prime. When a probable solution is found I make more tests to give a high certainty. All probable primes were finally proven prime with Primo. The primality certificates were validated by Cert_Val.
The trial factoring part could be much faster by only computing D mod p for each D and prime p and then look up in a precomputed table whether that modulo means A is divisible by p. If not then compute reverse(D) mod p and look up in another table whether p divides B. Assume we want a 50-digit solution and D has 6 digits. Then A=10^49+D*10^27+9. To precompute the tables use this: A mod p = ( (10^49 mod p) + (D mod p)*(10^27 mod p) + 9 ) mod p. B=9*10^49+reverse(D)*10^27+1 is similar. I estimated the simple trial division would find the 1000-digit solution within a few hours and did not bother to implement this fast version. The probable solution took around 1 hour. Primality proofs took 2.5 hours.
Smallest 50-digit solution:
Decimal expansions: A=10000000000000000000001882290000000000000000000009
Smallest 500-digit solution:
Smallest 1000-digit solution:
It would be relatively easy to compute probable solutions with 2000 or more digits but the time required for primality proofs would grow fast.