Discussion on: Write a script to find permutable prime numbers

View post

Nice one!

from collections import deque 

def perms(p):
    result = []
    d = deque(str(p))
    for _ in range(len(str(p))):
        d.rotate(1)
        result.append(int(''.join(d)))
    return result

prev_primes = []

for poss_prime in range(2,1001):
    for n in prev_primes:
        if poss_prime % n == 0:
            break
    else: # no break
        prev_primes.append(poss_prime)

result = [p for p in prev_primes if all(q in prev_primes for q in perms(p))]
print(result)

Vinay Pai • Apr 16 '18 • Edited

This solution has a bug but happens to produce the correct output. This doesn't test all permutations of digits. An n digit integer has n! permutations, but this only tests n of them. For example, 241 has six permutations (241, 214, 421, 412, 124, 142) but this only tests three (241 , 412, 124) of them.

It happens to work because all the three digit permutable prime happen to belong to a family that contain repeated digits, so you never get a false positive. It will fail for larger numbers, it will report 1193 as a permutable number, but it's not (1139 is not a prime number). It's a circular number, solved by Jonathan's Go code below.

Amazingly the next number in the permutable prime sequence after 991 is 1111111111111111111.

You can of course easily fix the bug with itertools.permutations). Just replace perms(p) with this:

def perms(p):
    return [int(''.join(p)) for p in itertools.permutations(str(p))]