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 sqrtfrom _collections import defaultdictdef 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 Truedef 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 Falseif __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 nI'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.
Looking for primes with all-different digits
python;performance;primes;dictionary
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 ash -> hundreds groupt -> tens groupv -> the values in the tens groupns -> the values in the hundreds groupYou 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-primesOr, 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 = Nonedef 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.