> Some of the questions state an iterative problem for which there is a 
> direct solution.
>
> For instance, the second problem looks iterative, but there is a direct 
> formula for any member of the Fibonacci series, there is a direct formula 
> for the sum of a power series, and the even-valued members of the 
> Fibonacci series occur at every third position starting with 0. When you 
> put that together, the sum is
>
> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
>
> where n is equal to the index of the highest even-valued member of the 
> Fibonacci series that is below one million.  It turns out that n is 30 in 
> this case, and therefore the sum is 5702886.

Well, this is one of the first few, I got it to calculate in about 12s with
a simple summation, so I didn't bother to find a formula, though I'm
not really suprised that such a formula exists.

Many of the solutions need to exceed double precision, which is
leading to things like re-implementing power functions, and square roots.
Like problem 78, I've discovered Watson's congruence on partition
function P, and narrowed the number of candidate answers to 147,
but the generating function
P(n,k) = P(n-1,k-1)+P(n-k,k)
is running out of memory on my machine, so the answer probably
lies in implementing accurately Hardy and Ramanujan's asymptotic
solution.
P(n) ~ (1/(4*n*(sqrt 3))) * (e^(pi*(sqrt (2*n/3))))

Post a reply to this message