problem41
長さが4の場合。 N = 1000a + 100b + 10c + d 3x = a + b + c + d の時 d = 3x - a - b -c 整理すると N = 999a + 99b + 9c + 3x # N is not prime
後は、各数字の和を調べて、7桁が最大ということが分かる。組み合わせを作って総当たり。
いやー、combinationsの作り方がテキトー過ぎる。
import math import itertools # def primes(): # yield(2) # r = [2] # n = 3 # while(True): # is_prime = True # for i in r: # if n % i == 0: # is_prime = False # break # if is_prime: # yield(n) # r.append(n) # n += 2 # def primes_till(n): # return itertools.takewhile(lambda x : x < n, primes()) ## too slow def is_prime(ns): n = reduce(lambda n, x : 10*n+x, ns, 0) if n % 2 == 0: return False sqn = math.floor(math.sqrt(n)) for i in range(3, sqn, 2): if n % i == 0: return False return True def combinations(xs, n): def delete(xs, e): return [x for x in xs if not x == e] def _combinations(xs, n): if 1 >= n: return [[i] for i in xs] else: return [[i] + sub_xs for i in xs for sub_xs in _combinations(delete(xs, i), n-1)] return _combinations(xs, n) candidates = [n for n in combinations(range(1, 8), 7) if is_prime(n)] ans = reduce(lambda ans, n : n if n > ans else ans, candidates, 0) print(ans)