Project Euler 52（2）

もっと攻める方法を取りましょう。桁を増やしていって、数字を数えてダメならそこは捨てるという方法です。
まず、1桁だけで考えます。最初の桁は1です。これを2倍、3倍すると、最初の方は、2,3,4,5,6となるはずです。分数で考えて、[1, 7/6)ならこうなるはずです。こうして得られた数は、6桁で考えるならあわせて数字は6個以内でなければなりません。ここではこれに当てはまります。次にこれを10倍します。すなわち、[10, 35/3)の領域で考えます。この領域を分割します。[10, 61/6)を考えます。この領域でやはり2倍、3倍すると、10,20,30,40,50,60となります。数字が7つ使われているのでアウトです。こうして次々に領域を縮小していくと解に遭遇するはずです。
領域の分割は、0,1/6,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,5/6,1が境界になります。分数を使うと遅いので、これを60倍した整数を使って工夫しています。

この方法で9桁まではあっという間に出ました。ただ、それ以降はどうしても遅くなりますね。12桁以上になると前回書いたパターンと違うものも出てきました。例えば、

153846076923
307692153846 = 2 * 153846076923
461538230769 = 3 * 153846076923
615384307692 = 4 * 153846076923
769230384615 = 5 * 153846076923
923076461538 = 6 * 153846076923

15桁以上は厳しいようです。

from itertools import islice, count
def gen_digits(n):

    while n:

        yield n % 10

        n /= 10
def all(f, a):

    for e in a:

        if not f(e):

            return False

    return True
def count_digit(n):

    a = [ 0 ] * 10

    for d in gen_digits(n):

        a[d] += 1

    return a
def max_count(a, b):

    return map(lambda k: max(a[k], b[k]), range(10))
def total_count(n):

    def f(k): return count_digit(k * n / 60)

    return sum(reduce(max_count, map(f, range(1, 7))))
def is_valid(n, m):

    return total_count(n) <= m
def gen_solution_core(m, k = 0, begin = 6, end = 10):

    if k == m:

        yield begin / 60

    else:

        begin *= 10

        end *= 10

        r = begin % 60

        p = intervals.index(r)

        b = begin

        while b < end:

            if p == len(intervals) - 1:

                q = 0

                e = b - intervals[p] + 60

            else:

                q = p + 1

                e = b + intervals[q] - intervals[p]

            if is_valid(b, m):

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

                    yield n

            p = q

            b = e
def calc_intervals():

    s = set()

    for n in range(1, 7):

        for m in range(n):

            s.add(60 * m / n)

    a = list(s)

    a.sort()

    return a
def gen_solution():

    for k in count(6):

        for n in gen_solution_core(k):

            yield n
N = 6

intervals = calc_intervals()

for n in islice(gen_solution(), 60):

    print n