My Weblog

Blog about programming and math

Project Euler 297

After long time i solved problem from project euler. The problem is Project Euler problem 297 . Although it took some time to figure out the solution. First i brute forced and tried to get pattern. The problem is 
Given f(k) is the  Kth Fibonacci number  : 
sum(1, f(k)) = sum(1, f(k-1)) + sum(1, f(k-2)) + f(k-2) - 1 

for non fibonacci number a [f(k-1) < a < f(k)] 
sum(1, a) = sum(1, f(k-1)) + sum(1, a - f(k-1)) + (a - f(k-1)) 
using namespace std;
typedef long long ll;
ll fib[90],sum[90];
ll lim=1;
ll recur(ll n)
		if(n<=2) return sum[n];
			int t;
			for(int i=0;i<90;i++) { if (fib[i]<=n) t=i;}
			return sum[t]+n-fib[t]+recur(n-fib[t]);
int main()
		for(int i=0;i<17;i++) lim=lim*10;
		for(int i=3;i<90;i++)




July 23, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: