• 1

• 639
• 4
• 17

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.