Prime generators
Inhaltsverzeichnis

Development of
Algorithmic Constructions

05:55:47
DeutschEnglish
19.Sep 2021

Prime generators on quadratic irreducible polynomials

a) Introduction
b) The algorithm
c) Calculation and sort order
d) Order by the discriminant
e) Order by the occuring primes
f) Graphic of the density of primes

a) Introduction

This is a collection of 204 different polynomials of the form f(x)=x2+bx+c .
The searched polynomials should fulfill the following conditions:
  1. The polynomial should be irreducible over N
  2. c should be a prime number or equal 1, so that f(0) is not a composite value.
  3. 2|f(0) and 2|f(1) at the same time should not be possible.
  4. Every polynomial should construct a special sequence of primes by the following described algorithm,
    where at least the sequence of the sieved prime numbers is infinite.
The sieved out primes appear in an non arising order in opposite to the sieve of Eratosthenes.

b) The algorithm

The following described algorithm is the simplest algorithm which calculate an infinite sequence of primes.
The algorithm can be improved of course by several means, but for the understanding the algorithm is limited to this simple form:
  1. All sequences start with x=0 and f(0)=|c| should be a prime number or equal 1.
  2. All values f(x)=x2+bx+c for x=0 up to n_max with x element N are precalculated.
  3. The factor 2 is eliminated of these values at first.
  4. If f(0) is not equal 1 respectively a prime number, the prime number normally sieved the precalculated list
    by dividing the values of f(x+k*p) and f(p-x-b+k*p) as often as possible, so that the prime number is not any longer a divisior of the values.
  5. If f(1) is not equal 1 respectively a prime number, the prime number normally sieved the precalculated list
    by dividing the values of f(x+k*p) and f(p-x-b+k*p) as often as possible, so that the prime number is not any longer a divisior of the values.
  6. If f(2) is not equal 1 respectively a prime number, the prime number normally sieved the precalculated list
    by dividing the values of f(x+k*p) and f(p-x-b+k*p) as often as possible, so that the prime number is not any longer a divisior of the values.
  7. Step for step the primes at the position f(x) with increasing x are eliminated in the sequence,
    so that only primes either as result of the function or either as reducible primes respectively as rest of divisions remain.

c) Calculation and sort order

    The following loop for b and c was made:

       for c={1, -1, 2, -2, 3, -3, 5, -5 for all primes up to 100, -100}
         for b={0, 1, -1, 2, -2, 3, -3, up to 300, -300}
           calculate the discriminant of f(x)=x2+bx+c
         end_for;
       end_for;

    The discriminant=b2-4c was calculated and the polynomial where b is minimal was choosen.
    For other values no suitable polynomials were found.

Every prime p(x) sieves both values of the polynomial for the values x+k*p and p-x+k*p.
Only p=b2-4c (discriminant) sieves one time the array because x=p-x

d) Order by the discriminant

There are 204 different polynomials with 2 negativ and 202 positiv discriminants.
The sequence of primes using a prime generator concerning the quadratic irrecucible polynomial is infinite.
You will find an implementation in pseudo code of the algorithm, some mathematical proofs and the distribution of the primes by following the link of the polynomial.

In the following table you find all polynomials listed sorted by the according discriminant.

Nr. polynomial discr.
b²-4c
1. n²+12n+179 -143
2. n²+4n+19 -15
3. n²+4n-11 15
4. n²+n-5 21
5. n²+4n-29 33
6. n²+4n-31 35
7. n²+8n-23 39
8. n²+12n-19 55
9. n²+4n-53 57
10. n²+4n-61 65
11. n²+5n-11 69
12. n²+n-19 77
13. n²+16n-23 87
14. n²+18n-101 91
15. n²+5n-17 93
16. n²+12n-59 95
17. n²+4n-101 105
18. n²+20n-11 111
19. n²+22n-109 115
20. n²+28n+67 129
21. n²-11n-3 133
22. n²+11n-5 141
23. n²+4n-139 143
24. n²+12n-109 145
25. n²-28n+41 155
26. n²-28n+37 159
27. n²+16n-97 161
28. n²+28n+19 177
29. n²-28n+13 183
30. n²+24n-41 185
31. n²+28n-5 201
32. n²+16n-139 203
33. n²+12n-173 209
34. n²+11n-23 213
35. n²+24n-71 215
36. n²+24n-73 217
37. n²-46n+59 235
38. n²+11n-29 237
39. n²+42n-53 247
40. n²+28n-53 249
41. n²-15n-7 253
42. n²+32n-3 259
43. n²+36n+59 265
44. n²+66n-107 299
45. n²+15n-19 301
46. n²+32n-47 303
47. n²+32n-53 309
48. n²-36n+5 319
49. n²+36n+3 321
50. n²+32n-71 327
Nr. polynomial discr.
b²-4c
51. n²+32n-79 335
52. n²-19n+5 341
53. n²-54n+19 355
54. n²-40n+29 371
55. n²+36n-53 377
56. n²+40n+7 393
57. n²+32n-139 395
58. n²+40n-3 403
59. n²-40n-7 407
60. n²+9n-83 413
61. n²+40n-17 417
62. n²+n-109 437
63. n²+40n-47 447
64. n²+17n-41 453
65. n²-40n-73 473
66. n²-44n+3 481
67. n²+40n-89 489
68. n²+36n-173 497
69. n²+90n+5 505
70. n²-94n+149 515
71. n²-23n+3 517
72. n²-48n+41 535
73. n²+40n-137 537
74. n²+44n-61 545
75. n²-66n-13 551
76. n²-48n+23 553
77. n²+23n-11 573
78. n²+66n-73 581
79. n²-70n+47 589
80. n²-52n+79 597
81. n²-56n+151 633
82. n²+44n-151 635
83. n²+48n-73 649
84. n²-52n+11 665
85. n²+52n-5 681
86. n²+74n-5 687
87. n²+48n-131 707
88. n²-48n-137 713
89. n²+23n-47 717
90. n²+52n-61 737
91. n²+25n-31 749
92. n²+52n-79 755
93. n²-56n-5 789
94. n²-60n+107 793
95. n²-29n+7 813
96. n²+114n-11 815
97. n²-29n-7 869
98. n²-29n-13 893
99. n²+60n-5 905
100. n²+60n-13 913
Nr. polynomial discr.
b²-4c
101. n²+23n-97 917
102. n²-64n+101 923
103. n²-126n+149 955
104. n²+31n-3 973
105. n²+60n-89 989
106. n²-64n+31 993
107. n²+60n-157 1057
108. n²+29n-59 1077
109. n²-94n-13 1111
110. n²+21n-173 1133
111. n²+64n-113 1137
112. n²-68n+11 1145
113. n²-72n+127 1169
114. n²+23n-181 1253
115. n²-76n+179 1265
116. n²+72n+23 1273
117. n²+35n-17 1293
118. n²-37n+5 1349
119. n²-37n+3 1357
120. n²-150n+173 1363
121. n²-37n-5 1389
122. n²-37n-7 1397
123. n²-80n+127 1473
124. n²+33n-113 1541
125. n²-80n+23 1577
126. n²-84n+131 1633
127. n²+114n-29 1639
128. n²+80n-41 1641
129. n²-80n-113 1713
130. n²-118n+3 1739
131. n²+37n-97 1757
132. n²-43n+3 1837
133. n²-88n+97 1839
134. n²-88n+53 1883
135. n²-88n+43 1893
136. n²+84n-179 1943
137. n²+84n-181 1945
138. n²+88n-113 2049
139. n²-92n+13 2103
140. n²+92n-3 2119
141. n²-92n-5 2121
142. n²-47n+5 2189
143. n²-92n-101 2217
144. n²+92n-113 2229
145. n²-96n-1 2305
146. n²-138n+131 2315
147. n²+96n-17 2321
148. n²-96n-19 2323
149. n²+96n-103 2407
150. n²+49n-3 2413
Nr. polynomial discr.
b²-4c
151. n²+96n-149 2453
152. n²-104n+191 2513
153. n²-100n-37 2537
154. n²-51n+7 2573
155. n²+104n-1 2705
156. n²-53n+13 2757
157. n²-214n-19 2867
158. n²-55n-7 3053
159. n²+108n-149 3065
160. n²+108n-157 3073
161. n²+53n-73 3101
162. n²-112n+23 3113
163. n²-57n-17 3317
164. n²-120n-113 3713
165. n²+120n-137 3737
166. n²-124n+101 3743
167. n²-124n+3 3841
168. n²-128n-7 4103
169. n²-65n+3 4213
170. n²+63n-67 4237
171. n²+136n+23 4601
172. n²-136n+5 4619
173. n²-140n+43 4857
174. n²-71n+3 5029
175. n²+294n+5 5401
176. n²-160n+23 6377
177. n²-164n+191 6533
178. n²-81n+5 6541
179. n²+168n-5 7061
180. n²-168n-41 7097
181. n²-176n-3 7747
182. n²-180n-53 8153
183. n²-184n+71 8393
184. n²-188n+139 8697
185. n²-188n+59 8777
186. n²-95n-3 9037
187. n²-192n+97 9119
188. n²+192n-1 9217
189. n²-200n+103 9897
190. n²-212n+107 11129
191. n²-115n-19 13301
192. n²+123n-127 15637
193. n²-256n+127 16257
194. n²+133n-3 17701
195. n²-276n+11 19033
196. n²+296n-89 21993
197. n²+153n-7 23437
198. n²-163n+5 26549
199. n²-392n-97 38513

d) Order by the occuring primes

In the following table you find all polynomials listed sorted by the sign of the discriminant and the occuring primes.

f) Graphic of the density of primes