mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2016-04-10, 15:59   #1
CadeBrown
 
CadeBrown's Avatar
 
"Cade Brown"
Feb 2016
USA

278 Posts
Default 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
CadeBrown is offline   Reply With Quote
Old 2016-04-10, 16:02   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by CadeBrown View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-04-10, 16:07   #3
CadeBrown
 
CadeBrown's Avatar
 
"Cade Brown"
Feb 2016
USA

23 Posts
Default

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).
CadeBrown is offline   Reply With Quote
Old 2016-04-10, 16:17   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CadeBrown View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-04-10, 16:22   #5
CadeBrown
 
CadeBrown's Avatar
 
"Cade Brown"
Feb 2016
USA

23 Posts
Default

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)
CadeBrown is offline   Reply With Quote
Old 2016-04-10, 16:34   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by CadeBrown View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-04-10, 16:37   #7
CadeBrown
 
CadeBrown's Avatar
 
"Cade Brown"
Feb 2016
USA

23 Posts
Default

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
CadeBrown is offline   Reply With Quote
Old 2016-04-10, 16:41   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CadeBrown View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-04-10, 16:43   #9
CadeBrown
 
CadeBrown's Avatar
 
"Cade Brown"
Feb 2016
USA

278 Posts
Default

you are suggesting is to try and weed out polynomials before we evaluate them right?
CadeBrown is offline   Reply With Quote
Old 2016-04-10, 16:45   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CadeBrown View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-04-10, 16:55   #11
CadeBrown
 
CadeBrown's Avatar
 
"Cade Brown"
Feb 2016
USA

23 Posts
Default

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.
CadeBrown is offline   Reply With Quote
Reply

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 2020-11-08 12:44
CUDA Install errors...HELP...never mind petrw1 GPU Computing 2 2016-03-06 13:39
Round Off Checking and Sum (Inputs) Error Checking Forceman Software 2 2013-01-30 17:32
Georgia on my mind davieddy Soap Box 5 2008-08-18 22:30
Mind Boggling Number mfgoode Math 22 2004-02-23 10:39

All times are UTC. The time now is 08:40.


Sun Nov 28 08:40:18 UTC 2021 up 128 days, 3:09, 0 users, load averages: 0.60, 0.87, 0.91

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.