Inhaltsverzeichnis

Development of
Algorithmic Constructions

15:57:10
Deutsch
28.Mar 2024

Polynom = x^2-304x+607

0. Sequence

1. Algorithm

2. Mathematical background

3. Correctness of the algorithm

4. Infinity of the sequence

5. Sequence of the polynom with 1

6. Sequence of the polynom (only primes)

7. Distribution of the primes

8. Check for existing Integer Sequences by OEIS

0. Sequence

f(0) = 607 = 607
f(1) = 19 = 19
f(2) = 3 = 3
f(3) = 37 = 37
f(4) = 593 = 593
f(5) = 111 = 3*37
f(6) = 1181 = 1181
f(7) = 23 = 23
f(8) = 1761 = 3*587
f(9) = 1 = 1
f(10) = 2333 = 2333
f(11) = 327 = 3*109
f(12) = 2897 = 2897
f(13) = 397 = 397
f(14) = 3453 = 3*1151
f(15) = 233 = 233
f(16) = 4001 = 4001
f(17) = 267 = 3*89
f(18) = 4541 = 19*239
f(19) = 601 = 601
f(20) = 5073 = 3*19*89
f(21) = 667 = 23*29
f(22) = 5597 = 29*193
f(23) = 183 = 3*61
f(24) = 6113 = 6113
f(25) = 199 = 199
f(26) = 6621 = 3*2207
f(27) = 859 = 859
f(28) = 7121 = 7121
f(29) = 921 = 3*307
f(30) = 7613 = 23*331
f(31) = 491 = 491
f(32) = 8097 = 3*2699
f(33) = 521 = 521
f(34) = 8573 = 8573
f(35) = 1101 = 3*367
f(36) = 9041 = 9041
f(37) = 1159 = 19*61
f(38) = 9501 = 3*3167
f(39) = 19 = 19
f(40) = 9953 = 37*269
f(41) = 159 = 3*53
f(42) = 10397 = 37*281
f(43) = 1327 = 1327
f(44) = 10833 = 3*23*157
f(45) = 1381 = 1381
f(46) = 11261 = 11261
f(47) = 717 = 3*239
f(48) = 11681 = 11681
f(49) = 743 = 743
f(50) = 12093 = 3*29*139
f(51) = 1537 = 29*53
f(52) = 12497 = 12497
f(53) = 1587 = 3*23*23
f(54) = 12893 = 12893
f(55) = 409 = 409
f(56) = 13281 = 3*19*233
f(57) = 421 = 421
f(58) = 13661 = 19*719
f(59) = 1731 = 3*577
f(60) = 14033 = 14033
f(61) = 1777 = 1777
f(62) = 14397 = 3*4799
f(63) = 911 = 911
f(64) = 14753 = 14753
f(65) = 933 = 3*311
f(66) = 15101 = 15101
f(67) = 1909 = 23*83
f(68) = 15441 = 3*5147
f(69) = 1951 = 1951
f(70) = 15773 = 15773
f(71) = 249 = 3*83
f(72) = 16097 = 16097
f(73) = 127 = 127
f(74) = 16413 = 3*5471
f(75) = 2071 = 19*109
f(76) = 16721 = 23*727
f(77) = 2109 = 3*19*37
f(78) = 17021 = 17021
f(79) = 1073 = 29*37
f(80) = 17313 = 3*29*199
f(81) = 1091 = 1091
f(82) = 17597 = 17597
f(83) = 2217 = 3*739
f(84) = 17873 = 61*293
f(85) = 2251 = 2251
f(86) = 18141 = 3*6047
f(87) = 571 = 571
f(88) = 18401 = 18401
f(89) = 579 = 3*193
f(90) = 18653 = 23*811
f(91) = 2347 = 2347
f(92) = 18897 = 3*6299
f(93) = 2377 = 2377
f(94) = 19133 = 19*19*53
f(95) = 1203 = 3*401
f(96) = 19361 = 19*1019
f(97) = 1217 = 1217
f(98) = 19581 = 3*61*107
f(99) = 2461 = 23*107
f(100) = 19793 = 19793

1. Algorithm

If you are interested in some better algorithms have a look at quadr_Sieb_x^2+1.php.

2. Mathematical background

Lemma: If p | f(x) then also p | f(x+p) and p | f(-x-b/a) a) p | f(x) <=> ax^2 + bx + c = 0 mod p p | f(x+p) <=> a(x+p)^2 + b(x+p) + c = 0 mod p <=> ax^2 + 2axp + ap^2 + bx + bp + c = 0 mod p <=> ax^2 + bx + c = 0 mod p Thus if p | f(x) then p | f(x+p) b) if b = 0 mod a p | f(x) <=> ax^2 + bx + c = 0 mod p p | f(-x-b/a) <=> a(-x-b/a)^2 + b(-x-b/a) + c = 0 mod p <=> ax^2 + 2bx + b^2/a - bx - b^2/a + c = 0 mod p <=> ax^2 + bx + c = 0 mod p Thus if p | f(x) then p | f(-x-b/a)

3. Correctness of the algorithm

The proof for this polynom is similar to the proof for the polynom f(x)=x^2-4x+1. a) First terms for the polynom f(x) = x^2-304x+607

f(0)=607
f(1)=19
f(2)=3
f(3)=37
f(4)=593
f(5)=1
f(6)=1181
f(7)=23
f(8)=587
f(9)=1
f(10)=2333
f(11)=109
f(12)=2897
f(13)=397
f(14)=1151
f(15)=233
f(16)=4001
f(17)=89
f(18)=239
f(19)=601
f(20)=1
f(21)=29
f(22)=193
f(23)=61
f(24)=6113
f(25)=199
f(26)=2207
f(27)=859
f(28)=7121
f(29)=307
f(30)=331
f(31)=491
f(32)=2699
f(33)=521
f(34)=8573
f(35)=367
f(36)=9041
f(37)=1
f(38)=3167
f(39)=1
f(40)=269
f(41)=53
f(42)=281
f(43)=1327
f(44)=157
f(45)=1381
f(46)=11261
f(47)=1
f(48)=11681
f(49)=743
f(50)=139
f(51)=1
f(52)=12497
f(53)=1
f(54)=12893
f(55)=409
f(56)=1
f(57)=421
f(58)=719
f(59)=577
f(60)=14033
f(61)=1777
f(62)=4799
f(63)=911
f(64)=14753
f(65)=311
f(66)=15101
f(67)=83
f(68)=5147
f(69)=1951
f(70)=15773
f(71)=1
f(72)=16097
f(73)=127
f(74)=5471
f(75)=1
f(76)=727
f(77)=1
f(78)=17021
f(79)=1
f(80)=1
f(81)=1091
f(82)=17597
f(83)=739
f(84)=293
f(85)=2251
f(86)=6047
f(87)=571
f(88)=18401
f(89)=1
f(90)=811
f(91)=2347
f(92)=6299
f(93)=2377
f(94)=1
f(95)=401
f(96)=1019
f(97)=1217
f(98)=107
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2-304x+607 could be written as f(y)= y^2-22497 with x=y+152

c) Backsubstitution Beside by backsubstitution you get an estimation for the huge of the primes with p | f(x) and p < f(x) f'(y)>(2y-1) with with y=x-152
f'(x)>2x-305 with x > 150

4. Infinity of the sequence

The mathematical proof is analogue to the proof for the polynom f(x)=x^2+1

5. Sequence of the polynom with 1

607, 19, 3, 37, 593, 1, 1181, 23, 587, 1, 2333, 109, 2897, 397, 1151, 233, 4001, 89, 239, 601, 1, 29, 193, 61, 6113, 199, 2207, 859, 7121, 307, 331, 491, 2699, 521, 8573, 367, 9041, 1, 3167, 1, 269, 53, 281, 1327, 157, 1381, 11261, 1, 11681, 743, 139, 1, 12497, 1, 12893, 409, 1, 421, 719, 577, 14033, 1777, 4799, 911, 14753, 311, 15101, 83, 5147, 1951, 15773, 1, 16097, 127, 5471, 1, 727, 1, 17021, 1, 1, 1091, 17597, 739, 293, 2251, 6047, 571, 18401, 1, 811, 2347, 6299, 2377, 1, 401, 1019, 1217, 107, 1, 19793, 829, 19997, 1, 1, 317, 229, 853, 709, 1, 6911, 1301, 20897, 1, 569, 1, 191, 2659, 21341, 223, 197, 673, 313, 2707, 21713, 907, 21821, 1367, 7307, 1373, 22013, 919, 1163, 2767, 389, 347, 967, 1, 769, 2791, 7451, 2797, 22397, 467, 22433, 1, 7487, 1, 22481, 937, 271, 1, 7499, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 613, 1, 2467, 1, 1, 1, 1249, 509, 1, 1, 5059, 337, 1, 379, 1, 1, 373, 929, 2593, 1, 1, 1, 9187, 1193, 3301, 1283, 10627, 1, 1, 733, 1, 1559, 443, 1, 1, 1, 4789, 461, 15139, 647, 15919, 2039, 5569, 1069, 761, 1, 18307, 2339, 6373, 2441, 1, 1, 1093, 1, 1, 2753, 22447, 953, 1013, 1483, 8053, 1, 863, 1061, 25903, 1, 8929, 1, 1, 1, 28579, 1, 9829, 1, 30403, 643, 31327, 1987, 10753, 4091, 33199, 1, 34147, 541, 11701, 1, 36067, 1523, 37039, 4691, 1, 1, 2053, 823, 1, 1, 13669, 5189, 42019, 1, 1, 1361, 1, 5573, 1, 1901, 46147, 2917, 15733, 1, 48259, 1, 1, 1, 1, 1, 51487, 1, 52579, 1, 617, 6779, 54787, 1153, 55903, 3529, 19009, 1, 3061, 2447, 3121, 1871, 20149, 1907, 61603, 2591, 2729, 7919, 21313, 1, 65119, 1, 1087, 8363, 22501, 8513, 1, 1, 2411, 1, 1031, 8969, 72367, 3041, 827, 4639, 1, 1, 76099, 1, 77359, 9749, 26209, 2477, 79903, 839, 4273, 1, 1447, 10391, 1, 1759, 85087, 1, 1, 10883, 2371, 1, 1, 701, 30133, 1423, 3989, 3851, 93103, 1, 31489, 1, 1, 2011, 1, 12239, 32869, 12413, 100003, 1049, 4409, 3191, 34273, 12941, 104239, 4373, 105667, 1, 1879, 1, 1, 1, 1, 13841, 1, 1753, 112927, 1, 1, 1, 38629, 1, 1097, 1, 2243, 7477, 40129, 797, 877, 1, 123427, 3881, 1811, 3929, 126499, 5303, 128047, 16103, 43201, 1, 4523, 2749, 132739, 16691, 44773, 16889, 1, 1, 7237, 2161, 1, 17489, 1291, 5897, 3847, 1, 1297, 9049, 145603, 6101, 1, 1, 49633, 4679, 150559, 1, 1, 1, 1, 1, 991, 3259, 157279, 9883, 1, 19979, 160687, 1, 1, 2551, 54709, 1289, 2719, 6947, 8821, 21059, 2971, 10639, 171103, 3583, 172867, 1, 2531, 1, 176419, 1847, 178207, 1, 2069, 22613, 1, 1, 1321, 1, 61813, 1, 1, 7841, 1489, 23753, 63649, 1499, 192799, 1009, 194659, 1063, 1, 24683, 997, 4153, 3779, 12577, 3547, 25391, 1, 8543, 7103, 1, 1873, 1, 1, 8783, 1, 26591, 71233, 13417, 2423, 4513, 9461, 1, 73189, 1451, 221539, 1, 2693, 1, 75169, 1231, 2741, 9521, 229507, 14407, 1, 14533, 1, 1, 8123, 29573, 79201, 7457, 12613, 1, 12721, 30341, 1, 1, 1, 1, 1579, 15559, 3623, 31379, 252079, 1, 254179, 1, 85429, 4021, 258403, 1, 260527, 1721, 87553, 1, 1, 1, 266947, 33503, 1, 33773, 4447, 2837, 1, 1, 91873, 34589, 1, 11621, 14737, 17569, 4951, 17707, 7687, 11897, 1, 35969, 96289, 1, 291103, 1, 1259, 36809, 98533, 1279, 10271, 6229, 13049, 1, 100801, 1997, 304687, 12743, 1, 9629, 103093, 1, 5879, 1, 3527, 39383, 4583, 1, 318559, 6661, 320899, 1, 1, 1, 17137, 1, 327967, 1, 3797, 1429, 1, 13913, 335107, 21019, 112501, 21169, 339907, 1, 342319, 1867, 114913, 1, 347167, 1, 349603, 43853, 1, 44159, 15413, 7411, 356959, 1, 119809, 45083, 361903, 15131, 3343, 1, 4217, 1, 19441, 15443, 1, 46643, 3373, 1, 376927, 7879, 379459, 47591, 1, 2083, 384547, 4019, 1, 1, 1, 48869, 392239, 1, 394819, 1303, 132469, 24919, 1487, 1, 13883, 1741, 1, 1, 1, 2131, 2953, 51473, 5987, 51803, 5009, 8689, 1, 1, 1, 1427, 423727, 1, 1, 13367, 1, 13451, 18773, 18047, 434479, 1, 2389, 27409, 439903, 1, 15263, 1, 2801, 2939, 4111, 2341, 450847, 3533, 151201, 56873, 456367, 19073, 8663, 1, 1439, 1, 1, 19421, 467503, 58613, 1, 14741, 1, 4943, 20693, 59669, 159589, 1, 16607, 1, 484447, 30367, 1, 61091, 490159, 20483, 493027, 3863, 7187, 1, 498787, 1, 2521, 1, 168193, 31627, 2657, 1, 510403, 1, 1, 1, 1, 5393, 3307, 1, 174049, 1, 1, 1, 27793, 1, 177013, 1, 534019, 1, 537007, 1, 180001, 8461, 23609, 1, 546019, 1, 1, 68819, 6203, 1, 1, 1831, 186049, 69959, 561199, 23447, 24533, 17681, 6521, 1, 570403, 23831, 573487, 71879, 192193, 1571, 15667, 12109, 1, 73043, 1, 73433, 589027, 1, 1789, 9277, 3253, 74609, 598447, 1, 11351, 37699, 201589, 37897, 607939, 1, 1, 1, 1, 1, 1, 6449, 5801, 1, 207973, 78191, 627139, 13099, 1, 39499, 1663, 1, 27689, 1, 640099, 1, 11287, 5039, 34033, 27011, 3299, 3541, 1, 40927, 656479, 13711, 22751, 2851, 2663, 83093, 666403, 6959, 8069, 20981, 1, 1, 2903, 1, 679747, 42589, 2089, 1, 1, 1, 1, 86441, 1, 1,

6. Sequence of the polynom (only primes)

607, 19, 3, 37, 593, 1181, 23, 587, 2333, 109, 2897, 397, 1151, 233, 4001, 89, 239, 601, 29, 193, 61, 6113, 199, 2207, 859, 7121, 307, 331, 491, 2699, 521, 8573, 367, 9041, 3167, 269, 53, 281, 1327, 157, 1381, 11261, 11681, 743, 139, 12497, 12893, 409, 421, 719, 577, 14033, 1777, 4799, 911, 14753, 311, 15101, 83, 5147, 1951, 15773, 16097, 127, 5471, 727, 17021, 1091, 17597, 739, 293, 2251, 6047, 571, 18401, 811, 2347, 6299, 2377, 401, 1019, 1217, 107, 19793, 829, 19997, 317, 229, 853, 709, 6911, 1301, 20897, 569, 191, 2659, 21341, 223, 197, 673, 313, 2707, 21713, 907, 21821, 1367, 7307, 1373, 22013, 919, 1163, 2767, 389, 347, 967, 769, 2791, 7451, 2797, 22397, 467, 22433, 7487, 22481, 937, 271, 7499, 613, 2467, 1249, 509, 5059, 337, 379, 373, 929, 2593, 9187, 1193, 3301, 1283, 10627, 733, 1559, 443, 4789, 461, 15139, 647, 15919, 2039, 5569, 1069, 761, 18307, 2339, 6373, 2441, 1093, 2753, 22447, 953, 1013, 1483, 8053, 863, 1061, 25903, 8929, 28579, 9829, 30403, 643, 31327, 1987, 10753, 4091, 33199, 34147, 541, 11701, 36067, 1523, 37039, 4691, 2053, 823, 13669, 5189, 42019, 1361, 5573, 1901, 46147, 2917, 15733, 48259, 51487, 52579, 617, 6779, 54787, 1153, 55903, 3529, 19009, 3061, 2447, 3121, 1871, 20149, 1907, 61603, 2591, 2729, 7919, 21313, 65119, 1087, 8363, 22501, 8513, 2411, 1031, 8969, 72367, 3041, 827, 4639, 76099, 77359, 9749, 26209, 2477, 79903, 839, 4273, 1447, 10391, 1759, 85087, 10883, 2371, 701, 30133, 1423, 3989, 3851, 93103, 31489, 2011, 12239, 32869, 12413, 100003, 1049, 4409, 3191, 34273, 12941, 104239, 4373, 105667, 1879, 13841, 1753, 112927, 38629, 1097, 2243, 7477, 40129, 797, 877, 123427, 3881, 1811, 3929, 126499, 5303, 128047, 16103, 43201, 4523, 2749, 132739, 16691, 44773, 16889, 7237, 2161, 17489, 1291, 5897, 3847, 1297, 9049, 145603, 6101, 49633, 4679, 150559, 991, 3259, 157279, 9883, 19979, 160687, 2551, 54709, 1289, 2719, 6947, 8821, 21059, 2971, 10639, 171103, 3583, 172867, 2531, 176419, 1847, 178207, 2069, 22613, 1321, 61813, 7841, 1489, 23753, 63649, 1499, 192799, 1009, 194659, 1063, 24683, 997, 4153, 3779, 12577, 3547, 25391, 8543, 7103, 1873, 8783, 26591, 71233, 13417, 2423, 4513, 9461, 73189, 1451, 221539, 2693, 75169, 1231, 2741, 9521, 229507, 14407, 14533, 8123, 29573, 79201, 7457, 12613, 12721, 30341, 1579, 15559, 3623, 31379, 252079, 254179, 85429, 4021, 258403, 260527, 1721, 87553, 266947, 33503, 33773, 4447, 2837, 91873, 34589, 11621, 14737, 17569, 4951, 17707, 7687, 11897, 35969, 96289, 291103, 1259, 36809, 98533, 1279, 10271, 6229, 13049, 100801, 1997, 304687, 12743, 9629, 103093, 5879, 3527, 39383, 4583, 318559, 6661, 320899, 17137, 327967, 3797, 1429, 13913, 335107, 21019, 112501, 21169, 339907, 342319, 1867, 114913, 347167, 349603, 43853, 44159, 15413, 7411, 356959, 119809, 45083, 361903, 15131, 3343, 4217, 19441, 15443, 46643, 3373, 376927, 7879, 379459, 47591, 2083, 384547, 4019, 48869, 392239, 394819, 1303, 132469, 24919, 1487, 13883, 1741, 2131, 2953, 51473, 5987, 51803, 5009, 8689, 1427, 423727, 13367, 13451, 18773, 18047, 434479, 2389, 27409, 439903, 15263, 2801, 2939, 4111, 2341, 450847, 3533, 151201, 56873, 456367, 19073, 8663, 1439, 19421, 467503, 58613, 14741, 4943, 20693, 59669, 159589, 16607, 484447, 30367, 61091, 490159, 20483, 493027, 3863, 7187, 498787, 2521, 168193, 31627, 2657, 510403, 5393, 3307, 174049, 27793, 177013, 534019, 537007, 180001, 8461, 23609, 546019, 68819, 6203, 1831, 186049, 69959, 561199, 23447, 24533, 17681, 6521, 570403, 23831, 573487, 71879, 192193, 1571, 15667, 12109, 73043, 73433, 589027, 1789, 9277, 3253, 74609, 598447, 11351, 37699, 201589, 37897, 607939, 6449, 5801, 207973, 78191, 627139, 13099, 39499, 1663, 27689, 640099, 11287, 5039, 34033, 27011, 3299, 3541, 40927, 656479, 13711, 22751, 2851, 2663, 83093, 666403, 6959, 8069, 20981, 2903, 679747, 42589, 2089, 86441,

7. Distribution of the primes

Legend of the table: I distinguish between primes p= x^2-304x+607 and
the reducible primes which appear as divisor for the first time
p | x^2-304x+607 and p < x^2-304x+607

To avoid confusion with the number of primes:
I did not count the primes <= A
but I counted the primes appending the x and therefore the x <= A

8. Check for existing Integer Sequences by OEIS

Found in Database : 607, 19, 3, 37, 593, 1, 1181, 23, 587, 1, 2333, 109, 2897, 397, 1151, 233, 4001, 89, 239, 601,
Found in Database : 607, 19, 3, 37, 593, 1181, 23, 587, 2333, 109, 2897, 397, 1151, 233, 4001, 89, 239, 601, 29, 193, 61, 6113, 199, 2207, 859, 7121, 307, 331, 491, 2699, 521, 8573, 367, 9041, 3167,
Found in Database : 3, 19, 23, 29, 37, 53, 61, 83, 89, 107, 109, 127, 139,