Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:06:04
Deutsch
28.Mar 2024

Polynom = x^2+64x-2689

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) = 2689 = 2689
f(1) = 41 = 41
f(2) = 2557 = 2557
f(3) = 311 = 311
f(4) = 2417 = 2417
f(5) = 293 = 293
f(6) = 2269 = 2269
f(7) = 137 = 137
f(8) = 2113 = 2113
f(9) = 127 = 127
f(10) = 1949 = 1949
f(11) = 233 = 233
f(12) = 1777 = 1777
f(13) = 211 = 211
f(14) = 1597 = 1597
f(15) = 47 = 47
f(16) = 1409 = 1409
f(17) = 41 = 41
f(18) = 1213 = 1213
f(19) = 139 = 139
f(20) = 1009 = 1009
f(21) = 113 = 113
f(22) = 797 = 797
f(23) = 43 = 43
f(24) = 577 = 577
f(25) = 29 = 29
f(26) = 349 = 349
f(27) = 29 = 29
f(28) = 113 = 113
f(29) = 1 = 1
f(30) = 131 = 131
f(31) = 1 = 1
f(32) = 383 = 383
f(33) = 1 = 1
f(34) = 643 = 643
f(35) = 97 = 97
f(36) = 911 = 911
f(37) = 131 = 131
f(38) = 1187 = 1187
f(39) = 83 = 83
f(40) = 1471 = 1471
f(41) = 101 = 101
f(42) = 1763 = 41*43
f(43) = 239 = 239
f(44) = 2063 = 2063
f(45) = 277 = 277
f(46) = 2371 = 2371
f(47) = 79 = 79
f(48) = 2687 = 2687
f(49) = 89 = 89
f(50) = 3011 = 3011
f(51) = 397 = 397
f(52) = 3343 = 3343
f(53) = 439 = 439
f(54) = 3683 = 29*127
f(55) = 241 = 241
f(56) = 4031 = 29*139
f(57) = 263 = 263
f(58) = 4387 = 41*107
f(59) = 571 = 571
f(60) = 4751 = 4751
f(61) = 617 = 617
f(62) = 5123 = 47*109
f(63) = 83 = 83
f(64) = 5503 = 5503
f(65) = 89 = 89
f(66) = 5891 = 43*137
f(67) = 761 = 761
f(68) = 6287 = 6287
f(69) = 811 = 811
f(70) = 6691 = 6691
f(71) = 431 = 431
f(72) = 7103 = 7103
f(73) = 457 = 457
f(74) = 7523 = 7523
f(75) = 967 = 967
f(76) = 7951 = 7951
f(77) = 1021 = 1021
f(78) = 8387 = 8387
f(79) = 269 = 269
f(80) = 8831 = 8831
f(81) = 283 = 283
f(82) = 9283 = 9283
f(83) = 1189 = 29*41
f(84) = 9743 = 9743
f(85) = 1247 = 29*43
f(86) = 10211 = 10211
f(87) = 653 = 653
f(88) = 10687 = 10687
f(89) = 683 = 683
f(90) = 11171 = 11171
f(91) = 1427 = 1427
f(92) = 11663 = 107*109
f(93) = 1489 = 1489
f(94) = 12163 = 12163
f(95) = 97 = 97
f(96) = 12671 = 12671
f(97) = 101 = 101
f(98) = 13187 = 13187
f(99) = 1681 = 41*41
f(100) = 13711 = 13711

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+64x-2689

f(0)=2689
f(1)=41
f(2)=2557
f(3)=311
f(4)=2417
f(5)=293
f(6)=2269
f(7)=137
f(8)=2113
f(9)=127
f(10)=1949
f(11)=233
f(12)=1777
f(13)=211
f(14)=1597
f(15)=47
f(16)=1409
f(17)=1
f(18)=1213
f(19)=139
f(20)=1009
f(21)=113
f(22)=797
f(23)=43
f(24)=577
f(25)=29
f(26)=349
f(27)=1
f(28)=1
f(29)=1
f(30)=131
f(31)=1
f(32)=383
f(33)=1
f(34)=643
f(35)=97
f(36)=911
f(37)=1
f(38)=1187
f(39)=83
f(40)=1471
f(41)=101
f(42)=1
f(43)=239
f(44)=2063
f(45)=277
f(46)=2371
f(47)=79
f(48)=2687
f(49)=89
f(50)=3011
f(51)=397
f(52)=3343
f(53)=439
f(54)=1
f(55)=241
f(56)=1
f(57)=263
f(58)=107
f(59)=571
f(60)=4751
f(61)=617
f(62)=109
f(63)=1
f(64)=5503
f(65)=1
f(66)=1
f(67)=761
f(68)=6287
f(69)=811
f(70)=6691
f(71)=431
f(72)=7103
f(73)=457
f(74)=7523
f(75)=967
f(76)=7951
f(77)=1021
f(78)=8387
f(79)=269
f(80)=8831
f(81)=283
f(82)=9283
f(83)=1
f(84)=9743
f(85)=1
f(86)=10211
f(87)=653
f(88)=10687
f(89)=683
f(90)=11171
f(91)=1427
f(92)=1
f(93)=1489
f(94)=12163
f(95)=1
f(96)=12671
f(97)=1
f(98)=13187
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2+64x-2689 could be written as f(y)= y^2-3713 with x=y-32

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+32
f'(x)>2x+63

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

2689, 41, 2557, 311, 2417, 293, 2269, 137, 2113, 127, 1949, 233, 1777, 211, 1597, 47, 1409, 1, 1213, 139, 1009, 113, 797, 43, 577, 29, 349, 1, 1, 1, 131, 1, 383, 1, 643, 97, 911, 1, 1187, 83, 1471, 101, 1, 239, 2063, 277, 2371, 79, 2687, 89, 3011, 397, 3343, 439, 1, 241, 1, 263, 107, 571, 4751, 617, 109, 1, 5503, 1, 1, 761, 6287, 811, 6691, 431, 7103, 457, 7523, 967, 7951, 1021, 8387, 269, 8831, 283, 9283, 1, 9743, 1, 10211, 653, 10687, 683, 11171, 1427, 1, 1489, 12163, 1, 12671, 1, 13187, 1, 13711, 1747, 14243, 907, 14783, 941, 15331, 1951, 15887, 1, 16451, 523, 587, 541, 607, 2237, 18191, 2311, 18787, 1193, 19391, 1231, 1, 2539, 503, 2617, 1, 337, 509, 347, 22531, 2857, 1, 2939, 1, 1511, 193, 1553, 1, 3191, 631, 1, 1, 1, 199, 863, 1, 3541, 28687, 3631, 29411, 1861, 701, 1907, 1, 3907, 673, 4001, 1, 1, 33151, 1, 33923, 4289, 34703, 1, 35491, 2243, 1, 2293, 1279, 1, 1307, 4789, 38723, 1223, 39551, 1249, 40387, 5101, 41231, 1, 42083, 2657, 42943, 2711, 227, 5531, 44687, 5641, 229, 719, 479, 733, 47363, 1, 48271, 6091, 487, 1, 50111, 1, 51043, 1, 1, 1, 1291, 1669, 53887, 1699, 54851, 6917, 55823, 7039, 1321, 3581, 57791, 3643, 58787, 7411, 59791, 7537, 1483, 1, 1, 1, 62851, 1, 2203, 1, 2239, 4091, 65983, 4157, 67043, 8447, 68111, 8581, 1609, 2179, 70271, 2213, 71363, 1, 1, 9127, 73571, 1, 74687, 4703, 1613, 9547, 76943, 9689, 691, 1229, 79231, 1, 80387, 1, 81551, 10267, 82723, 1, 83903, 5281, 85091, 10711, 86287, 10861, 87491, 2753, 829, 2791, 89923, 11317, 91151, 11471, 92387, 5813, 859, 1, 1, 11939, 1217, 12097, 3359, 1, 1, 1, 99971, 12577, 773, 12739, 102563, 6451, 1, 1, 359, 1, 2477, 13397, 107843, 3391, 2663, 3433, 1033, 13901, 881, 14071, 1039, 7121, 1381, 7207, 373, 1, 1319, 1, 118787, 1867, 1, 1889, 1, 15289, 2861, 15467, 1283, 7823, 125887, 1, 127331, 16007, 1447, 16189, 937, 4093, 131711, 4139, 133187, 16741, 983, 16927, 136163, 1, 1, 1, 4799, 17491, 1, 17681, 142211, 1117, 143743, 1129, 145283, 18257, 409, 18451, 148387, 9323, 1327, 9421, 151523, 1, 1, 19237, 154691, 1, 419, 4909, 3851, 1, 159503, 1, 161123, 1, 162751, 10223, 164387, 1, 166031, 20857, 167683, 2633, 169343, 2659, 1, 21481, 172687, 1, 1373, 1, 176063, 11057, 177763, 1, 179471, 22541, 443, 5689, 1811, 5743, 6367, 23189, 6427, 1, 449, 11813, 189887, 11923, 4457, 1, 193423, 1, 195203, 1, 196991, 1, 1451, 1, 200591, 1, 202403, 1, 461, 12821, 206051, 1, 463, 1, 1601, 1, 211583, 1, 1, 1, 1549, 27031, 4621, 13633, 219071, 13751, 2797, 27739, 222863, 1, 224771, 3527, 1, 3557, 228611, 28697, 5623, 1, 2801, 14591, 234431, 14713, 236387, 29671, 8219, 29917, 8287, 7541, 1, 7603, 244291, 30661, 6007, 30911, 248291, 15581, 5821, 1, 252323, 31667, 1, 1, 3089, 2011, 2287, 2027, 260483, 1, 262543, 1, 2473, 16603, 266687, 1, 268771, 1163, 1, 1, 3067, 8563, 6397, 8629, 2543, 34781, 279311, 1, 1, 17657, 283583, 17791, 285731, 35851, 287887, 1, 3259, 4549, 292223, 4583, 294403, 1, 296591, 1, 10303, 18743, 1, 1, 1571, 38039, 305423, 38317, 307651, 9649, 2843, 9719, 1, 39157, 6689, 39439, 7723, 19861, 318911, 1, 321187, 1, 323471, 40577, 1637, 1277, 328063, 1, 3271, 1429, 332687, 1439, 8171, 21011, 337343, 21157, 2593, 1, 1621, 42901, 8009, 10799, 346751, 1, 2749, 43789, 351503, 44087, 353891, 22193, 356287, 22343, 358691, 44987, 1871, 45289, 363523, 1, 12619, 5737, 12703, 1, 3823, 46507, 8681, 1, 375743, 23561, 3347, 47431, 1913, 47741, 383171, 1, 385663, 1, 388163, 48677, 390671, 48991, 393187, 1, 5009, 1, 3943, 49939, 1663, 1733, 403331, 1, 1, 3181, 1709, 51217, 2957, 51539, 3019, 25931, 10151, 1, 418787, 52511, 5077, 52837, 424003, 13291, 1831, 1, 9133, 1, 431887, 54151, 1, 27241, 10663, 27407, 1, 55147, 15259, 1, 445187, 6977, 1973, 7019, 450563, 56489, 1, 56827, 2161, 1, 2003, 28753, 461411, 57847, 464143, 58189, 1, 14633, 469631, 1, 2081, 59221, 475151, 59567, 2087, 1, 1787, 1, 483491, 60611, 1, 60961, 1, 1, 5527, 1, 494723, 62017, 497551, 1, 1, 1, 503231, 31541, 506083, 63439, 508943, 1, 511811, 1, 5783, 1, 517571, 64877, 1, 65239, 18047, 32801, 526271, 32983, 12907, 1, 4973, 66697, 1, 1, 1901, 8429, 4787, 67801, 543887, 68171, 2347, 1, 1, 34457, 1, 1, 5099, 69661, 558787, 17509, 11953, 1, 2039, 2441, 1627, 71167, 570851, 1, 573887, 35963, 13417, 72307, 579983, 72689, 5449, 4567, 586111, 4591, 589187, 1801, 1, 1, 595363, 37307, 598463, 37501, 5519, 75391, 5987, 75781, 20959, 1, 21067, 19141, 14281, 1877, 617231, 77351, 7853, 38873, 2609, 1, 626723, 78539, 629903, 1, 633091, 1, 636287, 9967, 639491, 1, 1, 1873, 6659, 40471, 649151, 1, 2707, 2819, 15991, 2833, 658883, 20641, 662143, 20743, 8017, 1, 668687, 83791, 671971, 42101, 675263, 42307, 678563, 85027, 16631, 1987, 1789, 2683, 688511, 1, 691843, 86689, 6883, 87107, 698531, 1, 24203, 43973, 1, 1, 6271, 88789, 15149, 22303, 1, 22409, 1, 1, 2143, 2207, 725603, 1, 729023, 1, 1, 91771, 1, 1, 739331, 11579, 742783, 11633, 746243, 93497, 749711, 1, 753187, 1, 17597, 1, 760163, 95239, 763663, 1, 2917, 24029, 2221, 1, 8699, 96997, 777743, 1, 781283, 1, 784831, 1, 788387, 2297, 791951, 2111, 19403, 6229, 799103, 6257, 1, 1, 27803, 1, 809891, 1, 813503, 50957, 817123, 102367, 2963, 1, 20107, 25819, 1, 25933, 831683, 2423, 2851, 1, 3119, 52553, 6151, 52783, 6089, 1, 850063, 1, 853763, 1, 857471, 1, 6781, 107881, 864911, 108347, 20201, 1, 872383, 1, 876131, 109751, 1, 110221, 1, 27673, 887423, 27791, 8329, 111637, 11329, 112111, 898787, 1, 902591, 56531, 906403, 113539, 31387, 1, 1, 1, 917887, 3593, 3257, 1, 8191, 1, 8527, 58211, 3001, 58453, 937187, 1, 4729, 117877, 944963, 1, 23143, 1, 952771, 1, 8941, 119831, 9511, 60161, 11621, 2083, 7393, 1, 972431, 1, 5059, 15287, 23911, 15349, 984323, 123289, 9067, 123787, 7243, 62143, 10271, 1, 1000291, 125287, 1004303, 125789, 1008323, 31573, 12197, 31699, 4817, 127301, 1020431, 127807, 35327, 64157, 1, 1, 5189, 1, 24109, 129841, 1040771, 8147, 7517, 8179, 1048963, 1, 1053071, 131891, 1, 1,

6. Sequence of the polynom (only primes)

2689, 41, 2557, 311, 2417, 293, 2269, 137, 2113, 127, 1949, 233, 1777, 211, 1597, 47, 1409, 1213, 139, 1009, 113, 797, 43, 577, 29, 349, 131, 383, 643, 97, 911, 1187, 83, 1471, 101, 239, 2063, 277, 2371, 79, 2687, 89, 3011, 397, 3343, 439, 241, 263, 107, 571, 4751, 617, 109, 5503, 761, 6287, 811, 6691, 431, 7103, 457, 7523, 967, 7951, 1021, 8387, 269, 8831, 283, 9283, 9743, 10211, 653, 10687, 683, 11171, 1427, 1489, 12163, 12671, 13187, 13711, 1747, 14243, 907, 14783, 941, 15331, 1951, 15887, 16451, 523, 587, 541, 607, 2237, 18191, 2311, 18787, 1193, 19391, 1231, 2539, 503, 2617, 337, 509, 347, 22531, 2857, 2939, 1511, 193, 1553, 3191, 631, 199, 863, 3541, 28687, 3631, 29411, 1861, 701, 1907, 3907, 673, 4001, 33151, 33923, 4289, 34703, 35491, 2243, 2293, 1279, 1307, 4789, 38723, 1223, 39551, 1249, 40387, 5101, 41231, 42083, 2657, 42943, 2711, 227, 5531, 44687, 5641, 229, 719, 479, 733, 47363, 48271, 6091, 487, 50111, 51043, 1291, 1669, 53887, 1699, 54851, 6917, 55823, 7039, 1321, 3581, 57791, 3643, 58787, 7411, 59791, 7537, 1483, 62851, 2203, 2239, 4091, 65983, 4157, 67043, 8447, 68111, 8581, 1609, 2179, 70271, 2213, 71363, 9127, 73571, 74687, 4703, 1613, 9547, 76943, 9689, 691, 1229, 79231, 80387, 81551, 10267, 82723, 83903, 5281, 85091, 10711, 86287, 10861, 87491, 2753, 829, 2791, 89923, 11317, 91151, 11471, 92387, 5813, 859, 11939, 1217, 12097, 3359, 99971, 12577, 773, 12739, 102563, 6451, 359, 2477, 13397, 107843, 3391, 2663, 3433, 1033, 13901, 881, 14071, 1039, 7121, 1381, 7207, 373, 1319, 118787, 1867, 1889, 15289, 2861, 15467, 1283, 7823, 125887, 127331, 16007, 1447, 16189, 937, 4093, 131711, 4139, 133187, 16741, 983, 16927, 136163, 4799, 17491, 17681, 142211, 1117, 143743, 1129, 145283, 18257, 409, 18451, 148387, 9323, 1327, 9421, 151523, 19237, 154691, 419, 4909, 3851, 159503, 161123, 162751, 10223, 164387, 166031, 20857, 167683, 2633, 169343, 2659, 21481, 172687, 1373, 176063, 11057, 177763, 179471, 22541, 443, 5689, 1811, 5743, 6367, 23189, 6427, 449, 11813, 189887, 11923, 4457, 193423, 195203, 196991, 1451, 200591, 202403, 461, 12821, 206051, 463, 1601, 211583, 1549, 27031, 4621, 13633, 219071, 13751, 2797, 27739, 222863, 224771, 3527, 3557, 228611, 28697, 5623, 2801, 14591, 234431, 14713, 236387, 29671, 8219, 29917, 8287, 7541, 7603, 244291, 30661, 6007, 30911, 248291, 15581, 5821, 252323, 31667, 3089, 2011, 2287, 2027, 260483, 262543, 2473, 16603, 266687, 268771, 1163, 3067, 8563, 6397, 8629, 2543, 34781, 279311, 17657, 283583, 17791, 285731, 35851, 287887, 3259, 4549, 292223, 4583, 294403, 296591, 10303, 18743, 1571, 38039, 305423, 38317, 307651, 9649, 2843, 9719, 39157, 6689, 39439, 7723, 19861, 318911, 321187, 323471, 40577, 1637, 1277, 328063, 3271, 1429, 332687, 1439, 8171, 21011, 337343, 21157, 2593, 1621, 42901, 8009, 10799, 346751, 2749, 43789, 351503, 44087, 353891, 22193, 356287, 22343, 358691, 44987, 1871, 45289, 363523, 12619, 5737, 12703, 3823, 46507, 8681, 375743, 23561, 3347, 47431, 1913, 47741, 383171, 385663, 388163, 48677, 390671, 48991, 393187, 5009, 3943, 49939, 1663, 1733, 403331, 3181, 1709, 51217, 2957, 51539, 3019, 25931, 10151, 418787, 52511, 5077, 52837, 424003, 13291, 1831, 9133, 431887, 54151, 27241, 10663, 27407, 55147, 15259, 445187, 6977, 1973, 7019, 450563, 56489, 56827, 2161, 2003, 28753, 461411, 57847, 464143, 58189, 14633, 469631, 2081, 59221, 475151, 59567, 2087, 1787, 483491, 60611, 60961, 5527, 494723, 62017, 497551, 503231, 31541, 506083, 63439, 508943, 511811, 5783, 517571, 64877, 65239, 18047, 32801, 526271, 32983, 12907, 4973, 66697, 1901, 8429, 4787, 67801, 543887, 68171, 2347, 34457, 5099, 69661, 558787, 17509, 11953, 2039, 2441, 1627, 71167, 570851, 573887, 35963, 13417, 72307, 579983, 72689, 5449, 4567, 586111, 4591, 589187, 1801, 595363, 37307, 598463, 37501, 5519, 75391, 5987, 75781, 20959, 21067, 19141, 14281, 1877, 617231, 77351, 7853, 38873, 2609, 626723, 78539, 629903, 633091, 636287, 9967, 639491, 1873, 6659, 40471, 649151, 2707, 2819, 15991, 2833, 658883, 20641, 662143, 20743, 8017, 668687, 83791, 671971, 42101, 675263, 42307, 678563, 85027, 16631, 1987, 1789, 2683, 688511, 691843, 86689, 6883, 87107, 698531, 24203, 43973, 6271, 88789, 15149, 22303, 22409, 2143, 2207, 725603, 729023, 91771, 739331, 11579, 742783, 11633, 746243, 93497, 749711, 753187, 17597, 760163, 95239, 763663, 2917, 24029, 2221, 8699, 96997, 777743, 781283, 784831, 788387, 2297, 791951, 2111, 19403, 6229, 799103, 6257, 27803, 809891, 813503, 50957, 817123, 102367, 2963, 20107, 25819, 25933, 831683, 2423, 2851, 3119, 52553, 6151, 52783, 6089, 850063, 853763, 857471, 6781, 107881, 864911, 108347, 20201, 872383, 876131, 109751, 110221, 27673, 887423, 27791, 8329, 111637, 11329, 112111, 898787, 902591, 56531, 906403, 113539, 31387, 917887, 3593, 3257, 8191, 8527, 58211, 3001, 58453, 937187, 4729, 117877, 944963, 23143, 952771, 8941, 119831, 9511, 60161, 11621, 2083, 7393, 972431, 5059, 15287, 23911, 15349, 984323, 123289, 9067, 123787, 7243, 62143, 10271, 1000291, 125287, 1004303, 125789, 1008323, 31573, 12197, 31699, 4817, 127301, 1020431, 127807, 35327, 64157, 5189, 24109, 129841, 1040771, 8147, 7517, 8179, 1048963, 1053071, 131891,

7. Distribution of the primes

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

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 : 2689, 41, 2557, 311, 2417, 293, 2269, 137, 2113, 127, 1949, 233, 1777, 211, 1597, 47, 1409, 1, 1213, 139,
Found in Database : 2689, 41, 2557, 311, 2417, 293, 2269, 137, 2113, 127, 1949, 233, 1777, 211, 1597, 47, 1409, 1213, 139, 1009, 113, 797, 43, 577, 29, 349, 131, 383, 643, 97, 911, 1187, 83,
Found in Database : 29, 41, 43, 47, 79, 83, 89, 97, 101, 107, 109, 113, 127, 131, 137, 139,