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 Questions: Find the smallest K digits example for: a) K=50 _____ Solution: 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: A=1*10^49+188229*10^27+9 B=9*10^49+922881*10^27+1 Decimal expansions: A=10000000000000000000001882290000000000000000000009 B=90000000000000000000009228810000000000000000000001 Smallest 500-digit solution: A=1*10^499+278661944238*10^244+9 B=9*10^499+832449166872*10^244+1 Smallest 1000-digit solution: A=1*10^999+411369147996*10^494+9 B=9*10^999+699741963114*10^494+1 It would be relatively easy to compute probable solutions with 2000 or more digits but the time required for primality proofs would grow fast. ***
|
||||||||
|
||||||||
|
|
||||||||
|
