プロジェクトオイラー
http://projecteuler.net/index.php
Q162.
16桁の16進数で、0・1・Aを1つ以上含み、かつ最初が0でない数の個数を16進数で表せ
最初が0でないという条件を取り除くと簡単。これを求めておき、最初の数字で場合わけする。
def g(n, k):
if k == 0:
return 13 ** n
elif k == 1 or k == 2 or k == 4:
return 14 ** n - g(n, 0)
elif k == 3 or k == 5 or k == 6:
return 15 ** n - 2 * g(n, 1) - g(n, 0)
else:
return 16 ** n - 3 * g(n, 3) - 3 * g(n, 1) - g(n, 0)def f(n):
return 15 * g(n - 1, 7) + 2 * g(n - 1, 3)N = 16
m = sum(map(f, range(3, N + 1)))
print hex(m).upper()[2:-1]
