## Project Euler Problem 216

Consider numbers t(n) of the form t(n) = 2n^(2)-1 with n > 1.

The first such numbers are 7, 17, 31, 49, 71, 97, 127 and 161.

It turns out that only 49 = 7*7 and 161 = 7*23 are not prime.

For n ≤ 10000 there are 2202 numbers t(n) that are prime.

How many numbers t(n) are prime for n ≤ 50,000,000 ?

My first approach was sieve in the multiple range but after 2 hours of running the code i realised that it will take atleast 5 days for answer.Then I go for second approach to test each number as prime using Miller Rabin primality testing. A simple brute force using some low level optimization. OOPs it again took 3 days to compute the result including powercut in mornning 6 to 9. So every morining I have to wake at 6 to save the result and feed the result as input for next run :(. I was just curious to know how this problem can be solved in one min as project euler site clams.I found how dumb I am. The key idea for problem was Shanks-Tonelli_algorithm.

Again nice problem but not solved by elegant method:(

Here is my python implimentation of Miller Rabin Algorithm which logN times faster than my C implimentation. I am in love with a cute girl as well python :).

import sys

import random

def rabin_miller(p):

if(p>=1

for i in xrange(10):

a=random.randrange(p-1)+1

temp=s

mod=pow(a,temp,p)

while(temp!=p-1 and mod!=1 and mod!=p-1):

mod=(mod*mod)%p

temp=temp*2

if(mod!=p-1 and temp%2==0):

return False

return True

**There is some problem in posting codes here.If you need any code posted here you just mail me**

No comments yet.

## Leave a Reply