Inhaltsverzeichnis

Development of
Algorithmic Constructions

09:46:47
Deutsch
29.Mar 2024

Polynom = x^2-208x+863

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) = 863 = 863
f(1) = 41 = 41
f(2) = 451 = 11*41
f(3) = 31 = 31
f(4) = 47 = 47
f(5) = 19 = 19
f(6) = 349 = 349
f(7) = 17 = 17
f(8) = 737 = 11*67
f(9) = 29 = 29
f(10) = 1117 = 1117
f(11) = 163 = 163
f(12) = 1489 = 1489
f(13) = 209 = 11*19
f(14) = 1853 = 17*109
f(15) = 127 = 127
f(16) = 2209 = 47*47
f(17) = 149 = 149
f(18) = 2557 = 2557
f(19) = 341 = 11*31
f(20) = 2897 = 2897
f(21) = 383 = 383
f(22) = 3229 = 3229
f(23) = 53 = 53
f(24) = 3553 = 11*17*19
f(25) = 29 = 29
f(26) = 3869 = 53*73
f(27) = 503 = 503
f(28) = 4177 = 4177
f(29) = 541 = 541
f(30) = 4477 = 11*11*37
f(31) = 289 = 17*17
f(32) = 4769 = 19*251
f(33) = 307 = 307
f(34) = 5053 = 31*163
f(35) = 649 = 11*59
f(36) = 5329 = 73*73
f(37) = 683 = 683
f(38) = 5597 = 29*193
f(39) = 179 = 179
f(40) = 5857 = 5857
f(41) = 187 = 11*17
f(42) = 6109 = 41*149
f(43) = 779 = 19*41
f(44) = 6353 = 6353
f(45) = 809 = 809
f(46) = 6589 = 11*599
f(47) = 419 = 419
f(48) = 6817 = 17*401
f(49) = 433 = 433
f(50) = 7037 = 31*227
f(51) = 893 = 19*47
f(52) = 7249 = 11*659
f(53) = 919 = 919
f(54) = 7453 = 29*257
f(55) = 59 = 59
f(56) = 7649 = 7649
f(57) = 121 = 11*11
f(58) = 7837 = 17*461
f(59) = 991 = 991
f(60) = 8017 = 8017
f(61) = 1013 = 1013
f(62) = 8189 = 19*431
f(63) = 517 = 11*47
f(64) = 8353 = 8353
f(65) = 527 = 17*31
f(66) = 8509 = 67*127
f(67) = 1073 = 29*37
f(68) = 8657 = 11*787
f(69) = 1091 = 1091
f(70) = 8797 = 19*463
f(71) = 277 = 277
f(72) = 8929 = 8929
f(73) = 281 = 281
f(74) = 9053 = 11*823
f(75) = 1139 = 17*67
f(76) = 9169 = 53*173
f(77) = 1153 = 1153
f(78) = 9277 = 9277
f(79) = 583 = 11*53
f(80) = 9377 = 9377
f(81) = 589 = 19*31
f(82) = 9469 = 17*557
f(83) = 1189 = 29*41
f(84) = 9553 = 41*233
f(85) = 1199 = 11*109
f(86) = 9629 = 9629
f(87) = 151 = 151
f(88) = 9697 = 9697
f(89) = 19 = 19
f(90) = 9757 = 11*887
f(91) = 1223 = 1223
f(92) = 9809 = 17*577
f(93) = 1229 = 1229
f(94) = 9853 = 59*167
f(95) = 617 = 617
f(96) = 9889 = 11*29*31
f(97) = 619 = 619
f(98) = 9917 = 47*211
f(99) = 1241 = 17*73
f(100) = 9937 = 19*523

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-208x+863

f(0)=863
f(1)=41
f(2)=11
f(3)=31
f(4)=47
f(5)=19
f(6)=349
f(7)=17
f(8)=67
f(9)=29
f(10)=1117
f(11)=163
f(12)=1489
f(13)=1
f(14)=109
f(15)=127
f(16)=1
f(17)=149
f(18)=2557
f(19)=1
f(20)=2897
f(21)=383
f(22)=3229
f(23)=53
f(24)=1
f(25)=1
f(26)=73
f(27)=503
f(28)=4177
f(29)=541
f(30)=37
f(31)=1
f(32)=251
f(33)=307
f(34)=1
f(35)=59
f(36)=1
f(37)=683
f(38)=193
f(39)=179
f(40)=5857
f(41)=1
f(42)=1
f(43)=1
f(44)=6353
f(45)=809
f(46)=599
f(47)=419
f(48)=401
f(49)=433
f(50)=227
f(51)=1
f(52)=659
f(53)=919
f(54)=257
f(55)=1
f(56)=7649
f(57)=1
f(58)=461
f(59)=991
f(60)=8017
f(61)=1013
f(62)=431
f(63)=1
f(64)=8353
f(65)=1
f(66)=1
f(67)=1
f(68)=787
f(69)=1091
f(70)=463
f(71)=277
f(72)=8929
f(73)=281
f(74)=823
f(75)=1
f(76)=173
f(77)=1153
f(78)=9277
f(79)=1
f(80)=9377
f(81)=1
f(82)=557
f(83)=1
f(84)=233
f(85)=1
f(86)=9629
f(87)=151
f(88)=9697
f(89)=1
f(90)=887
f(91)=1223
f(92)=577
f(93)=1229
f(94)=167
f(95)=617
f(96)=1
f(97)=619
f(98)=211
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2-208x+863 could be written as f(y)= y^2-9953 with x=y+104

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-104
f'(x)>2x-209 with x > 100

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

863, 41, 11, 31, 47, 19, 349, 17, 67, 29, 1117, 163, 1489, 1, 109, 127, 1, 149, 2557, 1, 2897, 383, 3229, 53, 1, 1, 73, 503, 4177, 541, 37, 1, 251, 307, 1, 59, 1, 683, 193, 179, 5857, 1, 1, 1, 6353, 809, 599, 419, 401, 433, 227, 1, 659, 919, 257, 1, 7649, 1, 461, 991, 8017, 1013, 431, 1, 8353, 1, 1, 1, 787, 1091, 463, 277, 8929, 281, 823, 1, 173, 1153, 9277, 1, 9377, 1, 557, 1, 233, 1, 9629, 151, 9697, 1, 887, 1223, 577, 1229, 167, 617, 1, 619, 211, 1, 523, 113, 9949, 311, 269, 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, 1283, 1, 1, 241, 1, 1, 2591, 1, 1, 409, 1, 467, 1, 263, 4447, 293, 4931, 647, 1, 709, 5923, 1, 1, 1, 6947, 1, 1, 967, 1, 1, 8543, 1, 9091, 1171, 877, 1, 10211, 1, 1, 1, 1033, 1, 1, 1531, 12547, 1, 13151, 1, 13763, 1759, 757, 1, 883, 479, 15647, 499, 1481, 1, 16943, 1, 607, 1, 1, 1163, 18947, 2411, 1, 1, 20323, 1, 21023, 1, 701, 1, 22447, 2851, 1, 1471, 1, 1, 1297, 1, 25391, 3221, 2377, 829, 1583, 853, 1, 1, 28463, 3607, 29251, 1, 30047, 1, 30851, 3907, 31663, 1, 2953, 1, 33311, 1, 34147, 1, 3181, 1, 491, 2267, 1, 1, 37571, 4751, 38447, 4861, 1063, 1, 1, 1, 1, 5197, 3821, 1, 641, 2713, 2309, 1, 4073, 5659, 1, 1, 46691, 1, 1, 1, 48611, 1, 1, 569, 857, 3191, 51551, 3253, 1, 1, 53551, 1, 54563, 1721, 1, 1753, 56611, 1, 3391, 661, 3089, 3701, 59743, 3767, 1483, 1, 61871, 1, 3313, 1, 5821, 1009, 65123, 8209, 1409, 1, 6121, 4243, 68447, 1, 2399, 797, 4159, 1, 71843, 1, 1553, 1, 1399, 9341, 593, 1, 1, 4817, 2099, 1, 2719, 9931, 1, 1, 2621, 1279, 82463, 1, 1249, 1, 1, 10691, 1, 1, 1, 5501, 88643, 11159, 743, 11317, 1, 1, 1, 2909, 8521, 1, 1, 11959, 96323, 1, 5743, 6143, 98947, 12451, 100271, 1, 101603, 1, 911, 1619, 1, 13121, 3643, 13291, 947, 1, 1, 1, 1, 13807, 2711, 1, 1, 3539, 6703, 3583, 115363, 1319, 4027, 773, 118211, 7433, 1, 7523, 1, 15227, 1, 811, 11273, 1949, 125471, 1, 1, 1451, 128431, 1, 751, 8167, 6917, 1, 1, 983, 4337, 16901, 1, 4273, 7237, 1, 8179, 17477, 12781, 1, 3467, 8933, 143711, 821, 145283, 1, 1, 18457, 5119, 1, 1, 2357, 151651, 1, 13933, 19259, 154883, 1, 156511, 9833, 1307, 1, 159791, 1181, 1, 1, 1, 1, 164771, 1, 9791, 1901, 8849, 1, 169823, 10667, 1, 1, 1, 1, 1, 1, 16061, 1, 178403, 22409, 1193, 1, 181891, 11423, 2741, 1, 5981, 1, 5059, 23509, 1, 1, 17341, 1, 192547, 24181, 1, 24407, 1049, 1, 6827, 1, 199811, 2281, 10613, 25321, 3449, 1597, 1, 1, 1, 26017, 209071, 26251, 1, 1, 1, 1, 214723, 26959, 1, 27197, 218531, 1, 220447, 1, 3769, 27917, 224303, 971, 1, 1291, 1, 14323, 12113, 1, 21101, 29137, 234083, 3673, 236063, 1, 1, 29881, 240047, 1039, 4567, 1381, 7873, 1, 3371, 1, 1093, 1, 250147, 1, 6151, 1, 1, 1877, 3511, 1693, 6983, 1, 23677, 1, 15443, 1, 1, 3019, 2447, 1, 14149, 4217, 9343, 1, 16063, 34267, 1847, 1, 1327, 17401, 1, 2063, 281647, 1, 25801, 1, 285983, 8971, 2269, 1, 290351, 2143, 9437, 18353, 294751, 1, 7243, 1, 17599, 37537, 1, 1, 303647, 2381, 2707, 38377, 1, 1, 1, 19471, 2767, 1783, 6701, 39511, 10939, 2341, 1, 1, 321823, 10093, 324131, 1, 1, 1321, 2017, 1213, 1, 1, 30313, 1, 11579, 1, 19891, 1, 9203, 1, 8363, 1, 345263, 1, 347651, 21803, 1, 1, 1, 44207, 1, 1, 357283, 1, 1, 11279, 362147, 1, 1, 4157, 1523, 23017, 1, 1, 371971, 4241, 374447, 1, 376931, 1, 2029, 1487, 1, 1, 12401, 1303, 1, 1277, 5813, 24421, 23059, 1, 9623, 49477, 1, 1, 399647, 1, 21169, 1627, 404783, 1, 1, 25541, 409951, 25703, 21713, 1, 1, 52057, 417763, 1637, 420383, 1, 1, 1, 1, 1, 5867, 2441, 1, 27017, 11719, 54367, 2333, 2879, 1669, 13759, 441631, 1, 1, 1, 10903, 1367, 2693, 1, 23813, 1, 455171, 1, 457903, 1, 460643, 7219, 1, 3631, 1, 58441, 27583, 58787, 471683, 29567, 43133, 29741, 8089, 1, 480047, 5471, 28403, 1, 16747, 1, 2531, 1, 7333, 3623, 494147, 1, 45181, 31151, 9431, 62659, 502703, 1, 1, 1, 2939, 1, 3137, 5827, 4049, 1, 1601, 32411, 520031, 2963, 522947, 65551, 525871, 2273, 48073, 1, 1, 1, 3541, 67021, 1, 67391, 540611, 1993, 4987, 1, 1, 68507, 549551, 68881, 1, 1, 17921, 1, 558563, 70009, 2687, 1, 1, 1, 33391, 35573, 1789, 71527, 30197, 71909, 8609, 1, 1, 18169, 1, 73061, 3881, 1, 589123, 1, 592223, 1, 54121, 74611, 598447, 1, 5519, 1, 54973, 9473, 607843, 4481, 5407, 6961, 614147, 1, 617311, 1, 1, 7069, 1787, 78157, 1, 1, 1, 19739, 33329, 79357, 1, 1697, 58153, 1, 8807, 40283, 646147, 1, 2311, 4283, 1, 10223, 11117, 1, 659171, 82601, 1, 1, 60521, 1, 669023, 1, 672323, 84247, 3613, 2731, 3793, 21269, 1, 1, 1, 85909, 11677, 1, 1, 3943, 1, 1, 10433, 87587, 63853, 1, 705763, 5527, 709151, 1, 1, 1, 15233, 1, 3169, 1, 722783, 45281, 1811, 4789, 23537, 8311, 1, 22963, 2659, 23071, 67273, 92717, 1, 93151, 39313, 1, 4013, 1, 2683, 1, 1, 8627, 1, 1, 764447, 1, 18731, 8747, 771503, 1, 775043, 1, 1913, 1, 782147, 1, 1, 1, 1, 1,

6. Sequence of the polynom (only primes)

863, 41, 11, 31, 47, 19, 349, 17, 67, 29, 1117, 163, 1489, 109, 127, 149, 2557, 2897, 383, 3229, 53, 73, 503, 4177, 541, 37, 251, 307, 59, 683, 193, 179, 5857, 6353, 809, 599, 419, 401, 433, 227, 659, 919, 257, 7649, 461, 991, 8017, 1013, 431, 8353, 787, 1091, 463, 277, 8929, 281, 823, 173, 1153, 9277, 9377, 557, 233, 9629, 151, 9697, 887, 1223, 577, 1229, 167, 617, 619, 211, 523, 113, 9949, 311, 269, 1283, 241, 2591, 409, 467, 263, 4447, 293, 4931, 647, 709, 5923, 6947, 967, 8543, 9091, 1171, 877, 10211, 1033, 1531, 12547, 13151, 13763, 1759, 757, 883, 479, 15647, 499, 1481, 16943, 607, 1163, 18947, 2411, 20323, 21023, 701, 22447, 2851, 1471, 1297, 25391, 3221, 2377, 829, 1583, 853, 28463, 3607, 29251, 30047, 30851, 3907, 31663, 2953, 33311, 34147, 3181, 491, 2267, 37571, 4751, 38447, 4861, 1063, 5197, 3821, 641, 2713, 2309, 4073, 5659, 46691, 48611, 569, 857, 3191, 51551, 3253, 53551, 54563, 1721, 1753, 56611, 3391, 661, 3089, 3701, 59743, 3767, 1483, 61871, 3313, 5821, 1009, 65123, 8209, 1409, 6121, 4243, 68447, 2399, 797, 4159, 71843, 1553, 1399, 9341, 593, 4817, 2099, 2719, 9931, 2621, 1279, 82463, 1249, 10691, 5501, 88643, 11159, 743, 11317, 2909, 8521, 11959, 96323, 5743, 6143, 98947, 12451, 100271, 101603, 911, 1619, 13121, 3643, 13291, 947, 13807, 2711, 3539, 6703, 3583, 115363, 1319, 4027, 773, 118211, 7433, 7523, 15227, 811, 11273, 1949, 125471, 1451, 128431, 751, 8167, 6917, 983, 4337, 16901, 4273, 7237, 8179, 17477, 12781, 3467, 8933, 143711, 821, 145283, 18457, 5119, 2357, 151651, 13933, 19259, 154883, 156511, 9833, 1307, 159791, 1181, 164771, 9791, 1901, 8849, 169823, 10667, 16061, 178403, 22409, 1193, 181891, 11423, 2741, 5981, 5059, 23509, 17341, 192547, 24181, 24407, 1049, 6827, 199811, 2281, 10613, 25321, 3449, 1597, 26017, 209071, 26251, 214723, 26959, 27197, 218531, 220447, 3769, 27917, 224303, 971, 1291, 14323, 12113, 21101, 29137, 234083, 3673, 236063, 29881, 240047, 1039, 4567, 1381, 7873, 3371, 1093, 250147, 6151, 1877, 3511, 1693, 6983, 23677, 15443, 3019, 2447, 14149, 4217, 9343, 16063, 34267, 1847, 1327, 17401, 2063, 281647, 25801, 285983, 8971, 2269, 290351, 2143, 9437, 18353, 294751, 7243, 17599, 37537, 303647, 2381, 2707, 38377, 19471, 2767, 1783, 6701, 39511, 10939, 2341, 321823, 10093, 324131, 1321, 2017, 1213, 30313, 11579, 19891, 9203, 8363, 345263, 347651, 21803, 44207, 357283, 11279, 362147, 4157, 1523, 23017, 371971, 4241, 374447, 376931, 2029, 1487, 12401, 1303, 1277, 5813, 24421, 23059, 9623, 49477, 399647, 21169, 1627, 404783, 25541, 409951, 25703, 21713, 52057, 417763, 1637, 420383, 5867, 2441, 27017, 11719, 54367, 2333, 2879, 1669, 13759, 441631, 10903, 1367, 2693, 23813, 455171, 457903, 460643, 7219, 3631, 58441, 27583, 58787, 471683, 29567, 43133, 29741, 8089, 480047, 5471, 28403, 16747, 2531, 7333, 3623, 494147, 45181, 31151, 9431, 62659, 502703, 2939, 3137, 5827, 4049, 1601, 32411, 520031, 2963, 522947, 65551, 525871, 2273, 48073, 3541, 67021, 67391, 540611, 1993, 4987, 68507, 549551, 68881, 17921, 558563, 70009, 2687, 33391, 35573, 1789, 71527, 30197, 71909, 8609, 18169, 73061, 3881, 589123, 592223, 54121, 74611, 598447, 5519, 54973, 9473, 607843, 4481, 5407, 6961, 614147, 617311, 7069, 1787, 78157, 19739, 33329, 79357, 1697, 58153, 8807, 40283, 646147, 2311, 4283, 10223, 11117, 659171, 82601, 60521, 669023, 672323, 84247, 3613, 2731, 3793, 21269, 85909, 11677, 3943, 10433, 87587, 63853, 705763, 5527, 709151, 15233, 3169, 722783, 45281, 1811, 4789, 23537, 8311, 22963, 2659, 23071, 67273, 92717, 93151, 39313, 4013, 2683, 8627, 764447, 18731, 8747, 771503, 775043, 1913, 782147,

7. Distribution of the primes

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

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 : 863, 41, 11, 31, 47, 19, 349, 17, 67, 29, 1117, 163, 1489, 1, 109, 127, 1, 149, 2557, 1,
Found in Database : 863, 41, 11, 31, 47, 19, 349, 17, 67, 29, 1117, 163, 1489, 109, 127, 149, 2557, 2897, 383, 3229, 53, 73, 503, 4177, 541, 37, 251, 307, 59, 683, 193, 179,
Found in Database : 11, 17, 19, 29, 31, 37, 41, 47, 53, 59, 67, 73, 109, 113, 127, 149,