My Weblog

Blog about programming and math

Project Euler 101

After long time again i started solving problems on Project Euler. I need to solve 20 more problems to go to level 2 (more than 150 + group) so i think i should go for it. Till now i have solved all the problems from first page , 17 remaining problem on page 2 and more than 30 problems on page 3 so currently i am trying to finish these back logs as my Govt job 🙂 me giving me enough time to pratice on topcoder and project euler.
This problem is related to Lagrange Interpolating Polynomial. May be you can look at wiki or mathworld before solving this problem. You just have to check the condition when OP(k,k+1) is equal to U_k+1 and you are done.
Here is my source code but use for better understanding.

#include<cstdio>
#include<iostream>
#include<vector>
#include<iostream>
using namespace std;

vector<long long> V;

long long generate(long long n)
	{
		//return n*n*n;
		return 1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n)))))))));
	}
long long lagran(long long  n)
	{
		if(n==2) return 1LL;//constant
		long long sum=0LL;
		for(long long i=1LL;i<n;i++)//y1,y2,y3
		{
			long long tmp_1=1LL,tmp_2=1LL;
			for(long long j=1;j<n;j++)
 			 {
				if(j==i) continue;
				tmp_1*=(n-j);
				tmp_2*=(i-j);
			 }
			sum+=(tmp_1*V[i]/tmp_2);//assuming a perfect division
		}
		return sum;
		
	}
int main()
	{

		//using lagrange interpolation 
		long long sum=0;
		V.push_back(0LL);
		for(long long i=1;;i++)
		{
			V.push_back(generate(i));
			if(lagran(i+1)==generate(i+1))//not bad polynomial 
			 break;
			else
				sum+=lagran(i+1);
		}

		cout<<sum<<endl;
	}
		

You can try this problem too.I solved it long time ago and just saw this problem mentioned on the forum.

Advertisements

March 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: