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