Inhaltsverzeichnis

Development of
Algorithmic Constructions

01:45:22
Deutsch
29.Mar 2024

Polynom = x^2-240x+2767

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) = 2767 = 2767
f(1) = 79 = 79
f(2) = 2291 = 29*79
f(3) = 257 = 257
f(4) = 1823 = 1823
f(5) = 199 = 199
f(6) = 1363 = 29*47
f(7) = 71 = 71
f(8) = 911 = 911
f(9) = 43 = 43
f(10) = 467 = 467
f(11) = 31 = 31
f(12) = 31 = 31
f(13) = 23 = 23
f(14) = 397 = 397
f(15) = 19 = 19
f(16) = 817 = 19*43
f(17) = 1 = 1
f(18) = 1229 = 1229
f(19) = 179 = 179
f(20) = 1633 = 23*71
f(21) = 229 = 229
f(22) = 2029 = 2029
f(23) = 139 = 139
f(24) = 2417 = 2417
f(25) = 163 = 163
f(26) = 2797 = 2797
f(27) = 373 = 373
f(28) = 3169 = 3169
f(29) = 419 = 419
f(30) = 3533 = 3533
f(31) = 29 = 29
f(32) = 3889 = 3889
f(33) = 127 = 127
f(34) = 4237 = 19*223
f(35) = 551 = 19*29
f(36) = 4577 = 23*199
f(37) = 593 = 593
f(38) = 4909 = 4909
f(39) = 317 = 317
f(40) = 5233 = 5233
f(41) = 337 = 337
f(42) = 5549 = 31*179
f(43) = 713 = 23*31
f(44) = 5857 = 5857
f(45) = 751 = 751
f(46) = 6157 = 47*131
f(47) = 197 = 197
f(48) = 6449 = 6449
f(49) = 103 = 103
f(50) = 6733 = 6733
f(51) = 859 = 859
f(52) = 7009 = 43*163
f(53) = 893 = 19*47
f(54) = 7277 = 19*383
f(55) = 463 = 463
f(56) = 7537 = 7537
f(57) = 479 = 479
f(58) = 7789 = 7789
f(59) = 989 = 23*43
f(60) = 8033 = 29*277
f(61) = 1019 = 1019
f(62) = 8269 = 8269
f(63) = 131 = 131
f(64) = 8497 = 29*293
f(65) = 269 = 269
f(66) = 8717 = 23*379
f(67) = 1103 = 1103
f(68) = 8929 = 8929
f(69) = 1129 = 1129
f(70) = 9133 = 9133
f(71) = 577 = 577
f(72) = 9329 = 19*491
f(73) = 589 = 19*31
f(74) = 9517 = 31*307
f(75) = 1201 = 1201
f(76) = 9697 = 9697
f(77) = 1223 = 1223
f(78) = 9869 = 71*139
f(79) = 311 = 311
f(80) = 10033 = 79*127
f(81) = 79 = 79
f(82) = 10189 = 23*443
f(83) = 1283 = 1283
f(84) = 10337 = 10337
f(85) = 1301 = 1301
f(86) = 10477 = 10477
f(87) = 659 = 659
f(88) = 10609 = 103*103
f(89) = 667 = 23*29
f(90) = 10733 = 10733
f(91) = 1349 = 19*71
f(92) = 10849 = 19*571
f(93) = 1363 = 29*47
f(94) = 10957 = 10957
f(95) = 43 = 43
f(96) = 11057 = 11057
f(97) = 347 = 347
f(98) = 11149 = 11149
f(99) = 1399 = 1399
f(100) = 11233 = 47*239

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-240x+2767

f(0)=2767
f(1)=79
f(2)=29
f(3)=257
f(4)=1823
f(5)=199
f(6)=47
f(7)=71
f(8)=911
f(9)=43
f(10)=467
f(11)=31
f(12)=1
f(13)=23
f(14)=397
f(15)=19
f(16)=1
f(17)=1
f(18)=1229
f(19)=179
f(20)=1
f(21)=229
f(22)=2029
f(23)=139
f(24)=2417
f(25)=163
f(26)=2797
f(27)=373
f(28)=3169
f(29)=419
f(30)=3533
f(31)=1
f(32)=3889
f(33)=127
f(34)=223
f(35)=1
f(36)=1
f(37)=593
f(38)=4909
f(39)=317
f(40)=5233
f(41)=337
f(42)=1
f(43)=1
f(44)=5857
f(45)=751
f(46)=131
f(47)=197
f(48)=6449
f(49)=103
f(50)=6733
f(51)=859
f(52)=1
f(53)=1
f(54)=383
f(55)=463
f(56)=7537
f(57)=479
f(58)=7789
f(59)=1
f(60)=277
f(61)=1019
f(62)=8269
f(63)=1
f(64)=293
f(65)=269
f(66)=379
f(67)=1103
f(68)=8929
f(69)=1129
f(70)=9133
f(71)=577
f(72)=491
f(73)=1
f(74)=307
f(75)=1201
f(76)=9697
f(77)=1223
f(78)=1
f(79)=311
f(80)=1
f(81)=1
f(82)=443
f(83)=1283
f(84)=10337
f(85)=1301
f(86)=10477
f(87)=659
f(88)=1
f(89)=1
f(90)=10733
f(91)=1
f(92)=571
f(93)=1
f(94)=10957
f(95)=1
f(96)=11057
f(97)=347
f(98)=11149
f(99)=1399

b) Substitution of the polynom
The polynom f(x)=x^2-240x+2767 could be written as f(y)= y^2-11633 with x=y+120

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-120
f'(x)>2x-241 with x > 108

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

2767, 79, 29, 257, 1823, 199, 47, 71, 911, 43, 467, 31, 1, 23, 397, 19, 1, 1, 1229, 179, 1, 229, 2029, 139, 2417, 163, 2797, 373, 3169, 419, 3533, 1, 3889, 127, 223, 1, 1, 593, 4909, 317, 5233, 337, 1, 1, 5857, 751, 131, 197, 6449, 103, 6733, 859, 1, 1, 383, 463, 7537, 479, 7789, 1, 277, 1019, 8269, 1, 293, 269, 379, 1103, 8929, 1129, 9133, 577, 491, 1, 307, 1201, 9697, 1223, 1, 311, 1, 1, 443, 1283, 10337, 1301, 10477, 659, 1, 1, 10733, 1, 571, 1, 10957, 1, 11057, 347, 11149, 1399, 239, 1409, 263, 709, 367, 1, 11437, 1433, 11489, 1439, 607, 1, 503, 181, 11597, 1451, 11617, 1453, 401, 727, 11633, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3251, 1, 1, 499, 4243, 281, 4751, 313, 1, 691, 5791, 757, 6323, 1, 6863, 1, 7411, 1, 1, 1031, 449, 1, 9103, 587, 421, 1, 10271, 1321, 10867, 349, 11471, 1, 1, 1549, 12703, 1627, 13331, 853, 13967, 1, 769, 1867, 15263, 1949, 15923, 1, 353, 1, 557, 1, 619, 2287, 1, 1187, 1, 1231, 20051, 2551, 1093, 1, 21491, 683, 1, 1, 22963, 2917, 1, 3011, 569, 1553, 1097, 1601, 26003, 3299, 26783, 1, 1, 1, 1493, 1, 941, 3697, 29983, 1, 30803, 1951, 673, 2003, 32467, 4111, 33311, 4217, 1, 1, 35023, 1, 1889, 1, 36767, 4651, 1637, 2381, 38543, 2437, 39443, 4987, 40351, 5101, 1423, 1, 1361, 1, 1487, 5449, 1, 1, 1, 2843, 1069, 2903, 661, 5927, 47903, 1, 48883, 1543, 49871, 787, 50867, 6421, 51871, 6547, 52883, 1, 2837, 1, 1, 1, 55967, 1, 1213, 1, 1873, 1831, 59123, 7457, 2617, 7591, 1, 3863, 62351, 3931, 63443, 1, 1, 1, 65651, 2069, 1, 1, 67891, 1, 3001, 8699, 70163, 4421, 2459, 4493, 72467, 1, 2539, 9277, 1, 1, 75983, 2393, 77171, 9721, 78367, 9871, 1693, 5011, 80783, 5087, 82003, 1, 83231, 1, 84467, 2659, 85711, 1, 1, 10949, 88223, 1, 89491, 1, 653, 1, 92051, 11587, 1, 1, 1, 1489, 1, 3019, 4229, 12241, 5189, 1, 99923, 6287, 773, 1, 102611, 12911, 103967, 1, 105331, 3313, 106703, 839, 3727, 13597, 109471, 1, 3823, 1, 1, 1, 113683, 1, 1, 1, 116531, 1, 1, 3709, 2777, 15017, 120863, 15199, 122323, 7691, 123791, 1, 1, 829, 126751, 15937, 1, 1, 5641, 2039, 131251, 1, 1289, 16691, 134291, 1, 1913, 8537, 137363, 1, 4481, 919, 7393, 2207, 142031, 4463, 881, 18049, 3089, 1, 1, 1, 148367, 9323, 149971, 1, 5227, 1, 6661, 4813, 1, 1, 156467, 19661, 3677, 19867, 159763, 10037, 1, 10141, 5261, 1, 164767, 1, 7237, 1307, 168143, 5281, 169843, 1123, 9029, 937, 173267, 10883, 174991, 1, 2237, 1, 997, 1, 180211, 5659, 181967, 2857, 1, 1, 1801, 1013, 9857, 1, 4397, 1, 1, 23971, 8377, 24197, 194483, 1, 196303, 6163, 1, 1, 199967, 25111, 6959, 12671, 203663, 1, 1, 1, 1, 26041, 209267, 6569, 211151, 1657, 213043, 1163, 214943, 26987, 216851, 13613, 7057, 1, 1109, 1, 11717, 1471, 224563, 1, 226511, 7109, 4861, 1, 230431, 28927, 1, 1, 234383, 1, 1, 29671, 1, 29921, 240371, 1, 12757, 3803, 244403, 30677, 1, 30931, 1, 1, 8081, 1, 1, 31699, 254623, 31957, 1303, 4027, 8923, 1, 13729, 1723, 9067, 32999, 3733, 16631, 1, 16763, 1, 33791, 1217, 34057, 6361, 8581, 1523, 1, 1, 1, 279967, 1, 1, 1, 1, 17837, 286483, 1, 2273, 1249, 1607, 2281, 293071, 1, 295283, 37049, 297503, 1, 299731, 18803, 1, 1, 304211, 38167, 306463, 38449, 308723, 1, 1, 4877, 313267, 39301, 315551, 1277, 10253, 19937, 320143, 1, 11119, 2129, 17093, 1, 11279, 1, 1, 10331, 3221, 41617, 1459, 41911, 14629, 1, 4289, 1, 341203, 1, 343583, 1, 1, 1, 348367, 2731, 350771, 43997, 11393, 1429, 15461, 1, 358031, 22453, 5077, 1559, 362911, 1979, 1319, 1, 367823, 1, 19489, 46441, 8669, 46751, 375251, 23531, 1, 23687, 1, 1, 382751, 2087, 385267, 1, 387791, 6079, 390323, 1579, 1, 2593, 1, 24793, 13723, 24953, 1367, 50227, 403103, 50549, 405683, 6359, 408271, 12799, 3989, 51521, 17977, 1, 1619, 1373, 22037, 26251, 421331, 2297, 1381, 53161, 426611, 1, 2179, 1, 13933, 1747, 6121, 1879, 10169, 1, 5569, 27581, 23297, 1, 1, 55837, 9533, 3511, 450767, 1, 19717, 56857, 456223, 1, 458963, 28771, 1, 1, 464467, 58231, 1, 3083, 1, 14731, 1, 1, 1, 59621, 1, 59971, 481171, 30161, 1, 1, 11321, 61027, 489631, 61381, 492467, 7717, 1, 1, 498163, 1, 1783, 1, 1, 31583, 3109, 1, 4013, 2203, 512543, 1, 1, 1, 1, 1, 521267, 1, 1, 65707, 527123, 33037, 530063, 1, 533011, 1, 535967, 67181, 538931, 2111, 23561, 16981, 544883, 1, 547871, 1597, 1, 1, 1, 1, 556883, 1, 1, 70177, 562931, 1, 18257, 8867, 569011, 71317, 572063, 71699, 575123, 1567, 578191, 1907, 30593, 1, 12433, 73237, 25541, 9203, 590543, 18503, 593651, 1583, 596767, 2579, 599891, 37591, 603023, 1, 2647, 75967, 32069, 4019, 1, 1, 1, 2411, 3457, 77549, 621983, 3389, 625171, 1, 1, 39373, 4973, 79147, 1, 79549, 2861, 1, 33749, 20089, 1, 80761, 1709, 3529, 22447, 40787, 654223, 1, 657491, 1753, 28729, 2671, 1, 1, 1, 10453, 1, 4423, 673951, 1, 8573, 42433, 1777, 42641, 683923, 1993, 29881, 86117, 690611, 1, 693967, 21739, 16217, 1, 700703, 4621, 37057, 44111, 1, 1, 710867, 89071, 23041, 2887, 717683, 22481, 7001, 5647, 724531, 3947, 5557, 1, 2719, 45821, 38677, 2423, 1, 92507, 25579, 92941, 2351, 1, 25819, 1, 2131, 1, 5437, 94687, 17657, 47563,

6. Sequence of the polynom (only primes)

2767, 79, 29, 257, 1823, 199, 47, 71, 911, 43, 467, 31, 23, 397, 19, 1229, 179, 229, 2029, 139, 2417, 163, 2797, 373, 3169, 419, 3533, 3889, 127, 223, 593, 4909, 317, 5233, 337, 5857, 751, 131, 197, 6449, 103, 6733, 859, 383, 463, 7537, 479, 7789, 277, 1019, 8269, 293, 269, 379, 1103, 8929, 1129, 9133, 577, 491, 307, 1201, 9697, 1223, 311, 443, 1283, 10337, 1301, 10477, 659, 10733, 571, 10957, 11057, 347, 11149, 1399, 239, 1409, 263, 709, 367, 11437, 1433, 11489, 1439, 607, 503, 181, 11597, 1451, 11617, 1453, 401, 727, 11633, 3251, 499, 4243, 281, 4751, 313, 691, 5791, 757, 6323, 6863, 7411, 1031, 449, 9103, 587, 421, 10271, 1321, 10867, 349, 11471, 1549, 12703, 1627, 13331, 853, 13967, 769, 1867, 15263, 1949, 15923, 353, 557, 619, 2287, 1187, 1231, 20051, 2551, 1093, 21491, 683, 22963, 2917, 3011, 569, 1553, 1097, 1601, 26003, 3299, 26783, 1493, 941, 3697, 29983, 30803, 1951, 673, 2003, 32467, 4111, 33311, 4217, 35023, 1889, 36767, 4651, 1637, 2381, 38543, 2437, 39443, 4987, 40351, 5101, 1423, 1361, 1487, 5449, 2843, 1069, 2903, 661, 5927, 47903, 48883, 1543, 49871, 787, 50867, 6421, 51871, 6547, 52883, 2837, 55967, 1213, 1873, 1831, 59123, 7457, 2617, 7591, 3863, 62351, 3931, 63443, 65651, 2069, 67891, 3001, 8699, 70163, 4421, 2459, 4493, 72467, 2539, 9277, 75983, 2393, 77171, 9721, 78367, 9871, 1693, 5011, 80783, 5087, 82003, 83231, 84467, 2659, 85711, 10949, 88223, 89491, 653, 92051, 11587, 1489, 3019, 4229, 12241, 5189, 99923, 6287, 773, 102611, 12911, 103967, 105331, 3313, 106703, 839, 3727, 13597, 109471, 3823, 113683, 116531, 3709, 2777, 15017, 120863, 15199, 122323, 7691, 123791, 829, 126751, 15937, 5641, 2039, 131251, 1289, 16691, 134291, 1913, 8537, 137363, 4481, 919, 7393, 2207, 142031, 4463, 881, 18049, 3089, 148367, 9323, 149971, 5227, 6661, 4813, 156467, 19661, 3677, 19867, 159763, 10037, 10141, 5261, 164767, 7237, 1307, 168143, 5281, 169843, 1123, 9029, 937, 173267, 10883, 174991, 2237, 997, 180211, 5659, 181967, 2857, 1801, 1013, 9857, 4397, 23971, 8377, 24197, 194483, 196303, 6163, 199967, 25111, 6959, 12671, 203663, 26041, 209267, 6569, 211151, 1657, 213043, 1163, 214943, 26987, 216851, 13613, 7057, 1109, 11717, 1471, 224563, 226511, 7109, 4861, 230431, 28927, 234383, 29671, 29921, 240371, 12757, 3803, 244403, 30677, 30931, 8081, 31699, 254623, 31957, 1303, 4027, 8923, 13729, 1723, 9067, 32999, 3733, 16631, 16763, 33791, 1217, 34057, 6361, 8581, 1523, 279967, 17837, 286483, 2273, 1249, 1607, 2281, 293071, 295283, 37049, 297503, 299731, 18803, 304211, 38167, 306463, 38449, 308723, 4877, 313267, 39301, 315551, 1277, 10253, 19937, 320143, 11119, 2129, 17093, 11279, 10331, 3221, 41617, 1459, 41911, 14629, 4289, 341203, 343583, 348367, 2731, 350771, 43997, 11393, 1429, 15461, 358031, 22453, 5077, 1559, 362911, 1979, 1319, 367823, 19489, 46441, 8669, 46751, 375251, 23531, 23687, 382751, 2087, 385267, 387791, 6079, 390323, 1579, 2593, 24793, 13723, 24953, 1367, 50227, 403103, 50549, 405683, 6359, 408271, 12799, 3989, 51521, 17977, 1619, 1373, 22037, 26251, 421331, 2297, 1381, 53161, 426611, 2179, 13933, 1747, 6121, 1879, 10169, 5569, 27581, 23297, 55837, 9533, 3511, 450767, 19717, 56857, 456223, 458963, 28771, 464467, 58231, 3083, 14731, 59621, 59971, 481171, 30161, 11321, 61027, 489631, 61381, 492467, 7717, 498163, 1783, 31583, 3109, 4013, 2203, 512543, 521267, 65707, 527123, 33037, 530063, 533011, 535967, 67181, 538931, 2111, 23561, 16981, 544883, 547871, 1597, 556883, 70177, 562931, 18257, 8867, 569011, 71317, 572063, 71699, 575123, 1567, 578191, 1907, 30593, 12433, 73237, 25541, 9203, 590543, 18503, 593651, 1583, 596767, 2579, 599891, 37591, 603023, 2647, 75967, 32069, 4019, 2411, 3457, 77549, 621983, 3389, 625171, 39373, 4973, 79147, 79549, 2861, 33749, 20089, 80761, 1709, 3529, 22447, 40787, 654223, 657491, 1753, 28729, 2671, 10453, 4423, 673951, 8573, 42433, 1777, 42641, 683923, 1993, 29881, 86117, 690611, 693967, 21739, 16217, 700703, 4621, 37057, 44111, 710867, 89071, 23041, 2887, 717683, 22481, 7001, 5647, 724531, 3947, 5557, 2719, 45821, 38677, 2423, 92507, 25579, 92941, 2351, 25819, 2131, 5437, 94687, 17657, 47563,

7. Distribution of the primes

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

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 1 2 1.5 0.5 1
2 4 5 2 3 1.25 0.5 0.75
3 8 9 3 6 1.125 0.375 0.75
4 16 15 5 10 0.9375 0.3125 0.625
5 32 28 12 16 0.875 0.375 0.5
6 64 52 20 32 0.8125 0.3125 0.5
7 128 97 34 63 0.7578125 0.265625 0.4921875
8 256 108 40 68 0.421875 0.15625 0.265625
9 512 286 105 181 0.55859375 0.20507813 0.35351563
10 1024 647 203 444 0.63183594 0.19824219 0.43359375
11 2048 1371 374 997 0.66943359 0.18261719 0.48681641
12 4096 2806 694 2112 0.68505859 0.16943359 0.515625
13 8192 5656 1290 4366 0.69042969 0.1574707 0.53295898
14 16384 11387 2418 8969 0.69500732 0.14758301 0.54742432
15 32768 22845 4415 18430 0.69717407 0.13473511 0.56243896
16 65536 45742 8206 37536 0.69796753 0.12521362 0.57275391
17 131072 91467 15369 76098 0.69783783 0.11725616 0.58058167
18 262144 183053 28765 154288 0.69829178 0.10972977 0.58856201
19 524288 366070 54338 311732 0.69822311 0.10364151 0.5945816
20 1048576 731818 102867 628951 0.69791603 0.09810162 0.59981441
21 2097152 1463544 194852 1268692 0.69787216 0.09291267 0.60495949
22 4194304 2926345 370474 2555871 0.69769502 0.08832788 0.60936713
23 8388608 5851325 705765 5145560 0.6975323 0.08413374 0.61339855
24 16777216 11698099 1349567 10348532 0.69726104 0.08044046 0.61682057


8. Check for existing Integer Sequences by OEIS

Found in Database : 2767, 79, 29, 257, 1823, 199, 47, 71, 911, 43, 467, 31, 1, 23, 397, 19, 1, 1, 1229, 179,
Found in Database : 2767, 79, 29, 257, 1823, 199, 47, 71, 911, 43, 467, 31, 23, 397, 19, 1229, 179, 229, 2029, 139, 2417, 163, 2797, 373, 3169, 419, 3533, 3889, 127, 223, 593, 4909, 317,
Found in Database : 19, 23, 29, 31, 43, 47, 71, 79, 103, 127, 131, 139,