Project Euler 148

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


数学的にはよくわかりませんが、実際に数えてみるとわかります。1行で7で割れない数えてみると、明らかな法則性が見えてきます。7進数で考えるとわかりやすいでしょう。その和は、7のべき乗までならきれいに求められます。そうでない部分も含めて再帰を使うと非常にきれいに書けます。

def digits(n):
    return [] if n == 0 else [ n % B ] + digits(n / B)

def f(n):
    def g(n):
        return reduce(lambda x, y: x * (y + 1), digits(n), 1)
    
    def sum_seq(n):
        return n * (n + 1) / 2
    
    if n < B:
        return sum_seq(n)
    q, r = divmod(n, B)
    return g(q) * sum_seq(r) + f(q) * sum_seq(B)

N = 10 ** 9
B = 7
print f(N)