My Weblog

Blog about programming and math

Project Euler Problem 132

A simple observation for this project euler problem 132, we can write this number as
(10^N)-1/10-1. Find out the prime numbers which divides it. Now instead of calculating this number we can see that this quantity is in fact equal to the 1+ a+ a^2+……….+a^(N-1) where a is 10. Now things are quite simple now as we can add this sequence recursively using divide and conquer technique. A c code for problem.

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
ll _pow(ll a,ll b,ll c)
	{
		ll ret=1;
		while(b)
		{
			if(b&1) ret=(ret*a)%c;
			a=(a*a)%c;
			b/=2;
		}
		return ret%c;
	}

ll geosum(ll a,ll n,ll c)
	{
		if(n==1LL) return 1LL;
		if(n==2LL) return (1LL+a)%c;
		int ret;
		ret=((geosum(a,n/2LL,c)%c)*((1LL+_pow(a,n/2LL,c))%c))%c; 
		if(n&1LL) ret=(ret+_pow(a,n-1LL,c))%c;

		return ret;
	}


bool isprime(ll n)
	{
		
		if(n==2LL) return 1;
		if(n<=1LL || n%2LL==0LL) return 0;
		for(ll i=3LL;i*i<=n;i+=2LL) if(n%i==0LL) return 0;
		return 1;
	}


int main()
	{

		long long sum=0;
		ll cnt=0LL;
		for(ll i=3LL;;i+=2LL)
		{
			if(isprime(i) && !geosum(10LL,(ll)pow(10,9),i)) 
			{
				cnt++;
				cout<<cnt<<" "<<i<<" divides it "<<endl;
				sum+=(long long) i;
				if(cnt==40LL) break;
			}
		}
		cout<<sum<<endl;
	}
Advertisements

April 25, 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: