mersenneforum.org prime generators for quadric irreducible polynomials
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-06, 10:40 #1 bhelmes     Mar 2016 25·13 Posts prime generators for quadric irreducible polynomials A peaceful day for all, there is a possibility to generate an infinitiv number of primes by investigating quadratic irreducible polynomials like f(n)=n^2+1 or f(n)=n^2+n+1. I propose and have described some nice algorithms how these prime generators can work and have collected some datas about distribution of the primes, runtime of the algorithms and some more information. For people who like primes the information can be found under http://devalco.de/quadr_Sieb_x%5E2+1.php and http://devalco.de/quadr_Sieb_x%5E2+x+1.php If you regard the algorithm exactly you will find that the sieve of Eratosthenes is a special algorithm of the class of algorithm for quadratic irreducible polynomials. I hope that some people will be amused by the topic. Two special question: Concerning the distribution of the prime p=n^2+1 and the reducible prime numbers with p| n^2+1 there is a Batman-Horn conjecture which is related to the topic, does anybody understand the math behind this conjecture Nice greetings from the primes Bernhard http://devalco.de
2016-05-06, 15:39   #2
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by bhelmes there is a possibility to generate an infinitiv number of primes by investigating quadratic irreducible polynomials like f(n)=n^2+1 or f(n)=n^2+n+1.
It's conjectured but not proven. This is an example of a problem with infinite complexity as defined by Green-Tao, see Definition 1.5 in
https://arxiv.org/abs/math/0606088

There progress is made toward solving problems of finite complexity.

I believe sieving for this sort of number is not hard but I have not implemented it personally.

Quote:
 Originally Posted by bhelmes Two special question: Concerning the distribution of the prime p=n^2+1 and the reducible prime numbers with p| n^2+1 there is a Batman-Horn conjecture which is related to the topic, does anybody understand the math behind this conjecture
I'm familiar with the Bateman-Horn-Stemmler conjecture, yes. (Not sure why the last name is often omitted.) It's not particularly complicated except for computing the constant factor for a given polynomial, which is a bit tricky. The basic idea is unchanged since Hardy & Littlewood's famous 1923 paper. Do you have any particular questions?

 2016-05-07, 10:21 #3 bhelmes     Mar 2016 25×13 Posts A peaceful day for you, Concerning the article https://en.wikipedia.org/wiki/Batema...orn_conjecture i did not understand how the exponent m is defined in this formula. Is it right that p is only a prime with p=f(n) or p|f(n) that means that p does not stand for all primes Nice greetings from the primes Bernhard P.S. There are several years i am occupied with these prime generators and i do not found it easy to implement an effective multicore sieve which use all found mathematical background. I am dreaming to sieve up to n=2^42 or more in a couple of weeks, but it is not so easy.
 2016-05-16, 12:13 #4 bhelmes     Mar 2016 25·13 Posts A peaceful day for all, Besides the mentioned prime generator for the function f(n)=n^2+1 and f(n)=n^2+n+1 there are 3 "basic polynomials" with results listed: http://devalco.de/quadr_Sieb_2x%5E2-1.php http://devalco.de/quadr_Sieb_2x%5E2+1.php http://devalco.de/quadr_Sieb_4x%5E2+1.php These three polynomials include all primes. (proof is given) Perhaps there are some mathematicians who are able to enjoy the algorithms and the descriptions. If some one has some further idea how to classify the quadratic polynomials, just write some lines. Nice greetings from the primes Bernhard
2016-05-16, 12:40   #5
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by bhelmes i did not understand how the exponent m is defined in this formula.
m is the number of polynomials. If you're looking for the primes in one particular polynomial (example: primes of the form n^2 + 1) then m = 1. If you're looking for numbers n such that two polynomials in n are simultaneously prime (example: n and n+2 for the twin prime conjecture) then m = 2, and so on.

Quote:
 Originally Posted by bhelmes Is it right that p is only a prime with p=f(n) or p|f(n) that means that p does not stand for all primes
$C = \prod_p \frac{1-N(p)/p}{(1-1/p)^m}$
then this is a product over all primes p. In other words you have
$C=\frac{1-N(2)/2}{(1-1/2)^m} \cdot \frac{1-N(3)/3}{(1-1/3)^m} \cdot \frac{1-N(5)/5}{(1-1/5)^m} \cdots$.

2016-05-16, 12:46   #6
CRGreathouse

Aug 2006

598710 Posts

Quote:
 Originally Posted by bhelmes Besides the mentioned prime generator for the function f(n)=n^2+1 and f(n)=n^2+n+1 there are 3 "basic polynomials" with results listed: http://devalco.de/quadr_Sieb_2x%5E2-1.php http://devalco.de/quadr_Sieb_2x%5E2+1.php http://devalco.de/quadr_Sieb_4x%5E2+1.php These three polynomials include all primes. (proof is given)
The three polynomials are $$2n^2-1,$$ $$2n^2+1,$$ and $$4n^2+1.$$ But it is not true that all primes are one of these three form, nor that all of these forms are prime for all n. For the former try n = 5 or n = 12 (both make all three forms composite), and for the latter take p = 11 or p = 13. In fact both of these have infinitely many counterexamples.

 2016-05-17, 15:04 #7 bhelmes     Mar 2016 25×13 Posts A peaceful day for all, The three polynomials are $$2n^2-1,$$ $$2n^2+1,$$ and $$4n^2+1.$$ Every prime p is either equal the function term of theses three polynomials or either a divisor of a function term of these polynomials: p = f(n) or p | f(n) with f(n)= $$2n^2-1,$$, $$2n^2+1,$$ or $$4n^2+1.$$ There are at least one proof for it : http://devalco.de/quadr_Sieb_2x%5E2+1.php#1 see Lemma 1. d) and an explication concerning the connection towards the discriminant of the polynomials. The first proof was given by Prof. Nebe and i hope that i quoted her correctly, the second explication was given by David Broadhurst and i think that the connection to the product of the discriminant is right. It may be that the formulation discriminant is not completely right, because i reduced the discriminant by a factor 4. Mathematically i guess it is more the fundamental discriminant. If you have a better formulation, to reveal that every prime can be found as function term or divisor of the function term of these three polynomials, then let it know me. If you think you have a counterexample, i will give you the n for n | f(n) and the corresponding polynomial. Greetings from the primes and thank you for your reply Bernhard
2016-05-17, 18:11   #8
CRGreathouse

Aug 2006

10111011000112 Posts

Quote:
 Originally Posted by bhelmes The three polynomials are $$2n^2-1,$$ $$2n^2+1,$$ and $$4n^2+1.$$ Every prime p is either equal the function term of theses three polynomials or either a divisor of a function term of these polynomials
In other words, for every prime p there is some integer n such that p divides
$(2n^2-1)(2n^2+1)(4n^2+1) = 16n^6 + 4n^4 - 4n^2 - 1.$

2016-05-18, 02:02   #9
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

2·47·109 Posts

Quote:
 Originally Posted by CRGreathouse In other words, for every prime p there is some integer n such that p divides $(2n^2-1)(2n^2+1)(4n^2+1) = 16n^6 + 4n^4 - 4n^2 - 1.$
That seems true for every odd p, not necessary prime. And?

edit:
Code:
gp > for(n=1,50,print(n": "factorint(16*n^6+4*n^4-4*n^2-1)[,1]~))
1: [3, 5]
2: [3, 7, 17]
3: [17, 19, 37]
4: [3, 5, 11, 13, 31]
5: [3, 7, 17, 101]
6: [5, 29, 71, 73]
7: [3, 11, 97, 197]
8: [3, 43, 127, 257]
9: [5, 7, 13, 23, 163]
10: [3, 67, 199, 401]
11: [3, 5, 97, 241]
12: [7, 17, 41, 577]
13: [3, 113, 337, 677]
14: [3, 5, 17, 23, 131, 157]
15: [11, 17, 41, 53, 449]
16: [3, 5, 7, 19, 41, 73]
17: [3, 13, 89, 193, 577]
18: [11, 59, 647, 1297]
19: [3, 5, 7, 17, 103, 241]
20: [3, 17, 47, 89, 1601]
21: [5, 353, 881, 883]
22: [3, 13, 17, 19, 149, 967]
23: [3, 7, 29, 73, 151, 353]
24: [5, 461, 1151, 1153]
25: [3, 41, 61, 139, 1249]
26: [3, 5, 7, 11, 41, 193, 541]
27: [31, 47, 1459, 2917]
28: [3, 523, 1567, 3137]
29: [3, 5, 11, 17, 41, 673]
30: [7, 13, 257, 277, 1801]
31: [3, 5, 17, 113, 641, 769]
32: [3, 17, 23, 89, 241, 683]
33: [7, 311, 2179, 4357]
34: [3, 5, 37, 257, 2311]
35: [3, 13, 19, 29, 31, 43, 79]
36: [5, 17, 61, 2591, 2593]
37: [3, 7, 11, 17, 23, 83, 5477]
...etc...

Last fiddled with by LaurV on 2016-05-18 at 02:04

 2016-05-18, 07:31 #10 bhelmes     Mar 2016 25×13 Posts A peaceful day for all, [QUOTE=LaurV;434259]That seems true for every odd p, not necessary prime. And? You can try to code a prime generator for this three polynomials, and i think the theoretical analyse predict that these primegenerators are faster than the sieve of Eratosthenes resp. they are more efficient because the primes you find are nearly constant by 0.7*n where n is the huge of the examined array. By the way did you ever heared anything about prime sieve concerning quadratic polynomials ? I think Landau was the first person who treated this subject, Shanks calculated the polynomial f(n)=n^2+1 up to 10^6 , The described algorithms in http://devalco.de/quadr_Sieb_x^2+1.php are very nice and i think most of them are new. Greetings from the primes Bernhard
2016-05-18, 12:44   #11
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by bhelmes You can try to code a prime generator for this three polynomials, and i think the theoretical analyse predict that these primegenerators are faster than the sieve of Eratosthenes resp. they are more efficient because the primes you find are nearly constant by 0.7*n where n is the huge of the examined array.
I don't know what algorithm you are suggesting. Would you elaborate on its purpose (e.g., "Generate the primes between a and b") and the steps of its operation?

Quote:
 Originally Posted by bhelmes By the way did you ever heared anything about prime sieve concerning quadratic polynomials ?
Would you be more specific?

 Similar Threads Thread Thread Starter Forum Replies Last Post Orgasmic Troll Math 61 2017-04-05 19:28 Nick Puzzles 0 2013-10-29 10:19 henryzz Puzzles 2 2013-02-17 05:27 Orgasmic Troll Math 28 2004-12-02 16:37 Erasmus Factoring 3 2004-05-21 13:55

All times are UTC. The time now is 06:37.

Thu Dec 8 06:37:35 UTC 2022 up 112 days, 4:06, 0 users, load averages: 1.17, 1.03, 0.95