Question about a program generating palindromic prime numbers
I'm a programmer and software designer. I'm definitely not a mathematician and my maths is quite basic.
One of my colleagues challenged me to generate a palindromic prime number, at least 1000 digits long and using only the digits 1 and 7.
I wrote a 1-minute Java hack built around an instinctive and faulty conjecture: let's try to build a small palindromic prime number first, and then randomly add the same digit before and after, hoping to get another one. It sounds a bit of childish, but the whole thing was just a game.
Well with my surprise it "worked", or kind of. Obviously, if you take a palindromic prime and you append and prepend a digit (1, 3, 7 or 9), you don't get another palindromic prime. But if you continue adding random digits before and after, it seems you eventually reach another palindromic prime, and this happens... quite often.
With this tottering and pointless method, I managed to win the bet and generate this number, in about 10 minutes:
71771177771711117177717711111717117111711777117717117117777117711117177711177777171777717111771777717777111711717711177711177771771717117777177777777771777111177717177777771177177717777171177771771111717177777117717117711777177771177111711777711717711717771177771711117117171171771111771717777711177171171771717111117711111711177717171117777777111171777717777117117711177111711771777771111777171117711717711117777117111711177771777111777111777117777171711711717111771117777111777171111711111111717177171111117111771117177777771711717171171171117171171177111171777117717771177771171717111771111117777177771111117711171717117777117771771177717111177117117171117117117171711717777777171117711171111117177171711111111711117177711177771117711171711711717177771177711177711177717777111711171177771111771711771117177711117777717711711177111771171177771777717111177777771117171777111711111771111171717717117177111777771717711117717117171171111717777117771711771711777711711177117777177711771171771177777171711117717777117177771777177117777777171777111177717777777777177771171717717777111777111771711711177771777717711171777717177777111777171111771177771171171771177711711171171711111771777171111717777117717
It is palindromic, it is 1199 digits long, and seems to be prime or, at least, Mathematica's PrimeQ tells so, but I didn't test it with a deterministic method.
This is the program:
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class PalindromicPrimeFinder implements Runnable {
/**
* Test main
*/
public static void main(String[] args) {
int maxDepth = 50;
int testCertainty = 20;
Character[] digitsFinal = { '1', '7' }; // should be a subset of {1, 3, 7, 9}
Character[] digitsAll = { '1', '7' };
PrintWriter writer = new PrintWriter(System.out);
PalindromicPrimeFinder finder = new PalindromicPrimeFinder(
maxDepth, testCertainty, digitsFinal, digitsAll, writer);
finder.run();
}
private final Random random = new Random();
private final int maxDepth;
private final int testCertainty;
private final Character[] digitsFinal;
private final Character[] digitsAll;
private final PrintWriter writer;
/**
* Constructor.
*
* @param start The starting number
* @param maxDepth Max search depth
* @param testCertainty Certainty of primality test
* @param digitsFinal final digits (subset of {1, 3, 7, 9})
* @param digitsAll all digits
*/
public PalindromicPrimeFinder(int maxDepth,
int testCertainty, Character[] digitsFinal, Character[] digitsAll,
PrintWriter writer) {
this.maxDepth = maxDepth;
this.testCertainty = testCertainty;
this.digitsFinal = digitsFinal;
this.digitsAll = digitsAll;
this.writer = writer;
}
/**
* Run method
*/
@Override
public void run() {
String start = ""+digitsFinal[random.nextInt(digitsFinal.length)];
findPalindromicPrime(start, 0);
}
/**
* Worker recursive method
* @param number current number
* @param depth current depth
*/
private void findPalindromicPrime(String number, int depth) {
for (char digit : digitsFinal) {
String nextNumber = digit + number + digit;
if (new BigInteger(nextNumber).isProbablePrime(testCertainty)) {
writer.println("New prime [length=" + nextNumber.length()
+ "]: " + nextNumber + "\n");
writer.flush();
findPalindromicPrime(nextNumber, 0);
return;
}
}
if (depth > maxDepth) {
return;
}
List<Character> digitsAll_shuffled = new ArrayList<Character>(
Arrays.asList(digitsAll));
Collections.shuffle(digitsAll_shuffled, random);
for (char digit : digitsAll_shuffled) {
String nextNumber = digit + number + digit;
findPalindromicPrime(nextNumber, depth + 1);
}
}
}
Actually, sometimes my program can generate numbers like that one in a snap, other times it just fails or hangs. If it hangs for hours, you have to interrupt it (CTRL+C).
I'm interested, out of idle curiosity, in knowing why it works (when it does) and if it uses some known feature of palindromic primes. I'm quite unlearned in mathematics, but I'm a curious person.
EDIT: you can read my own answer.
EDIT2: I created a multi-threaded program that gives up after a timeout. Check it out if you have spare time. :)
Finding palindromic primes is not very hard, but rather proving them and labeling them as Prime instead of PRP (Probable Prime) is the hard job. You can find the list of world's largest palindromic primes here
And the reason why proving most of them is time-consuming lies in odd digits in them. That is if you could express your number as $k*2^n +- 1$ then proving is much easier using several algorithms out there, but since palindromic primes usually have more odd digits than $0$ ones, then their finding procedure becomes too long.
As an example, the best palindromic number is of the following form (the smallest one is $101$):
$100000000000...00000000000000001$
It can be easily expressed as $5^n*2^n + 1$ and therefore easy to do primility test. Occurance of a non-zero digit at any position, cause the power of $2$ in the formula to be decreased. So the best place for such a digits is near the center of number.
Again as an example where power of $2$ is near $n/2$
$100000000000...007700...00000000000000001$
Updated
And for generating the number you can build a simple formula like the following in Mathematica:
Palindromic[n_, digit_, position_] :=
(10^n - 1)/9 + (digit - 1) (10^position + 10^(n - position - 1))
In[1]:= Palindromic[20, 7, 9]
Out[1]= 11111111177111111111
Actually, I've found a reason, and it is so stupid that I'm sorry having wasted your time.
The reason is simple as that: for a relatively small number of digits, it appears that palindromic prime numbers are not so scarce!
I was able to find very long palindromic primes just generating them randomly.
I'm satisfied of this conclusion. It's plain and simple: it is no special feature of palindromic primes, it's just chance. :)
I was somewhat biased by the fact that prime numbers are "special" (also for people like me, who is not a mathematician) and palindrome are "special" as well, so primes palindrome should be very rare. But this is not so true.
Comments and explanations from competent people, if needed, are very welcome. :)