Inhaltsverzeichnis

Development of
Algorithmic Constructions

22:09:14
Deutsch
28.Mar 2024

Polynom = x^2-172x+1163

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) = 1163 = 1163
f(1) = 31 = 31
f(2) = 823 = 823
f(3) = 41 = 41
f(4) = 491 = 491
f(5) = 41 = 41
f(6) = 167 = 167
f(7) = 1 = 1
f(8) = 149 = 149
f(9) = 19 = 19
f(10) = 457 = 457
f(11) = 19 = 19
f(12) = 757 = 757
f(13) = 113 = 113
f(14) = 1049 = 1049
f(15) = 149 = 149
f(16) = 1333 = 31*43
f(17) = 23 = 23
f(18) = 1609 = 1609
f(19) = 109 = 109
f(20) = 1877 = 1877
f(21) = 251 = 251
f(22) = 2137 = 2137
f(23) = 283 = 283
f(24) = 2389 = 2389
f(25) = 157 = 157
f(26) = 2633 = 2633
f(27) = 43 = 43
f(28) = 2869 = 19*151
f(29) = 373 = 373
f(30) = 3097 = 19*163
f(31) = 401 = 401
f(32) = 3317 = 31*107
f(33) = 107 = 107
f(34) = 3529 = 3529
f(35) = 227 = 227
f(36) = 3733 = 3733
f(37) = 479 = 479
f(38) = 3929 = 3929
f(39) = 503 = 503
f(40) = 4117 = 23*179
f(41) = 263 = 263
f(42) = 4297 = 4297
f(43) = 137 = 137
f(44) = 4469 = 41*109
f(45) = 569 = 569
f(46) = 4633 = 41*113
f(47) = 589 = 19*31
f(48) = 4789 = 4789
f(49) = 19 = 19
f(50) = 4937 = 4937
f(51) = 313 = 313
f(52) = 5077 = 5077
f(53) = 643 = 643
f(54) = 5209 = 5209
f(55) = 659 = 659
f(56) = 5333 = 5333
f(57) = 337 = 337
f(58) = 5449 = 5449
f(59) = 43 = 43
f(60) = 5557 = 5557
f(61) = 701 = 701
f(62) = 5657 = 5657
f(63) = 713 = 23*31
f(64) = 5749 = 5749
f(65) = 181 = 181
f(66) = 5833 = 19*307
f(67) = 367 = 367
f(68) = 5909 = 19*311
f(69) = 743 = 743
f(70) = 5977 = 43*139
f(71) = 751 = 751
f(72) = 6037 = 6037
f(73) = 379 = 379
f(74) = 6089 = 6089
f(75) = 191 = 191
f(76) = 6133 = 6133
f(77) = 769 = 769
f(78) = 6169 = 31*199
f(79) = 773 = 773
f(80) = 6197 = 6197
f(81) = 97 = 97
f(82) = 6217 = 6217
f(83) = 389 = 389
f(84) = 6229 = 6229
f(85) = 779 = 19*41
f(86) = 6233 = 23*271
f(87) = 779 = 19*41
f(88) = 6229 = 6229
f(89) = 389 = 389
f(90) = 6217 = 6217
f(91) = 97 = 97
f(92) = 6197 = 6197
f(93) = 773 = 773
f(94) = 6169 = 31*199
f(95) = 769 = 769
f(96) = 6133 = 6133
f(97) = 191 = 191
f(98) = 6089 = 6089
f(99) = 379 = 379
f(100) = 6037 = 6037

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-172x+1163

f(0)=1163
f(1)=31
f(2)=823
f(3)=41
f(4)=491
f(5)=1
f(6)=167
f(7)=1
f(8)=149
f(9)=19
f(10)=457
f(11)=1
f(12)=757
f(13)=113
f(14)=1049
f(15)=1
f(16)=43
f(17)=23
f(18)=1609
f(19)=109
f(20)=1877
f(21)=251
f(22)=2137
f(23)=283
f(24)=2389
f(25)=157
f(26)=2633
f(27)=1
f(28)=151
f(29)=373
f(30)=163
f(31)=401
f(32)=107
f(33)=1
f(34)=3529
f(35)=227
f(36)=3733
f(37)=479
f(38)=3929
f(39)=503
f(40)=179
f(41)=263
f(42)=4297
f(43)=137
f(44)=1
f(45)=569
f(46)=1
f(47)=1
f(48)=4789
f(49)=1
f(50)=4937
f(51)=313
f(52)=5077
f(53)=643
f(54)=5209
f(55)=659
f(56)=5333
f(57)=337
f(58)=5449
f(59)=1
f(60)=5557
f(61)=701
f(62)=5657
f(63)=1
f(64)=5749
f(65)=181
f(66)=307
f(67)=367
f(68)=311
f(69)=743
f(70)=139
f(71)=751
f(72)=6037
f(73)=379
f(74)=6089
f(75)=191
f(76)=6133
f(77)=769
f(78)=199
f(79)=773
f(80)=6197
f(81)=97
f(82)=6217
f(83)=389
f(84)=6229
f(85)=1
f(86)=271
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2-172x+1163 could be written as f(y)= y^2-6233 with x=y+86

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-86
f'(x)>2x-173 with x > 79

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

1163, 31, 823, 41, 491, 1, 167, 1, 149, 19, 457, 1, 757, 113, 1049, 1, 43, 23, 1609, 109, 1877, 251, 2137, 283, 2389, 157, 2633, 1, 151, 373, 163, 401, 107, 1, 3529, 227, 3733, 479, 3929, 503, 179, 263, 4297, 137, 1, 569, 1, 1, 4789, 1, 4937, 313, 5077, 643, 5209, 659, 5333, 337, 5449, 1, 5557, 701, 5657, 1, 5749, 181, 307, 367, 311, 743, 139, 751, 6037, 379, 6089, 191, 6133, 769, 199, 773, 6197, 97, 6217, 389, 6229, 1, 271, 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, 1511, 211, 1867, 1, 1, 1, 1, 349, 1, 397, 3371, 223, 3767, 1, 1, 547, 4583, 599, 5003, 1, 5431, 353, 5867, 761, 6311, 1, 6763, 1, 233, 1, 7691, 991, 8167, 1051, 1, 1, 1, 587, 9643, 1237, 10151, 1301, 10667, 683, 1, 1, 617, 1499, 12263, 1567, 557, 409, 13367, 853, 13931, 1777, 14503, 1, 15083, 1, 15671, 499, 16267, 1, 16871, 1, 17483, 1, 421, 1151, 18731, 2381, 1, 1, 20011, 1, 20663, 1, 21323, 2707, 21991, 2791, 1193, 719, 1229, 1481, 24043, 3049, 1, 3137, 821, 1613, 1, 829, 26891, 3407, 1201, 3499, 1, 449, 677, 1, 29867, 1, 30631, 3877, 1013, 1987, 32183, 509, 32971, 1, 33767, 4271, 1, 1093, 863, 2237, 883, 1, 1949, 1, 1993, 2393, 38711, 1223, 39563, 4999, 40423, 5107, 1, 1, 1, 2663, 43051, 5437, 43943, 1, 44843, 1, 45751, 1, 2029, 1, 47591, 6007, 48523, 1531, 49463, 3121, 50411, 6361, 1657, 6481, 1217, 3301, 1, 1, 2857, 1, 2909, 6971, 56267, 887, 57271, 1, 1, 7349, 1913, 7477, 60331, 3803, 563, 967, 1, 7867, 63463, 1, 571, 1, 613, 4133, 1, 1, 67751, 8537, 1601, 4337, 3041, 2203, 1, 8951, 72167, 9091, 73291, 577, 3917, 1, 1, 1, 1871, 9661, 77867, 4903, 79031, 1, 1, 10099, 839, 10247, 82571, 1, 1, 5273, 2741, 1, 86183, 1, 87403, 5501, 1, 2789, 89867, 11311, 1, 11467, 92363, 1453, 1, 1, 3061, 11941, 96167, 12101, 1, 6131, 5197, 1553, 100043, 1, 2357, 1, 102667, 3229, 103991, 1, 105323, 13249, 106663, 13417, 108011, 6793, 109367, 1, 110731, 733, 112103, 1, 1, 1, 1, 1, 1, 14621, 117671, 14797, 119083, 7487, 120503, 947, 121931, 15331, 1, 15511, 6569, 3923, 4073, 7937, 1, 16057, 1, 1, 3187, 1, 132151, 4153, 1249, 1, 907, 16987, 136651, 1, 4457, 1, 857, 1, 141223, 17749, 1, 8971, 144311, 2267, 1, 797, 1, 1, 1367, 1, 150583, 9461, 8009, 19121, 8093, 1, 155371, 1, 877, 4931, 1, 19927, 160231, 1, 1031, 1, 1447, 10271, 1, 20749, 166823, 1103, 168491, 1, 170167, 1, 171851, 21587, 173543, 21799, 5653, 5503, 176951, 11113, 1, 22441, 180391, 1, 182123, 11437, 9677, 1, 9769, 23311, 187367, 23531, 6101, 2969, 1, 11987, 4481, 24197, 194471, 24421, 4787, 12323, 4831, 3109, 1459, 1321, 1, 1, 203531, 6389, 8929, 12893, 1, 26017, 209063, 26249, 210923, 13241, 212791, 6679, 214667, 26951, 216551, 1, 11497, 1, 11597, 13831, 2039, 27901, 2311, 1, 2113, 1, 228023, 1789, 229963, 28867, 7481, 1, 2411, 1, 2087, 1, 1, 1571, 239783, 30097, 241771, 15173, 5669, 7649, 245771, 1, 7993, 1, 10861, 3919, 251831, 15803, 253867, 1, 13469, 32117, 13577, 16187, 260023, 4079, 1759, 1061, 264167, 33151, 1471, 8353, 268343, 1, 270443, 33937, 1, 1487, 274667, 1, 1, 1, 6803, 1129, 281063, 35267, 283211, 2221, 2053, 17903, 1, 1, 1373, 1, 1933, 18311, 1, 1153, 1, 37171, 1, 37447, 300683, 9431, 302903, 19001, 305131, 38281, 307367, 38561, 1621, 19421, 1723, 9781, 10133, 1, 316391, 2089, 1429, 1, 2309, 1, 323243, 1, 325543, 1, 327851, 20563, 330167, 1, 1427, 1, 1753, 41999, 7841, 1, 1, 1, 1, 1, 344231, 43177, 1, 21737, 2141, 1, 15277, 44071, 353767, 44371, 356171, 1, 1, 1, 361003, 2383, 363431, 2399, 1, 22943, 1, 2887, 9043, 46499, 9103, 46807, 8737, 11779, 378167, 1, 380651, 47737, 383143, 48049, 20297, 24181, 1, 1, 1721, 48991, 393191, 49307, 1289, 6203, 1, 24971, 3547, 50261, 1297, 50581, 2963, 1, 17761, 1, 411083, 2713, 1, 51871, 1, 13049, 418871, 26261, 421483, 1, 424103, 1, 426731, 1, 429367, 1, 2861, 54167, 22877, 54499, 23017, 1, 439991, 27583, 2473, 55501, 10357, 55837, 1, 28087, 1, 1, 453451, 1, 456167, 57191, 458891, 1, 4759, 1523, 1, 58217, 1861, 1, 1, 29453, 472631, 14813, 475403, 1, 1, 1, 11731, 7537, 483767, 30323, 25609, 1, 1, 1979, 1, 30851, 3037, 7757, 497867, 1, 1, 2729, 503563, 1, 506423, 31741, 4507, 63841, 512167, 1, 2441, 1699, 3299, 16231, 1, 65287, 3823, 65651, 526667, 2063, 2333, 33191, 532523, 66749, 1, 1637, 538411, 1, 28493, 4241, 28649, 68227, 2081, 1, 550283, 1, 3313, 34673, 556267, 1, 18041, 1, 562283, 1, 565303, 17713, 13217, 1, 1, 3769, 3209, 8999, 577463, 36187, 1, 2347, 2617, 73141, 586667, 1, 589751, 9239, 592843, 1, 595943, 74687, 1, 1, 1, 1, 26317, 2447, 608423, 76249, 2161, 38321, 3089, 19259, 14369, 77431, 621031, 1, 624203, 4889, 627383, 2069, 20341, 4159, 633767, 1847, 5953, 1, 3217, 1, 643403, 80627, 646631, 81031, 649867, 20359, 653111, 1, 1, 1, 1, 82657, 1, 1, 666167, 1, 669451, 1, 672743, 84299, 676043, 10589, 29537, 1, 6263, 1, 685991, 1999, 2621, 2273, 692663, 1, 1, 87211, 699367, 87631, 702731, 22013, 16421, 1, 4519, 88897, 4721, 1, 5153, 1951, 719671, 22543, 2003, 90599, 38237, 1, 729931, 1, 1, 45943, 17971, 92317, 6551, 1, 1, 46591, 7703, 5851, 750667, 1, 1, 4973, 32941, 1, 1, 47681, 7883, 95801, 768167, 1, 771691, 48341, 4283, 24281, 778763, 2269, 782311, 98011, 1, 1, 41549, 49451, 41737, 99349, 796583, 4339, 800171, 50123, 1, 1, 807371, 2467, 2591, 101599, 814603, 1, 818231, 1, 7681, 5419, 2917, 5443,

6. Sequence of the polynom (only primes)

1163, 31, 823, 41, 491, 167, 149, 19, 457, 757, 113, 1049, 43, 23, 1609, 109, 1877, 251, 2137, 283, 2389, 157, 2633, 151, 373, 163, 401, 107, 3529, 227, 3733, 479, 3929, 503, 179, 263, 4297, 137, 569, 4789, 4937, 313, 5077, 643, 5209, 659, 5333, 337, 5449, 5557, 701, 5657, 5749, 181, 307, 367, 311, 743, 139, 751, 6037, 379, 6089, 191, 6133, 769, 199, 773, 6197, 97, 6217, 389, 6229, 271, 1511, 211, 1867, 349, 397, 3371, 223, 3767, 547, 4583, 599, 5003, 5431, 353, 5867, 761, 6311, 6763, 233, 7691, 991, 8167, 1051, 587, 9643, 1237, 10151, 1301, 10667, 683, 617, 1499, 12263, 1567, 557, 409, 13367, 853, 13931, 1777, 14503, 15083, 15671, 499, 16267, 16871, 17483, 421, 1151, 18731, 2381, 20011, 20663, 21323, 2707, 21991, 2791, 1193, 719, 1229, 1481, 24043, 3049, 3137, 821, 1613, 829, 26891, 3407, 1201, 3499, 449, 677, 29867, 30631, 3877, 1013, 1987, 32183, 509, 32971, 33767, 4271, 1093, 863, 2237, 883, 1949, 1993, 2393, 38711, 1223, 39563, 4999, 40423, 5107, 2663, 43051, 5437, 43943, 44843, 45751, 2029, 47591, 6007, 48523, 1531, 49463, 3121, 50411, 6361, 1657, 6481, 1217, 3301, 2857, 2909, 6971, 56267, 887, 57271, 7349, 1913, 7477, 60331, 3803, 563, 967, 7867, 63463, 571, 613, 4133, 67751, 8537, 1601, 4337, 3041, 2203, 8951, 72167, 9091, 73291, 577, 3917, 1871, 9661, 77867, 4903, 79031, 10099, 839, 10247, 82571, 5273, 2741, 86183, 87403, 5501, 2789, 89867, 11311, 11467, 92363, 1453, 3061, 11941, 96167, 12101, 6131, 5197, 1553, 100043, 2357, 102667, 3229, 103991, 105323, 13249, 106663, 13417, 108011, 6793, 109367, 110731, 733, 112103, 14621, 117671, 14797, 119083, 7487, 120503, 947, 121931, 15331, 15511, 6569, 3923, 4073, 7937, 16057, 3187, 132151, 4153, 1249, 907, 16987, 136651, 4457, 857, 141223, 17749, 8971, 144311, 2267, 797, 1367, 150583, 9461, 8009, 19121, 8093, 155371, 877, 4931, 19927, 160231, 1031, 1447, 10271, 20749, 166823, 1103, 168491, 170167, 171851, 21587, 173543, 21799, 5653, 5503, 176951, 11113, 22441, 180391, 182123, 11437, 9677, 9769, 23311, 187367, 23531, 6101, 2969, 11987, 4481, 24197, 194471, 24421, 4787, 12323, 4831, 3109, 1459, 1321, 203531, 6389, 8929, 12893, 26017, 209063, 26249, 210923, 13241, 212791, 6679, 214667, 26951, 216551, 11497, 11597, 13831, 2039, 27901, 2311, 2113, 228023, 1789, 229963, 28867, 7481, 2411, 2087, 1571, 239783, 30097, 241771, 15173, 5669, 7649, 245771, 7993, 10861, 3919, 251831, 15803, 253867, 13469, 32117, 13577, 16187, 260023, 4079, 1759, 1061, 264167, 33151, 1471, 8353, 268343, 270443, 33937, 1487, 274667, 6803, 1129, 281063, 35267, 283211, 2221, 2053, 17903, 1373, 1933, 18311, 1153, 37171, 37447, 300683, 9431, 302903, 19001, 305131, 38281, 307367, 38561, 1621, 19421, 1723, 9781, 10133, 316391, 2089, 1429, 2309, 323243, 325543, 327851, 20563, 330167, 1427, 1753, 41999, 7841, 344231, 43177, 21737, 2141, 15277, 44071, 353767, 44371, 356171, 361003, 2383, 363431, 2399, 22943, 2887, 9043, 46499, 9103, 46807, 8737, 11779, 378167, 380651, 47737, 383143, 48049, 20297, 24181, 1721, 48991, 393191, 49307, 1289, 6203, 24971, 3547, 50261, 1297, 50581, 2963, 17761, 411083, 2713, 51871, 13049, 418871, 26261, 421483, 424103, 426731, 429367, 2861, 54167, 22877, 54499, 23017, 439991, 27583, 2473, 55501, 10357, 55837, 28087, 453451, 456167, 57191, 458891, 4759, 1523, 58217, 1861, 29453, 472631, 14813, 475403, 11731, 7537, 483767, 30323, 25609, 1979, 30851, 3037, 7757, 497867, 2729, 503563, 506423, 31741, 4507, 63841, 512167, 2441, 1699, 3299, 16231, 65287, 3823, 65651, 526667, 2063, 2333, 33191, 532523, 66749, 1637, 538411, 28493, 4241, 28649, 68227, 2081, 550283, 3313, 34673, 556267, 18041, 562283, 565303, 17713, 13217, 3769, 3209, 8999, 577463, 36187, 2347, 2617, 73141, 586667, 589751, 9239, 592843, 595943, 74687, 26317, 2447, 608423, 76249, 2161, 38321, 3089, 19259, 14369, 77431, 621031, 624203, 4889, 627383, 2069, 20341, 4159, 633767, 1847, 5953, 3217, 643403, 80627, 646631, 81031, 649867, 20359, 653111, 82657, 666167, 669451, 672743, 84299, 676043, 10589, 29537, 6263, 685991, 1999, 2621, 2273, 692663, 87211, 699367, 87631, 702731, 22013, 16421, 4519, 88897, 4721, 5153, 1951, 719671, 22543, 2003, 90599, 38237, 729931, 45943, 17971, 92317, 6551, 46591, 7703, 5851, 750667, 4973, 32941, 47681, 7883, 95801, 768167, 771691, 48341, 4283, 24281, 778763, 2269, 782311, 98011, 41549, 49451, 41737, 99349, 796583, 4339, 800171, 50123, 807371, 2467, 2591, 101599, 814603, 818231, 7681, 5419, 2917, 5443,

7. Distribution of the primes

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

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 : 1163, 31, 823, 41, 491, 1, 167, 1, 149, 19, 457, 1, 757, 113, 1049, 1, 43, 23, 1609, 109,
Found in Database : 1163, 31, 823, 41, 491, 167, 149, 19, 457, 757, 113, 1049, 43, 23, 1609, 109, 1877, 251, 2137, 283, 2389, 157, 2633, 151, 373, 163, 401, 107, 3529, 227, 3733, 479, 3929, 503,
Found in Database : 19, 23, 31, 41, 43, 97, 107, 109, 113, 137, 139, 149,