CODEWITHSUNDEEP
pythonalgorithmloops
dcgoss
dcgoss

Reputation: 2207

Palindrome/Prime Checker in Python not working

My task is this:

What is the only (double-digit, or above) Prime number that is palindromic in both base-2 (binary), and base-10 (decimal) instances?

Whenever I run this code nothing happens, and it acts like an infinite loop. What am I doing wrong, or how can I improve? Many thanks in advance.

def isPrime(n):
    if type(n) != int or n <= 1:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    else:
        for x in range(2, int(n**0.5)+1):
            if n%x == 0:
                return False
                break
        return True
def isPalindrome(x):
    num = str(x)[::-1]
    if str(x) == num:
        return True
    else:
        return False
while True:
    a = 11
    if isPrime(a) and isPalindrome(a) == True:
        if isPalindrome(bin(a)) == True:
            print a
            break
    else:
        a+=2
        print a

--------- Edit: **SOLVED** ---------

Revised code:

def isPrime(n):
    if n < 2 or n%2 == 0:
        return False
    if n == 2:
        return True
    else:
        for x in range(3, int(n**0.5)+1, 2):
            if n%x == 0:
                return False
        return True
def isPalindrome(x):
    num = str(x)[::-1]
    return str(x) == num
a = 11
while True:
    if isPrime(a) and isPalindrome(a) and isPalindrome(format(a, "b")):
            print a
            break
    a+=2

Thank you to all who contributed answers.

Upvotes: 1

Views: 623

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1123400

The output of bin() is never a palindrome, because the characters 0b are prepended to it:

>>> bin(3)
'0b11'
>>> isPalindrome(bin(3))
False

Either slice those two characters of, or use format() to produce a binary representation:

>>> format(3, 'b')
'11'
>>> isPalindrome(format(3, 'b'))
True

Your loop has another problem: it won't increment if you found a palindromic prime that is not a palindromic prime in base 2:

if isPrime(a) and isPalindrome(a) == True:
    if isPalindrome(format(a, 'b')) == True:
        print a
        break
    # no else here
else:
    a+=2
    print a

Just test for all conditions in one test:

if isPrime(a) and isPalindrome(a) and isPalindrome(format(a, 'b')):
    print a
    break
a += 2

There is rarely a need to test for == True in a boolean test.

Next is that you reset a in the loop:

while True:
    a = 11

It doesn't matter what you do to a in the rest of the loop, at the top it goes back to 11. Move that out of the loop:

a = 11
while True:
    if isPrime(a) and isPalindrome(a) and isPalindrome(format(a, 'b')):
        print a
        break
    a += 2

Whenever you write if comparison: return True followed by else: return False, just return the test instead:

def isPalindrome(x):
    num = str(x)[::-1]
    return str(x) == num

because the == comparison operator already returns a boolean value.

Your primality test doesn't need to test for the type of n, really (you only ever pass in integers), but the correct way to test for a type is to use:

isinstance(n, int)

as this allows for subclasses of int too. Even if you do need to limit something to a very specific type and cannot allow for subclasses, you'd use:

type(n) is int

as types are singletons.

Taking advice from isPrime Function for Python Language your isPrime() function would be a little faster if you used:

def isPrime2(n):
    if n < 2: return False
    if n == 2: return True
    for i in range(3, int(n ** 0.5) + 1, 2):   # only odd numbers
        if n % i == 0:
            return False
    return True

instead.

Your loop could be made more efficient by limiting the number of values you look at. If you look at the Palindronic Prime series on the OEIS you'll see that apart from 11, all base-10 palindromic primes have an odd number of digits, so you can skip large swathes of numbers. The following would produce better candidates:

def palindromic_candidates():
    yield 11
    outer = 1
    while True:
        for i in range(10):
            yield int('{}{}{}'.format(outer, i, str(outer)[::-1]))
        outer += 1

Demo:

>>> from itertools import islice
>>> pc = palindromic_candidates()
>>> list(islice(pc, 30))
[11, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383]
>>> list(islice(pc, 100, 130))
[13931, 14041, 14141, 14241, 14341, 14441, 14541, 14641, 14741, 14841, 14941, 15051, 15151, 15251, 15351, 15451, 15551, 15651, 15751, 15851, 15951, 16061, 16161, 16261, 16361, 16461, 16561, 16661, 16761, 16861]

Use this instead of your while True loop, remove the a += 2 line:

for a in palindromic_candidates():
    if isPrime(a) and isPalindrome(format(a, 'b')):
        print a
        break

where you can drop the test for base-10 palindromes as the generator produces only palindromes.

Upvotes: 7

Related Questions