Today’s the first day of Twin Cities Code Camp 12. It’s been great so far, but I decided to make a separate blog post just for this one thing. While in line during registration, I noticed some people doing some recruiting. They wanted us to send an email to [The Answer to This Problem]@theirwebsite.com, basically. What was the problem?

What is the first seven-digit prime palindrome in pi? So, while looking at the digits of pi, what is the first sequence of seven of them that are both prime (not divisible by anything but one and itself) and a palindrome (the characters are the same both backwards and forwards).

Well, the way I am, I just wanted to solve it just to solve it. So I did (I think). Feel free to:

A) Tell me if I’m wrong and

B) Tell me if my code is suboptimal

My code takes about nine seconds to run on my machine. That sounds slow, but then again, it’s doing a LOT. But again: feel free to let me know if it’s not efficient. I’ll show blocks of code and explain them.

Here’s the beginning of the method that does all the work (it’s called on a button click. It fills in a text box with the answer):

function GetEmailAddress()
{

var palindromes = [];
var indexString;
var reverseIndexString;
var primePalindromes = [];
var piIndices = [];
var lowestIndex = 4294967295;
var savedIndex = 0;

We’re going to have some palindromes, some prime palindromes, the indices of the locations of the prime palindromes within the digits of pi and a few placeholder variables along the way.

// Make seven-digit palindromes instead of checking all seven-digit numbers
// Get all three digit numbers, filter them, reverse them and plop one digit between the original and the reversed
for (var index = 100; index < 999; index++)
{

// If the FIRST digit is divisible by two, in a palindrome, obviously the LAST digit is, too, so skip it
if(parseInt(index.toString()[0]) % 2 === 0)

index += 100;

indexString = index.toString();
var reverseIndexString = indexString.split(”).reverse().join(”);
for (var middleDigit = 0; middleDigit < 10; middleDigit++)
{

palindromes.push(parseInt(indexString + middleDigit + reverseIndexString));

}

}

The point here is to find all the palindromes first instead of trying to find the prime numbers first. I think this filters it down from nine million numbers (seven digit numbers) to 5,000 (I didn’t check this). The way I do this is that I know we’re making seven-digit palindromes, right? So in reality, the first three digits are the same as the last three, just reversed. The middle digit doesn’t matter. So… just build three digit numbers, add any number and then reverse the original three numbers. While doing so, we can filter out anything that STARTS with an even number. Because, since it’s a palindrome, if it STARTS with an even number, it ENDS with an even number. No prime number does this. That’s why we jump from 200 to 300, from 400 to 500, etc. That brings us down to five hundred numbers (again, these are all guesses. I didn’t debug this code because it just worked right away). Multiply that by ten (one per middle digit, 0-9) and you get 5,000. Instead of testing 9,000,000 numbers for palindromes, we’re only testing 5,000. Next block of code:

// Now we only have 5,000 numbers from a possible 9,000,000 if we just checked all seven-digit numbers
// Find all the prime numbers
for(var index = 0; index < palindromes.length; index++)

if(IsPrime(palindromes[index]))

primePalindromes.push(palindromes[index]);

I run all of these through my IsPrime method (I’ll show it after this paragraph). I tried to cheat on this part, but every algorithm I found was extremely inefficient. So here’s mine, from scratch (all my code is):

function IsPrime(number)
{

var middle = Math.floor(number / 2);
// We can start from 3 because everything’s divisible by one and we know we don’t have any even numbers from previous filtering,
// also allowing us to skip every other number
for(var index = 3; index <= middle; index += 2)

if(number % index === 0)

return false;

return true;

}

The algorithms I found were horrific. By comparison, most weren’t smart about where to start or stop evaluating. I started at three because everything’s divisible by one and I’ve done some filtering already to make sure I don’t have any even numbers like two. Also, I’m not doing a ++ in the third clause of my for loop. I’m doing += 2. I’m skipping the even numbers. The last bit of optimization is the immediate return of false if we find out it’s not a palindrome. For some weird reason, some algorithms just saved the value, continued to check against all other possible multiples and then returned the saved value.

The next bit of code was setting a pi variable… I’m not going to post it because it’s thousands and thousands of digits of pi. I put it in a string (don’t include “3.”) so I could do an indexOf on each of the prime numbers I found in the previous step within the pi string. So here’s the last block of code:

// Find the first prime palindrome
for(var index = 0; index < primePalindromes.length; index++)
{

piIndices[index] = pi.indexOf(primePalindromes[index].toString());
if(piIndices[index] < lowestIndex && piIndices[index] > -1)
{

lowestIndex = piIndices[index];
savedIndex = index;

}

}

document.getElementById(‘emailAddress’).value = primePalindromes[savedIndex];

}

So here, we’re running through all the primePalindromes to find the index of each of them within the pi string. If it’s not -1 (meaning, it’s actually in the string), then I save its index if it’s lower than the last one I saved. After that, I populate the textbox with the value at this saved, lowest index. Here’s the little bit of HTML if you want to see this working for yourself (you’ll have to slap together all the bits of code – they’re just two Javascript methods, and you’ll need to set var pi = ‘[Many thousands of digits of pi]‘;):

<input type=’text’ id=’emailAddress’ />
<input type=’button’ onclick=’javascript:GetEmailAddress();’ value=’Click me to get the answer’ />

Again, let me know if I’m wrong or if you’ve got a way to optimize it. Mine took about nine seconds, consistently, on my machine.