CODEWITHSUNDEEP
python
user3636636
user3636636

Reputation: 2499

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 range(2, x):
        if x % i == 0 or str(x) != str(x)[::-1]:
            golf(number + 1)
    return x

E.g golf(13) = 101

I'm actually looking for an alternative option than the recursion method i used. How can this best be accomplished without using recursion?

Thanks

Upvotes: 0

Views: 315

Answers (5)

Gary Walker
Gary Walker

Reputation: 9134

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

Upvotes: 1

byron he
byron he

Reputation: 342

improved according to Blckknght's advice, thanks.

def golf(number):
    x = number 
    while True:
        x += 1
        if str(x) != str(x)[::-1]:
            continue
        for i in xrange(2, x):
            if x % i == 0 :
                break
        else:
            return x

Upvotes: 0

Blckknght
Blckknght

Reputation: 104762

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

def next_prime_palindrome(x):
    while True:
        x += 1

        if x > 2 and x % 2 == 0:        # even numbers greater than 2 are non-prime
            continue

        s = str(x)                      # compute str(x) just once
        if x > 11 and len(s) % 2 == 0:  # all even-length palindromes are multiples of 11
            x = 10 ** len(s)            # so jump to the next odd-length integer
            continue

        if s != s[::-1]:                # palindrome test
            continue

        for i in xrange(3, round(math.sqrt(x))+1, 2): # loop over odd potential divisors
            if x % i == 0:              # prime test
                break
        else: # this else block runs only if no break happened in the loop, so x is prime
            return 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.

Upvotes: 1

Nir Alfasi
Nir Alfasi

Reputation: 53535

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

def golf(number):
    x = number + 1
    while True:     
        is_golf = True
        for i in range(2, x):
            if x % i == 0 or str(x) != str(x)[::-1]:
                is_golf = False
                break

        if is_golf:
            return x
        x += 1

Upvotes: 0

inspectorG4dget
inspectorG4dget

Reputation: 114025

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

    answer = primes[-1] + 1
    while True:
        if isPrime(answer, primes):
            primes.append(answer)
        if str(answer) == str(answer)[::-1]:
            return answer
        answer += 1

def isPrime(n, primes):
    for (p for p in primes if p<=n**0.5):
        if n%p == 0:
            return False
    return True

Upvotes: 0

Related Questions