5
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Just reverse with int(str(your_number)[::-1]) \$\endgroup\$ – Jeremy Weirich Jul 1 '16 at 18:46
10
\$\begingroup\$

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), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

Using all of these ideas the final code to iterate over the palindromes can be written as

def largest_palindrome_prime(num):
    digits = len(str(num))-1
    if digits % 2 == 0:
        digits -=1

    middle_digit = map(str, range(9, -1, -1))
    for first in ['9', '7', '3', '1']:
        for perm in product(middle_digit, repeat = digits//2-1):
            second = ''.join(perm)
            for middle in middle_digit:
                palindrome = int(first + second + middle + second[::-1] + first)
                if isprime(palindrome):
                    return palindrome

The first part makes sure that we are rounding down to the closes palindrome with odd length. The isprime function you have to write yourself. If you want you can see my answer on how to write a good prime checker.

This now gives a rough \$ 1500 \$ speed increase over your naive implementation.

Speed comparisons

I ran \$1000\$ runs for all the functions below. The first value is the running time of your implementation. Then I timed how many times faster my implementation was. To be fair I only timed odd powers since there are no prime palindromes of even length as discussed earlier.

 limit        naive   new_sieve    Iterator   palindrome
---------------------------------------------------------
  10^3 |     1.0 ms         7.0      21.277       19.568
  10^5 |    32.0 ms      62.105     457.425     1692.082
  10^7 |  3740.0 ms      89.969    9194.808    34402.762
---------------------------------------------------------

For the lowest values palindrome seem to be performing worse than the Iterator, however it is still a clear improvement.

I then further compared Iterator and Palindrome below. The reason why I did not test yours or the improved sieve is that they take too long to run.

  limit     Iterator   palindrome      ratio
----------------------------------------------
  10^7  |   1.225 ms     0.265 ms      4.629 
  10^9  |  11.973 ms     0.242 ms     49.544
  10^11 |  33.632 ms     0.287 ms    117.119 
  10^13 | 291.021 ms     0.282 ms   1032.654 
----------------------------------------------

Seems like the power does not really matter to the palindrome. Just for fun I tested the palindrome function for some really high values.

  limit          Palindrome
-------------------------------------------
  10^25  |  4.6782084283 ms
  10^51  | 20.3384558935 ms
  10^75  |  7.3286887458 ms
  10^101 | 79.0633348572 ms
-------------------------------------------

The isprime function I used for Palindrome can be found in this answer. I used the Miller-Rabin and not the isprime from the prime_fac module. However that should only cause minor differences.

\$\endgroup\$
2
\$\begingroup\$

Performance optimization

Rather than having a method to produce a sieve, why not have a method that uses a sieve to produce a list of primes?

Fortunately, most of the logic is already present simply, declare an empty list primes = [] and when a prime is located add to the list primes.append(prime) and once iteration is complete return it to the main method call from which you can loop through reverse order by calling reversed on the list.

All this simplifies the calling and called method as such:

def compute_primes_below(limit):
    primes = []
    sieve = [True] * limit

    for prime in range(2, limit):
        if sieve[prime]:
            primes.append(prime)
            for composite in range(prime * prime, limit, prime):
                sieve[composite] = False
    return primes

def compute_largest_prime_palindrome_below(limit):
    primes = compute_primes_below(limit)
    for prime in reversed(primes):
        if is_palindromic(prime):
            return prime

Avoid redundancies

Notice that the sieve_length variable was not used. It was stored in the question, but this same value is passed as the limit parameter so it doesn't need to exist, use limit directly.

Be Pythonic

Note that the conditional blocks do not explicitly require parentheses. The Pythonic way is to do more with less, so in the above code the parentheses are omitted. Snakes on a prime...may as well be the only curly entity on the code.

Additionally, since in Python positive integers evaluate as true the not 0 conditionals may exclude them e.g. in the while loop while (integer != 0) can be just while integer:

\$\endgroup\$
1
\$\begingroup\$

Style

Python has a style guide called PEP 8 which is definitly worth reading and and worth following if you do not have good reasons not to. In you case, your usage of useless parenthesis for instance is not compliant to PEP8. You'll find tools online to check your code compliancy to PEP8 in a automated way if you want to.

Simplification

limit and sieve_length are the same thing : you do not need sieve_length.

divmod

In Python, when you are performing arithmetic and are interested in both the quotient and the remainder of a division, you can use divmod.

Magic numbers

You have 10 hardcoded in multiple places. My preference is to use a default argument giving the base to use.

def reverse(integer, base=10):
    result = 0
    while integer:
        integer, r = divmod(integer, base)
        result = base * result + r
    return result
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.