# My Weblog

## Project Euler 146

Brute forced with bit of analysis. After carefully observation , the numbers should be multiple of 5. For n = 1 or 4 mod 5, $n^2=1 \mod 5$ then $n^2+9=0 \mod 5$. Similarly for n = 2 or 3 mod 5 $n^2=4 \mod 5$ then $n^2+1=0 \mod 5$. It takes couple of minutes on my office’s faster computer.
Edit:: Forum suggests ” n must be congruent to 10, 80, 130 or 200 mod 210 [2,3,5,7]” so this could be make bit more faster using this fact.Changed the loop from for(_int i=5;i<150000000;i+=5) to for(_int i=10;i<150000000;i+=10) makes it bit faster.

```#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 main()
{
_int sum=0,k;
for(_int i=10;i<150000000;i+=10)
{
k=( i*i+1 );
if(mpz_probab_prime_p(k.get_mpz_t(),5) )
{
_int next , curr = k;
mpz_nextprime(next.get_mpz_t(),curr.get_mpz_t());
if( next == ( i*i + 3 ) )
{
curr= next ;
mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
if( next == ( i*i + 7 ) )
{
curr = next;
mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
if ( next == ( i*i + 9 ) )
{
curr = next;
mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
if(next == ( i*i + 13 ) )
{
curr = next;
mpz_nextprime(next.get_mpz_t() , curr.get_mpz_t());
if( next == ( i*i + 27 )) sum += i;
}
}
}
}
}
}
cout<<sum<<endl;

}
```