Prime generators
Inhaltsverzeichnis

Development of
Algorithmic Constructions

21:26:44
DeutschEnglish
23.Nov 2020

Prime generators on quadratic irreducible polynomials

a) Introduction
b) The algorithm
c) Calculation and sort order
d) Order by the discriminant

a) Introduction

This is a collection of 286 different polynomials of the form f(x)=x2+bx+c :
30 polynomials with a negativ discriminant and 256 polynomials with a positiv discriminant.
The searched polynomials should fulfill the following conditions:
  1. The polynomial should be irreducible over N
  2. b element of Z, 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 100000, -100000}
         for b={0, 1, -1, 2, -2, 3, -3, up to 2000, -2000}
           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 286 different polynomials with 30 negativ and 256 positiv discriminant.
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 Nr. polynomial discr. b² -4c Nr. polynomial discr. b² -4c Nr. polynomial discr. b² -4c
1. n²+1 -1 9. n²+23 -23 17. n²+103 -103 25. n²-24n+631 -487
2. n²+2 -2 10. n²+8n+47 -31 18. n²-16n+191 -127 26. n²+823 -823
3. n²+3 -3 11. n²+37 -37 19. n²-8n+167 -151 27. n²-44n+1451 -967
4. n²+5 -5 12. n²+43 -43 20. n²+163 -163 28. n²+1087 -1087
5. n²+7 -7 13. n²+47 -47 21. n²+10n+821 -199 29. n²+1423 -1423
6. n²+11 -11 14. n²+67 -67 22. n²+223 -223 30. n²-24n+3607 -3463
7. n²+13 -13 15. n²-12n+107 -71 23. n²+16n+431 -367


8. n²+19 -19 16. n²+79 -79 24. n²-20n+563 -463



Nr. polynomial discr. b² -4c Nr. polynomial discr. b² -4c Nr. polynomial discr. b² -4c Nr. polynomial discr. b² -4c
1. n²-2 2 65. n²+19n+3 349 129. n²+60n-263 1163 193. n²+55n-3 3037
2. n²-3 3 66. n²+28n-157 353 130. n²-35n+11 1181 194. n²+80n-1657 3257
3. n²-5 5 67. n²+36n-43 367 131. n²-68n-37 1193 195. n²-230n-3 3307
4. n²-7 7 68. n²+19n-3 373 132. n²+44n-733 1217 196. n²-116n+5 3359
5. n²-11 11 69. n²+32n-127 383 133. n²+138n-163 1231 197. n²-120n+167 3433
6. n²-13 13 70. n²+19n-7 389 134. n²+33n-37 1237 198. n²+53n-163 3461
7. n²-17 17 71. n²+21n+11 397 135. n²-72n+47 1249 199. n²+47n-331 3533
8. n²+8n-3 19 72. n²-40n-19 419 136. n²-142n+5 1259 200. n²-238n-3 3541
9. n²-23 23 73. n²+82n-3 421 137. n²+25n-163 1277 201. n²+108n-677 3593
10. n²+n-7 29 74. n²-44n+53 431 138. n²-84n+467 1297 202. n²-124n+167 3677
11. n²-12n+5 31 75. n²-48n+127 449 139. n²+64n-283 1307 203. n²-61n-19 3797
12. n²+3n-7 37 76. n²-60n+443 457 140. n²-72n-23 1319 204. n²+124n-3 3847
13. n²-41 41 77. n²+21n-5 461 141. n²-158n+797 1361 205. n²+120n-281 3881
14. n²+12n-7 43 78. n²+86n-3 463 142. n²+72n-113 1409 206. n²-250n-3 3907
15. n²-47 47 79. n²-44n+17 467 143. n²+146n-379 1427 207. n²+59n-127 3989
16. n²+n-13 53 80. n²-44n+5 479 144. n²+64n-409 1433 208. n²+120n-449 4049
17. n²+8n-43 59 81. n²-44n-3 487 145. n²+76n-3 1447 209. n²-63n-31 4093
18. n²+7n-3 61 82. n²+36n-179 503 146. n²-80n+113 1487 210. n²+120n-557 4157
19. n²+16n-3 67 83. n²+19n-37 509 147. n²+33n-101 1493 211. n²-132n+179 4177
20. n²+16n-7 71 84. n²-60n+379 521 148. n²+16n-1489 1553 212. n²-152n+1559 4217
21. n²+12n-37 73 85. n²-48n+53 523 149. n²+80n+3 1597 213. n²-65n-7 4253
22. n²-83 83 86. n²+21n-29 557 150. n²-64n-577 1601 214. n²+132n+59 4297
23. n²+8n-73 89 87. n²+32n-307 563 151. n²-41n+17 1613 215. n²-124n-613 4457
24. n²-97 97 88. n²+48n+7 569 152. n²+33n-137 1637 216. n²+132n-127 4483
25. n²+3n-23 101 89. n²+48n-1 577 153. n²+84n+107 1657 217. n²+132n-157 4513
26. n²+20n-3 103 90. n²+44n-103 587 154. n²+39n-37 1669 218. n²-136n+107 4517
27. n²+12n-71 107 91. n²+24n-449 593 155. n²+39n-43 1693 219. n²+124n-829 4673
28. n²+9n-7 109 92. n²-25n+3 613 156. n²+60n-797 1697 220. n²-176n+2927 4817
29. n²-113 113 93. n²-56n+167 617 157. n²+84n+17 1747 221. n²-140n-3 4903
30. n²-24n+17 127 94. n²+19n-73 653 158. n²+72n-457 1753 222. n²+136n-349 4973
31. n²+20n-31 131 95. n²+48n-97 673 159. n²-84n-13 1777 223. n²-144n+191 4993
32. n²+12n-101 137 96. n²+3n-167 677 160. n²+84n-37 1801 224. n²-148n+467 5009
33. n²+24n+5 139 97. n²+48n-107 683 161. n²+43n-3 1861 225. n²+136n-457 5081
34. n²+9n-17 149 98. n²+23n-43 701 162. n²+84n-109 1873 226. n²+140n-373 5273
35. n²+13n+3 157 99. n²-56n+41 743 163. n²+43n-7 1877 227. n²+100n-2797 5297
36. n²+24n-19 163 100. n²+27n-7 757 164. n²-92n+227 1889 228. n²+69n-137 5309
37. n²-167 167 101. n²-24n-617 761 165. n²+84n-167 1931 229. n²+144n-337 5521
38. n²+n-43 173 102. n²-222n+17 769 166. n²+45n+23 1933 230. n²+75n-19 5701
39. n²-28n+17 179 103. n²+19n-103 773 167. n²+88n-13 1949 231. n²-156n+347 5737
40. n²+13n-3 181 104. n²+56n-3 787 168. n²+88n-43 1979 232. n²-156n+131 5953
41. n²-28n+5 191 105. n²+17n-127 797 169. n²+41n-79 1997 233. n²-156n+5 6079
42. n²-193 193 106. n²+56n-37 821 170. n²+84n-317 2081 234. n²+81n+41 6397
43. n²+3n-47 197 107. n²+56n-43 827 171. n²-92n+3 2113 235. n²-322n-3 6481
44. n²-28n-3 199 108. n²+27n-31 853 172. n²+88n-193 2129 236. n²+156n-653 6737
45. n²+58n-3 211 109. n²+40n-457 857 173. n²+76n-709 2153 237. n²+85n+3 7213
46. n²-227 227 110. n²-60n+37 863 174. n²+32n-2017 2273 238. n²-180n+563 7537
47. n²-233 233 111. n²-80n+719 881 175. n²+92n-181 2297 239. n²+132n-3221 7577
48. n²-32n+17 239 112. n²+48n-311 887 176. n²+96n-5 2309 240. n²+168n-617 7673
49. n²-36n+83 241 113. n²-60n-29 929 177. n²-96n-47 2351 241. n²+172n-397 7793
50. n²+32n+5 251 114. n²+31n+5 941 178. n²-104n+311 2393 242. n²-358n+773 7817
51. n²+16n-193 257 115. n²+52n-271 947 179. n²+96n-107 2411 243. n²-180n+227 7873
52. n²+28n-67 263 116. n²-88n+983 953 180. n²-100n+59 2441 244. n²+180n-277 8377
53. n²+15n-11 269 117. n²-68n+179 977 181. n²+29n-409 2477 245. n²-188n+17 8819
54. n²-66n+5 271 118. n²+52n-307 983 182. n²+198n-211 2503 246. n²-200n+839 9161
55. n²+15n-13 277 119. n²+25n-97 1013 183. n²+84n-853 2617 247. n²-204n+971 9433
56. n²+20n-181 281 120. n²-258n+337 1019 184. n²+51n-5 2621 248. n²+188n-997 9833
57. n²-36n+41 283 121. n²+64n+3 1021 185. n²+92n-541 2657 249. n²+406n-3 10303
58. n²+n-73 293 122. n²-64n-7 1031 186. n²-104n+17 2687 250. n²+172n-3037 10433
59. n²+70n-3 307 123. n²-72n+263 1033 187. n²+49n-73 2693 251. n²+103n+3 10597
60. n²-36n+13 311 124. n²+52n-373 1049 188. n²+49n-97 2789 252. n²-220n+1499 10601
61. n²+36n+11 313 125. n²+44n-613 1097 189. n²+108n+83 2833 253. n²-216n+311 11353
62. n²+13n-37 317 126. n²+134n-3 1123 190. n²-108n+59 2857 254. n²-232n+2063 11393
63. n²+36n-13 337 127. n²-72n+167 1129 191. n²-108n+19 2897 255. n²-240n+2767 11633
64. n²+36n-23 347 128. n²-68n+5 1151 192. n²-108n+13 2903 256. n²-224n+863 11681