Wednesday 30 October 2013

PROJECT EULER SOLUTION # 146

Solution to problem number 146 of Project Euler.
Question # 146

The smallest positive integer n for which the numbers n2+1, n2+3, n2+7, n2+9, n2+13, and n2+27 are consecutive primes is 10. The sum of all such integers n below one-million is 1242490.
What is the sum of all such integers n below 150 million?

Solution # 146
/*******************************************************************************/
#include<stdio.h>

int is_prime(long long int);
long long int next_prime(long long int);
int fun(long long int);
int main()
{
      long long int i,sum=0;
      for(i=2;i<150000000;i+=2)
      {
            //printf("i = %lld  sum = %lld\n",i,sum);
            if(fun(i))
            {
                  sum+=i;
                  printf("sum = %lld\t\ti = %lld\n",sum,i);
            }

      }

      printf("sum = %lld\n",sum);

      return 0;
}

int is_prime(long long int n)
{
      long long int i;
      if(n%2==0)
            return 0;
      for(i=3;i*i<=n;i+=2)
            if(n%i==0)
                  return 0;
      return 1;
}

long long int next_prime(long long int n)
{
      long long int i;
      for(i=n+2;;i+=2)
      {
            if(is_prime(i))
                  return i;
      }
      return 0;
}

int fun(long long int n)
{
      if(primecheck(n))
            if(next_prime(n*n+1)==n*n+3 && next_prime(n*n+3)==n*n+7 && next_prime(n*n+7)==n*n+9 && next_prime(n*n+9)==n*n+13 && next_prime(n*n+13)==n*n+27)
                  return 1;

      return 0;
}

int primecheck(long long int n)
{
      long long int i;
      if((n*n+1)%2==0)
            return 0;
      for(i=3;i*i<=(n*n+27);i+=2)
      {
            if((n*n+1)%i==0)
                  return 0;
            if((n*n+3)%i==0)
                  return 0;
            if((n*n+7)%i==0)
                        return 0;
                if((n*n+9)%i==0)
                        return 0;
            if((n*n+13)%i==0)
                        return 0;
                if((n*n+27)%i==0)
                        return 0;
      }
      return 1;
}
/*******************************************************************************/

Friday 18 October 2013

PROJECT EULER SOLUTION # 57




Solution to problem number 57 of Project Euler.
Question # 57
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
√2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
By expanding this for the first four iterations, we get:
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Solution # 57
/**********************************************************************************/
#include<stdio.h>
#include<time.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>

int n[1000],d[1000],tmp[1000];
void new_d();
void new_n();

int countDigits(int*);

int main()
{
       int i,j,k,counter=0;
       for(i=0;i<1000;i++)
              n[i]=d[i]=tmp[i]=0;

       n[999]=3;
       d[999]=2;
       for(k=1;k<1000;k++)
       {
             
              new_d();
              new_n();
              for(j=0;j<1000;j++)
                     d[j]=tmp[j];
              if(countDigits(n)>countDigits(d))
                     counter++;
       }
       printf("\nANSWER = %d\n",counter);
       printf("\nEXECUTION TIME = %f\n",clock()/(float)CLK_TCK);
       system("pause");
}

void new_n()
{
       int i;
       for(i=0;i<1000;i++)
              n[i]=d[i]+tmp[i];
       for(i=999;i>0;i--)
       {
              if(n[i]>9)
              {
                     n[i]%=10;
                     n[i-1]+=1;
              }
       }
}     

/* this function stores the
new denominator in tmp array*/
void new_d()
{
       int i;
       for(i=0;i<1000;i++)
              tmp[i]=n[i]+d[i];
       for(i=999;i>0;i--)
       {
              if(tmp[i]>9)
              {
                     tmp[i]%=10;
                     tmp[i-1]+=1;
              }
       }
}     

int countDigits(int *arr)
{
       int i;
       for(i=0;i<1000;i++)
              if(arr[i]!=0)
                     break;
       return (1000-i);
}
/**********************************************************************************/

Thursday 17 October 2013

PROJECT EULER SOLUTION # 97



Solution to problem number 97 of Project Euler.
Question # 97
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.
Find the last ten digits of this prime number.
Solution # 97
/**********************************************************************************/
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int tmp[10];
int arr[10];
void fun();
void add();
int main()
{
       int i;
       long j;
       for(i=0;i<10;i++)
              tmp[i]=arr[i]=0;
       arr[9]=1;

       /*the following loop computes last 10 digits of
              2^7830457 */
       for(j=0;j<7830457;j++)
              fun();
      
       for(i=0;i<28433;i++)
              add();
       tmp[9]+=1;
       for(i=0;i<10;i++)
              printf("%d",tmp[i]);
       printf("\nEXECUTION TIME = %f",clock()/(float)CLK_TCK);
      
       system("pause");

}

void fun()
{
       int i;
       for(i=9;i>=0;i--)
       {
              arr[i]*=2;
             
       }
       for(i=9;i>=0;i--)
       {
              if(arr[i]>9)
              {
                     if(i!=0)
                     {
                           arr[i-1]+=1;
                           arr[i]%=10;
                     }
                     if(i==0)
                           arr[i]%=10;
              }
       }

}

void add()
{
       int i;
       for(i=9;i>=0;i--)
       {
              tmp[i]+=arr[i];
       }
       for(i=9;i>=0;i--)
       {
              if(tmp[i]>9)
              {
                     if(i!=0)
                     {
                           tmp[i-1]+=1;
                           tmp[i]%=10;
                     }
                     if(i==0)
                           tmp[i]%=10;
              }
       }
}
/**********************************************************************************/