mersenneforum.org > Math pari's capabality
 Register FAQ Search Today's Posts Mark Forums Read

 2012-06-23, 05:05 #1 devarajkandadai     May 2004 13C16 Posts pari's capabality I tried running the following program {p(n)=isprime(n^2+1))} It runs satisfactorily only till about n= 5000; beyond that pari does not seem to be able to handle.
2012-06-23, 11:46   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by devarajkandadai I tried running the following program {p(n)=isprime(n^2+1))} It runs satisfactorily only till about n= 5000; beyond that pari does not seem to be able to handle.
what version might be useful to some others here ( not me personally)? both versions I have seem to work for up to n=50000 at least.

Last fiddled with by science_man_88 on 2012-06-23 at 12:06

2012-06-23, 15:03   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 what version might be useful to some others here ( not me personally)? both versions I have seem to work for up to n=50000 at least.
doh I see now it works just slower than you wanted I guess. one thing I see that could speed speed it up is the fact that x^2 mod 6 -> 1,4,3,4,1,0 repeating so for x^2+1 to be 1 or 5 mod 6 ( the only ones that can be prime for numbers >3) if(x mod 2 == 1,return 0)

Last fiddled with by science_man_88 on 2012-06-23 at 15:41

 2012-06-24, 13:13 #4 mart_r     Dec 2008 you know...around... 22·5·29 Posts It works fine for me. Attached Thumbnails   Last fiddled with by mart_r on 2012-06-24 at 13:13
2012-06-24, 17:34   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by devarajkandadai I tried running the following program {p(n)=isprime(n^2+1))} It runs satisfactorily only till about n= 5000; beyond that pari does not seem to be able to handle.
I'm guessing you've already picked up on the fact that n<n^2+1 which sounds trivial but can be used, this shows that when y^2+1 is prime all indexes greater than that that fall in the groups y or -y mod y^2+1 are divisible by it I believe so as you find primes you can eliminate a lot from the search without primes outside the sequence.

 2012-06-24, 18:43 #6 science_man_88     "Forget I exist" Jul 2009 Dumbassville 20C016 Posts I've got a code that runs in 25-27 seconds in 2.4.2 and 19-21 seconds in 2.5.1 by the looks of it: Code: a=vector(9000000,x,1);for(y=1,#a,if(a[y]==1,if(isprime(y^2+1),forstep(z=(y^2+1)-y,#a,[2*y,(y^2+1)-(2*y)],if(z%(y^2+1)==y || z%(y^2+1)==-y,a[z]=0)),a[y]=0),next()));a only one thing to add to get it to print something other than 1's and 0's and it can add about 3 seconds to the run time. okay maybe I tested the add-on with 50000 still under 4 minutes in 2.5.1 doesn't sound bad for doing a search and print in a 9000000 element vector. Last fiddled with by science_man_88 on 2012-06-24 at 19:00

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Programming 6 2017-12-21 06:04 paul0 Programming 2 2015-11-17 13:04 skan Miscellaneous Math 0 2012-12-16 00:13 devarajkandadai Programming 21 2012-08-31 18:08 CRGreathouse Software 2 2009-03-13 04:22

All times are UTC. The time now is 02:33.

Wed Sep 30 02:33:04 UTC 2020 up 19 days, 23:44, 0 users, load averages: 1.97, 1.95, 1.79