My Weblog

Blog about programming and math

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

Advertisements

February 28, 2009 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: