# 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. :)

-

## 2 Answers

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. :)

-
I agree with your result, although you should check some of these probable primes completely. Also to confirm your theory, take out the randomisation and just brute force through a few of these to actually count how many you find. BTW Note that you're resetting the depth each time you do find a prime, so as long as you keep finding primes within the next maxDepth pairs of digits added you'll get to very big numbers, thus perhaps explaining the "hangs". –  Mark Hurd Dec 2 '12 at 15:41
It may be a worthwhile experiment to compute the 'success rate' for each length. Then, you could compare the proportion of $n$-digit numbers that are prime to the "odds" that a "random" number of that many digits is prime, given that is not divisible by 2 or 5. That probability is, I believe, roughly $2.5 / \log_e(10^n)$ for $n$-digit numbers. –  Hurkyl Dec 2 '12 at 18:30