Project Euler 110（1）

http://projecteuler.net/index.php?section=problems&id=110

n = p₁^e₁…p_m^e_m

とすると、解の個数は、

((2e₁ + 1)…(2e_m + 1) + 1) / 2

なので、指数のみで決まります。例えば、2^e₁・3^e₂と2^e₁・5^e₂では、解の個数は同じでも前者の方が小さくなります。また、2³・3⁴より2⁴・3³のほうが小さくなります。k番目の素数をp_kとすると、答えは

p₁^e₁…p_m^e_m
e₁ ≥ e₂ ≥ … ≥ e_m

の形でなければならないことがわかります。この形の自然数を勝手にヤング数と呼ぶことにしましょう（ヤング図形からの類推）。ヤング数を昇順に並べられれば、最初に解の個数が400万を超えた数が答えになります。
最小のヤング数は2です。2をリストに入れて、ここから素数を追加してヤング数を作っていきます。2からは2²と2・3が生成されます。2はリストから取り出して、2²と2・3のうち小さいのは2²の方です。これをリストから取り出して、2³と2²・3が生成されるので、これをリストに入れます。このようにすればヤング数を並べられます。
これで10秒でした。もっと速くならないのでしょうか。

from itertools import *

def get_primes(k):
    if k == len(primes):
        for n in count(primes[-1] + 1 if k > 0 else 2):
            if all(n % m != 0 for m in xrange(2, n)):
                primes.append(n)
                break
    return primes[k]

def f_value(f):
    return reduce(lambda x, y: x * y[0] ** y[1], f, 1)

def gen_Young():
    def f_tuple(f):
        return (f, f_value(f))
    
    def gen_next(f0):
        if len(f0) == 1 or f0[-2][1] > f0[-1][1]:
            p, e = f0[-1]
            yield f_tuple(f0[:-1] + [(p, e + 1)])
        yield f_tuple(f0 + [(get_primes(len(f0)), 1)])
    
    def index(a, y, begin = 0, end = -1):
        if end == -1:
            if len(a) == 0:
                return 0
            elif y[1] > a[-1]:
                return len(a)
            end = len(a)
        
        if begin == end - 1:
            return end
        else:
            mid = (begin + end) / 2
            if a[mid][1] < y[1]:
                return index(a, y, mid, end)
            else:
                return index(a, y, begin, mid)
    
    a = [ f_tuple([(get_primes(0), 1)]) ]
    while True:
        x = a.pop(0)
        yield x
        for y in gen_next(x[0]):
            k = index(a, y)
            a = a[:k] + [ y ] + a[k:]

def count_solutions(f):
    return (reduce(lambda x, y: x * (y[1] * 2 + 1), f, 1) + 1) / 2

N = 4 * 10 ** 6
primes = []
for x in gen_Young():
    if count_solutions(x[0]) > N:
        print x[1]
        break