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.