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