My Weblog

Blog about programming and math

Project Euler Problem 153

Project euler problem 153 is one the best problem which i solved on Project Euler.I tried this problem in 2007 and could not solved.Once you spot the pattern its rather easy to solve.
1—->1
2—->1,1+i,1-i,2
3—->1,3
4—->1,1-i,1+i,2,2+2I,2-2I,4
5—->1,1+2i,1-2i,2+i,2-i,5
6—->1,1+i,1-i,2,3,3+3i,3-3i,6
7—->1,7
8—->1,1+i,1-i,2,2+2i,2-2i,4,4+4i,4-4i,8
9—->1,3,9
10—> 1,1+i,1-i,2,2+2i,2-2i,5,1+2i,1-2i,2+i,2-i,2+4i,2-4i,4+2i,4-2i,1+3i,1-3i,3+i,3-i
If you notice that 1+i and 1-i are divisors of all the numbers which are multiple of 2. 2+2i and 2-2i is divisors of all the number which are multiple of 4. 1+2i is divisor of all the numbers multiple of 5. Also out of these all the divisors only 1+i ,1-i, 1+2i,1-2i,2+i,2-i,1+3i,1-3i,3+i and 3-i are primitive solutions and rest can be derived from these solutions so i wrote brute force to test this algorithm.

#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
#define Lim 100000
typedef pair<int,int> PI;
multimap<int,int> M;
int real[Lim+1],ima[Lim+1];

int main()
	{
		long long sum=0;
		for(int i=1;i<=Lim;i++) for(int j=i;j<=Lim;j+=i) real[j]+=i;
		for(int a=1;a*a<=Lim;a++) 
		  for(int b=1;b<=a;b++) if(__gcd(a,b)==1)M.insert(PI(a*a+b*b,(a==b)?(a+b):2*(a+b)));
		
		for(multimap<int,int>:: iterator it=M.begin();it!=M.end();it++)
		{
			int i=(*it).first,val=(*it).second;
			for(int j=1;i*j<=Lim;j++)
			 for(int k=i*j;k<=Lim;k+=i*j) ima[k]+=j*val;
		}

		for(int i=1;i<=Lim;i++) sum+=real[i]+ima[i];
		cout<<sum<<endl;
	}

But for 10^8, its not going work because this code heavily depends on memory. For this problem we don’t need any array and map. Here is source code which i derived for previous code.

#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define Lim 100000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PI;

multimap<ll,ll> M;
int main()
	{
		ll sum=0;
		for(int i=1;i<=Lim;i++)  
		{
			sum+=(Lim/i)*i;
			
		}
		




	      for(int a=1;a*a<Lim;a++)
		  for(int b=1;b<=a /*&& (a*a+b*b)<=Lim*/;b++) 
			if(__gcd(a,b)==1)
		{	
			int i=(a*a+b*b),val=(a==b)?(a+b):2*(a+b);
			for(int j=1;i*j<=Lim;j++) 
			 {
				sum+=(j*val*(Lim/(i*j)));
			 }
		}
		
		
		cout<<sum<<endl;
	}

149th problem. One more to go to next level.

Advertisements

February 9, 2011 - 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: