PROJECT EULER SOLUTION # 146

Solution to problem number 146 of Project Euler.

Question # 146

The smallest positive integer n for which the numbers n²+1, n²+3, n²+7, n²+9, n²+13, and n²+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;

}

/*******************************************************************************/

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

}

/**********************************************************************************/

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 2^69725931; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 284332^7830457+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;

              }

       }

}

/**********************************************************************************/