Snakes on a prime

The challenge is to find and print the largest palindrome prime under 1000.

def reverse(integer):
    result = 0

    while (integer != 0):
        result *= 10
        result += (integer % 10)
        integer //= 10
    return result

def is_palindromic(integer):
    return integer == reverse(integer)

def produce_sieve(limit):
    sieve = [True] * limit
    sieve_length = len(sieve)

    for prime in range(2, sieve_length):
        if (sieve[prime]):
            for composite in range(prime * prime, sieve_length, prime):
                sieve[composite] = False
    return sieve

def compute_largest_prime_palindrome_below(limit):
    sieve = produce_sieve(limit)
    for prime in range(limit - 1, 1, -1):
        if (sieve[prime] and is_palindromic(prime)):
            return prime
    raise ValueError('No primes found')

if __name__ == "__main__":
    print(compute_largest_prime_palindrome_below(1000))

Introduction

It took me a good 30 hours to figure out this solution. However when one sees the drastic speed increases it produces it might have been worth it. Before I go into the performance optimizations I will give you some advice on the code you have written

-
Your naming scheme is for the most part good. Good variable names should be descriptive, distinct and succinct in that order. You have nailed the first two, however I would try to also not make the names too long as it will hurt the readability of your code. The function name compute_largest_prime_palindrome_below could just as well be named largest_prime_palindrome without being less clear. Similarly is_palindromic could have been is_palindrome.

-
You should include a https://www.python.org/dev/peps/pep-0257/ at the start of your code. You can never start too early with good documentation. Ask yourself are you sure you will understand your code a year down the road, what about 5 or 10?

-
The while (integer != 0): is superfluous. Python treats 0 as false, so you could have written while integer:. I will not comment on the parenthesis, since you have already mentioned these.

-
You still have inconsistent spacing in your code. This symbolizes to me a lack of detail.

Improving your algorithm

You use a very simple prime sieve to find the primes. However there exists much faster primesieves out there. Here is a large list of sieves, pick your favorite. My favorite is the primesieve library. Here is a description of the Python implementation. If you are on windows this can be installed from the command window using

pip install primesieve

Your code can now be written as.

from primesieve import generate_primes

def is_palindromic(integer):
    return integer == reverse(integer)

def largest_prime_palindrome_2(limit):
    for prime in reversed(generate_primes(limit)):
        if prime and is_palindromic(prime):
            return prime
    raise ValueError('No primes found')

This gives me a speed increase of about \$40\$ times. However we can do slightly better than this. One problem with your code is that you use Memoization and store all the primes up to $N$. For large values this takes up a lot of memory. If you try \$10^9\$ or \$10^{11}\$ you can be sure that your computer will quickly run out of memory. An alternative is to use a prime generator instead of creating all the values.

from primesieve import Iterator

def is_palindrome(num):
    num_str = str(num)
    return num_str == num_str[::-1]

def biggest_palindrome_prime_faster(limit):
    it = Iterator()
    it.skipto(limit)
    prime = it.previous_prime()
    while prime > 0:
        if is_palindrome(prime):
            return prime
        prime = it.previous_prime()

For \$10^5\$ this gives a \$400\$ times speed increase over your implementation for \$10^5\$. The code should be self explanatory, but feel free to ask if you have any questions. You can also check out the package documentation.

New algorithm

Your algorithm iterates over the primes and then check if it is palindrome.
However we can switch this around and rather iterate over the palindromes and check for primality. There are many advantages with this method.

• We only have to iterate over palindromes with odd length. All palindromes with even length are divisible by \$11\$ and hence not prime.

• We can skip palindromes ending in a even digit or \$5\$, since these are not primes

• You do not run out of memory, since we generate palindromes on the fly.

• By starting at the largest values we can stop once we find a prime.

• Checking primality is much faster than creating a list of all primes.

As an example I can show that a \$4\$ digit palindrome, will be divisible by \$11\$.
Any palindrome of length \$4\$ can be written as \$abba\$. This is the same as

$$
1000a + 100b + 10b + a = 1001a + 110b = 11 (91a + 10b)
$$

The more general proof is included above. So if we have a number with even digits we know there will be no solutions. Any odd digit palindrome can be written on the form

$$
[\text{digit}] \ + \ \text{second} \ + \ [\text{middle}] \ + \ \text{second_reverse} \ + \ [\text{digit}]
$$

No prime > 2 can end in [2, 4, 6, 0, 5]. So the first digit can only be [1, 3, 7, 9], since this is also the last digit. The middle can be any number in [0-9]
and the \$\text{second}\$ can be any number with a certain length. Say our number has n digits.
Then \$\text{second}\$ has to have a length of \$\text{floor}(n/2)-1\$.

Take \$5\$ for instance, then we use \$1\$ digit in front, \$1\$ in the back and one in the middle. This leaves \$5-3 = 2\$ for the two second numbers, so each second has to have \$1\$ digit. Similarly \$\text{floor}(n/2) -1 = 2 - 1 = 1$.

To generate numbers with n digits, we can use the Cartesian Product. This can be imported from the itertools module. As an example

```
print(list(product([1,2,3], repeat = 2)))
[(1, 1), (1, 2), (1, 3), (

StackExchange Code Review Q#133630, answer score: 9