Looking for primes with all-different digits

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:
                    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.

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.

StackExchange Code Review Q#134529, answer score: 8