Given And Integer, Return The Next Integer That Is A Prime Number And A Palindrome . Python

Given any random integer, create a function to find the next number that is a prime number and also a palindrome. My attempt def golf(number): x = number + 1 for i in rang

Solution 1:

Here's a variation on byron he's answer which adds several optimizations:

1. We can eliminate all even x values (other than 2) before doing any elaborate tests, since we can trivially tell they are not prime.
2. A small improvement is to only call str(x) once, and reuse the value later.
3. We can take advantage of the fact that all even-length palindromes are multiples of 11, which means that (except for 11 itself) they're not prime. We can jump ahead to the next odd-length x value.
4. Since we've already eliminated even numbers, our prime test only needs to test odd divisors. Further we can stop our loop when we reach sqrt(x), rather than going all the way to x itself.
5. Finally, there's no need to use a Boolean flag variable to carry the primeness out of the loop. If we don't break, the else block attached to the loop will be run.

The code:

import math

defnext_prime_palindrome(x):
    whileTrue:
        x += 1if x > 2and x % 2 == 0:        # even numbers greater than 2 are non-primecontinue

        s = str(x)                      # compute str(x) just onceif x > 11andlen(s) % 2 == 0:  # all even-length palindromes are multiples of 11
            x = 10 ** len(s)            # so jump to the next odd-length integercontinueif s != s[::-1]:                # palindrome testcontinuefor i in xrange(3, round(math.sqrt(x))+1, 2): # loop over odd potential divisorsif x % i == 0:              # prime testbreakelse: # this else block runs only if no break happened in the loop, so x is primereturn x

Here are some tests runs, showing a few cases where the optimizations save significant time:

>>>next_prime_palindrome(1)
2
>>>next_prime_palindrome(3)
5
>>>next_prime_palindrome(9)
11
>>>next_prime_palindrome(11)
101
>>>next_prime_palindrome(99999)
1003001
>>>next_prime_palindrome(999999999)
10000500001

A further improvement might be to directly generate palindromes, rather than working with integers to start with, and doing a palindrome test to filter them. That would get quite a bit further from your original design, so I'll leave that for someone else.

Solution 2:

Palindrome are a sparser set of numbers than primes, and you can generate palindromes directly.

Consider the sequence 98.102

These are palidrome numbers you can base on these

989, 9889, 999, 9999, 10001, 100001, 10101, 101101, 10201, 102201

ADDED

Not also that all of the palidromes with an odd number of digits will come before the palidromes with an even number of digits.

If you write this as a generator (ie using yield) get get a straightforward algorithm for generating palindromic numbers in order.

For 1..9 you generate either 9 or 18 palindromes depending upon whether you consider 1 digit numbers palindromic.

For 10..99 you generate 90 even digit and 90 odd digit palindromes.

For 100..999 you generate 900 even digit and 900 odd digit palindromes.

You have just generated all 1989 (or 1997 if including single digit numbers) of the palindromic numbers less than 1 million. There are 78,498 primes less than 1 million

Any algorithm that is based on generating primes then testing for a palindrome will be much slower that generating palindromes and then testing for primes

Solution 3:

defgolf(number):
    primes = []
    i = 2while i <= number:
        if isPrime(i, primes):
            primes.append(i)
        i += 1

    answer = primes[-1] + 1whileTrue:
        if isPrime(answer, primes):
            primes.append(answer)
        ifstr(answer) == str(answer)[::-1]:
            return answer
        answer += 1defisPrime(n, primes):
    for (p for p in primes if p<=n**0.5):
        if n%p == 0:
            returnFalsereturnTrue

Solution 4:

Your solution can be slightly modified in order to create an iterative solution:

defgolf(number):
    x = number + 1whileTrue:     
        is_golf = Truefor i inrange(2, x):
            if x % i == 0orstr(x) != str(x)[::-1]:
                is_golf = Falsebreakif is_golf:
            return x
        x += 1

Solution 5:

improved according to Blckknght's advice, thanks.

defgolf(number):
    x = number 
    whileTrue:
        x += 1ifstr(x) != str(x)[::-1]:
            continuefor i in xrange(2, x):
            if x % i == 0 :
                breakelse:
            return x