Prime Number and Binomial (Problem 5)
Points : 25
Answer : 9222683165156720133
Consider the prime number 5 and all the binomial coefficient of 4.
4C0 = 1
4C1 = 4
4C2 = 6
4C3 = 4
4C4 = 1
None of the above binomial is divisible by 5. 9 is another such value.
Let sum(p) gives the sum of all such unique values n for p that are less than 255 such that none of the binomial nC0, nC1, ..., nCn is divisible by p.
Find ∑sum(p) for all primes p below 100.
Solution
Following relation can be used to solve this problem,
where k is such that t.pk-1 < 255 < t.pk+1-1
Code
- #include<iostream>
- using namespace std;
- #include<vector>
- #include<ctime>
- #include<cmath>
- int primes[100],c=1;
- void improved_sieve(int N)
- {
- int M=(N-1)/2;
- int x=(floor(sqrt(N))-1)/2,i,j;
- vector<bool> S(M+1,0);
- primes[0]=2;
- for (i=1;i<=x;i++)
- if (!S[i])
- {
- primes[c++]=(2*i+1);
- for (j=2*i*(i+1);j<=M;j+=(2*i+1))
- S[j]=1;
- }
- for (;i<=M;i++)
- if (!S[i])
- primes[c++]=(2*i+1);
- }
- long long pow(long long p,long long m)
- {
- long long r=1,i;
- for (i=1;i<=m;i++)
- r*=p;
- return r;
- }
- int main()
- {
- improved_sieve(100);
- long long i,t,m,p,k,sum=0;
- for (i=0;i<c;i++)
- {
- p=primes[i];
- for (t=1;t<p;t++)
- {
- for (m=0;(t*pow(p,m)-1)<36028797018963968LL;m++)
- {
- sum+=t*pow(p,m)-1;
- }
- }
- }
- cout<<sum<<endl;
- }
#include<iostream>
using namespace std;
#include<vector>
#include<ctime>
#include<cmath>
int primes[100],c=1;
void improved_sieve(int N)
{
int M=(N-1)/2;
int x=(floor(sqrt(N))-1)/2,i,j;
vector<bool> S(M+1,0);
primes[0]=2;
for (i=1;i<=x;i++)
if (!S[i])
{
primes[c++]=(2*i+1);
for (j=2*i*(i+1);j<=M;j+=(2*i+1))
S[j]=1;
}
for (;i<=M;i++)
if (!S[i])
primes[c++]=(2*i+1);
}
long long pow(long long p,long long m)
{
long long r=1,i;
for (i=1;i<=m;i++)
r*=p;
return r;
}
int main()
{
improved_sieve(100);
long long i,t,m,p,k,sum=0;
for (i=0;i<c;i++)
{
p=primes[i];
for (t=1;t<p;t++)
{
for (m=0;(t*pow(p,m)-1)<36028797018963968LL;m++)
{
sum+=t*pow(p,m)-1;
}
}
}
cout<<sum<<endl;
}
Submit your solution
You need to be logged in to submit a solution.
discussions
| KoenR | count n = 0? |
| Q: | Is n = 0 to be considered? We know n < 2^55, But is n > 0 or n >= 0? |
| A: | No. n>0. |
post a question
Loading...
