20160410, 15:59  #1 
"Cade Brown"
Feb 2016
USA
17_{16} Posts 
Mind checking out my program I wrote?
First post here after a few months lurking. I am currently working on https://github.com/ChemicalDevelopment/PGS . This program searches for polynomials that generate primes for the first few values (like euler's example of x^2 + x + 41 being prime for x = 0, 1, ... 39). Any kind of project like this that you guys have seen anywhere, and what are your thoughts on this?
Its currently running all coefficients up to 10000 A few polynomials found: 359 + 558x^1 + 36x^2 is prime for x = 0, 1, ... 28, 29 Last fiddled with by CadeBrown on 20160410 at 16:09 
20160410, 16:02  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20160410 at 16:08 

20160410, 16:07  #3 
"Cade Brown"
Feb 2016
USA
23 Posts 
Yes, but I've found it's not worth it to factor the polynomial. I have a fairly efficient primality test (I precompute a sieve up to a limit, and binary search it to test a number is prime).

20160410, 16:17  #4 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
so you don't check if the coefficients have a common factor ( in PARI/gp it would be done with gcdext or isirreducible) that is all I meant though factoring could do more than just that. but then again I'm crap at coding.

20160410, 16:22  #5 
"Cade Brown"
Feb 2016
USA
23 Posts 
Well, it would test f(0) whether it's prime (whether the constant factor is zero), and then it would fail on f(1) on a polynomial with the gcd of all the coefficients != 0. ex. f(x) = 2x^2 + 2 would fail on f(1) because 2*1^2 + 2 = 4 is not prime. But thats actually faster than computing the gcd of variables (I have a good algorithm for primality)

20160410, 16:34  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


20160410, 16:37  #7 
"Cade Brown"
Feb 2016
USA
23 Posts 
But wouldn't that be more expensive CPUwise than division on f(1)?
EDIT: Especially on higher degree polynomials. Last fiddled with by CadeBrown on 20160410 at 16:39 
20160410, 16:41  #8 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
if neither f(0) or f(1) divide by 3 it doesn't stop f(2) from dividing by 3 if you truly want a string of primes you need to know it will never divide by primes under a certain range the reason Euler's polynomial can produce the number of values in a row that are prime is because none of the first p x values divide by p for all primes p<41. if they did then it wouldn't create the number of primes it can for x values under 40. well I did say about number of coefficients meeting a certain criteria as another test to help out.
Last fiddled with by science_man_88 on 20160410 at 16:42 
20160410, 16:43  #9 
"Cade Brown"
Feb 2016
USA
23 Posts 
you are suggesting is to try and weed out polynomials before we evaluate them right?

20160410, 16:45  #10 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 

20160410, 16:55  #11 
"Cade Brown"
Feb 2016
USA
23 Posts 
Lets take an example. 2x^2 + 2x + 2
My method: We evaluate f(0) = 2 + 2 * 0 + 2 * 0^2 = 2 My prime test knows two is prime (by hardcoded example  two) f(2) = 2 + 2 * 2 + 2 * 2^2 = 14 . My method tries 14 as prime  Mod 2 is 0, so 14 is not prime. My program then stops testing this function. Your method: We modulo the coefficients [2, 2, 2] by some primes, and on two we get [0, 0, 0] ~ While this works, we had to do 3 modulos (think of higher degrees as well). Using mine, we learned it is prime for x = 0, and we ended up doing 6 multiplies and 1 mod. Yours actually can be pretty efficient, but doing so many mods on small integers is very costly. I'm thinking we would want to implement that kind of stuff in the beginning. Kind of like sieving the primes, but we are sieving polynomials. Pretty good idea, would save a lot of time. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Soap Box clutterbot  What's on your mind? Squeak up!  only_human  Soap Box  106  20201108 12:44 
CUDA Install errors...HELP...never mind  petrw1  GPU Computing  2  20160306 13:39 
Round Off Checking and Sum (Inputs) Error Checking  Forceman  Software  2  20130130 17:32 
Georgia on my mind  davieddy  Soap Box  5  20080818 22:30 
Mind Boggling Number  mfgoode  Math  22  20040223 10:39 