mersenneforum.org Mind checking out my program I wrote?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-04-10, 15:59 #1 CadeBrown     "Cade Brown" Feb 2016 USA 23 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 2016-04-10 at 16:09
2016-04-10, 16:02   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by CadeBrown 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?
well at least there's a few things known like if the polynomial is reducible then either one factor must equal one or it's not prime ever. for example 2*x^2-2 is never prime because it's 2*(x^2-1). so it always has a factor of 2. oh and of course if there's an odd constant term the number of variable terms with odd coefficients must be even etc.

Last fiddled with by science_man_88 on 2016-04-10 at 16:08

 2016-04-10, 16:07 #3 CadeBrown     "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).
2016-04-10, 16:17   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by CadeBrown 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).
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.

 2016-04-10, 16:22 #5 CadeBrown     "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)
2016-04-10, 16:34   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by CadeBrown 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)
see my testing ( if I did it) would fail it before that as creating composite for having all terms share a factor. testing for divisibility is more than just binary for x=0,1,2 either one of them creates a number that divides by 3 or no x value ever creates a number divisible by 3.

 2016-04-10, 16:37 #7 CadeBrown     "Cade Brown" Feb 2016 USA 1716 Posts But wouldn't that be more expensive CPU-wise than division on f(1)? EDIT: Especially on higher degree polynomials. Last fiddled with by CadeBrown on 2016-04-10 at 16:39
2016-04-10, 16:41   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by CadeBrown But wouldn't that be more expensive CPU-wise than division on f(1)?
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 2016-04-10 at 16:42

 2016-04-10, 16:43 #9 CadeBrown     "Cade Brown" Feb 2016 USA 23 Posts you are suggesting is to try and weed out polynomials before we evaluate them right?
2016-04-10, 16:45   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by CadeBrown you are suggesting is to try and weed out polynomials before we evaluate them right?
yes I am especially for division by 2. but after that we still can't say for certain without tests that there are no x values that divide by certain primes.

 2016-04-10, 16:55 #11 CadeBrown     "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 hard-coded 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 only_human Soap Box 106 2020-11-08 12:44 petrw1 GPU Computing 2 2016-03-06 13:39 Forceman Software 2 2013-01-30 17:32 davieddy Soap Box 5 2008-08-18 22:30 mfgoode Math 22 2004-02-23 10:39

All times are UTC. The time now is 20:55.

Mon Dec 6 20:55:07 UTC 2021 up 136 days, 15:24, 0 users, load averages: 2.99, 5.04, 5.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.