mersenneforum.org  

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

Reply
 
Thread Tools
Old 2016-05-06, 10:40   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25·13 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2016-05-06, 15:39   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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 View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2016-05-07, 10:21   #3
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25×13 Posts
Default

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.
bhelmes is offline   Reply With Quote
Old 2016-05-16, 12:13   #4
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25·13 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2016-05-16, 12:40   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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 View Post
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
If you're talking about
\[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\].
CRGreathouse is offline   Reply With Quote
Old 2016-05-16, 12:46   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

598710 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2016-05-17, 15:04   #7
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25×13 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2016-05-17, 18:11   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000112 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.\]
CRGreathouse is offline   Reply With Quote
Old 2016-05-18, 02:02   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·47·109 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
LaurV is offline   Reply With Quote
Old 2016-05-18, 07:31   #10
bhelmes
 
bhelmes's Avatar
 
Mar 2016

25×13 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2016-05-18, 12:44   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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 View Post
By the way did you ever heared anything about prime sieve concerning
quadratic polynomials ?
Would you be more specific?
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime generating polynomials that stop? Orgasmic Troll Math 61 2017-04-05 19:28
Mersenne primes and irreducible polynomials Nick Puzzles 0 2013-10-29 10:19
Primes on quadric irreducible polynomials henryzz Puzzles 2 2013-02-17 05:27
Prime-generating polynomials Orgasmic Troll Math 28 2004-12-02 16:37
Prime Generators and/or Source Codes 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔