Inhaltsverzeichnis

Development of
Algorithmic Constructions

10:40:05
Deutsch
29.Mar 2024

Polynom = x^2-212x+307

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) = 307 = 307
f(1) = 3 = 3
f(2) = 113 = 113
f(3) = 5 = 5
f(4) = 525 = 3*5*5*7
f(5) = 91 = 7*13
f(6) = 929 = 929
f(7) = 141 = 3*47
f(8) = 1325 = 5*5*53
f(9) = 95 = 5*19
f(10) = 1713 = 3*571
f(11) = 119 = 7*17
f(12) = 2093 = 7*13*23
f(13) = 285 = 3*5*19
f(14) = 2465 = 5*17*29
f(15) = 331 = 331
f(16) = 2829 = 3*23*41
f(17) = 47 = 47
f(18) = 3185 = 5*7*7*13
f(19) = 105 = 3*5*7
f(20) = 3533 = 3533
f(21) = 463 = 463
f(22) = 3873 = 3*1291
f(23) = 505 = 5*101
f(24) = 4205 = 5*29*29
f(25) = 273 = 3*7*13
f(26) = 4529 = 7*647
f(27) = 293 = 293
f(28) = 4845 = 3*5*17*19
f(29) = 625 = 5*5*5*5
f(30) = 5153 = 5153
f(31) = 663 = 3*13*17
f(32) = 5453 = 7*19*41
f(33) = 175 = 5*5*7
f(34) = 5745 = 3*5*383
f(35) = 23 = 23
f(36) = 6029 = 6029
f(37) = 771 = 3*257
f(38) = 6305 = 5*13*97
f(39) = 805 = 5*7*23
f(40) = 6573 = 3*7*313
f(41) = 419 = 419
f(42) = 6833 = 6833
f(43) = 435 = 3*5*29
f(44) = 7085 = 5*13*109
f(45) = 901 = 17*53
f(46) = 7329 = 3*7*349
f(47) = 931 = 7*7*19
f(48) = 7565 = 5*17*89
f(49) = 15 = 3*5
f(50) = 7793 = 7793
f(51) = 247 = 13*19
f(52) = 8013 = 3*2671
f(53) = 1015 = 5*7*29
f(54) = 8225 = 5*5*7*47
f(55) = 1041 = 3*347
f(56) = 8429 = 8429
f(57) = 533 = 13*41
f(58) = 8625 = 3*5*5*5*23
f(59) = 545 = 5*109
f(60) = 8813 = 7*1259
f(61) = 1113 = 3*7*53
f(62) = 8993 = 17*23*23
f(63) = 1135 = 5*227
f(64) = 9165 = 3*5*13*47
f(65) = 289 = 17*17
f(66) = 9329 = 19*491
f(67) = 147 = 3*7*7
f(68) = 9485 = 5*7*271
f(69) = 1195 = 5*239
f(70) = 9633 = 3*13*13*19
f(71) = 1213 = 1213
f(72) = 9773 = 29*337
f(73) = 615 = 3*5*41
f(74) = 9905 = 5*7*283
f(75) = 623 = 7*89
f(76) = 10029 = 3*3343
f(77) = 1261 = 13*97
f(78) = 10145 = 5*2029
f(79) = 1275 = 3*5*5*17
f(80) = 10253 = 10253
f(81) = 161 = 7*23
f(82) = 10353 = 3*7*17*29
f(83) = 325 = 5*5*13
f(84) = 10445 = 5*2089
f(85) = 1311 = 3*19*23
f(86) = 10529 = 10529
f(87) = 1321 = 1321
f(88) = 10605 = 3*5*7*101
f(89) = 665 = 5*7*19
f(90) = 10673 = 13*821
f(91) = 669 = 3*223
f(92) = 10733 = 10733
f(93) = 1345 = 5*269
f(94) = 10785 = 3*5*719
f(95) = 1351 = 7*193
f(96) = 10829 = 7*7*13*17
f(97) = 339 = 3*113
f(98) = 10865 = 5*41*53
f(99) = 85 = 5*17
f(100) = 10893 = 3*3631

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-212x+307

f(0)=307
f(1)=3
f(2)=113
f(3)=5
f(4)=7
f(5)=13
f(6)=929
f(7)=47
f(8)=53
f(9)=19
f(10)=571
f(11)=17
f(12)=23
f(13)=1
f(14)=29
f(15)=331
f(16)=41
f(17)=1
f(18)=1
f(19)=1
f(20)=3533
f(21)=463
f(22)=1291
f(23)=101
f(24)=1
f(25)=1
f(26)=647
f(27)=293
f(28)=1
f(29)=1
f(30)=5153
f(31)=1
f(32)=1
f(33)=1
f(34)=383
f(35)=1
f(36)=6029
f(37)=257
f(38)=97
f(39)=1
f(40)=313
f(41)=419
f(42)=6833
f(43)=1
f(44)=109
f(45)=1
f(46)=349
f(47)=1
f(48)=89
f(49)=1
f(50)=7793
f(51)=1
f(52)=2671
f(53)=1
f(54)=1
f(55)=347
f(56)=8429
f(57)=1
f(58)=1
f(59)=1
f(60)=1259
f(61)=1
f(62)=1
f(63)=227
f(64)=1
f(65)=1
f(66)=491
f(67)=1
f(68)=271
f(69)=239
f(70)=1
f(71)=1213
f(72)=337
f(73)=1
f(74)=283
f(75)=1
f(76)=3343
f(77)=1
f(78)=2029
f(79)=1
f(80)=10253
f(81)=1
f(82)=1
f(83)=1
f(84)=2089
f(85)=1
f(86)=10529
f(87)=1321
f(88)=1
f(89)=1
f(90)=821
f(91)=223
f(92)=10733
f(93)=269
f(94)=719
f(95)=193
f(96)=1
f(97)=1
f(98)=1
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2-212x+307 could be written as f(y)= y^2-10929 with x=y+106

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-106
f'(x)>2x-213 with x > 105

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

307, 3, 113, 5, 7, 13, 929, 47, 53, 19, 571, 17, 23, 1, 29, 331, 41, 1, 1, 1, 3533, 463, 1291, 101, 1, 1, 647, 293, 1, 1, 5153, 1, 1, 1, 383, 1, 6029, 257, 97, 1, 313, 419, 6833, 1, 109, 1, 349, 1, 89, 1, 7793, 1, 2671, 1, 1, 347, 8429, 1, 1, 1, 1259, 1, 1, 227, 1, 1, 491, 1, 271, 239, 1, 1213, 337, 1, 283, 1, 3343, 1, 2029, 1, 10253, 1, 1, 1, 2089, 1, 10529, 1321, 1, 1, 821, 223, 10733, 269, 719, 193, 1, 1, 1, 1, 3631, 1, 1559, 1, 1, 683, 3643, 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, 1171, 1, 1, 1, 1, 1, 1, 1, 599, 1, 1, 1, 1, 1, 4447, 587, 1, 1, 1091, 1, 853, 1, 433, 1, 7027, 1, 1, 1, 541, 1049, 1, 373, 1847, 1, 467, 631, 1, 1, 439, 1409, 1, 1, 487, 1, 673, 1637, 1, 1, 401, 1, 863, 937, 1021, 1, 2281, 1, 1279, 1, 1153, 1, 17971, 1, 1, 1, 6449, 1231, 20047, 1, 593, 1, 421, 2729, 1, 1, 1, 1, 1, 601, 1, 1033, 25171, 1597, 1, 1, 1571, 1129, 27487, 1, 1, 1, 4153, 1, 1, 757, 1, 1, 643, 1, 1, 1, 11057, 1, 6803, 1, 1, 1103, 11909, 1, 563, 1543, 1, 677, 2557, 1, 3019, 827, 2113, 1, 1, 5189, 1, 1, 1, 1, 2087, 1, 503, 1, 1, 2887, 1, 1, 1361, 1, 3739, 1, 16529, 1, 1, 1, 3967, 1, 701, 1327, 1307, 1, 1, 1, 3709, 7019, 56671, 2383, 1, 1, 1031, 1, 2063, 1, 641, 1097, 1, 3907, 12611, 1, 2789, 8087, 1, 1, 577, 1, 619, 1063, 1, 1, 1423, 1, 70867, 1, 4801, 1, 10453, 1, 14867, 1873, 25169, 1, 1, 1, 1, 1, 26357, 1, 1, 1, 1663, 733, 1451, 2083, 16787, 1, 1607, 1, 823, 1, 3023, 1, 5231, 2239, 859, 811, 1, 1, 1427, 1, 1, 1, 1, 1, 1487, 3041, 1, 12329, 2837, 1, 2141, 1, 829, 1283, 20663, 1, 787, 1013, 7069, 1, 5653, 1, 15541, 1, 1, 13859, 6563, 2339, 4519, 1, 1, 14387, 115807, 971, 23447, 1, 5651, 1, 24023, 1, 7151, 15287, 1783, 1, 3557, 2609, 5477, 1, 1, 1, 1, 1, 130447, 1, 1, 1, 10267, 1, 1, 1697, 2677, 8581, 1367, 1, 3989, 1, 47057, 1109, 28547, 1, 144307, 2591, 6947, 1, 1, 3089, 11467, 1, 1, 1, 152287, 6379, 11839, 967, 10369, 1, 22453, 1, 1381, 1, 1, 1, 1, 1, 1, 1583, 2903, 20789, 1, 1, 24121, 5303, 4373, 857, 1, 7213, 1, 1, 1, 2207, 177427, 1, 179167, 1, 1723, 1, 6299, 1, 36887, 1, 8867, 1, 187987, 1, 7591, 1, 63857, 1, 1, 1619, 10273, 1, 1, 1237, 1, 1, 200671, 1, 1, 2543, 204367, 1, 1733, 5179, 13873, 1, 209971, 1, 6053, 1, 71249, 1, 2423, 1, 3347, 1951, 1493, 1, 44279, 1, 1, 1, 1, 1, 1567, 2377, 229171, 2213, 1, 1, 33301, 4877, 12373, 1, 1, 29759, 1, 1429, 9643, 1, 1, 1907, 245107, 1, 1, 31019, 6389, 1, 1069, 1051, 1, 1, 85109, 1, 51479, 1, 15263, 1163, 1, 1, 263647, 1, 265747, 1, 2551, 1, 1093, 1, 54419, 6829, 1, 1229, 3037, 1, 1, 34949, 93557, 1, 8081, 1, 285007, 17881, 3301, 7207, 1, 1, 1811, 1, 3917, 1, 1, 12379, 1, 1, 20029, 1, 1, 6329, 4691, 1, 14627, 1, 7547, 1, 1, 1, 14951, 1, 3329, 1, 2819, 1, 106949, 1, 1319, 13513, 1201, 40829, 1, 1, 47161, 1, 332467, 1, 1, 41999, 1747, 1, 1, 4259, 113969, 3299, 14969, 2879, 1, 1553, 5059, 1, 1, 2939, 12203, 1, 1, 1, 5519, 7499, 19009, 1, 3463, 1303, 1, 1913, 7841, 2311, 24733, 1, 53353, 1, 4423, 1, 1249, 1, 54421, 1, 1447, 2531, 128657, 12101, 77699, 1, 4297, 49037, 7717, 9871, 1, 1, 1, 3571, 1, 1, 1, 16879, 17669, 1, 1, 12821, 4243, 17203, 16567, 1, 1, 3733, 24671, 1753, 84407, 52919, 10889, 7607, 1, 1, 10487, 1, 11093, 1, 12437, 1, 25763, 27457, 1, 1, 443347, 2647, 9103, 2237, 29917, 1, 1889, 1, 1, 1627, 1, 57287, 1861, 1, 4021, 1, 1, 2011, 1, 3911, 1, 14753, 3221, 1, 19051, 1531, 10193, 1, 1, 1, 4073, 1, 487507, 1, 1, 61469, 1499, 1, 1, 3109, 166289, 2719, 4603, 1, 1, 31627, 1, 1871, 102071, 1, 1, 1, 172049, 1, 103811, 2711, 1, 1, 4999, 13159, 1, 11027, 530767, 6653, 1, 1, 536671, 1, 107927, 1, 13913, 1, 1901, 1, 21943, 2371, 3469, 2659, 3169, 1, 2333, 4111, 186869, 1, 1, 1, 80953, 1, 1999, 14281, 44059, 23929, 82261, 1, 38593, 36277, 1, 1, 6883, 1, 4001, 1, 1, 1, 4099, 74489, 1, 1, 1, 1, 26249, 37831, 202289, 1, 1, 1, 1, 19211, 2417, 1931, 1, 3697, 2521, 15607, 1669, 39217, 1, 1877, 3613, 1, 4507, 1, 37571, 1, 18341, 1, 1973, 80849, 3163, 5417, 651667, 1, 2399, 1, 131639, 1, 2459, 82889, 1, 1, 668047, 1, 1, 1, 1, 1, 4211, 14159, 1, 8537, 12011, 6599, 3389, 1, 1, 2707, 1, 1, 10739, 1, 1, 87887, 8101, 8831, 2179, 1, 101653, 1, 9533, 1, 718387, 1, 13619, 1, 6907, 1, 42863, 2341, 146423, 9173, 35027, 1, 739027, 6173, 11423, 2269, 248657, 1, 1, 1, 3407, 3253, 1, 1, 21713, 2267, 763471, 1, 51133, 19219, 770527, 4597, 110581, 1, 1, 6089, 781171, 1, 3203, 1,

6. Sequence of the polynom (only primes)

307, 3, 113, 5, 7, 13, 929, 47, 53, 19, 571, 17, 23, 29, 331, 41, 3533, 463, 1291, 101, 647, 293, 5153, 383, 6029, 257, 97, 313, 419, 6833, 109, 349, 89, 7793, 2671, 347, 8429, 1259, 227, 491, 271, 239, 1213, 337, 283, 3343, 2029, 10253, 2089, 10529, 1321, 821, 223, 10733, 269, 719, 193, 3631, 1559, 683, 3643, 1171, 599, 4447, 587, 1091, 853, 433, 7027, 541, 1049, 373, 1847, 467, 631, 439, 1409, 487, 673, 1637, 401, 863, 937, 1021, 2281, 1279, 1153, 17971, 6449, 1231, 20047, 593, 421, 2729, 601, 1033, 25171, 1597, 1571, 1129, 27487, 4153, 757, 643, 11057, 6803, 1103, 11909, 563, 1543, 677, 2557, 3019, 827, 2113, 5189, 2087, 503, 2887, 1361, 3739, 16529, 3967, 701, 1327, 1307, 3709, 7019, 56671, 2383, 1031, 2063, 641, 1097, 3907, 12611, 2789, 8087, 577, 619, 1063, 1423, 70867, 4801, 10453, 14867, 1873, 25169, 26357, 1663, 733, 1451, 2083, 16787, 1607, 823, 3023, 5231, 2239, 859, 811, 1427, 1487, 3041, 12329, 2837, 2141, 829, 1283, 20663, 787, 1013, 7069, 5653, 15541, 13859, 6563, 2339, 4519, 14387, 115807, 971, 23447, 5651, 24023, 7151, 15287, 1783, 3557, 2609, 5477, 130447, 10267, 1697, 2677, 8581, 1367, 3989, 47057, 1109, 28547, 144307, 2591, 6947, 3089, 11467, 152287, 6379, 11839, 967, 10369, 22453, 1381, 1583, 2903, 20789, 24121, 5303, 4373, 857, 7213, 2207, 177427, 179167, 1723, 6299, 36887, 8867, 187987, 7591, 63857, 1619, 10273, 1237, 200671, 2543, 204367, 1733, 5179, 13873, 209971, 6053, 71249, 2423, 3347, 1951, 1493, 44279, 1567, 2377, 229171, 2213, 33301, 4877, 12373, 29759, 1429, 9643, 1907, 245107, 31019, 6389, 1069, 1051, 85109, 51479, 15263, 1163, 263647, 265747, 2551, 1093, 54419, 6829, 1229, 3037, 34949, 93557, 8081, 285007, 17881, 3301, 7207, 1811, 3917, 12379, 20029, 6329, 4691, 14627, 7547, 14951, 3329, 2819, 106949, 1319, 13513, 1201, 40829, 47161, 332467, 41999, 1747, 4259, 113969, 3299, 14969, 2879, 1553, 5059, 2939, 12203, 5519, 7499, 19009, 3463, 1303, 1913, 7841, 2311, 24733, 53353, 4423, 1249, 54421, 1447, 2531, 128657, 12101, 77699, 4297, 49037, 7717, 9871, 3571, 16879, 17669, 12821, 4243, 17203, 16567, 3733, 24671, 1753, 84407, 52919, 10889, 7607, 10487, 11093, 12437, 25763, 27457, 443347, 2647, 9103, 2237, 29917, 1889, 1627, 57287, 1861, 4021, 2011, 3911, 14753, 3221, 19051, 1531, 10193, 4073, 487507, 61469, 1499, 3109, 166289, 2719, 4603, 31627, 1871, 102071, 172049, 103811, 2711, 4999, 13159, 11027, 530767, 6653, 536671, 107927, 13913, 1901, 21943, 2371, 3469, 2659, 3169, 2333, 4111, 186869, 80953, 1999, 14281, 44059, 23929, 82261, 38593, 36277, 6883, 4001, 4099, 74489, 26249, 37831, 202289, 19211, 2417, 1931, 3697, 2521, 15607, 1669, 39217, 1877, 3613, 4507, 37571, 18341, 1973, 80849, 3163, 5417, 651667, 2399, 131639, 2459, 82889, 668047, 4211, 14159, 8537, 12011, 6599, 3389, 2707, 10739, 87887, 8101, 8831, 2179, 101653, 9533, 718387, 13619, 6907, 42863, 2341, 146423, 9173, 35027, 739027, 6173, 11423, 2269, 248657, 3407, 3253, 21713, 2267, 763471, 51133, 19219, 770527, 4597, 110581, 6089, 781171, 3203,

7. Distribution of the primes

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

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 : 307, 3, 113, 5, 7, 13, 929, 47, 53, 19, 571, 17, 23, 1, 29, 331, 41, 1, 1, 1,
Found in Database : 307, 3, 113, 5, 7, 13, 929, 47, 53, 19, 571, 17, 23, 29, 331, 41, 3533, 463, 1291, 101, 647, 293, 5153, 383, 6029, 257, 97,
Found in Database : 3, 5, 7, 13, 17, 19, 23, 29, 41, 47, 53, 89, 97, 101, 109, 113,