My Weblog

Blog about programming and math

Project Euler problem 268

Project Euler problem 268 is related to principal of inclusion and exclusion. I was aware of inclusion exclusion but don’t how to extend it to set of k element so i did bit of brute force and got the pattern.I counted how many time a number appearing more than once in series i.e. 2310 appear 6 times. Factor of 2310 is 2*3*5*7*11.It appeared five time because of taking 4 combinations 1)2*3*5*7 (11) 2)2*3*5*11 (7) 3)2*3*7*11 (5) 4)2*5*7*11 (3) 5) 3*5*7*11 (2) and taking 6 at a time 2*3*5*7*11.Other repetitions were 12. I searched 1 4 10 since there were extra appearing in summation and OEIS. Nice problem. Happy to solve but not satisfied. Need to study combinatorics more.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<gmpxx.h>
typedef mpz_class _int;
using namespace std;
_int p[25]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
_int coff[25]={1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, 1771, 2024, 2300, 2600, 2925};
_int Lim=1,sum=0,n;
vector<_int> C,V;

void comB(int k,_int ret,int lev,int v)
	{
		if(ret>Lim) return;
		if(lev==v) C.push_back(ret);
		else 
		  {
			for(int i=k+1;i<25;i++)
			{
				ret*=p[i];
				comB(i,ret,lev+1,v);
				ret/=p[i];
			}
		  }
		
	}
void print()
	{
		_int cnt=0,f;
		for(int i=1;i+1<V.size();i++) 
		  if((V[i-1]!=V[i] and V[i]==V[i+1]) or (V[i]==V[i+1]) or (V[i-1]==V[i] and V[i]!=V[i+1])) cnt++,f=V[i];
		  else { if (cnt>1) cout<<"( "<<f<<" "<<cnt<<") "; cnt=0;}

	}
int main()
	{
		int par=1;
		for(int i=0;i<16;i++) Lim*=10;
		_int tmp;
		for(int i=4;i<=25;i++)
		 {
			C.clear();tmp=0;
			for(int j=0;j<25;j++) comB(j,p[j],1,i);
			n=C.size();
			if(n==0) break;
			for(int j=0;j<n;j++) 
			   tmp+=(Lim/C[j])*par;
			//for(int j=0;j<n;j++) for(_int k=C[j];k<Lim;k+=C[j]) V.push_back(k);
			par*=-1;
			sum+=tmp*coff[i-4];
		}
		//sort(V.begin(),V.end());
		//print();
		//cout<<endl;
		cout<<sum<<endl;
		
	}

February 23, 2011 Posted by | Programming | Leave a comment

   

Follow

Get every new post delivered to your Inbox.

Join 249 other followers