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.

• SylvainD: Your question seems interesting. Would you be able to tell us a bit more about the expected output and some explanation ?
• BusyAnt: Sure ! About which part do you need more explanations ? The output will be a list of numbers that satisfy the property, that is to say all the digits until the hundreds are different, and each ten of this hundred has a prime. The goal is to figure out if there can be a winning strategy to the game described in the linked question.
• Bradley Thomas: I'm confused by this part of your question: "the second last digit can always be chosen". Is it the case that there is some (one) specific 2nd to last digit that we can use that will lead to all 6 digit numbers with all digits different being non-prime? Then why use the word "always"?
• BusyAnt: @BradThomas "always" was employed because the player needs a winning strategy, therefore they must "always"/"in all cases" be able to choose a number that leads to them winning. Perhaps is it more clear in the original question that I linked.

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.

• SylvainD: Nice answer. You could use string.digits instead of the manual definition.
• machine yearning: Wow that's clever, I didn't even know about that.
• Daerdemandt: Be sure to drop numbers starting with 0s though.
• machine yearning: @Daerdemandt: Confirmed and added

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.

• BusyAnt: This answer gives a remarkable complement. The previous one explained to me the basics of itertools though, that I didn't know about, and put me on the right path, that's why I accepted it. Thank you for these pieces of additional information and that new point of view !
• Daerdemandt: > basics of itertools Make sure you are familiar with generators, especially with a yield from thing. Generating data only as you need it is indeed powerful tool but casts to eager data structures without necessity waste some of that power.
• machine yearning: @Daerdemandt. Nice stuff here. Really good point about needless casting. I'll edit my answer just to include a way of grabbing a counterexample