Inhaltsverzeichnis

Development of
Algorithmic Constructions

01:12:11
Deutsch
29.Mar 2024

Polynom = x^2-88x+983

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) = 983 = 983
f(1) = 7 = 7
f(2) = 811 = 811
f(3) = 91 = 7*13
f(4) = 647 = 647
f(5) = 71 = 71
f(6) = 491 = 491
f(7) = 13 = 13
f(8) = 343 = 7*7*7
f(9) = 17 = 17
f(10) = 203 = 7*29
f(11) = 17 = 17
f(12) = 71 = 71
f(13) = 1 = 1
f(14) = 53 = 53
f(15) = 7 = 7
f(16) = 169 = 13*13
f(17) = 7 = 7
f(18) = 277 = 277
f(19) = 41 = 41
f(20) = 377 = 13*29
f(21) = 53 = 53
f(22) = 469 = 7*67
f(23) = 1 = 1
f(24) = 553 = 7*79
f(25) = 37 = 37
f(26) = 629 = 17*37
f(27) = 83 = 83
f(28) = 697 = 17*41
f(29) = 91 = 7*13
f(30) = 757 = 757
f(31) = 49 = 7*7
f(32) = 809 = 809
f(33) = 13 = 13
f(34) = 853 = 853
f(35) = 109 = 109
f(36) = 889 = 7*127
f(37) = 113 = 113
f(38) = 917 = 7*131
f(39) = 29 = 29
f(40) = 937 = 937
f(41) = 59 = 59
f(42) = 949 = 13*73
f(43) = 119 = 7*17
f(44) = 953 = 953
f(45) = 119 = 7*17
f(46) = 949 = 13*73
f(47) = 59 = 59
f(48) = 937 = 937
f(49) = 29 = 29
f(50) = 917 = 7*131
f(51) = 113 = 113
f(52) = 889 = 7*127
f(53) = 109 = 109
f(54) = 853 = 853
f(55) = 13 = 13
f(56) = 809 = 809
f(57) = 49 = 7*7
f(58) = 757 = 757
f(59) = 91 = 7*13
f(60) = 697 = 17*41
f(61) = 83 = 83
f(62) = 629 = 17*37
f(63) = 37 = 37
f(64) = 553 = 7*79
f(65) = 1 = 1
f(66) = 469 = 7*67
f(67) = 53 = 53
f(68) = 377 = 13*29
f(69) = 41 = 41
f(70) = 277 = 277
f(71) = 7 = 7
f(72) = 169 = 13*13
f(73) = 7 = 7
f(74) = 53 = 53
f(75) = 1 = 1
f(76) = 71 = 71
f(77) = 17 = 17
f(78) = 203 = 7*29
f(79) = 17 = 17
f(80) = 343 = 7*7*7
f(81) = 13 = 13
f(82) = 491 = 491
f(83) = 71 = 71
f(84) = 647 = 647
f(85) = 91 = 7*13
f(86) = 811 = 811
f(87) = 7 = 7
f(88) = 983 = 983
f(89) = 67 = 67
f(90) = 1163 = 1163
f(91) = 157 = 157
f(92) = 1351 = 7*193
f(93) = 181 = 181
f(94) = 1547 = 7*13*17
f(95) = 103 = 103
f(96) = 1751 = 17*103
f(97) = 29 = 29
f(98) = 1963 = 13*151
f(99) = 259 = 7*37
f(100) = 2183 = 37*59

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-88x+983

f(0)=983
f(1)=7
f(2)=811
f(3)=13
f(4)=647
f(5)=71
f(6)=491
f(7)=1
f(8)=1
f(9)=17
f(10)=29
f(11)=1
f(12)=1
f(13)=1
f(14)=53
f(15)=1
f(16)=1
f(17)=1
f(18)=277
f(19)=41
f(20)=1
f(21)=1
f(22)=67
f(23)=1
f(24)=79
f(25)=37
f(26)=1
f(27)=83
f(28)=1
f(29)=1
f(30)=757
f(31)=1
f(32)=809
f(33)=1
f(34)=853
f(35)=109
f(36)=127
f(37)=113
f(38)=131
f(39)=1
f(40)=937
f(41)=59
f(42)=73
f(43)=1
f(44)=953
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1163
f(91)=157
f(92)=193
f(93)=181
f(94)=1
f(95)=103
f(96)=1
f(97)=1
f(98)=151
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2-88x+983 could be written as f(y)= y^2-953 with x=y+44

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-44
f'(x)>2x-89 with x > 31

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

983, 7, 811, 13, 647, 71, 491, 1, 1, 17, 29, 1, 1, 1, 53, 1, 1, 1, 277, 41, 1, 1, 67, 1, 79, 37, 1, 83, 1, 1, 757, 1, 809, 1, 853, 109, 127, 113, 131, 1, 937, 59, 73, 1, 953, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1163, 157, 193, 181, 1, 103, 1, 1, 151, 1, 1, 1, 2411, 1, 2647, 173, 1, 1, 449, 409, 1, 1, 3671, 1, 3947, 1, 4231, 547, 4523, 1, 1, 311, 733, 661, 419, 701, 199, 1, 359, 1, 379, 827, 6791, 1, 1021, 229, 1, 1, 7883, 1009, 8263, 1, 211, 1, 1, 1, 727, 1, 1409, 1259, 1, 1, 10711, 683, 1, 1, 1, 1, 12043, 1, 12503, 1, 1, 1, 1, 1, 13931, 443, 14423, 1, 14923, 271, 1187, 1, 431, 1013, 1, 523, 347, 1, 331, 1, 1, 1, 643, 1, 19211, 2437, 1, 1, 2909, 1291, 1, 1, 743, 2731, 1303, 401, 1, 1, 349, 1481, 1847, 3041, 503, 3121, 3613, 1601, 25943, 821, 719, 1, 27271, 1, 27947, 1, 28631, 1811, 1, 3709, 4289, 3797, 389, 1, 1, 1, 607, 1, 2531, 4159, 1979, 1063, 1, 1, 5021, 4441, 35911, 1, 36683, 1, 37463, 1, 1319, 4831, 39047, 4931, 5693, 1, 1, 1, 3191, 5237, 1459, 1, 3319, 1, 43991, 1, 44843, 5659, 6529, 1, 6653, 1, 2791, 1, 2843, 1, 49223, 887, 50123, 1, 51031, 1609, 1, 6551, 1, 1, 1, 1, 4211, 1, 55691, 1, 1531, 1, 1087, 3631, 8369, 1, 1, 7507, 1, 587, 61547, 1, 881, 563, 3739, 8009, 1, 1, 1, 4133, 9521, 2099, 1, 8527, 68743, 1237, 1, 1, 541, 4463, 71947, 1, 10433, 1, 10589, 1, 75223, 1, 2063, 1373, 77447, 1, 78571, 2473, 6131, 1, 11549, 10177, 1, 10321, 1, 5233, 1429, 1, 1171, 1, 1097, 839, 1489, 691, 12721, 1, 12893, 1, 91463, 677, 92683, 1, 93911, 1, 1, 11971, 2351, 1, 1, 1, 1, 6221, 919, 12601, 1, 1823, 6043, 1, 1, 3271, 105323, 1019, 15233, 13411, 2203, 1697, 967, 6871, 110603, 1987, 1, 2011, 1, 1, 8819, 1, 16573, 1, 1, 14759, 1051, 3733, 2267, 1, 121547, 1, 3323, 1, 124363, 7817, 1, 1, 1069, 15991, 1249, 1, 10007, 1, 131543, 1181, 787, 1, 134471, 16901, 19421, 8543, 1, 1, 138923, 1, 140423, 2521, 141931, 1, 2141, 9013, 4999, 18217, 20929, 1, 21149, 1, 1, 1, 1, 2713, 1, 2741, 1, 2423, 155863, 9791, 1, 1, 22721, 1, 160651, 10091, 162263, 1, 163883, 1, 165511, 1223, 2833, 1, 24113, 10601, 1873, 1, 2917, 21617, 13367, 1559, 175447, 1, 177131, 22247, 1, 1, 1, 1, 3719, 11443, 6343, 1777, 2237, 3331, 971, 1, 2591, 2969, 190891, 23971, 1, 1423, 27773, 1, 15091, 1, 197963, 1, 199751, 3583, 201547, 12653, 203351, 1, 1, 25759, 29569, 1999, 1, 1, 12391, 1889, 5743, 1, 2081, 1, 16631, 1, 31153, 1, 2417, 27611, 221831, 27847, 1, 1, 5503, 1, 227531, 1, 1153, 1, 33053, 1117, 33329, 7321, 235243, 29527, 8179, 4253, 239147, 1, 1091, 15131, 1, 30509, 2693, 30757, 1217, 1, 1, 3907, 251051, 1, 253063, 1, 255083, 1, 6271, 1, 37021, 1913, 37313, 1, 3929, 1, 2089, 1, 1, 4793, 1277, 33811, 20887, 4259, 39089, 17167, 1, 1193, 1, 1, 2137, 1, 282071, 1, 4817, 1, 1, 1, 41213, 9049, 41521, 18233, 1, 2161, 22691, 1, 10247, 2663, 23027, 1, 1997, 37831, 6199, 1, 1, 2399, 10627, 1487, 1, 5563, 1, 1, 18523, 19751, 3821, 4973, 1, 1, 45953, 40351, 24919, 10159, 2887, 1, 1, 1, 330823, 2441, 333131, 1229, 1, 1, 1, 3259, 340103, 1471, 4691, 1, 344791, 3089, 8467, 43541, 1931, 1, 2957, 22067, 1, 2777, 4297, 1, 1, 1, 361451, 1619, 12547, 22817, 6911, 1, 52673, 3557, 1433, 1, 4729, 1, 12967, 6737, 378503, 6781, 380971, 1493, 1, 24043, 4241, 48397, 7927, 1, 30071, 1, 23143, 1, 23291, 1, 398471, 1723, 1, 1, 57649, 25301, 58013, 3917, 9967, 51241, 411211, 1, 413783, 1, 7057, 1, 1, 1, 1, 6607, 1, 26591, 426763, 1, 1, 7691, 2861, 1, 434647, 1, 1, 1, 3697, 4243, 1, 13873, 445271, 1, 4349, 1, 1, 1, 34871, 1, 456023, 14293, 1, 1, 65921, 1, 464171, 3637, 12619, 1, 1733, 1, 472391, 59221, 475147, 1, 1, 7489, 68669, 60259, 28439, 60607, 28603, 1, 37619, 1, 491851, 61657, 2927, 1, 71069, 31181, 71473, 15679, 503147, 1, 9547, 1, 2557, 1, 511703, 2467, 514571, 1, 2549, 1753, 1, 32611, 2711, 4099, 40471, 9421, 7247, 9473, 1, 1, 1, 33521, 76829, 67409, 77249, 67777, 3463, 2621, 1, 2447, 7741, 1, 552583, 69259, 2633, 1, 11399, 1, 80221, 70381, 43427, 1, 1, 5081, 43891, 1, 1, 1, 576647, 72271, 82813, 1, 1, 1, 2027, 73417, 588871, 1, 1, 1, 1, 1, 598123, 74959, 85889, 75347, 1, 9467, 4637, 2239, 1, 1, 5431, 10987, 616843, 38651, 21379, 1, 89021, 6007, 1, 78487, 629483, 1, 17099, 1, 1, 11383, 37591, 1, 1789, 40241, 1, 1, 92669, 2803, 50147, 1, 8293, 1, 658391, 1, 1, 4877, 1, 1, 1801, 41863, 1, 1, 674731, 1, 678023, 1, 10169, 3049, 1973, 1, 52919, 86201, 1, 2341, 1, 43517, 1, 21863, 701291, 12553, 704647, 12613, 708011, 1, 1877, 1, 1, 1, 102593, 1, 721547, 2659, 4801, 1, 2087, 13037, 1, 1, 735211, 23029, 8117, 46273, 106013, 1, 745543, 3221, 44059, 6703, 44263, 1, 20431, 1787, 759431, 1, 1, 1, 1, 1, 1, 96461, 773447, 1, 1, 1, 10993, 1, 1, 98227, 1907, 1, 113021, 1, 794711, 1, 27527, 1, 9661, 1, 805451, 3881, 47591, 25339, 6829, 101807, 4021, 102259, 22159, 1, 63347, 7369, 827147, 1, 63907, 1, 1, 52267, 1, 1, 1, 6203, 845447, 8147, 849131, 1, 16091, 1, 4951, 2617, 10889, 107761, 1, 1, 123953, 1, 3943, 109159, 51479, 15661, 67607, 1, 3257, 1, 4201, 3001, 1, 111509, 127709, 1, 897751, 14057, 901547, 1, 31219, 1, 5023, 1,

6. Sequence of the polynom (only primes)

983, 7, 811, 13, 647, 71, 491, 17, 29, 53, 277, 41, 67, 79, 37, 83, 757, 809, 853, 109, 127, 113, 131, 937, 59, 73, 953, 1163, 157, 193, 181, 103, 151, 2411, 2647, 173, 449, 409, 3671, 3947, 4231, 547, 4523, 311, 733, 661, 419, 701, 199, 359, 379, 827, 6791, 1021, 229, 7883, 1009, 8263, 211, 727, 1409, 1259, 10711, 683, 12043, 12503, 13931, 443, 14423, 14923, 271, 1187, 431, 1013, 523, 347, 331, 643, 19211, 2437, 2909, 1291, 743, 2731, 1303, 401, 349, 1481, 1847, 3041, 503, 3121, 3613, 1601, 25943, 821, 719, 27271, 27947, 28631, 1811, 3709, 4289, 3797, 389, 607, 2531, 4159, 1979, 1063, 5021, 4441, 35911, 36683, 37463, 1319, 4831, 39047, 4931, 5693, 3191, 5237, 1459, 3319, 43991, 44843, 5659, 6529, 6653, 2791, 2843, 49223, 887, 50123, 51031, 1609, 6551, 4211, 55691, 1531, 1087, 3631, 8369, 7507, 587, 61547, 881, 563, 3739, 8009, 4133, 9521, 2099, 8527, 68743, 1237, 541, 4463, 71947, 10433, 10589, 75223, 2063, 1373, 77447, 78571, 2473, 6131, 11549, 10177, 10321, 5233, 1429, 1171, 1097, 839, 1489, 691, 12721, 12893, 91463, 677, 92683, 93911, 11971, 2351, 6221, 919, 12601, 1823, 6043, 3271, 105323, 1019, 15233, 13411, 2203, 1697, 967, 6871, 110603, 1987, 2011, 8819, 16573, 14759, 1051, 3733, 2267, 121547, 3323, 124363, 7817, 1069, 15991, 1249, 10007, 131543, 1181, 787, 134471, 16901, 19421, 8543, 138923, 140423, 2521, 141931, 2141, 9013, 4999, 18217, 20929, 21149, 2713, 2741, 2423, 155863, 9791, 22721, 160651, 10091, 162263, 163883, 165511, 1223, 2833, 24113, 10601, 1873, 2917, 21617, 13367, 1559, 175447, 177131, 22247, 3719, 11443, 6343, 1777, 2237, 3331, 971, 2591, 2969, 190891, 23971, 1423, 27773, 15091, 197963, 199751, 3583, 201547, 12653, 203351, 25759, 29569, 1999, 12391, 1889, 5743, 2081, 16631, 31153, 2417, 27611, 221831, 27847, 5503, 227531, 1153, 33053, 1117, 33329, 7321, 235243, 29527, 8179, 4253, 239147, 1091, 15131, 30509, 2693, 30757, 1217, 3907, 251051, 253063, 255083, 6271, 37021, 1913, 37313, 3929, 2089, 4793, 1277, 33811, 20887, 4259, 39089, 17167, 1193, 2137, 282071, 4817, 41213, 9049, 41521, 18233, 2161, 22691, 10247, 2663, 23027, 1997, 37831, 6199, 2399, 10627, 1487, 5563, 18523, 19751, 3821, 4973, 45953, 40351, 24919, 10159, 2887, 330823, 2441, 333131, 1229, 3259, 340103, 1471, 4691, 344791, 3089, 8467, 43541, 1931, 2957, 22067, 2777, 4297, 361451, 1619, 12547, 22817, 6911, 52673, 3557, 1433, 4729, 12967, 6737, 378503, 6781, 380971, 1493, 24043, 4241, 48397, 7927, 30071, 23143, 23291, 398471, 1723, 57649, 25301, 58013, 3917, 9967, 51241, 411211, 413783, 7057, 6607, 26591, 426763, 7691, 2861, 434647, 3697, 4243, 13873, 445271, 4349, 34871, 456023, 14293, 65921, 464171, 3637, 12619, 1733, 472391, 59221, 475147, 7489, 68669, 60259, 28439, 60607, 28603, 37619, 491851, 61657, 2927, 71069, 31181, 71473, 15679, 503147, 9547, 2557, 511703, 2467, 514571, 2549, 1753, 32611, 2711, 4099, 40471, 9421, 7247, 9473, 33521, 76829, 67409, 77249, 67777, 3463, 2621, 2447, 7741, 552583, 69259, 2633, 11399, 80221, 70381, 43427, 5081, 43891, 576647, 72271, 82813, 2027, 73417, 588871, 598123, 74959, 85889, 75347, 9467, 4637, 2239, 5431, 10987, 616843, 38651, 21379, 89021, 6007, 78487, 629483, 17099, 11383, 37591, 1789, 40241, 92669, 2803, 50147, 8293, 658391, 4877, 1801, 41863, 674731, 678023, 10169, 3049, 1973, 52919, 86201, 2341, 43517, 21863, 701291, 12553, 704647, 12613, 708011, 1877, 102593, 721547, 2659, 4801, 2087, 13037, 735211, 23029, 8117, 46273, 106013, 745543, 3221, 44059, 6703, 44263, 20431, 1787, 759431, 96461, 773447, 10993, 98227, 1907, 113021, 794711, 27527, 9661, 805451, 3881, 47591, 25339, 6829, 101807, 4021, 102259, 22159, 63347, 7369, 827147, 63907, 52267, 6203, 845447, 8147, 849131, 16091, 4951, 2617, 10889, 107761, 123953, 3943, 109159, 51479, 15661, 67607, 3257, 4201, 3001, 111509, 127709, 897751, 14057, 901547, 31219, 5023,

7. Distribution of the primes

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

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 7 4 3 0.875 0.5 0.375
4 16 10 5 5 0.625 0.3125 0.3125
5 32 18 8 10 0.5625 0.25 0.3125
6 64 27 11 16 0.421875 0.171875 0.25
7 128 50 18 32 0.390625 0.140625 0.25
8 256 125 37 88 0.48828125 0.14453125 0.34375
9 512 286 72 214 0.55859375 0.140625 0.41796875
10 1024 609 127 482 0.59472656 0.12402344 0.47070313
11 2048 1261 247 1014 0.61572266 0.12060547 0.49511719
12 4096 2607 447 2160 0.63647461 0.10913086 0.52734375
13 8192 5294 814 4480 0.64624023 0.09936523 0.546875
14 16384 10646 1505 9141 0.64978027 0.09185791 0.55792236
15 32768 21438 2771 18667 0.65423584 0.08456421 0.56967163
16 65536 43062 5172 37890 0.65707397 0.07891846 0.57815552
17 131072 86465 9633 76832 0.6596756 0.07349396 0.58618164
18 262144 173483 18020 155463 0.66178513 0.06874084 0.59304428
19 524288 348002 34058 313944 0.66376114 0.06496048 0.59880066
20 1048576 697523 64528 632995 0.66520977 0.0615387 0.60367107
21 2097152 1398216 122413 1275803 0.66672134 0.05837107 0.60835028
22 4194304 2801709 232500 2569209 0.66797948 0.05543232 0.61254716
23 8388608 5613118 442823 5170295 0.66913581 0.05278862 0.61634719
24 16777216 11243134 845315 10397819 0.67014301 0.0503847 0.61975831


8. Check for existing Integer Sequences by OEIS

Found in Database : 983, 7, 811, 13, 647, 71, 491, 1, 1, 17, 29, 1, 1, 1, 53, 1, 1, 1, 277, 41,
Found in Database : 983, 7, 811, 13, 647, 71, 491, 17, 29, 53, 277, 41, 67, 79, 37, 83, 757, 809, 853, 109, 127, 113, 131,
Found in Database : 7, 13, 17, 29, 37, 41, 53, 59, 67, 71, 73, 79, 83, 103, 109, 113, 127, 131,