Inhaltsverzeichnis

Development of
Algorithmic Constructions

01:32:59
Deutsch
29.Mar 2024

Polynom = x^2+84x-853

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) = 853 = 853
f(1) = 3 = 3
f(2) = 681 = 3*227
f(3) = 37 = 37
f(4) = 501 = 3*167
f(5) = 51 = 3*17
f(6) = 313 = 313
f(7) = 27 = 3*3*3
f(8) = 117 = 3*3*13
f(9) = 1 = 1
f(10) = 87 = 3*29
f(11) = 3 = 3
f(12) = 299 = 13*23
f(13) = 51 = 3*17
f(14) = 519 = 3*173
f(15) = 79 = 79
f(16) = 747 = 3*3*83
f(17) = 27 = 3*3*3
f(18) = 983 = 983
f(19) = 69 = 3*23
f(20) = 1227 = 3*409
f(21) = 169 = 13*13
f(22) = 1479 = 3*17*29
f(23) = 201 = 3*67
f(24) = 1739 = 37*47
f(25) = 117 = 3*3*13
f(26) = 2007 = 3*3*223
f(27) = 67 = 67
f(28) = 2283 = 3*761
f(29) = 303 = 3*101
f(30) = 2567 = 17*151
f(31) = 339 = 3*113
f(32) = 2859 = 3*953
f(33) = 47 = 47
f(34) = 3159 = 3*3*3*3*3*13
f(35) = 207 = 3*3*23
f(36) = 3467 = 3467
f(37) = 453 = 3*151
f(38) = 3783 = 3*13*97
f(39) = 493 = 17*29
f(40) = 4107 = 3*37*37
f(41) = 267 = 3*89
f(42) = 4439 = 23*193
f(43) = 9 = 3*3
f(44) = 4779 = 3*3*3*3*59
f(45) = 619 = 619
f(46) = 5127 = 3*1709
f(47) = 663 = 3*13*17
f(48) = 5483 = 5483
f(49) = 177 = 3*59
f(50) = 5847 = 3*1949
f(51) = 377 = 13*29
f(52) = 6219 = 3*3*691
f(53) = 801 = 3*3*89
f(54) = 6599 = 6599
f(55) = 849 = 3*283
f(56) = 6987 = 3*17*137
f(57) = 449 = 449
f(58) = 7383 = 3*23*107
f(59) = 237 = 3*79
f(60) = 7787 = 13*599
f(61) = 999 = 3*3*3*37
f(62) = 8199 = 3*3*911
f(63) = 1051 = 1051
f(64) = 8619 = 3*13*13*17
f(65) = 69 = 3*23
f(66) = 9047 = 83*109
f(67) = 579 = 3*193
f(68) = 9483 = 3*29*109
f(69) = 1213 = 1213
f(70) = 9927 = 3*3*1103
f(71) = 1269 = 3*3*3*47
f(72) = 10379 = 97*107
f(73) = 663 = 3*13*17
f(74) = 10839 = 3*3613
f(75) = 173 = 173
f(76) = 11307 = 3*3769
f(77) = 1443 = 3*13*37
f(78) = 11783 = 11783
f(79) = 1503 = 3*3*167
f(80) = 12267 = 3*3*29*47
f(81) = 391 = 17*23
f(82) = 12759 = 3*4253
f(83) = 813 = 3*271
f(84) = 13259 = 13259
f(85) = 1689 = 3*563
f(86) = 13767 = 3*13*353
f(87) = 1753 = 1753
f(88) = 14283 = 3*3*3*23*23
f(89) = 909 = 3*3*101
f(90) = 14807 = 13*17*67
f(91) = 471 = 3*157
f(92) = 15339 = 3*5113
f(93) = 1951 = 1951
f(94) = 15879 = 3*67*79
f(95) = 2019 = 3*673
f(96) = 16427 = 16427
f(97) = 261 = 3*3*29
f(98) = 16983 = 3*3*3*17*37
f(99) = 1079 = 13*83
f(100) = 17547 = 3*5849

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+84x-853

f(0)=853
f(1)=3
f(2)=227
f(3)=37
f(4)=167
f(5)=17
f(6)=313
f(7)=1
f(8)=13
f(9)=1
f(10)=29
f(11)=1
f(12)=23
f(13)=1
f(14)=173
f(15)=79
f(16)=83
f(17)=1
f(18)=983
f(19)=1
f(20)=409
f(21)=1
f(22)=1
f(23)=67
f(24)=47
f(25)=1
f(26)=223
f(27)=1
f(28)=761
f(29)=101
f(30)=151
f(31)=113
f(32)=953
f(33)=1
f(34)=1
f(35)=1
f(36)=3467
f(37)=1
f(38)=97
f(39)=1
f(40)=1
f(41)=89
f(42)=193
f(43)=1
f(44)=59
f(45)=619
f(46)=1709
f(47)=1
f(48)=5483
f(49)=1
f(50)=1949
f(51)=1
f(52)=691
f(53)=1
f(54)=6599
f(55)=283
f(56)=137
f(57)=449
f(58)=107
f(59)=1
f(60)=599
f(61)=1
f(62)=911
f(63)=1051
f(64)=1
f(65)=1
f(66)=109
f(67)=1
f(68)=1
f(69)=1213
f(70)=1103
f(71)=1
f(72)=1
f(73)=1
f(74)=3613
f(75)=1
f(76)=3769
f(77)=1
f(78)=11783
f(79)=1
f(80)=1
f(81)=1
f(82)=4253
f(83)=271
f(84)=13259
f(85)=563
f(86)=353
f(87)=1753
f(88)=1
f(89)=1
f(90)=1
f(91)=157
f(92)=5113
f(93)=1951
f(94)=1
f(95)=673
f(96)=16427
f(97)=1
f(98)=1
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2+84x-853 could be written as f(y)= y^2-2617 with x=y-42

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+42
f'(x)>2x+83

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

853, 3, 227, 37, 167, 17, 313, 1, 13, 1, 29, 1, 23, 1, 173, 79, 83, 1, 983, 1, 409, 1, 1, 67, 47, 1, 223, 1, 761, 101, 151, 113, 953, 1, 1, 1, 3467, 1, 97, 1, 1, 89, 193, 1, 59, 619, 1709, 1, 5483, 1, 1949, 1, 691, 1, 6599, 283, 137, 449, 107, 1, 599, 1, 911, 1051, 1, 1, 109, 1, 1, 1213, 1103, 1, 1, 1, 3613, 1, 3769, 1, 11783, 1, 1, 1, 4253, 271, 13259, 563, 353, 1753, 1, 1, 1, 157, 5113, 1951, 1, 673, 16427, 1, 1, 1, 5849, 743, 18119, 1, 1, 1187, 2143, 1, 337, 1, 6829, 1, 541, 1, 587, 1, 191, 2833, 163, 971, 23627, 499, 8093, 769, 1, 1, 883, 1, 8761, 1, 1, 569, 1627, 389, 1, 1, 9689, 613, 1, 1, 10169, 1, 1, 439, 1, 1, 10909, 2069, 11161, 1, 1489, 1, 1297, 2213, 11933, 1, 36587, 1, 733, 4723, 4243, 1, 661, 821, 1021, 1, 797, 1, 3191, 1, 4703, 1, 1, 1, 937, 1, 14969, 1, 5087, 1, 2029, 1, 1, 1, 557, 1019, 49367, 1, 1, 6343, 1, 2153, 3067, 1, 1361, 3347, 1, 757, 54983, 2311, 1097, 3527, 18973, 1, 57899, 811, 727, 571, 19961, 1, 60887, 1279, 1, 269, 6991, 881, 4919, 1, 21661, 1, 1693, 1, 67079, 1, 1, 1, 1, 1453, 1049, 1, 23789, 1, 1, 1, 4327, 1, 24889, 9403, 25261, 3181, 76907, 1, 1, 1, 26393, 3323, 1, 3371, 1, 1, 3061, 1, 1061, 3517, 977, 823, 28729, 1, 87383, 1, 1, 11149, 809, 3767, 91019, 1, 317, 1451, 1, 1307, 94727, 1, 1, 3019, 32413, 2039, 98507, 1, 11087, 12553, 1, 1, 102359, 1, 1, 1, 1, 1, 4621, 1, 35869, 1, 36313, 4567, 1, 1, 1, 7019, 2897, 1, 3943, 4793, 2269, 14551, 4337, 1, 2521, 1, 1, 15073, 40429, 1, 4231, 857, 4597, 1, 41849, 5261, 5521, 1, 1, 1009, 14431, 907, 10103, 5503, 44269, 16693, 2633, 1, 991, 1, 1, 1327, 2011, 5813, 1, 1, 1, 1, 15923, 1, 144839, 6067, 827, 1, 3793, 1549, 1801, 2087, 1291, 18979, 50873, 1, 1, 3229, 51929, 1, 1, 1, 919, 3329, 1, 1, 2351, 6793, 163847, 2287, 1, 5197, 1, 3499, 12983, 1, 56813, 1, 1471, 1201, 173783, 1, 2543, 22039, 59053, 7417, 178859, 1, 20063, 1, 60761, 1, 184007, 7703, 1, 1, 1, 1, 11131, 1, 1, 1, 1367, 2017, 1151, 1, 1283, 1, 66029, 8291, 1459, 1, 1, 487, 7537, 1, 205319, 1, 2381, 3251, 69661, 4373, 210827, 1, 7877, 26701, 5501, 1, 1, 1, 1, 1, 1439, 1, 222059, 1, 74653, 14057, 75289, 1, 13399, 1, 25523, 1109, 77213, 2423, 1433, 1, 78509, 1, 26387, 1, 1, 5009, 80473, 1, 1, 1, 1, 1, 27487, 3881, 1, 10433, 4261, 1, 4969, 7951, 9461, 1, 6959, 10771, 86509, 32569, 1, 5471, 9091, 1, 1, 33343, 89261, 1, 20759, 1, 1, 1, 1, 3821, 1, 11551, 92761, 1, 1, 1, 4217, 1, 1, 1553, 1427, 2999, 1, 6043, 1, 36529, 1, 1, 2711, 1, 1, 9337, 99961, 12541, 1123, 4211, 33811, 1193, 1231, 1, 5233, 12911, 4507, 3001, 1289, 1, 1, 1, 105913, 1733, 106669, 13381, 1907, 1, 4007, 20357, 1, 1, 3259, 13763, 1, 20789, 37087, 1163, 1, 1, 3049, 42451, 3917, 1, 343127, 1, 1669, 2549, 2467, 14543, 350219, 7321, 9041, 1, 39443, 1, 1, 1, 119929, 1, 1, 1, 1, 5081, 2399, 3541, 1559, 7723, 371927, 1, 124793, 1619, 1, 1, 379307, 1, 127261, 647, 1, 16063, 1, 1, 1, 24407, 130589, 1, 8389, 16481, 4561, 2927, 44371, 1, 1, 1, 1, 1, 135661, 17011, 24091, 1, 1579, 12919, 1, 17333, 32099, 1, 8233, 6581, 1, 1, 5381, 1, 142573, 53629, 3877, 1, 432983, 1, 1, 1, 146093, 1409, 440939, 1, 2207, 27809, 16529, 6217, 6701, 1, 1, 1, 1, 1, 35159, 6367, 17029, 1, 6703, 1, 27367, 9721, 3319, 4513, 1, 1, 1, 1, 158749, 1, 159673, 1, 4967, 2237, 2341, 15187, 12497, 1, 16903, 20483, 12641, 2687, 1, 1, 498647, 5209, 9833, 1699, 168109, 1621, 3037, 1, 56671, 2459, 1, 739, 515783, 1, 2083, 32507, 1, 1, 40343, 1, 7643, 66103, 13597, 1, 14411, 1, 6619, 1, 179693, 1, 542027, 1, 3079, 17077, 1, 1, 1, 23017, 184633, 4339, 1, 11633, 559883, 1, 1, 70549, 188633, 11821, 1, 2971, 190649, 1, 2203, 1, 5303, 6037, 1777, 2801, 194713, 1, 7433, 1, 65587, 787, 2383, 6197, 25933, 24917, 199853, 2591, 1, 1, 12889, 12653, 1, 1, 204013, 1, 36187, 4283, 22901, 1, 9007, 1997, 1, 1, 3547, 1, 70111, 1, 634187, 1, 212461, 79873, 3187, 1, 49523, 1, 1, 1, 16673, 1, 1, 1, 1, 1789, 73331, 1, 663239, 2131, 1, 41759, 1, 1, 18191, 9371, 1, 84751, 226553, 1, 682967, 839, 17597, 1, 25541, 9601, 1, 1, 10091, 1, 2309, 29221, 702983, 9787, 26161, 1, 236573, 14821, 41947, 1, 238829, 1, 79987, 5011, 723287, 1, 14249, 1, 1, 30493, 12433, 1, 6299, 1, 246809, 1, 1, 1, 10831, 46817, 83423, 1, 754283, 1, 252589, 1, 5399, 1987, 26371, 5323, 85363, 1, 1, 1, 2593, 16189, 2917, 12197, 1, 10891, 1, 1, 2713, 1, 264349, 1, 796619, 1, 1, 5897, 267929, 1, 807383, 8429, 270329, 101599, 90511, 1, 818219, 4271, 1, 51479, 275161, 34471, 1, 3847, 5443, 52163, 278813, 1, 5351, 35081, 2053, 1, 1, 1, 851159, 1, 3607, 107089, 1, 35851, 862283, 1, 96223, 1, 1, 1, 13037, 36473, 1, 1, 1, 6131, 2791, 36943, 2621, 111301, 1, 1, 52711, 1, 33329, 1, 1, 1, 24527, 9473, 1, 57077, 4421, 1, 1, 38371, 307609, 1993, 23761, 1, 5927, 1, 1, 117043, 1, 1, 942167, 1, 13711, 1, 1, 1, 6317, 19913, 1, 1, 1, 40153, 965639, 1, 8287, 1, 1, 20323, 4423, 1, 1, 122929, 36497, 6857, 1, 1, 2417, 1, 332461, 41641, 1001387, 1, 1, 1, 7159, 1, 2081, 1, 339161, 63719, 8731, 1, 1025579, 1, 1, 128959, 1, 10789, 45121, 1, 115763, 130489, 20509, 3359, 1, 1, 9497, 2539, 1, 4909, 1062407, 2609, 355513, 1, 356893, 22349, 2851, 14957, 1, 7949,

6. Sequence of the polynom (only primes)

853, 3, 227, 37, 167, 17, 313, 13, 29, 23, 173, 79, 83, 983, 409, 67, 47, 223, 761, 101, 151, 113, 953, 3467, 97, 89, 193, 59, 619, 1709, 5483, 1949, 691, 6599, 283, 137, 449, 107, 599, 911, 1051, 109, 1213, 1103, 3613, 3769, 11783, 4253, 271, 13259, 563, 353, 1753, 157, 5113, 1951, 673, 16427, 5849, 743, 18119, 1187, 2143, 337, 6829, 541, 587, 191, 2833, 163, 971, 23627, 499, 8093, 769, 883, 8761, 569, 1627, 389, 9689, 613, 10169, 439, 10909, 2069, 11161, 1489, 1297, 2213, 11933, 36587, 733, 4723, 4243, 661, 821, 1021, 797, 3191, 4703, 937, 14969, 5087, 2029, 557, 1019, 49367, 6343, 2153, 3067, 1361, 3347, 757, 54983, 2311, 1097, 3527, 18973, 57899, 811, 727, 571, 19961, 60887, 1279, 269, 6991, 881, 4919, 21661, 1693, 67079, 1453, 1049, 23789, 4327, 24889, 9403, 25261, 3181, 76907, 26393, 3323, 3371, 3061, 1061, 3517, 977, 823, 28729, 87383, 11149, 809, 3767, 91019, 317, 1451, 1307, 94727, 3019, 32413, 2039, 98507, 11087, 12553, 102359, 4621, 35869, 36313, 4567, 7019, 2897, 3943, 4793, 2269, 14551, 4337, 2521, 15073, 40429, 4231, 857, 4597, 41849, 5261, 5521, 1009, 14431, 907, 10103, 5503, 44269, 16693, 2633, 991, 1327, 2011, 5813, 15923, 144839, 6067, 827, 3793, 1549, 1801, 2087, 1291, 18979, 50873, 3229, 51929, 919, 3329, 2351, 6793, 163847, 2287, 5197, 3499, 12983, 56813, 1471, 1201, 173783, 2543, 22039, 59053, 7417, 178859, 20063, 60761, 184007, 7703, 11131, 1367, 2017, 1151, 1283, 66029, 8291, 1459, 487, 7537, 205319, 2381, 3251, 69661, 4373, 210827, 7877, 26701, 5501, 1439, 222059, 74653, 14057, 75289, 13399, 25523, 1109, 77213, 2423, 1433, 78509, 26387, 5009, 80473, 27487, 3881, 10433, 4261, 4969, 7951, 9461, 6959, 10771, 86509, 32569, 5471, 9091, 33343, 89261, 20759, 3821, 11551, 92761, 4217, 1553, 1427, 2999, 6043, 36529, 2711, 9337, 99961, 12541, 1123, 4211, 33811, 1193, 1231, 5233, 12911, 4507, 3001, 1289, 105913, 1733, 106669, 13381, 1907, 4007, 20357, 3259, 13763, 20789, 37087, 1163, 3049, 42451, 3917, 343127, 1669, 2549, 2467, 14543, 350219, 7321, 9041, 39443, 119929, 5081, 2399, 3541, 1559, 7723, 371927, 124793, 1619, 379307, 127261, 647, 16063, 24407, 130589, 8389, 16481, 4561, 2927, 44371, 135661, 17011, 24091, 1579, 12919, 17333, 32099, 8233, 6581, 5381, 142573, 53629, 3877, 432983, 146093, 1409, 440939, 2207, 27809, 16529, 6217, 6701, 35159, 6367, 17029, 6703, 27367, 9721, 3319, 4513, 158749, 159673, 4967, 2237, 2341, 15187, 12497, 16903, 20483, 12641, 2687, 498647, 5209, 9833, 1699, 168109, 1621, 3037, 56671, 2459, 739, 515783, 2083, 32507, 40343, 7643, 66103, 13597, 14411, 6619, 179693, 542027, 3079, 17077, 23017, 184633, 4339, 11633, 559883, 70549, 188633, 11821, 2971, 190649, 2203, 5303, 6037, 1777, 2801, 194713, 7433, 65587, 787, 2383, 6197, 25933, 24917, 199853, 2591, 12889, 12653, 204013, 36187, 4283, 22901, 9007, 1997, 3547, 70111, 634187, 212461, 79873, 3187, 49523, 16673, 1789, 73331, 663239, 2131, 41759, 18191, 9371, 84751, 226553, 682967, 839, 17597, 25541, 9601, 10091, 2309, 29221, 702983, 9787, 26161, 236573, 14821, 41947, 238829, 79987, 5011, 723287, 14249, 30493, 12433, 6299, 246809, 10831, 46817, 83423, 754283, 252589, 5399, 1987, 26371, 5323, 85363, 2593, 16189, 2917, 12197, 10891, 2713, 264349, 796619, 5897, 267929, 807383, 8429, 270329, 101599, 90511, 818219, 4271, 51479, 275161, 34471, 3847, 5443, 52163, 278813, 5351, 35081, 2053, 851159, 3607, 107089, 35851, 862283, 96223, 13037, 36473, 6131, 2791, 36943, 2621, 111301, 52711, 33329, 24527, 9473, 57077, 4421, 38371, 307609, 1993, 23761, 5927, 117043, 942167, 13711, 6317, 19913, 40153, 965639, 8287, 20323, 4423, 122929, 36497, 6857, 2417, 332461, 41641, 1001387, 7159, 2081, 339161, 63719, 8731, 1025579, 128959, 10789, 45121, 115763, 130489, 20509, 3359, 9497, 2539, 4909, 1062407, 2609, 355513, 356893, 22349, 2851, 14957, 7949,

7. Distribution of the primes

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

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 1 4 1.25 0.25 1
3 8 8 2 6 1 0.25 0.75
4 16 13 2 11 0.8125 0.125 0.6875
5 32 23 3 20 0.71875 0.09375 0.625
6 64 41 6 35 0.640625 0.09375 0.546875
7 128 77 11 66 0.6015625 0.0859375 0.515625
8 256 151 18 133 0.58984375 0.0703125 0.51953125
9 512 300 31 269 0.5859375 0.06054688 0.52539063
10 1024 604 58 546 0.58984375 0.05664063 0.53320313
11 2048 1229 107 1122 0.60009766 0.05224609 0.54785156
12 4096 2497 198 2299 0.60961914 0.04833984 0.5612793
13 8192 5051 363 4688 0.61657715 0.04431152 0.57226563
14 16384 10183 676 9507 0.621521 0.04125977 0.58026123
15 32768 20543 1268 19275 0.62692261 0.03869629 0.58822632
16 65536 41311 2335 38976 0.63035583 0.03562927 0.59472656
17 131072 83074 4336 78738 0.63380432 0.03308105 0.60072327
18 262144 167117 8093 159024 0.63750076 0.03087234 0.60662842
19 524288 335771 15255 320516 0.64043236 0.0290966 0.61133575
20 1048576 674829 28818 646011 0.64356709 0.02748299 0.6160841
21 2097152 1354907 54581 1300326 0.64607 0.02602625 0.62004375
22 4194304 2719017 103996 2615021 0.64826417 0.02479458 0.62346959
23 8388608 5455660 198234 5257426 0.65036535 0.02363133 0.62673402
24 16777216 10942051 377870 10564181 0.65219706 0.02252281 0.62967426


8. Check for existing Integer Sequences by OEIS

Found in Database : 853, 3, 227, 37, 167, 17, 313, 1, 13, 1, 29, 1, 23, 1, 173, 79, 83, 1, 983, 1,
Found in Database : 853, 3, 227, 37, 167, 17, 313, 13, 29, 23, 173, 79, 83, 983, 409, 67, 47, 223, 761, 101, 151, 113, 953, 3467, 97,
Found in Database : 3, 13, 17, 23, 29, 37, 47, 59, 67, 79, 83, 89, 97, 101, 107, 109, 113, 137,