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)) 
#include<cstdio>
#include<iostream>
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];
		else 
		{
			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;
		fib[0]=0,fib[1]=1,fib[2]=2;
		sum[0]=0,sum[1]=1,sum[2]=2;
		for(int i=3;i<90;i++)
		{
			fib[i]=fib[i-1]+fib[i-2];
			sum[i]=sum[i-1]+sum[i-2]+fib[i-2]-1;
		}

		cout<<recur(lim-1)<<endl;

	}

Advertisements

July 23, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: