Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:49:24
Deutsch
28.Mar 2024

Polynom = x^2-358x+773

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) = 773 = 773
f(1) = 13 = 13
f(2) = 61 = 61
f(3) = 73 = 73
f(4) = 643 = 643
f(5) = 31 = 31
f(6) = 1339 = 13*103
f(7) = 421 = 421
f(8) = 2027 = 2027
f(9) = 37 = 37
f(10) = 2707 = 2707
f(11) = 761 = 761
f(12) = 3379 = 31*109
f(13) = 29 = 29
f(14) = 4043 = 13*311
f(15) = 1093 = 1093
f(16) = 4699 = 37*127
f(17) = 157 = 157
f(18) = 5347 = 5347
f(19) = 1417 = 13*109
f(20) = 5987 = 5987
f(21) = 197 = 197
f(22) = 6619 = 6619
f(23) = 1733 = 1733
f(24) = 7243 = 7243
f(25) = 59 = 59
f(26) = 7859 = 29*271
f(27) = 2041 = 13*157
f(28) = 8467 = 8467
f(29) = 137 = 137
f(30) = 9067 = 9067
f(31) = 2341 = 2341
f(32) = 9659 = 13*743
f(33) = 311 = 311
f(34) = 10243 = 10243
f(35) = 2633 = 2633
f(36) = 10819 = 31*349
f(37) = 347 = 347
f(38) = 11387 = 59*193
f(39) = 2917 = 2917
f(40) = 11947 = 13*919
f(41) = 191 = 191
f(42) = 12499 = 29*431
f(43) = 3193 = 31*103
f(44) = 13043 = 13043
f(45) = 13 = 13
f(46) = 13579 = 37*367
f(47) = 3461 = 3461
f(48) = 14107 = 14107
f(49) = 449 = 449
f(50) = 14627 = 14627
f(51) = 3721 = 61*61
f(52) = 15139 = 15139
f(53) = 481 = 13*37
f(54) = 15643 = 15643
f(55) = 3973 = 29*137
f(56) = 16139 = 16139
f(57) = 1 = 1
f(58) = 16627 = 13*1279
f(59) = 4217 = 4217
f(60) = 17107 = 17107
f(61) = 271 = 271
f(62) = 17579 = 17579
f(63) = 4453 = 61*73
f(64) = 18043 = 18043
f(65) = 571 = 571
f(66) = 18499 = 13*1423
f(67) = 4681 = 31*151
f(68) = 18947 = 18947
f(69) = 599 = 599
f(70) = 19387 = 19387
f(71) = 4901 = 13*13*29
f(72) = 19819 = 19819
f(73) = 313 = 313
f(74) = 20243 = 31*653
f(75) = 5113 = 5113
f(76) = 20659 = 73*283
f(77) = 163 = 163
f(78) = 21067 = 21067
f(79) = 5317 = 13*409
f(80) = 21467 = 21467
f(81) = 677 = 677
f(82) = 21859 = 21859
f(83) = 5513 = 37*149
f(84) = 22243 = 13*29*59
f(85) = 701 = 701
f(86) = 22619 = 22619
f(87) = 5701 = 5701
f(88) = 22987 = 127*181
f(89) = 181 = 181
f(90) = 23347 = 37*631
f(91) = 5881 = 5881
f(92) = 23699 = 13*1823
f(93) = 373 = 373
f(94) = 24043 = 24043
f(95) = 6053 = 6053
f(96) = 24379 = 24379
f(97) = 767 = 13*59
f(98) = 24707 = 31*797
f(99) = 6217 = 6217
f(100) = 25027 = 29*863

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-358x+773

f(0)=773
f(1)=13
f(2)=61
f(3)=73
f(4)=643
f(5)=31
f(6)=103
f(7)=421
f(8)=2027
f(9)=37
f(10)=2707
f(11)=761
f(12)=109
f(13)=29
f(14)=311
f(15)=1093
f(16)=127
f(17)=157
f(18)=5347
f(19)=1
f(20)=5987
f(21)=197
f(22)=6619
f(23)=1733
f(24)=7243
f(25)=59
f(26)=271
f(27)=1
f(28)=8467
f(29)=137
f(30)=9067
f(31)=2341
f(32)=743
f(33)=1
f(34)=10243
f(35)=2633
f(36)=349
f(37)=347
f(38)=193
f(39)=2917
f(40)=919
f(41)=191
f(42)=431
f(43)=1
f(44)=13043
f(45)=1
f(46)=367
f(47)=3461
f(48)=14107
f(49)=449
f(50)=14627
f(51)=1
f(52)=15139
f(53)=1
f(54)=15643
f(55)=1
f(56)=16139
f(57)=1
f(58)=1279
f(59)=4217
f(60)=17107
f(61)=1
f(62)=17579
f(63)=1
f(64)=18043
f(65)=571
f(66)=1423
f(67)=151
f(68)=18947
f(69)=599
f(70)=19387
f(71)=1
f(72)=19819
f(73)=313
f(74)=653
f(75)=5113
f(76)=283
f(77)=163
f(78)=21067
f(79)=409
f(80)=21467
f(81)=677
f(82)=21859
f(83)=149
f(84)=1
f(85)=701
f(86)=22619
f(87)=5701
f(88)=181
f(89)=1
f(90)=631
f(91)=5881
f(92)=1823
f(93)=373
f(94)=24043
f(95)=6053
f(96)=24379
f(97)=1
f(98)=797
f(99)=6217

b) Substitution of the polynom
The polynom f(x)=x^2-358x+773 could be written as f(y)= y^2-31268 with x=y+179

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-179
f'(x)>2x-359 with x > 177

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

773, 13, 61, 73, 643, 31, 103, 421, 2027, 37, 2707, 761, 109, 29, 311, 1093, 127, 157, 5347, 1, 5987, 197, 6619, 1733, 7243, 59, 271, 1, 8467, 137, 9067, 2341, 743, 1, 10243, 2633, 349, 347, 193, 2917, 919, 191, 431, 1, 13043, 1, 367, 3461, 14107, 449, 14627, 1, 15139, 1, 15643, 1, 16139, 1, 1279, 4217, 17107, 1, 17579, 1, 18043, 571, 1423, 151, 18947, 599, 19387, 1, 19819, 313, 653, 5113, 283, 163, 21067, 409, 21467, 677, 21859, 149, 1, 701, 22619, 5701, 181, 1, 631, 5881, 1823, 373, 24043, 6053, 24379, 1, 797, 6217, 863, 787, 25339, 6373, 25643, 1, 25939, 6521, 26227, 1, 2039, 6661, 439, 1, 27043, 6793, 27299, 857, 1, 6917, 751, 1, 28019, 541, 463, 443, 1, 1, 263, 1, 28867, 557, 29059, 911, 29243, 7333, 1, 461, 29587, 7417, 1, 233, 1031, 1, 2311, 941, 293, 7561, 30307, 1, 30427, 7621, 30539, 239, 30643, 7673, 521, 1, 1063, 7717, 997, 967, 2383, 7753, 839, 971, 227, 251, 31147, 487, 2399, 269, 31219, 1, 199, 601, 31259, 977, 31267, 7817, 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, 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, 1493, 1, 2221, 647, 2957, 1, 3701, 1019, 1, 1, 401, 1399, 5981, 1, 1, 1787, 7541, 1, 641, 1, 9133, 1, 9941, 1, 1, 1, 1, 2999, 12413, 1, 457, 1, 1, 1, 14957, 3847, 1217, 1, 16693, 4283, 17573, 563, 18461, 1, 1489, 619, 20261, 5179, 683, 1, 22093, 5639, 23021, 1, 23957, 1, 673, 1, 1, 1, 26813, 853, 2137, 1, 1, 1, 29741, 7559, 1, 1, 2441, 8059, 1129, 1039, 33757, 659, 34781, 1103, 607, 1, 1, 1, 1, 739, 1, 617, 1291, 10139, 1, 1301, 1, 1, 43261, 1, 44357, 1, 1, 719, 46573, 11783, 1289, 1, 48821, 12347, 49957, 1579, 1, 12919, 52253, 1, 1723, 13499, 54581, 1, 4289, 14087, 56941, 1, 953, 14683, 59333, 1873, 4657, 15287, 61757, 1949, 62981, 1223, 1, 1013, 1, 16519, 66701, 1, 67957, 1319, 69221, 1, 1, 17783, 5521, 1, 73061, 18427, 74357, 1, 2609, 19079, 1, 1213, 1327, 19739, 79621, 1, 1109, 20407, 82301, 2593, 83653, 727, 1, 1, 86381, 21767, 691, 1, 6857, 1, 90533, 2851, 1, 23159, 3011, 2939, 1, 823, 96181, 757, 97613, 1, 99053, 1559, 100501, 25307, 101957, 3209, 103421, 2003, 3617, 3301, 106373, 1, 8297, 1697, 109357, 27527, 1879, 1, 1091, 28283, 8761, 3583, 115421, 937, 1, 1, 1, 29819, 1, 1, 3923, 827, 1, 1, 1709, 31387, 126341, 1, 1, 32183, 129533, 4073, 1, 32987, 132757, 2087, 10337, 1, 136013, 1069, 137653, 2663, 139301, 1, 4547, 35447, 1123, 4483, 1, 2791, 2393, 1, 147661, 1, 11489, 2347, 5209, 1, 4129, 4801, 154493, 38839, 1, 4909, 1, 1, 159701, 1, 161453, 40583, 1, 1, 5689, 41467, 1619, 1, 168541, 42359, 2887, 5351, 13241, 1, 1, 1, 175757, 1523, 1, 2789, 1, 45083, 181253, 5693, 1, 3539, 184957, 1, 1, 1, 188693, 2963, 190573, 1, 192461, 1511, 1, 1, 1, 6163, 198173, 49783, 2741, 1, 202021, 1637, 1, 1601, 1889, 51719, 1, 1, 209813, 1, 211781, 1, 3623, 1451, 1, 1, 217733, 1, 7577, 3449, 1, 1, 223757, 1, 225781, 1, 1, 7151, 17681, 57719, 231901, 1, 7547, 4519, 236021, 1, 238093, 1, 240173, 3769, 242261, 4679, 244357, 7669, 1277, 61879, 19121, 1, 250693, 62939, 6833, 3967, 1861, 64007, 19777, 2017, 8363, 1759, 3581, 1, 1, 1, 265757, 1, 267941, 1, 270133, 1, 272333, 1, 1, 1, 1, 69467, 278981, 8753, 9697, 70583, 2069, 8893, 21977, 71707, 1907, 4517, 4919, 1, 292493, 1, 294773, 2551, 297061, 9319, 299357, 5779, 1, 9463, 1, 76283, 23561, 1201, 308621, 77447, 3019, 4877, 313301, 2711, 24281, 9901, 1951, 1, 1, 1, 322757, 1, 1, 5099, 2579, 82183, 1, 1, 3049, 1367, 1, 10499, 1, 2729, 339613, 10651, 1, 85819, 5839, 1, 2053, 1427, 12049, 5479, 1, 6791, 354373, 11113, 2273, 89527, 359357, 1, 4957, 6983, 364373, 1, 1901, 2969, 1, 1, 371957, 93307, 374501, 11743, 12163, 94583, 29201, 11903, 2531, 2591, 384757, 1, 387341, 97159, 2617, 6113, 1, 98459, 395141, 1, 397757, 99767, 400381, 12553, 1, 1, 1741, 6359, 13171, 102407, 6737, 3221, 31817, 1, 1471, 1, 3299, 1, 421661, 13219, 14633, 106427, 7001, 3347, 429773, 8291, 11689, 6779, 435221, 109147, 1, 13729, 6037, 1, 443453, 13901, 1867, 1, 34537, 1, 1667, 113287, 454541, 1, 457333, 1571, 14843, 14423, 1, 4003, 4273, 1, 468581, 117499, 1, 1847, 1, 1, 2927, 7477, 479957, 1, 16649, 1, 37361, 1, 488573, 15313, 491461, 9479, 1, 1, 497261, 124679, 500173, 3919, 8527, 1, 17449, 15859, 508957, 127607, 1, 1, 514853, 129083, 2063, 4057, 2179, 2213, 40289, 1, 526741, 132059, 2689, 1, 532733, 133559, 535741, 1, 14561, 4357, 541781, 1, 544813, 1871, 547853, 1, 1, 138107, 2207, 17359, 557021, 1, 560093, 17551, 43321, 141179, 7757, 1, 1, 10979, 572461, 8969, 575573, 1, 578693, 18133, 581821, 1, 1, 18329, 1, 147419, 45481, 1, 1, 4027, 597581, 1, 1, 150587, 46457, 1, 1, 152183, 3067, 1, 10399, 5303, 616757, 4831, 619981, 155399, 4549, 1, 1, 157019, 629701, 1, 1, 158647, 3331, 1, 639493, 5527,

6. Sequence of the polynom (only primes)

773, 13, 61, 73, 643, 31, 103, 421, 2027, 37, 2707, 761, 109, 29, 311, 1093, 127, 157, 5347, 5987, 197, 6619, 1733, 7243, 59, 271, 8467, 137, 9067, 2341, 743, 10243, 2633, 349, 347, 193, 2917, 919, 191, 431, 13043, 367, 3461, 14107, 449, 14627, 15139, 15643, 16139, 1279, 4217, 17107, 17579, 18043, 571, 1423, 151, 18947, 599, 19387, 19819, 313, 653, 5113, 283, 163, 21067, 409, 21467, 677, 21859, 149, 701, 22619, 5701, 181, 631, 5881, 1823, 373, 24043, 6053, 24379, 797, 6217, 863, 787, 25339, 6373, 25643, 25939, 6521, 26227, 2039, 6661, 439, 27043, 6793, 27299, 857, 6917, 751, 28019, 541, 463, 443, 263, 28867, 557, 29059, 911, 29243, 7333, 461, 29587, 7417, 233, 1031, 2311, 941, 293, 7561, 30307, 30427, 7621, 30539, 239, 30643, 7673, 521, 1063, 7717, 997, 967, 2383, 7753, 839, 971, 227, 251, 31147, 487, 2399, 269, 31219, 199, 601, 31259, 977, 31267, 7817, 1493, 2221, 647, 2957, 3701, 1019, 401, 1399, 5981, 1787, 7541, 641, 9133, 9941, 2999, 12413, 457, 14957, 3847, 1217, 16693, 4283, 17573, 563, 18461, 1489, 619, 20261, 5179, 683, 22093, 5639, 23021, 23957, 673, 26813, 853, 2137, 29741, 7559, 2441, 8059, 1129, 1039, 33757, 659, 34781, 1103, 607, 739, 617, 1291, 10139, 1301, 43261, 44357, 719, 46573, 11783, 1289, 48821, 12347, 49957, 1579, 12919, 52253, 1723, 13499, 54581, 4289, 14087, 56941, 953, 14683, 59333, 1873, 4657, 15287, 61757, 1949, 62981, 1223, 1013, 16519, 66701, 67957, 1319, 69221, 17783, 5521, 73061, 18427, 74357, 2609, 19079, 1213, 1327, 19739, 79621, 1109, 20407, 82301, 2593, 83653, 727, 86381, 21767, 691, 6857, 90533, 2851, 23159, 3011, 2939, 823, 96181, 757, 97613, 99053, 1559, 100501, 25307, 101957, 3209, 103421, 2003, 3617, 3301, 106373, 8297, 1697, 109357, 27527, 1879, 1091, 28283, 8761, 3583, 115421, 937, 29819, 3923, 827, 1709, 31387, 126341, 32183, 129533, 4073, 32987, 132757, 2087, 10337, 136013, 1069, 137653, 2663, 139301, 4547, 35447, 1123, 4483, 2791, 2393, 147661, 11489, 2347, 5209, 4129, 4801, 154493, 38839, 4909, 159701, 161453, 40583, 5689, 41467, 1619, 168541, 42359, 2887, 5351, 13241, 175757, 1523, 2789, 45083, 181253, 5693, 3539, 184957, 188693, 2963, 190573, 192461, 1511, 6163, 198173, 49783, 2741, 202021, 1637, 1601, 1889, 51719, 209813, 211781, 3623, 1451, 217733, 7577, 3449, 223757, 225781, 7151, 17681, 57719, 231901, 7547, 4519, 236021, 238093, 240173, 3769, 242261, 4679, 244357, 7669, 1277, 61879, 19121, 250693, 62939, 6833, 3967, 1861, 64007, 19777, 2017, 8363, 1759, 3581, 265757, 267941, 270133, 272333, 69467, 278981, 8753, 9697, 70583, 2069, 8893, 21977, 71707, 1907, 4517, 4919, 292493, 294773, 2551, 297061, 9319, 299357, 5779, 9463, 76283, 23561, 1201, 308621, 77447, 3019, 4877, 313301, 2711, 24281, 9901, 1951, 322757, 5099, 2579, 82183, 3049, 1367, 10499, 2729, 339613, 10651, 85819, 5839, 2053, 1427, 12049, 5479, 6791, 354373, 11113, 2273, 89527, 359357, 4957, 6983, 364373, 1901, 2969, 371957, 93307, 374501, 11743, 12163, 94583, 29201, 11903, 2531, 2591, 384757, 387341, 97159, 2617, 6113, 98459, 395141, 397757, 99767, 400381, 12553, 1741, 6359, 13171, 102407, 6737, 3221, 31817, 1471, 3299, 421661, 13219, 14633, 106427, 7001, 3347, 429773, 8291, 11689, 6779, 435221, 109147, 13729, 6037, 443453, 13901, 1867, 34537, 1667, 113287, 454541, 457333, 1571, 14843, 14423, 4003, 4273, 468581, 117499, 1847, 2927, 7477, 479957, 16649, 37361, 488573, 15313, 491461, 9479, 497261, 124679, 500173, 3919, 8527, 17449, 15859, 508957, 127607, 514853, 129083, 2063, 4057, 2179, 2213, 40289, 526741, 132059, 2689, 532733, 133559, 535741, 14561, 4357, 541781, 544813, 1871, 547853, 138107, 2207, 17359, 557021, 560093, 17551, 43321, 141179, 7757, 10979, 572461, 8969, 575573, 578693, 18133, 581821, 18329, 147419, 45481, 4027, 597581, 150587, 46457, 152183, 3067, 10399, 5303, 616757, 4831, 619981, 155399, 4549, 157019, 629701, 158647, 3331, 639493, 5527,

7. Distribution of the primes

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

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

A B C D E F G H
exponent
=log2 (x)
<=x number
of all primes
number of primes
p = f(x)
number of primes
p | f(x)
C / x D / x E / x
1 2 3 2 1 1.5 1 0.5
2 4 5 3 2 1.25 0.75 0.5
3 8 9 4 5 1.125 0.5 0.625
4 16 17 5 12 1.0625 0.3125 0.75
5 32 31 11 20 0.96875 0.34375 0.625
6 64 54 21 33 0.84375 0.328125 0.515625
7 128 107 37 70 0.8359375 0.2890625 0.546875
8 256 151 49 102 0.58984375 0.19140625 0.3984375
9 512 250 87 163 0.48828125 0.16992188 0.31835938
10 1024 609 188 421 0.59472656 0.18359375 0.41113281
11 2048 1326 371 955 0.64746094 0.18115234 0.46630859
12 4096 2750 712 2038 0.67138672 0.17382813 0.49755859
13 8192 5623 1275 4348 0.68640137 0.15563965 0.53076172
14 16384 11352 2347 9005 0.69287109 0.14324951 0.54962158
15 32768 22815 4364 18451 0.69625854 0.13317871 0.56307983
16 65536 45684 8162 37522 0.69708252 0.12454224 0.57254028
17 131072 91508 15284 76224 0.69815063 0.11660767 0.58154297
18 262144 183081 28777 154304 0.69839859 0.10977554 0.58862305
19 524288 366119 54122 311997 0.69831657 0.10322952 0.59508705
20 1048576 732112 102499 629613 0.69819641 0.09775066 0.60044575
21 2097152 1464144 194270 1269874 0.69815826 0.09263515 0.60552311
22 4194304 2927323 369547 2557776 0.69792819 0.08810687 0.60982132
23 8388608 5853389 704661 5148728 0.69777834 0.08400214 0.61377621
24 16777216 11703799 1346476 10357323 0.69760078 0.08025622 0.61734456


8. Check for existing Integer Sequences by OEIS

Found in Database : 773, 13, 61, 73, 643, 31, 103, 421, 2027, 37, 2707, 761, 109, 29, 311, 1093, 127, 157, 5347, 1,
Found in Database : 773, 13, 61, 73, 643, 31, 103, 421, 2027, 37, 2707, 761, 109, 29, 311, 1093, 127, 157, 5347, 5987, 197, 6619, 1733, 7243, 59, 271, 8467, 137, 9067, 2341, 743, 10243, 2633, 349, 347, 193, 2917,
Found in Database : 13, 29, 31, 37, 59, 61, 73, 103, 109, 127, 137, 149,