Prime generators

# Development ofAlgorithmic Constructions

 05:56:22 19.Sep 2021

## 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