169 : ある数を2のべき乗の和で表せる方法の数の探査

整数nを2のべき乗の和で表すことを考える. ただし各数は高々2回しか使ってはいけないものとする. この表し方の数を$f(n)$とする. ただし$f(0)=1$と定義する.

例として$n=10$を考える.

• 1+1+8

• 1+1+4+4

• 1+1+2+2+4

• 2+4+4

• 2+8

と5通りの異なる表し方があるので,$f(10)=5$である.

$f(10^{25})$を求めよ.