Inhaltsverzeichnis

Development of
Algorithmic Constructions

06:24:40
Deutsch
29.Mar 2024

Polynom = x^2-200x+839

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) = 839 = 839
f(1) = 5 = 5
f(2) = 443 = 443
f(3) = 31 = 31
f(4) = 55 = 5*11
f(5) = 17 = 17
f(6) = 325 = 5*5*13
f(7) = 1 = 1
f(8) = 697 = 17*41
f(9) = 55 = 5*11
f(10) = 1061 = 1061
f(11) = 155 = 5*31
f(12) = 1417 = 13*109
f(13) = 199 = 199
f(14) = 1765 = 5*353
f(15) = 121 = 11*11
f(16) = 2105 = 5*421
f(17) = 71 = 71
f(18) = 2437 = 2437
f(19) = 325 = 5*5*13
f(20) = 2761 = 11*251
f(21) = 365 = 5*73
f(22) = 3077 = 17*181
f(23) = 101 = 101
f(24) = 3385 = 5*677
f(25) = 221 = 13*17
f(26) = 3685 = 5*11*67
f(27) = 479 = 479
f(28) = 3977 = 41*97
f(29) = 515 = 5*103
f(30) = 4261 = 4261
f(31) = 275 = 5*5*11
f(32) = 4537 = 13*349
f(33) = 73 = 73
f(34) = 4805 = 5*31*31
f(35) = 617 = 617
f(36) = 5065 = 5*1013
f(37) = 649 = 11*59
f(38) = 5317 = 13*409
f(39) = 85 = 5*17
f(40) = 5561 = 67*83
f(41) = 355 = 5*71
f(42) = 5797 = 11*17*31
f(43) = 739 = 739
f(44) = 6025 = 5*5*241
f(45) = 767 = 13*59
f(46) = 6245 = 5*1249
f(47) = 397 = 397
f(48) = 6457 = 11*587
f(49) = 205 = 5*41
f(50) = 6661 = 6661
f(51) = 845 = 5*13*13
f(52) = 6857 = 6857
f(53) = 869 = 11*79
f(54) = 7045 = 5*1409
f(55) = 223 = 223
f(56) = 7225 = 5*5*17*17
f(57) = 457 = 457
f(58) = 7397 = 13*569
f(59) = 935 = 5*11*17
f(60) = 7561 = 7561
f(61) = 955 = 5*191
f(62) = 7717 = 7717
f(63) = 487 = 487
f(64) = 7865 = 5*11*11*13
f(65) = 31 = 31
f(66) = 8005 = 5*1601
f(67) = 1009 = 1009
f(68) = 8137 = 79*103
f(69) = 1025 = 5*5*41
f(70) = 8261 = 11*751
f(71) = 65 = 5*13
f(72) = 8377 = 8377
f(73) = 527 = 17*31
f(74) = 8485 = 5*1697
f(75) = 1067 = 11*97
f(76) = 8585 = 5*17*101
f(77) = 1079 = 13*83
f(78) = 8677 = 8677
f(79) = 545 = 5*109
f(80) = 8761 = 8761
f(81) = 275 = 5*5*11
f(82) = 8837 = 8837
f(83) = 1109 = 1109
f(84) = 8905 = 5*13*137
f(85) = 1117 = 1117
f(86) = 8965 = 5*11*163
f(87) = 281 = 281
f(88) = 9017 = 71*127
f(89) = 565 = 5*113
f(90) = 9061 = 13*17*41
f(91) = 1135 = 5*227
f(92) = 9097 = 11*827
f(93) = 1139 = 17*67
f(94) = 9125 = 5*5*5*73
f(95) = 571 = 571
f(96) = 9145 = 5*31*59
f(97) = 143 = 11*13
f(98) = 9157 = 9157
f(99) = 1145 = 5*229
f(100) = 9161 = 9161

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-200x+839

f(0)=839
f(1)=5
f(2)=443
f(3)=31
f(4)=11
f(5)=17
f(6)=13
f(7)=1
f(8)=41
f(9)=1
f(10)=1061
f(11)=1
f(12)=109
f(13)=199
f(14)=353
f(15)=1
f(16)=421
f(17)=71
f(18)=2437
f(19)=1
f(20)=251
f(21)=73
f(22)=181
f(23)=101
f(24)=677
f(25)=1
f(26)=67
f(27)=479
f(28)=97
f(29)=103
f(30)=4261
f(31)=1
f(32)=349
f(33)=1
f(34)=1
f(35)=617
f(36)=1013
f(37)=59
f(38)=409
f(39)=1
f(40)=83
f(41)=1
f(42)=1
f(43)=739
f(44)=241
f(45)=1
f(46)=1249
f(47)=397
f(48)=587
f(49)=1
f(50)=6661
f(51)=1
f(52)=6857
f(53)=79
f(54)=1409
f(55)=223
f(56)=1
f(57)=457
f(58)=569
f(59)=1
f(60)=7561
f(61)=191
f(62)=7717
f(63)=487
f(64)=1
f(65)=1
f(66)=1601
f(67)=1009
f(68)=1
f(69)=1
f(70)=751
f(71)=1
f(72)=8377
f(73)=1
f(74)=1697
f(75)=1
f(76)=1
f(77)=1
f(78)=8677
f(79)=1
f(80)=8761
f(81)=1
f(82)=8837
f(83)=1109
f(84)=137
f(85)=1117
f(86)=163
f(87)=281
f(88)=127
f(89)=113
f(90)=1
f(91)=227
f(92)=827
f(93)=1
f(94)=1
f(95)=571
f(96)=1
f(97)=1
f(98)=9157
f(99)=229

b) Substitution of the polynom
The polynom f(x)=x^2-200x+839 could be written as f(y)= y^2-9161 with x=y+100

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

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

839, 5, 443, 31, 11, 17, 13, 1, 41, 1, 1061, 1, 109, 199, 353, 1, 421, 71, 2437, 1, 251, 73, 181, 101, 677, 1, 67, 479, 97, 103, 4261, 1, 349, 1, 1, 617, 1013, 59, 409, 1, 83, 1, 1, 739, 241, 1, 1249, 397, 587, 1, 6661, 1, 6857, 79, 1409, 223, 1, 457, 569, 1, 7561, 191, 7717, 487, 1, 1, 1601, 1009, 1, 1, 751, 1, 8377, 1, 1697, 1, 1, 1, 8677, 1, 8761, 1, 8837, 1109, 137, 1117, 163, 281, 127, 113, 1, 227, 827, 1, 1, 571, 1, 1, 9157, 229, 9161, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 331, 233, 1, 1, 2503, 1, 2939, 1, 1, 1, 1, 1, 859, 283, 433, 1, 1, 1, 1, 373, 1, 1, 1, 1, 1, 1, 1, 1, 8263, 1, 1759, 1, 1867, 1201, 9883, 1, 1, 1, 11003, 1, 463, 1483, 1, 389, 12743, 1, 13339, 1, 1, 1, 1, 929, 607, 1, 15803, 1, 967, 419, 1553, 1, 3547, 1129, 1, 2341, 1733, 1, 19739, 1, 1571, 1, 1, 2683, 4363, 1, 1, 1, 1367, 1, 773, 3041, 449, 1, 5087, 1613, 26183, 1, 1, 683, 2131, 3511, 1, 1, 5851, 1, 2311, 761, 30839, 1, 31643, 2003, 6491, 1, 1, 4211, 509, 863, 34939, 1, 3253, 1, 431, 1, 7499, 1, 1, 1, 39239, 1, 40123, 461, 631, 1, 1, 1, 1, 541, 1, 1, 757, 5641, 829, 2879, 1, 1, 1, 1, 821, 1223, 1, 1559, 1, 1, 10271, 6481, 3079, 1321, 1, 673, 1753, 857, 11071, 6983, 1, 547, 1, 1, 58439, 1, 3499, 577, 12107, 1, 1, 1, 1, 1, 4903, 1607, 1, 8171, 13183, 1, 1031, 1, 563, 1, 69239, 1, 4139, 1, 1, 1, 1, 9151, 73783, 1, 1, 1, 76103, 4793, 1, 9733, 1, 1, 1091, 1, 7349, 1, 6311, 10331, 16651, 953, 1, 2659, 85703, 1, 86939, 1, 1, 653, 1, 1, 1, 1427, 2243, 1, 93239, 2347, 661, 1487, 19163, 6029, 19423, 1, 1, 2477, 5867, 1, 101063, 1, 20479, 991, 20747, 1, 1, 1, 1, 1, 1609, 1, 1, 1, 22111, 1, 1, 1, 1, 2851, 114743, 14431, 1787, 1, 4703, 7393, 2017, 1, 10949, 1, 121883, 1, 1451, 3877, 2269, 1, 4073, 1, 127739, 1, 129223, 8123, 2011, 16433, 853, 1511, 133723, 1, 1, 1, 12433, 17191, 1627, 17383, 27967, 1, 12853, 1777, 142939, 3593, 1741, 1, 5843, 1, 29531, 4639, 8779, 1, 1, 1, 152443, 4789, 2801, 9679, 1, 1, 157303, 1, 14449, 1997, 160583, 1, 1, 1, 32779, 1, 9739, 1, 4079, 1, 1, 21221, 34123, 21433, 1, 1, 1723, 1093, 5669, 883, 1, 22291, 35839, 1, 36187, 1033, 1, 1, 1019, 1, 2357, 1063, 1, 1, 37951, 23831, 1583, 1, 1, 1, 1, 12253, 3581, 24733, 7951, 1, 1187, 1, 2087, 1, 3049, 1, 41227, 1, 2447, 6529, 3557, 1, 19249, 1, 213623, 26821, 43103, 1, 1, 1, 16871, 5507, 221239, 1, 5443, 1, 3463, 1, 2671, 2591, 228983, 5749, 230939, 1, 1, 7309, 1879, 29483, 1, 2287, 21713, 1499, 1, 3023, 5923, 1, 3767, 1, 1, 15493, 248903, 1, 1, 6299, 252983, 31751, 4637, 4001, 51419, 1, 259163, 1301, 1, 1, 263323, 1, 1, 1, 53503, 1, 269623, 1, 20903, 1, 1999, 17183, 1, 1, 1, 2053, 1163, 3517, 282439, 1, 25873, 1, 11471, 35983, 57791, 1, 291143, 1, 293339, 1, 1, 3371, 1, 18679, 1, 1, 1, 7583, 304439, 7639, 1, 9619, 1, 19379, 1, 39041, 18439, 1, 315739, 1, 318023, 4987, 64063, 1, 1, 40471, 4451, 1, 1, 1, 1, 41341, 1619, 1, 1, 20963, 1523, 2111, 4643, 1, 341303, 1381, 1, 1, 1, 1973, 348443, 8741, 4441, 1, 1889, 22153, 1, 1, 14323, 1, 2521, 9043, 5417, 1, 1913, 2083, 5659, 46133, 2389, 46441, 372763, 1, 1, 1, 1307, 1, 1, 1, 76543, 1, 385223, 4831, 1, 1, 390263, 1, 6043, 2239, 4651, 6197, 2441, 1, 30803, 1, 403003, 6317, 16223, 1, 1, 1, 1, 10301, 4013, 1, 37813, 1, 1, 1693, 1, 4801, 423803, 2657, 32803, 5347, 429083, 1, 1, 54133, 1, 1, 39733, 1, 25867, 11027, 1949, 1, 8093, 1, 89563, 1, 14533, 1, 453239, 2273, 1, 1, 1, 1, 1, 1, 2027, 1, 1, 2927, 36131, 29443, 18899, 59233, 8641, 59581, 6733, 1, 480839, 1, 483643, 60631, 1, 4691, 19571, 1, 492103, 1, 494939, 12409, 1, 62401, 1, 31379, 100699, 1, 3541, 2539, 509239, 1, 7213, 1459, 1, 1, 103583, 64921, 12703, 1, 7817, 1, 1861, 2063, 9629, 66383, 1, 66751, 2423, 1, 1579, 1, 4967, 1, 1, 6203, 109471, 34303, 1, 3449, 4357, 1, 556343, 1, 111871, 1, 1, 2711, 1, 14173, 568439, 14249, 4723, 1, 8839, 9001, 1, 6581, 580663, 1, 1, 1, 34519, 3343, 1, 4349, 118603, 5717, 54193, 1, 5303, 1, 1, 5807, 1, 75883, 121727, 19069, 1, 1, 47303, 15413, 1, 1, 24851, 3539, 1, 1, 627643, 15731, 57349, 1, 1, 1, 1, 39929, 1, 1, 643703, 1, 1, 1, 650183, 20369, 130687, 81883, 10103, 7481, 659963, 1, 663239, 8311, 1, 1, 133963, 83933, 7919, 1, 61493, 1, 1, 3407, 6763, 1, 137279, 1, 137947, 1, 5059, 1, 1, 1, 53831, 2579, 2557, 22027, 141311, 1, 1, 17791, 64849, 1, 716743, 1, 144031, 1, 1, 5333, 727003, 9109, 42967, 1, 733883, 91951, 1, 92383, 13469, 5801, 57251, 1, 10243, 1, 2203, 94121, 1, 47279, 151643, 1, 11369, 19087, 1871, 1, 10531, 1, 154459, 1, 155167, 7477, 70853, 1, 9433, 1, 19183, 1, 1, 1, 158731, 99431, 8219, 1,

6. Sequence of the polynom (only primes)

839, 5, 443, 31, 11, 17, 13, 41, 1061, 109, 199, 353, 421, 71, 2437, 251, 73, 181, 101, 677, 67, 479, 97, 103, 4261, 349, 617, 1013, 59, 409, 83, 739, 241, 1249, 397, 587, 6661, 6857, 79, 1409, 223, 457, 569, 7561, 191, 7717, 487, 1601, 1009, 751, 8377, 1697, 8677, 8761, 8837, 1109, 137, 1117, 163, 281, 127, 113, 227, 827, 571, 9157, 229, 9161, 331, 233, 2503, 2939, 859, 283, 433, 373, 8263, 1759, 1867, 1201, 9883, 11003, 463, 1483, 389, 12743, 13339, 929, 607, 15803, 967, 419, 1553, 3547, 1129, 2341, 1733, 19739, 1571, 2683, 4363, 1367, 773, 3041, 449, 5087, 1613, 26183, 683, 2131, 3511, 5851, 2311, 761, 30839, 31643, 2003, 6491, 4211, 509, 863, 34939, 3253, 431, 7499, 39239, 40123, 461, 631, 541, 757, 5641, 829, 2879, 821, 1223, 1559, 10271, 6481, 3079, 1321, 673, 1753, 857, 11071, 6983, 547, 58439, 3499, 577, 12107, 4903, 1607, 8171, 13183, 1031, 563, 69239, 4139, 9151, 73783, 76103, 4793, 9733, 1091, 7349, 6311, 10331, 16651, 953, 2659, 85703, 86939, 653, 1427, 2243, 93239, 2347, 661, 1487, 19163, 6029, 19423, 2477, 5867, 101063, 20479, 991, 20747, 1609, 22111, 2851, 114743, 14431, 1787, 4703, 7393, 2017, 10949, 121883, 1451, 3877, 2269, 4073, 127739, 129223, 8123, 2011, 16433, 853, 1511, 133723, 12433, 17191, 1627, 17383, 27967, 12853, 1777, 142939, 3593, 1741, 5843, 29531, 4639, 8779, 152443, 4789, 2801, 9679, 157303, 14449, 1997, 160583, 32779, 9739, 4079, 21221, 34123, 21433, 1723, 1093, 5669, 883, 22291, 35839, 36187, 1033, 1019, 2357, 1063, 37951, 23831, 1583, 12253, 3581, 24733, 7951, 1187, 2087, 3049, 41227, 2447, 6529, 3557, 19249, 213623, 26821, 43103, 16871, 5507, 221239, 5443, 3463, 2671, 2591, 228983, 5749, 230939, 7309, 1879, 29483, 2287, 21713, 1499, 3023, 5923, 3767, 15493, 248903, 6299, 252983, 31751, 4637, 4001, 51419, 259163, 1301, 263323, 53503, 269623, 20903, 1999, 17183, 2053, 1163, 3517, 282439, 25873, 11471, 35983, 57791, 291143, 293339, 3371, 18679, 7583, 304439, 7639, 9619, 19379, 39041, 18439, 315739, 318023, 4987, 64063, 40471, 4451, 41341, 1619, 20963, 1523, 2111, 4643, 341303, 1381, 1973, 348443, 8741, 4441, 1889, 22153, 14323, 2521, 9043, 5417, 1913, 2083, 5659, 46133, 2389, 46441, 372763, 1307, 76543, 385223, 4831, 390263, 6043, 2239, 4651, 6197, 2441, 30803, 403003, 6317, 16223, 10301, 4013, 37813, 1693, 4801, 423803, 2657, 32803, 5347, 429083, 54133, 39733, 25867, 11027, 1949, 8093, 89563, 14533, 453239, 2273, 2027, 2927, 36131, 29443, 18899, 59233, 8641, 59581, 6733, 480839, 483643, 60631, 4691, 19571, 492103, 494939, 12409, 62401, 31379, 100699, 3541, 2539, 509239, 7213, 1459, 103583, 64921, 12703, 7817, 1861, 2063, 9629, 66383, 66751, 2423, 1579, 4967, 6203, 109471, 34303, 3449, 4357, 556343, 111871, 2711, 14173, 568439, 14249, 4723, 8839, 9001, 6581, 580663, 34519, 3343, 4349, 118603, 5717, 54193, 5303, 5807, 75883, 121727, 19069, 47303, 15413, 24851, 3539, 627643, 15731, 57349, 39929, 643703, 650183, 20369, 130687, 81883, 10103, 7481, 659963, 663239, 8311, 133963, 83933, 7919, 61493, 3407, 6763, 137279, 137947, 5059, 53831, 2579, 2557, 22027, 141311, 17791, 64849, 716743, 144031, 5333, 727003, 9109, 42967, 733883, 91951, 92383, 13469, 5801, 57251, 10243, 2203, 94121, 47279, 151643, 11369, 19087, 1871, 10531, 154459, 155167, 7477, 70853, 9433, 19183, 158731, 99431, 8219,

7. Distribution of the primes

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

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 2 3 1.25 0.5 0.75
3 8 8 2 6 1 0.25 0.75
4 16 13 3 10 0.8125 0.1875 0.625
5 32 26 5 21 0.8125 0.15625 0.65625
6 64 47 9 38 0.734375 0.140625 0.59375
7 128 68 15 53 0.53125 0.1171875 0.4140625
8 256 89 22 67 0.34765625 0.0859375 0.26171875
9 512 234 47 187 0.45703125 0.09179688 0.36523438
10 1024 534 90 444 0.52148438 0.08789063 0.43359375
11 2048 1143 174 969 0.55810547 0.08496094 0.47314453
12 4096 2426 318 2108 0.59228516 0.07763672 0.51464844
13 8192 4983 575 4408 0.60827637 0.07019043 0.53808594
14 16384 10132 1067 9065 0.6184082 0.06512451 0.55328369
15 32768 20483 1979 18504 0.62509155 0.06039429 0.56469727
16 65536 41314 3681 37633 0.63040161 0.0561676 0.57423401
17 131072 83315 6878 76437 0.63564301 0.05247498 0.58316803
18 262144 167602 12996 154606 0.63935089 0.04957581 0.58977509
19 524288 336685 24499 312186 0.64217567 0.04672813 0.59544754
20 1048576 676070 46464 629606 0.6447506 0.04431152 0.60043907
21 2097152 1357453 88166 1269287 0.64728403 0.04204082 0.60524321
22 4194304 2724582 167719 2556863 0.64959097 0.03998733 0.60960364
23 8388608 5466434 319209 5147225 0.65164971 0.03805268 0.61359704


8. Check for existing Integer Sequences by OEIS

Found in Database : 839, 5, 443, 31, 11, 17, 13, 1, 41, 1, 1061, 1, 109, 199, 353, 1, 421, 71, 2437, 1,
Found in Database : 839, 5, 443, 31, 11, 17, 13, 41, 1061, 109, 199, 353, 421, 71, 2437, 251, 73, 181, 101, 677, 67, 479, 97, 103, 4261, 349, 617, 1013, 59, 409,
Found in Database : 5, 11, 13, 17, 31, 41, 59, 67, 71, 73, 79, 83, 97, 101, 103, 109, 113, 127, 137,