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.

using namespace std;
typedef long long ll;
ll _pow(ll a,ll b,ll c)
		ll ret=1;
			if(b&1) ret=(ret*a)%c;
		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;
		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)) 
				cout<<cnt<<" "<<i<<" divides it "<<endl;
				sum+=(long long) i;
				if(cnt==40LL) break;

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