Project Euler 43

Problem 43
1406357289という数は、0から9のpandigitalであるが、さらに興味深い部分に分割したときの性質を持ちます。
d₁を最初の数字、d₂を2番目の数字などとする。
d₂d₃d₄=406は2で割り切れる。
d₃d₄d₅=063は3で割り切れる。
d₄d₅d₆=635は5で割り切れる。
d₅d₆d₇=357は7で割り切れる。
d₆d₇d₈=572は11で割り切れる。
d₇d₈d₉=728は13で割り切れる。
d₈d₉d₁₀=289は17で割り切れる。
このような性質を持つ0〜9のpandigitalの和を求めよ。
http://projecteuler.net/index.php?section=problems&id=43

順列を出して、この性質を持つものをピックアップすればよいでしょう。

from itertools import count, permutations, ifilter, islice
def make_primes(num):

    def is_prime(n):

        return reduce(lambda x, y: x and n % y != 0, range(2, n), True)

    

    return list(islice(ifilter(is_prime, count(2)), num))
def numerize(a):

    return reduce(lambda x, y: x * 10 + y, a)
def is_valid(a):

    for k in range(D - M):

        m = numerize(a[k+1:k+M+1])

        if m % primes[k] != 0:

            return False

    return True
D = 10

M = 3

primes = make_primes(D - M)

print primes

print sum(map(numerize, filter(is_valid, permutations(range(D)))))

しかし、この性質を持つ数を作っていったほうが速くなります。そのときに同時に数字の重複をチェックします。
まず、3桁までの17の倍数を列挙します。017,034,051,...となります。その一つずつについて前に数字を1つ追加して新たな数を作ります。085なら、0085,2085,...,9085となります。重複がないかを調べて、上位3桁が13で割り切れるかどうかチェックします。2085がこれを満たします。これを繰り返し、最後に一つ残った数字を前につけます。

from itertools import count, islice, ifilter
def make_primes(num):

    def is_prime(n):

        return reduce(lambda x, y: x and n % y != 0, range(2, n), True)

    

    return list(islice(ifilter(is_prime, count(2)), num))
def gen_digits(n):

    while n:

        yield n % D

        n /= D
def check(b, d):

    if (b >> d) & 1:

        return -1

    else:

        return b | (1 << d)
def remained_digit(b):

    for d in range(D):

        if ((b >> d) & 1) == 0:

            return d
def gen_pandigital_primes(n0 = 0, k = 0, b0 = 0):

    p = primes[D-M-k-1]

    if k == 0:

        for n in range(p, D ** M, p):

            b = reduce(lambda x, y: check(x, y), gen_digits(n), b0)

            if b == -1:

                continue

            for m in gen_pandigital_primes(n, k + 1, b):

                yield m

    else:

        for d in range(D):

            b = check(b0, d)

            if b == -1:

                continue

            n = n0 + d * D ** (k + M - 1)

            if n / D ** k % p != 0:

                continue

            if k == D - M - 1:

                d1 = remained_digit(b)

                yield n + D ** (D - 1) * d1

            else:

                for m in gen_pandigital_primes(n, k + 1, b):

                    yield m
D = 10

M = 3

primes = make_primes(D - M)

print sum(gen_pandigital_primes())