Inhaltsverzeichnis

Development of
Algorithmic Constructions

06:23:30
Deutsch
29.Mar 2024

Polynom = x^2-196x+4547

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) = 4547 = 4547
f(1) = 17 = 17
f(2) = 4159 = 4159
f(3) = 31 = 31
f(4) = 3779 = 3779
f(5) = 449 = 449
f(6) = 3407 = 3407
f(7) = 403 = 13*31
f(8) = 3043 = 17*179
f(9) = 179 = 179
f(10) = 2687 = 2687
f(11) = 157 = 157
f(12) = 2339 = 2339
f(13) = 271 = 271
f(14) = 1999 = 1999
f(15) = 229 = 229
f(16) = 1667 = 1667
f(17) = 47 = 47
f(18) = 1343 = 17*79
f(19) = 37 = 37
f(20) = 1027 = 13*79
f(21) = 109 = 109
f(22) = 719 = 719
f(23) = 71 = 71
f(24) = 419 = 419
f(25) = 17 = 17
f(26) = 127 = 127
f(27) = 1 = 1
f(28) = 157 = 157
f(29) = 37 = 37
f(30) = 433 = 433
f(31) = 71 = 71
f(32) = 701 = 701
f(33) = 13 = 13
f(34) = 961 = 31*31
f(35) = 17 = 17
f(36) = 1213 = 1213
f(37) = 167 = 167
f(38) = 1457 = 31*47
f(39) = 197 = 197
f(40) = 1693 = 1693
f(41) = 113 = 113
f(42) = 1921 = 17*113
f(43) = 127 = 127
f(44) = 2141 = 2141
f(45) = 281 = 281
f(46) = 2353 = 13*181
f(47) = 307 = 307
f(48) = 2557 = 2557
f(49) = 83 = 83
f(50) = 2753 = 2753
f(51) = 89 = 89
f(52) = 2941 = 17*173
f(53) = 379 = 379
f(54) = 3121 = 3121
f(55) = 401 = 401
f(56) = 3293 = 37*89
f(57) = 211 = 211
f(58) = 3457 = 3457
f(59) = 221 = 13*17
f(60) = 3613 = 3613
f(61) = 461 = 461
f(62) = 3761 = 3761
f(63) = 479 = 479
f(64) = 3901 = 47*83
f(65) = 31 = 31
f(66) = 4033 = 37*109
f(67) = 1 = 1
f(68) = 4157 = 4157
f(69) = 527 = 17*31
f(70) = 4273 = 4273
f(71) = 541 = 541
f(72) = 4381 = 13*337
f(73) = 277 = 277
f(74) = 4481 = 4481
f(75) = 283 = 283
f(76) = 4573 = 17*269
f(77) = 577 = 577
f(78) = 4657 = 4657
f(79) = 587 = 587
f(80) = 4733 = 4733
f(81) = 149 = 149
f(82) = 4801 = 4801
f(83) = 151 = 151
f(84) = 4861 = 4861
f(85) = 611 = 13*47
f(86) = 4913 = 17*17*17
f(87) = 617 = 617
f(88) = 4957 = 4957
f(89) = 311 = 311
f(90) = 4993 = 4993
f(91) = 313 = 313
f(92) = 5021 = 5021
f(93) = 629 = 17*37
f(94) = 5041 = 71*71
f(95) = 631 = 631
f(96) = 5053 = 31*163
f(97) = 79 = 79
f(98) = 5057 = 13*389
f(99) = 79 = 79
f(100) = 5053 = 31*163

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-196x+4547

f(0)=4547
f(1)=17
f(2)=4159
f(3)=31
f(4)=3779
f(5)=449
f(6)=3407
f(7)=13
f(8)=179
f(9)=1
f(10)=2687
f(11)=157
f(12)=2339
f(13)=271
f(14)=1999
f(15)=229
f(16)=1667
f(17)=47
f(18)=79
f(19)=37
f(20)=1
f(21)=109
f(22)=719
f(23)=71
f(24)=419
f(25)=1
f(26)=127
f(27)=1
f(28)=1
f(29)=1
f(30)=433
f(31)=1
f(32)=701
f(33)=1
f(34)=1
f(35)=1
f(36)=1213
f(37)=167
f(38)=1
f(39)=197
f(40)=1693
f(41)=113
f(42)=1
f(43)=1
f(44)=2141
f(45)=281
f(46)=181
f(47)=307
f(48)=2557
f(49)=83
f(50)=2753
f(51)=89
f(52)=173
f(53)=379
f(54)=3121
f(55)=401
f(56)=1
f(57)=211
f(58)=3457
f(59)=1
f(60)=3613
f(61)=461
f(62)=3761
f(63)=479
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=4157
f(69)=1
f(70)=4273
f(71)=541
f(72)=337
f(73)=277
f(74)=4481
f(75)=283
f(76)=269
f(77)=577
f(78)=4657
f(79)=587
f(80)=4733
f(81)=149
f(82)=4801
f(83)=151
f(84)=4861
f(85)=1
f(86)=1
f(87)=617
f(88)=4957
f(89)=311
f(90)=4993
f(91)=313
f(92)=5021
f(93)=1
f(94)=1
f(95)=631
f(96)=163
f(97)=1
f(98)=389
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2-196x+4547 could be written as f(y)= y^2-5057 with x=y+98

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-98
f'(x)>2x-197 with x > 71

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

4547, 17, 4159, 31, 3779, 449, 3407, 13, 179, 1, 2687, 157, 2339, 271, 1999, 229, 1667, 47, 79, 37, 1, 109, 719, 71, 419, 1, 127, 1, 1, 1, 433, 1, 701, 1, 1, 1, 1213, 167, 1, 197, 1693, 113, 1, 1, 2141, 281, 181, 307, 2557, 83, 2753, 89, 173, 379, 3121, 401, 1, 211, 3457, 1, 3613, 461, 3761, 479, 1, 1, 1, 1, 4157, 1, 4273, 541, 337, 277, 4481, 283, 269, 577, 4657, 587, 4733, 149, 4801, 151, 4861, 1, 1, 617, 4957, 311, 4993, 313, 5021, 1, 1, 631, 163, 1, 389, 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, 593, 4943, 643, 5347, 347, 443, 373, 1, 1, 6607, 853, 7043, 227, 7487, 241, 467, 1021, 1, 1, 8867, 569, 9343, 599, 317, 1259, 607, 1321, 349, 1, 1, 1, 911, 1, 1, 1579, 12899, 823, 1, 857, 1, 1783, 14543, 1, 15107, 1, 15679, 499, 1, 2069, 991, 2143, 17443, 1109, 18047, 1, 397, 2371, 1483, 1, 1171, 1, 20543, 1, 21187, 2689, 21839, 1, 1, 1427, 23167, 1, 1, 3023, 24527, 3109, 25219, 1, 25919, 821, 26627, 3373, 739, 3463, 1, 1777, 929, 1823, 1, 3739, 977, 3833, 839, 491, 1871, 503, 32579, 1, 33359, 4219, 34147, 1, 421, 1, 35747, 4519, 36559, 4621, 37379, 1181, 2939, 1, 39043, 4933, 39887, 5039, 40739, 1, 2447, 1, 42467, 1, 487, 1, 941, 1, 45119, 1, 2707, 1, 1, 5923, 47843, 3019, 48767, 1, 3823, 6271, 641, 6389, 653, 1627, 52543, 1657, 53507, 1, 1, 6871, 1789, 1, 1201, 3559, 1, 7243, 1, 7369, 1607, 937, 1, 953, 61507, 7753, 1, 7883, 63587, 4007, 1747, 4073, 65699, 1, 1, 1, 67843, 2137, 68927, 1, 70019, 8821, 71119, 1, 72227, 4549, 1033, 1, 659, 1, 4447, 9521, 5903, 1, 1097, 613, 79043, 1, 80207, 10099, 4787, 1, 82559, 5197, 1009, 811, 1, 1, 1, 2711, 87359, 2749, 1, 11149, 2897, 1, 1, 1, 1, 5807, 1051, 1, 2017, 1, 5651, 1511, 1, 1531, 98627, 12409, 1, 967, 797, 6367, 1, 6449, 103843, 13063, 105167, 13229, 1, 1, 107839, 3391, 1, 1, 110543, 13903, 2381, 1, 113279, 1, 114659, 14419, 116047, 14593, 117443, 1, 6991, 1, 1, 15121, 1, 15299, 1, 1, 124543, 7829, 7411, 1, 9803, 1, 1553, 4051, 130367, 1, 4253, 16573, 133327, 16759, 4349, 1, 136319, 1, 137827, 1019, 139343, 1, 140867, 2213, 907, 2237, 8467, 18089, 145487, 1, 11311, 9239, 859, 9337, 1901, 1, 1, 19069, 1723, 4817, 154943, 1, 4231, 1, 1451, 1, 159779, 10037, 161407, 10139, 3469, 20483, 4451, 1217, 919, 1, 12923, 1319, 169667, 21313, 10079, 21523, 2437, 10867, 1, 10973, 176419, 22159, 178127, 1721, 1, 5647, 5857, 5701, 183299, 23021, 1, 1367, 1237, 1, 1129, 11839, 14639, 23899, 1, 24121, 193859, 1, 1093, 1, 1, 24793, 199247, 1, 11827, 971, 202879, 1, 204707, 25703, 206543, 25933, 208387, 1, 1, 6599, 212099, 1, 1, 26863, 215843, 1, 217727, 1, 219619, 1, 5987, 27809, 1, 1753, 225343, 1, 227267, 1, 229199, 28771, 6247, 1, 13711, 14629, 235043, 1, 2663, 1, 1, 7499, 240959, 7561, 1, 30493, 244943, 1, 246947, 15497, 5297, 1, 250979, 2423, 2239, 1, 255043, 4001, 1, 1, 1, 1913, 1, 32779, 263267, 16519, 20411, 16649, 15731, 1, 269519, 1091, 271619, 8521, 273727, 1, 5869, 34613, 1, 2683, 280099, 17573, 282239, 17707, 284387, 2099, 286543, 1, 1, 1, 290879, 2281, 22543, 1, 295247, 2179, 8039, 1, 3793, 18797, 3821, 37871, 1, 38149, 1951, 1, 1, 9677, 1861, 1, 4409, 1, 1, 19777, 1, 19919, 1409, 40123, 1, 2377, 324419, 5087, 3671, 1, 329027, 1, 2609, 1, 333667, 1231, 335999, 1621, 338339, 1, 340687, 1, 1187, 1, 1637, 10831, 347779, 1, 350159, 1, 1, 22109, 20879, 22259, 357347, 44819, 1571, 45121, 1, 1, 364607, 1429, 1523, 3541, 369487, 1, 371939, 1, 374399, 1381, 12157, 1, 379343, 1, 1, 11971, 1, 12049, 2161, 1, 1, 48823, 4721, 1, 394367, 1, 1, 1, 399439, 3853, 401987, 6301, 1, 1, 1, 1, 1, 1, 2383, 25847, 1, 1, 1, 3079, 420047, 1699, 2593, 13249, 425279, 13331, 25171, 53653, 430543, 1459, 433187, 2089, 435839, 1, 438499, 54979, 25951, 55313, 4987, 1, 2467, 3499, 2129, 3313, 34763, 56659, 454627, 28499, 14753, 28669, 1, 57679, 14929, 3413, 4271, 14591, 1, 1, 3709, 59053, 1, 59399, 476579, 29873, 1, 30047, 1, 60443, 1439, 60793, 2207, 7643, 490559, 7687, 6949, 1, 13411, 3659, 6317, 1, 6353, 1, 7109, 1, 507599, 63629, 10861, 1, 1, 16087, 516227, 64709, 519119, 65071, 30707, 32717, 1, 1, 527843, 1, 530767, 66529, 4723, 1, 31567, 1, 3119, 1, 3593, 5231, 17597, 2011, 1, 1, 17789, 69119, 554447, 69493, 557443, 17467, 560447, 1, 1, 70621, 1787, 70999, 569507, 1, 33679, 35879, 3863, 72139, 1, 1543, 581699, 1, 584767, 9161, 1, 73673, 15971, 2389, 3557, 37223, 3299, 1, 1, 75223, 46411, 1, 1, 19001, 609599, 1, 13037, 4517, 615887, 1, 2203, 1, 2741, 2999, 36787, 1, 7573, 1, 1, 1, 634943, 4973, 638147, 1, 1, 1, 1, 40387, 20897, 1, 651043, 4799, 13921, 1, 657539, 20599, 660799, 1, 664067, 1, 1, 4919, 670627, 42017, 1931, 42223, 2393, 84859, 40031, 1, 683843, 10711, 52859, 1, 5437, 2791, 2879, 86939, 41011, 1, 6427, 43889, 703907, 1, 707279, 1, 19207, 1, 1, 22367, 717443, 1, 720847, 1, 724259, 1, 1, 45587, 56239, 1949, 734543, 92033, 43411, 5779, 8933, 2903, 24029, 93329, 9473, 93763, 1, 3623, 1, 47317, 758819, 95071, 762319, 1, 765827, 1, 16369, 24097, 772867, 2617, 59723, 1, 779939, 48857, 783487, 2887, 787043, 1, 790607, 2677, 794179, 12437, 1, 1, 2957, 100393, 804943, 3253,

6. Sequence of the polynom (only primes)

4547, 17, 4159, 31, 3779, 449, 3407, 13, 179, 2687, 157, 2339, 271, 1999, 229, 1667, 47, 79, 37, 109, 719, 71, 419, 127, 433, 701, 1213, 167, 197, 1693, 113, 2141, 281, 181, 307, 2557, 83, 2753, 89, 173, 379, 3121, 401, 211, 3457, 3613, 461, 3761, 479, 4157, 4273, 541, 337, 277, 4481, 283, 269, 577, 4657, 587, 4733, 149, 4801, 151, 4861, 617, 4957, 311, 4993, 313, 5021, 631, 163, 389, 593, 4943, 643, 5347, 347, 443, 373, 6607, 853, 7043, 227, 7487, 241, 467, 1021, 8867, 569, 9343, 599, 317, 1259, 607, 1321, 349, 911, 1579, 12899, 823, 857, 1783, 14543, 15107, 15679, 499, 2069, 991, 2143, 17443, 1109, 18047, 397, 2371, 1483, 1171, 20543, 21187, 2689, 21839, 1427, 23167, 3023, 24527, 3109, 25219, 25919, 821, 26627, 3373, 739, 3463, 1777, 929, 1823, 3739, 977, 3833, 839, 491, 1871, 503, 32579, 33359, 4219, 34147, 421, 35747, 4519, 36559, 4621, 37379, 1181, 2939, 39043, 4933, 39887, 5039, 40739, 2447, 42467, 487, 941, 45119, 2707, 5923, 47843, 3019, 48767, 3823, 6271, 641, 6389, 653, 1627, 52543, 1657, 53507, 6871, 1789, 1201, 3559, 7243, 7369, 1607, 937, 953, 61507, 7753, 7883, 63587, 4007, 1747, 4073, 65699, 67843, 2137, 68927, 70019, 8821, 71119, 72227, 4549, 1033, 659, 4447, 9521, 5903, 1097, 613, 79043, 80207, 10099, 4787, 82559, 5197, 1009, 811, 2711, 87359, 2749, 11149, 2897, 5807, 1051, 2017, 5651, 1511, 1531, 98627, 12409, 967, 797, 6367, 6449, 103843, 13063, 105167, 13229, 107839, 3391, 110543, 13903, 2381, 113279, 114659, 14419, 116047, 14593, 117443, 6991, 15121, 15299, 124543, 7829, 7411, 9803, 1553, 4051, 130367, 4253, 16573, 133327, 16759, 4349, 136319, 137827, 1019, 139343, 140867, 2213, 907, 2237, 8467, 18089, 145487, 11311, 9239, 859, 9337, 1901, 19069, 1723, 4817, 154943, 4231, 1451, 159779, 10037, 161407, 10139, 3469, 20483, 4451, 1217, 919, 12923, 1319, 169667, 21313, 10079, 21523, 2437, 10867, 10973, 176419, 22159, 178127, 1721, 5647, 5857, 5701, 183299, 23021, 1367, 1237, 1129, 11839, 14639, 23899, 24121, 193859, 1093, 24793, 199247, 11827, 971, 202879, 204707, 25703, 206543, 25933, 208387, 6599, 212099, 26863, 215843, 217727, 219619, 5987, 27809, 1753, 225343, 227267, 229199, 28771, 6247, 13711, 14629, 235043, 2663, 7499, 240959, 7561, 30493, 244943, 246947, 15497, 5297, 250979, 2423, 2239, 255043, 4001, 1913, 32779, 263267, 16519, 20411, 16649, 15731, 269519, 1091, 271619, 8521, 273727, 5869, 34613, 2683, 280099, 17573, 282239, 17707, 284387, 2099, 286543, 290879, 2281, 22543, 295247, 2179, 8039, 3793, 18797, 3821, 37871, 38149, 1951, 9677, 1861, 4409, 19777, 19919, 1409, 40123, 2377, 324419, 5087, 3671, 329027, 2609, 333667, 1231, 335999, 1621, 338339, 340687, 1187, 1637, 10831, 347779, 350159, 22109, 20879, 22259, 357347, 44819, 1571, 45121, 364607, 1429, 1523, 3541, 369487, 371939, 374399, 1381, 12157, 379343, 11971, 12049, 2161, 48823, 4721, 394367, 399439, 3853, 401987, 6301, 2383, 25847, 3079, 420047, 1699, 2593, 13249, 425279, 13331, 25171, 53653, 430543, 1459, 433187, 2089, 435839, 438499, 54979, 25951, 55313, 4987, 2467, 3499, 2129, 3313, 34763, 56659, 454627, 28499, 14753, 28669, 57679, 14929, 3413, 4271, 14591, 3709, 59053, 59399, 476579, 29873, 30047, 60443, 1439, 60793, 2207, 7643, 490559, 7687, 6949, 13411, 3659, 6317, 6353, 7109, 507599, 63629, 10861, 16087, 516227, 64709, 519119, 65071, 30707, 32717, 527843, 530767, 66529, 4723, 31567, 3119, 3593, 5231, 17597, 2011, 17789, 69119, 554447, 69493, 557443, 17467, 560447, 70621, 1787, 70999, 569507, 33679, 35879, 3863, 72139, 1543, 581699, 584767, 9161, 73673, 15971, 2389, 3557, 37223, 3299, 75223, 46411, 19001, 609599, 13037, 4517, 615887, 2203, 2741, 2999, 36787, 7573, 634943, 4973, 638147, 40387, 20897, 651043, 4799, 13921, 657539, 20599, 660799, 664067, 4919, 670627, 42017, 1931, 42223, 2393, 84859, 40031, 683843, 10711, 52859, 5437, 2791, 2879, 86939, 41011, 6427, 43889, 703907, 707279, 19207, 22367, 717443, 720847, 724259, 45587, 56239, 1949, 734543, 92033, 43411, 5779, 8933, 2903, 24029, 93329, 9473, 93763, 3623, 47317, 758819, 95071, 762319, 765827, 16369, 24097, 772867, 2617, 59723, 779939, 48857, 783487, 2887, 787043, 790607, 2677, 794179, 12437, 2957, 100393, 804943, 3253,

7. Distribution of the primes

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

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 : 4547, 17, 4159, 31, 3779, 449, 3407, 13, 179, 1, 2687, 157, 2339, 271, 1999, 229, 1667, 47, 79, 37,
Found in Database : 4547, 17, 4159, 31, 3779, 449, 3407, 13, 179, 2687, 157, 2339, 271, 1999, 229, 1667, 47, 79, 37, 109, 719, 71, 419, 127, 433, 701, 1213, 167, 197,
Found in Database : 13, 17, 31, 37, 47, 71, 79, 83, 89, 109, 113, 127, 149,