Looking for primes with all-different digits

Question

I recently answered a question on Mathematics Stack Exchange, where I used a small Python program to check the following :

For all 6-digit numbers, with all digits being different, choosing the digits one by one from left to right, the second last digit can always be chosen so that the number will never be a prime.

In a nutshell, I go through all the hundreds and check for each ten if there is at least one prime number. If this is true for all the tens in the hundred, then we check if the rule of all digits are different has been violated.

There is not much complicated algorithmic involved, but I look for an elegant and fast way to do this.

Here is the code :

# -*- encoding: utf-8 -*-

from math import sqrt
from _collections import defaultdict


def is_prime(n):
"""checks primality of n"""
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    sqr = int(sqrt(n)) + 1
    for divisor in xrange(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True


def has_primes(n):
"""checks if there are any primes in [n, n+9]
with the last digit different from the others"""
    m = n / 10
    l = [int(i) for i in str(m)]
    for i in xrange(n + 1, n + 10, 2):
        if (i % 10 not in l) and is_prime(i):
            return True
    return False

if __name__ == '__main__':
    s = 100000
    e = 1000000
    res = list()
    for h in xrange(s, e, 100):  # hundreds
        for t in xrange(h, h + 100, 10):  # tens
            if not has_primes(t):
                break
        else:  # every ten has at least one prime
            l = [int(i) for i in str(h / 100)]
            d = defaultdict(int)
            for i in l:  # counting occurrences of each digit
                d[i] += 1
            print h
            for i in d:
                if d[i] > 1:
                    print '>', i
                    break
            else:
                res.append(h)
    print '\nres :'
    for n in res:
        print n

I'd like to know how I could improve it. I'm particularly not satisfied with my testing of the doublon digits; it could maybe go only through the numbers with all-different digits. I don't know how to implement this efficiently.

If you are any other suggestions, they're very welcome. Thank you.

Answer 1

You can use itertools.permutations() to generate your sequences of unique digits. Also consider using itertools.groupby() to organize things nicely.

So first you can create all your non-dup-digit numbers as strings:

nodups = [''.join(s) for s in permutations('1234567890', 6)]

As Josay mentioned in a comment, '0123456789' can also be expressed as string.digits in python.

And Daerdemandt reminds us to remove numbers starting with 0. For efficiency's sake, let's just construct a generator instead of a list.

nodups = (''.join(s) for s in permutations('1234567890', 6) if s[0] != '0')

Now if you were to call the list() constructor on this you'd get something like:

['123456', '123457', '123458', '123459', '123450', '123465', '123467', '123468', '123469', '123460'...]

Then you need to organize by hundreds digits, more specifically everything except the last 2 digits ([:-2]):

hundo = groupby(nodups, lambda n: n[:-2])

Now hundo contains some nested generators so it might be hard to inspect on the surface, but if you unpacked everything inside you'd find something like this:

{'1235':
        ['123546',
         '123547',
         '123548',
         ...
        ],
 '1234': ['123456', 
          '123457', 
          '123458',
          ...
        ]
  ...
}

Then organize each hundred-digit-group further by the tens digit, more specifically the second-to-last digit ([-2]):

hundreds = {h:{t:v for t,v in groupby(ns,lambda n: n[-2])} for h,ns in hundo}

That line is a bit of a mouthful, imagine the variables as

h -> hundreds group
t -> tens group
v -> the values in the tens group
ns -> the values in the hundreds group

You can kind of read it like "make a dictionary that maps each hundreds group to (a dictionary mapping each tens group in that hundreds group to the values in that tens group)."

Now they're organized to test in a structured way. Your check is, if I'm not misreading the problem statement:

all hundreds groups contain any (some) tens group with all not-primes

Or, in python:

all(
    any(
        all(not is_prime(int(n)) for n in ns)
        for ns in tens.values()
       )
    for tens in hundreds.values()
   )

If you want to log the counterexample, you could define a memoized_is_prime() function and use a global variable:

counter_example = None
def memoized_is_prime(n):
    global counter_example
    counter_example = n
    return is_prime(n)

You'd just have to access the counter_example variable afterwards if your check returns False.

Although note that the global keyword is not strictly necessary here, and using global-style patterns is discouraged in general. It it fine in this tiny program but if you were to extend this code in any way you'd probably want to encapsulate your memoization.

I haven't tested this, feel free to try it out and let me know if you have any questions.

Answer 2

Factorisation of each number seems wasteful a bit. You could simply pre-generate list of all 6-digit primes.

Including less-than-6-digit primes would not spoil things but make implementation a bit easier and set could be called just primes.

Then the check would look like:

all(
    any(
        not(tens & primes)
    ) for tens in hundreds.values()
)

Use of all and any, as @machine yearning suggests is generally advised, not only because they are readable, but also performance-wise because they short circuit. Well, you do something similar with your break's but that does not look expressive enough and does not cover all cases.

However, if you'd like to also have a counterexample (if there is some) then all won't work. You can use some simple iteration and raise a custom exception when you've found a result (questionable, but will free you from cluttering your code with lots of checks), but that will only work if you need one counterexample.

I'd say we can split core of the logic and all the iteration by extracting logic to is_counterexample function, like that:

def is_counterexample(hundreds):
    return all(tens & primes for tens in hundreds.values())

Then you generate all your hundreds and do either of 3 options:

• any if you need to check for counterexample
• filter if you need to get all counterexamples
• filter and use next on that to get 1 counterexample
• itertools.filterfalse (docs) to get all numbers that are not counterexamples.

The output will be a list of numbers that satisfy the property

Your code assumes you need #2 and accepted answer does #1 and in math context you'd probably get by with #3.

Edit: based on comment "...The output will be a list of numbers that satisfy the property...", added an option that implements that.