# My Weblog

## 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;

}
```