Projecteuler 169

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

引用

Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.

For example, f(10)=5 since there are five different ways to express 10:

1 + 1 + 8
1 + 1 + 4 + 4
1 + 1 + 2 + 2 + 4
2 + 4 + 4
2 + 8

What is f(10^(25))?

注意到
f(2k+1) = f(k)              
f(2k)   = f(k) + f(k-1)      k >= 1
容易得到，对 n = p*2^m(其中p%2==1,m>=0)，有：
f(n) = f(p) + m*f(p-1)
因此
f(n+1) = f(p*2^m+1)
       = f(p*2^(m-1))
       = f(p) + (m-1)*f(p-1)
从而：
x*f(n)+y*f(n+1) = (mx+(m-1)y)f(p-1)+(x+y)f(p)

因此得到下面的代码：

/**
  compute x*f(n)+y*f(n+1) where n%2 == 0
*/
def count(x: BigInt, y: BigInt, n: BigInt): BigInt = {
   if(n == 0) return x + y
   val m = n.lowestSetBit    // n = p*2^m where p%2 == 1
   val p = n >> m
   count(x*m + y*(m-1),x+y,p-1)
}

引用

scala> count(1,0,(10: BigInt).pow(25))                      
res1: BigInt = 178653872807