Project Euler 30 - inamori’s diary

Problem 30
驚くべきことに各桁の4乗の和として書ける数は3つしかありません（中略）
1 = 1⁴は和でないので除きます。
（中略）各桁の5乗和として書ける全ての数の和を求めよ。
http://projecteuler.net/index.php?section=problems&id=30

まず、範囲を抑えることを考えましょう。7桁なら最大9999999ですが、9⁵ + 9⁵ + 9⁵ + 9⁵ + 9⁵ + 9⁵ + 9⁵ = 413343となり6桁です。よって、6桁以内であることがわかります。また6桁でも最大9⁵ * 6 = 354294以下になることがわかります。
この範囲で2から順に各桁の5乗の和を求めて一致するかどうか調べます。



from itertools import count
def calc_max_number():

    n = 0

    for m in count(1):

        n += 9 ** E

        if n < 10 ** (m - 1):

            n -= 9 ** E

            break

    return n
def gen_digits(n):

    while n:

        yield n % 10

        n /= 10
def is_valid(n):

    return sum(map(lambda d: d ** E, gen_digits(n))) == n
E = 5

max_n = calc_max_number()

print sum(filter(is_valid, xrange(2, max_n + 1)))

しかし、これは時間がかかります。やはり、Project Eulerは「逆から考える」が基本です。
0〜9の中から6つの数字を列挙します。重複も許します。ただし小さい数字から順に並べます。そして6つの数字の5乗和を求めます。その各桁の数字をソートして、元の6つの数字と一致すればOKです。4乗の場合で例を挙げると、

[ 0, 1, 3, 4, 6 ] -> 0⁴ + 1⁴ + 3⁴ + 4⁴ + 6⁴ = 1634

> [ 0, 1, 6, 3, 4 ] -> [ 0, 1, 3, 4, 6 ] OK.

最初に6つの数字を選ぶのは、重複組合せと呼ばれるものです。簡単のために0〜2の数字の中から3つの数字を選ぶ方法を考えましょう。全ての組合せは、

000 001 002 011 012 022 111 112 122 222

の10個です。これは次のように考えます。まず、○を5つ用意します。

○○○○○

そして、この5つの中から2つを選んで、｜に変えます。

｜○○｜○

この仕切りで分けられた○がそれぞれの数字の個数です。この場合は、

0112

を表しています。よって、₅C₂個あることになります。10進で5乗和の場合、₁₅C₉ = 5005でグッと調べるべき数が減ります。これなら10乗でも十分に速いです。



from itertools import count, combinations, imap
def calc_num_digits():

    n = 0

    for m in count(1):

        n += 9 ** E

        if n < 10 ** (m - 1):

            break

    return m - 1
def gen_digits(n):

    for k in range(num_d):

        yield n % 10

        n /= 10
def convert_digits(comb):

    a = [ ]

    d = 0

    prev = -1

    for m in comb:

        if m - prev > 1:

            a += [ d ] * (m - prev - 1)

        d += 1

        prev = m

    a += [ d ] * (num_d + 8 - prev)

    return a
def is_equal(a, b):

    for k in range(num_d):

        if a[k] != b[k]:

            return False

    return True
E = 10

num_d = calc_num_digits()

s = 0

for a in imap(convert_digits, combinations(range(num_d + 9), 9)):

    n = sum(map(lambda d: d ** E, a))

    b = [ d for d in gen_digits(n) ]

    b.sort()

    if is_equal(a, b):

        s += n

print s - 1