Project Euler 38

Problem 38
192という数に1,2,3をかけると、
192 x 1 = 192
192 x 2 = 384
192 x 3 = 576
これをつなげると192384576という1から9の数字が一度ずつ使われる数になる。192384576を192と(1,2,3)の結合した積と呼ぶ。
（中略）整数と(1,2,...,n)(n > 1)の結合した積で1から9の数字が一度ずつ使われる数で最も大きいものは？
http://projecteuler.net/index.php?section=problems&id=38

nで積の桁数が決まります。例えば、n = 4なら、

m x 1 = (2桁)
m x 2 = (2桁)
m x 3 = (2桁)
m x 4 = (3桁)

となります。そうすると、3番目から、

m x 3 < 100

4番目から、

m x 4 ≥ 100

両方あわせて、

25 ≤ m ≤ 33

で調べればよいです。
最大の数を得られればよいので、mが大きいほうから調べていき、最初に条件に合えばそこでやめます。また、それ以前のnでそのような数が一つでもあれば、mを小さくしていったときに今のところの最大を超えないことがわかればそこで打ち切ります。
nが小さいほうがmの取る範囲が大きくなるので、nが大きいほうから調べるとよいでしょう。

def gen_digits(n):

    while n:

        yield n % 10

        n /= 10
def is_pandigital(a):

    m = 0

    for e in a:

        for d in gen_digits(e):

            if ((m >> d) & 1) == 1:

                return False

            m |= 1 << d

            if a[0] == 9:

                print a, d, m

    return m == 1022
def upper_pow(n):

    m = 10

    while m <= n:

        m *= 10

    return m
def concatenate(a):

    return reduce(lambda x, y: x * upper_pow(y) + y, a)
def gen_pandigital(n, max_num):

    m1 = 9 / n

    if 9 % n == 0:

        begin = max(10 ** (m1 - 1), max_num / 10 ** (9 - m1))

        end = 10 ** m1

    else:

        k1 = n * (m1 + 1) - 9

        begin = max(10 ** (m1 - 1) / (k1 + 1), max_num / 10 ** (9 - m1))

        end = 10 ** m1 / k1

    

    for l in xrange(end - 1, begin - 1, -1):

        a = [ l * k for k in range(1, n + 1) ]

        if is_pandigital(a):

            m = concatenate(a)

            print m, a

            if m > max_num:

                yield m

                break
max_num = 0

for n in range(9, 1, -1):

    for m in gen_pandigital(n, max_num):

        max_num = m

print max_num