PalPrimes

Computer Science Level 4

A palindromic-prime or PalPrime is a prime number that is also a palindrome.The first few PalPrimes are 2, 3, 5, 7, 11, 101, 131, 151, 181..... Let S be the sum of the digits of the largest PalPrime N such that N<10^9 . What is the value of S ?

The answer is 70.

2 solutions

Arulx Z
Sep 7, 2015

EDIT

Here is a much more efficient way.

def prime(n): # primality test
    if n < 2 or not n & 1: return False
    if n == 2: return True
    for x in range(3, int(n **0.5) + 1, 2):
        if n % x == 0: return False
    return True

for x in xrange(9999, 1000, -1): # generate digits abcd
    for y in xrange(0, 9): # generate digit e
        if prime(int(str(x) + str (y) + str(x)[::-1])): # combine and reverse the digits to form abcdedcba
            sum(int(x) for x in (str(x) + str (y) + str(x)[::-1]))] # print the sum of digits if it's prime

This code is created to only search for 9 digit palindromes. To search for smaller length palindromes, slight modifications need to be made.

One more optimization could be made, which is that when first digit of x is even, we can skip 1000 counts. Note: If first digit is even, then in my code last digit will also be even. But there are no even primes apart from 2.

It only takes 21 iteration to find the answer.

Old Answer

Here is a basic brute force way to do it. For obvious reasons, I start at $10^9$ and then loop backward. I also only test for odd numbers as all even numbers except 2 are composite.

Here's the code -

>>> def prime(n):
        if n < 2 or not n & 1: return False
        if n == 2: return True
        for x in range(3, int(n **0.5) + 1, 2):
            if n % x == 0: return False
        return True
>>> for x in xrange(10 ** 9 - 1, 181, -2):
        if str(x) == str(x)[::-1] and prime(x):
            print x
            break
999727999
>>> sum(int(x) for x in str(999727999))
70

Moderator note:

Can you explain what you mean by "A much better way would be to create a palindrome generator using a combinatorics approach."?

And if so, how would we implement that?

Can you explain what you mean by "A much better way would be to create a palindrome generator using a combinatorics approach."?

And if so, how would we implement that?

Calvin Lin Staff - 5 years, 9 months ago

Let $n$ be equal to 999727999. When I'm using my way, I'm bruteforcing all the way down to $n$ . So I'm checking all numbers between $10^9$ and $n$ if they are palindromes and if they are, then I'm testing if they are primes. But this all search is not reasonable because 9-digit palindromes follow a certain pattern - $\overline { abcdedcba }$ where $a,b,c,d,e$ represent not necessarliy distinct digits and $a \neq 0$ . Now, with my code, I need to test for $10^9 - 999727999 = 272001$ numbers for prime and palindromes. But if I made a palindrome generator and start generating palindromes in reverse from $10^9$ , then I just need to check for 27 numbers.

I'm not sure about how am I going to implement a palindrome generator but I think it will be using a similar mechanism to a cryptarithm solver (ie, itertools in python) I'm currently working on the code. I'll post my code when I'm done.

Arulx Z - 5 years, 9 months ago

Well, like you mentioned, all that matters is the first 5 digits. So, you can just do a for loop, counting down from 99999, and given $\overline{abcde}$ to test $\overline{abcdedcba}$ for primality.

Calvin Lin Staff - 5 years, 9 months ago

@Calvin Lin – I posted my code (I posted it long time ago. Sorry for late notice)

Arulx Z - 5 years, 7 months ago

Bill Bell
Sep 10, 2015

Good fun! Counting backwards palindromically.

from gmpy2 import is_prime

k=99999
while True:
    k-=1
    str_k=str(k)
    rev_str_k=str_k[::-1]
    for i in range(-1+len(rev_str_k),0,-1):
        if rev_str_k[i]!='9':
            break
    palindrome_str=str_k[:-i+len(str_k)]+rev_str_k
    palindrome=int(palindrome_str)
    if is_prime(palindrome):
        print sum(map(int,list(palindrome_str)))
        break

Can you please explain your code?

Aryan Gaikwad - 5 years, 9 months ago

My pleasure.

The idea behind it is this. We want 9-digit palindromes in the sequence 999989999, 999979999, ..., 999222999, ... and so on. We notice that if we start with 99999 and subtract 1 repeatedly we obtain the first five digits of the numbers in this sequence. At any point in this process the digits we can calculate how many digits have been changed by subtraction on the basis of the number of 9 digits that remain. And knowing how many 9 digits remain unchanged tells us how to pack up a palindrome.

For instance, take 99929. Three unchanged 9s remain. This means that we need four digits reversed to make the corresponding palidrome, 999292999.

Line 5 calculates the succession of smaller and smaller 5-digit numbers. Line 6 calculates the strings corresponding to these numbers, and line 7 calculates these strings in reverse. Lines 8 through 10 calculate the number of unchanged 9 digits. Line 11 packs the palindrome as a string. Line 12 calculates the palindrome as an integer. Lines 13 through 15 print the palindrome if it is a prime and break out of the while loop.

Bill Bell - 5 years, 9 months ago

Great explanation!

Arulx Z - 5 years, 7 months ago

@Arulx Z – Ah! Thanks very much.

Bill Bell - 5 years, 7 months ago

PalPrimes

The answer is 70.

2 solutions

This code is created to only search for 9 digit palindromes. To search for smaller length palindromes, slight modifications need to be made.

Moderator note:

0 pending reports