20160506, 10:40  #1 
Mar 2016
2^{5}·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 BatmanHorn conjecture which is related to the topic, does anybody understand the math behind this conjecture Nice greetings from the primes Bernhard http://devalco.de 
20160506, 15:39  #2  
Aug 2006
5,987 Posts 
Quote:
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. I'm familiar with the BatemanHornStemmler 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? 

20160507, 10:21  #3 
Mar 2016
2^{5}×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 pf(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. 
20160516, 12:13  #4 
Mar 2016
2^{5}·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%5E21.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 
20160516, 12:40  #5  
Aug 2006
5,987 Posts 
Quote:
Quote:
\[C = \prod_p \frac{1N(p)/p}{(11/p)^m}\] then this is a product over all primes p. In other words you have \[C=\frac{1N(2)/2}{(11/2)^m} \cdot \frac{1N(3)/3}{(11/3)^m} \cdot \frac{1N(5)/5}{(11/5)^m} \cdots\]. 

20160516, 12:46  #6  
Aug 2006
5987_{10} Posts 
Quote:


20160517, 15:04  #7 
Mar 2016
2^{5}×13 Posts 
A peaceful day for all,
The three polynomials are \(2n^21,\) \(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^21,\), \(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 
20160517, 18:11  #8  
Aug 2006
1011101100011_{2} Posts 
Quote:
\[(2n^21)(2n^2+1)(4n^2+1) = 16n^6 + 4n^4  4n^2  1.\] 

20160518, 02:02  #9  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·47·109 Posts 
Quote:
edit: Code:
gp > for(n=1,50,print(n": "factorint(16*n^6+4*n^44*n^21)[,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 20160518 at 02:04 

20160518, 07:31  #10 
Mar 2016
2^{5}×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 
20160518, 12:44  #11  
Aug 2006
5,987 Posts 
Quote:
Would you be more specific? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime generating polynomials that stop?  Orgasmic Troll  Math  61  20170405 19:28 
Mersenne primes and irreducible polynomials  Nick  Puzzles  0  20131029 10:19 
Primes on quadric irreducible polynomials  henryzz  Puzzles  2  20130217 05:27 
Primegenerating polynomials  Orgasmic Troll  Math  28  20041202 16:37 
Prime Generators and/or Source Codes  Erasmus  Factoring  3  20040521 13:55 