Inhaltsverzeichnis

Development of
Algorithmic Constructions

14:00:56
Deutsch
28.Mar 2024

Polynom = x^2-96x+199

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) = 199 = 199
f(1) = 13 = 13
f(2) = 11 = 11
f(3) = 5 = 5
f(4) = 169 = 13*13
f(5) = 1 = 1
f(6) = 341 = 11*31
f(7) = 53 = 53
f(8) = 505 = 5*101
f(9) = 73 = 73
f(10) = 661 = 661
f(11) = 23 = 23
f(12) = 809 = 809
f(13) = 55 = 5*11
f(14) = 949 = 13*73
f(15) = 127 = 127
f(16) = 1081 = 23*47
f(17) = 143 = 11*13
f(18) = 1205 = 5*241
f(19) = 79 = 79
f(20) = 1321 = 1321
f(21) = 43 = 43
f(22) = 1429 = 1429
f(23) = 185 = 5*37
f(24) = 1529 = 11*139
f(25) = 197 = 197
f(26) = 1621 = 1621
f(27) = 13 = 13
f(28) = 1705 = 5*11*31
f(29) = 109 = 109
f(30) = 1781 = 13*137
f(31) = 227 = 227
f(32) = 1849 = 43*43
f(33) = 235 = 5*47
f(34) = 1909 = 23*83
f(35) = 121 = 11*11
f(36) = 1961 = 37*53
f(37) = 31 = 31
f(38) = 2005 = 5*401
f(39) = 253 = 11*23
f(40) = 2041 = 13*157
f(41) = 257 = 257
f(42) = 2069 = 2069
f(43) = 65 = 5*13
f(44) = 2089 = 2089
f(45) = 131 = 131
f(46) = 2101 = 11*191
f(47) = 263 = 263
f(48) = 2105 = 5*421
f(49) = 263 = 263
f(50) = 2101 = 11*191
f(51) = 131 = 131
f(52) = 2089 = 2089
f(53) = 65 = 5*13
f(54) = 2069 = 2069
f(55) = 257 = 257
f(56) = 2041 = 13*157
f(57) = 253 = 11*23
f(58) = 2005 = 5*401
f(59) = 31 = 31
f(60) = 1961 = 37*53
f(61) = 121 = 11*11
f(62) = 1909 = 23*83
f(63) = 235 = 5*47
f(64) = 1849 = 43*43
f(65) = 227 = 227
f(66) = 1781 = 13*137
f(67) = 109 = 109
f(68) = 1705 = 5*11*31
f(69) = 13 = 13
f(70) = 1621 = 1621
f(71) = 197 = 197
f(72) = 1529 = 11*139
f(73) = 185 = 5*37
f(74) = 1429 = 1429
f(75) = 43 = 43
f(76) = 1321 = 1321
f(77) = 79 = 79
f(78) = 1205 = 5*241
f(79) = 143 = 11*13
f(80) = 1081 = 23*47
f(81) = 127 = 127
f(82) = 949 = 13*73
f(83) = 55 = 5*11
f(84) = 809 = 809
f(85) = 23 = 23
f(86) = 661 = 661
f(87) = 73 = 73
f(88) = 505 = 5*101
f(89) = 53 = 53
f(90) = 341 = 11*31
f(91) = 1 = 1
f(92) = 169 = 13*13
f(93) = 5 = 5
f(94) = 11 = 11
f(95) = 13 = 13
f(96) = 199 = 199
f(97) = 37 = 37
f(98) = 395 = 5*79
f(99) = 31 = 31
f(100) = 599 = 599

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-96x+199

f(0)=199
f(1)=13
f(2)=11
f(3)=5
f(4)=1
f(5)=1
f(6)=31
f(7)=53
f(8)=101
f(9)=73
f(10)=661
f(11)=23
f(12)=809
f(13)=1
f(14)=1
f(15)=127
f(16)=47
f(17)=1
f(18)=241
f(19)=79
f(20)=1321
f(21)=43
f(22)=1429
f(23)=37
f(24)=139
f(25)=197
f(26)=1621
f(27)=1
f(28)=1
f(29)=109
f(30)=137
f(31)=227
f(32)=1
f(33)=1
f(34)=83
f(35)=1
f(36)=1
f(37)=1
f(38)=401
f(39)=1
f(40)=157
f(41)=257
f(42)=2069
f(43)=1
f(44)=2089
f(45)=131
f(46)=191
f(47)=263
f(48)=421
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
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-96x+199 could be written as f(y)= y^2-2105 with x=y+48

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-48
f'(x)>2x-97 with x > 46

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

199, 13, 11, 5, 1, 1, 31, 53, 101, 73, 661, 23, 809, 1, 1, 127, 47, 1, 241, 79, 1321, 43, 1429, 37, 139, 197, 1621, 1, 1, 109, 137, 227, 1, 1, 83, 1, 1, 1, 401, 1, 157, 257, 2069, 1, 2089, 131, 191, 263, 421, 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, 599, 1, 811, 1, 1031, 1, 1259, 1, 1, 1, 1, 233, 181, 1, 2251, 149, 229, 1, 1, 367, 3079, 1, 3371, 1, 3671, 239, 173, 1, 859, 557, 1, 1, 4951, 1, 1, 683, 5639, 727, 1, 193, 6359, 409, 1, 1, 547, 1, 7499, 1, 1579, 1, 1, 1063, 281, 223, 397, 1, 1, 1, 1999, 1277, 1, 1, 10891, 1, 11351, 1, 1, 1, 2459, 1567, 983, 1, 577, 1, 293, 1753, 1, 1, 269, 941, 15319, 487, 1, 1, 443, 2083, 1303, 1, 3499, 1, 18059, 2293, 601, 1, 19211, 1, 1523, 1, 4079, 1, 1, 2663, 21611, 1, 1, 1409, 22859, 2897, 1, 1, 1, 1, 1907, 1, 821, 1, 26119, 3307, 1, 1, 27479, 1, 1, 1, 28871, 1, 2689, 1871, 1, 479, 31019, 3923, 31751, 1, 32491, 1, 773, 1, 523, 4297, 34759, 1, 35531, 449, 3301, 1, 1613, 1, 1, 4787, 38699, 1, 39511, 499, 1301, 463, 521, 5197, 1, 1, 42839, 1, 43691, 1103, 1, 5623, 4129, 1433, 1, 1, 4289, 5953, 907, 1213, 3767, 3089, 1609, 1, 10159, 1, 51719, 593, 1423, 1, 53591, 1, 54539, 1, 1009, 6997, 1, 3559, 1, 1, 58411, 1, 59399, 7487, 1, 1, 4723, 1, 1, 1, 1, 7993, 883, 1, 13099, 2063, 1, 1, 1, 1, 1, 1, 1, 4391, 14159, 1, 71879, 823, 1697, 919, 74071, 1, 5783, 9467, 15259, 739, 77419, 2437, 1, 1, 79691, 1, 7349, 10177, 1, 1, 607, 2617, 1, 1, 1, 1, 1, 1, 17579, 5531, 641, 11213, 6947, 2273, 1, 1, 1, 1459, 1709, 11827, 95239, 1, 2053, 1, 1, 1, 1193, 12457, 1543, 1, 647, 6389, 102871, 1, 1427, 13103, 1, 13267, 1, 1, 9829, 1, 109451, 2753, 4817, 13933, 112139, 1, 22699, 1, 114859, 1, 2473, 1, 1, 3697, 937, 7481, 1, 15137, 3929, 15313, 1, 1549, 9587, 3917, 3407, 1, 1, 1, 128939, 1013, 1291, 1, 1669, 16573, 133319, 1289, 26959, 1, 953, 2141, 137771, 3463, 1151, 761, 140779, 4423, 1, 8941, 1, 1, 1, 1, 146891, 839, 148439, 4663, 1, 1, 4889, 1, 13921, 1, 1181, 9719, 1093, 1, 1373, 1, 159499, 1, 2207, 1, 162731, 20443, 1, 1877, 33199, 1, 3163, 10529, 1, 4253, 15541, 1, 172619, 1, 3169, 1, 175979, 1, 1, 4463, 991, 1, 7873, 1, 36559, 2087, 4987, 23173, 14327, 2339, 3547, 1, 1, 23827, 38299, 1, 17569, 6067, 1931, 1, 1, 1901, 198599, 2267, 3083, 1, 1, 1, 6581, 1, 5563, 1, 1, 3259, 1, 13151, 211339, 1, 19381, 1, 215051, 13499, 216919, 1, 43759, 1, 3023, 2131, 9677, 1, 1, 1, 226379, 1, 45659, 28657, 20929, 14449, 2797, 1, 1637, 29383, 1223, 1, 47599, 1867, 10433, 1, 241931, 6073, 243911, 1, 245899, 1187, 1153, 3889, 1, 1, 22901, 6323, 6863, 1, 23269, 16061, 51599, 32377, 1, 32633, 1759, 1, 8521, 8287, 5023, 3037, 2333, 1, 270379, 4241, 3449, 1, 1, 1, 21283, 1, 1, 17491, 1, 2203, 283051, 7103, 285191, 3253, 1, 9013, 57899, 1, 5503, 1, 293831, 1, 296011, 1, 27109, 1, 1, 1, 27509, 37963, 23447, 1, 307031, 19259, 309259, 3527, 62299, 1699, 313739, 1789, 1, 1, 1, 1, 1627, 1297, 5869, 1, 325079, 20389, 29761, 1, 329671, 3181, 10709, 1, 1, 1, 4261, 42223, 14737, 1, 7937, 5351, 343639, 1, 5323, 43397, 2879, 3361, 350731, 1, 1, 1, 355499, 44587, 2309, 44887, 2837, 1, 9803, 4549, 28087, 1, 367559, 1487, 73999, 23201, 16193, 11677, 1, 9403, 29027, 1279, 1, 1, 1, 23971, 384779, 1, 7307, 1, 8293, 24439, 392279, 1, 3433, 1597, 2351, 49823, 399851, 1, 1, 25229, 1, 50777, 1, 1381, 31543, 1, 1, 1, 4111, 4733, 7883, 52387, 1, 1, 3229, 1, 11503, 1, 428231, 53693, 1, 27011, 1, 1, 1, 1, 1933, 11003, 1571, 1, 1, 2531, 1, 1, 10453, 1, 452171, 5669, 19777, 1, 1, 57367, 8369, 1, 5861, 1, 3257, 5839, 468491, 58733, 1, 59077, 2017, 1, 476759, 1, 36887, 1, 6607, 4651, 2137, 1, 97579, 1, 1439, 1, 1, 12373, 45121, 2393, 499159, 15643, 7723, 62927, 1723, 1, 507691, 1, 510551, 2909, 513419, 1, 1, 64717, 22573, 2503, 1531, 1, 524971, 2861, 1, 1, 2003, 16633, 533719, 1, 536651, 1, 41507, 1, 542539, 1, 1, 17093, 548459, 68743, 5059, 1, 3877, 1, 2801, 2687, 1, 70237, 15227, 1, 10687, 1, 569431, 1, 13313, 5519, 115099, 1, 1, 18127, 1, 1, 3061, 1559, 1, 1, 1, 37021, 4153, 1, 2677, 1, 600071, 1, 2347, 1, 121259, 37991, 5591, 1, 13033, 1, 19861, 1, 1, 1, 1, 3389, 1, 1, 1, 1, 27457, 39569, 48823, 79537, 127579, 1, 17327, 40169, 4703, 1, 647531, 1, 650759, 81547, 1, 1, 1, 41179, 1, 16553, 1, 2683, 667019, 1, 134059, 10499, 673579, 7673, 52067, 16963, 1, 1, 683479, 42821, 137359, 1831, 690119, 2011, 1, 8689, 13147, 1, 63649, 2371, 1, 1, 1, 11071, 1, 1, 713611, 89413, 1, 8167, 11083, 45131, 723799, 1, 727211, 18223, 1, 2953, 5281, 22993, 1, 1, 740939, 1, 744391, 1, 57527, 4259, 751319, 1, 150959, 8597, 758279, 95003, 3947, 1, 1, 47939, 1, 1, 154459, 96757, 70529, 2113, 779351, 2441, 782891, 2281, 1, 1, 157999, 1, 61043, 4519, 797131, 19973, 800711, 100313, 10181, 1, 1, 25303, 62423, 101663, 74101, 1, 35597, 12821, 17497, 51511, 1, 1, 829639, 1, 6361, 1, 836951, 6553, 64663, 1, 1, 105767, 1, 26557, 851671, 1, 77761, 1, 66083, 4679, 4013, 4157, 866519, 2467, 1, 21803, 873991, 1, 877739, 1, 176299, 1, 16703, 1, 6217, 22273, 3319, 1, 81509, 1, 1, 112787,

6. Sequence of the polynom (only primes)

199, 13, 11, 5, 31, 53, 101, 73, 661, 23, 809, 127, 47, 241, 79, 1321, 43, 1429, 37, 139, 197, 1621, 109, 137, 227, 83, 401, 157, 257, 2069, 2089, 131, 191, 263, 421, 599, 811, 1031, 1259, 233, 181, 2251, 149, 229, 367, 3079, 3371, 3671, 239, 173, 859, 557, 4951, 683, 5639, 727, 193, 6359, 409, 547, 7499, 1579, 1063, 281, 223, 397, 1999, 1277, 10891, 11351, 2459, 1567, 983, 577, 293, 1753, 269, 941, 15319, 487, 443, 2083, 1303, 3499, 18059, 2293, 601, 19211, 1523, 4079, 2663, 21611, 1409, 22859, 2897, 1907, 821, 26119, 3307, 27479, 28871, 2689, 1871, 479, 31019, 3923, 31751, 32491, 773, 523, 4297, 34759, 35531, 449, 3301, 1613, 4787, 38699, 39511, 499, 1301, 463, 521, 5197, 42839, 43691, 1103, 5623, 4129, 1433, 4289, 5953, 907, 1213, 3767, 3089, 1609, 10159, 51719, 593, 1423, 53591, 54539, 1009, 6997, 3559, 58411, 59399, 7487, 4723, 7993, 883, 13099, 2063, 4391, 14159, 71879, 823, 1697, 919, 74071, 5783, 9467, 15259, 739, 77419, 2437, 79691, 7349, 10177, 607, 2617, 17579, 5531, 641, 11213, 6947, 2273, 1459, 1709, 11827, 95239, 2053, 1193, 12457, 1543, 647, 6389, 102871, 1427, 13103, 13267, 9829, 109451, 2753, 4817, 13933, 112139, 22699, 114859, 2473, 3697, 937, 7481, 15137, 3929, 15313, 1549, 9587, 3917, 3407, 128939, 1013, 1291, 1669, 16573, 133319, 1289, 26959, 953, 2141, 137771, 3463, 1151, 761, 140779, 4423, 8941, 146891, 839, 148439, 4663, 4889, 13921, 1181, 9719, 1093, 1373, 159499, 2207, 162731, 20443, 1877, 33199, 3163, 10529, 4253, 15541, 172619, 3169, 175979, 4463, 991, 7873, 36559, 2087, 4987, 23173, 14327, 2339, 3547, 23827, 38299, 17569, 6067, 1931, 1901, 198599, 2267, 3083, 6581, 5563, 3259, 13151, 211339, 19381, 215051, 13499, 216919, 43759, 3023, 2131, 9677, 226379, 45659, 28657, 20929, 14449, 2797, 1637, 29383, 1223, 47599, 1867, 10433, 241931, 6073, 243911, 245899, 1187, 1153, 3889, 22901, 6323, 6863, 23269, 16061, 51599, 32377, 32633, 1759, 8521, 8287, 5023, 3037, 2333, 270379, 4241, 3449, 21283, 17491, 2203, 283051, 7103, 285191, 3253, 9013, 57899, 5503, 293831, 296011, 27109, 27509, 37963, 23447, 307031, 19259, 309259, 3527, 62299, 1699, 313739, 1789, 1627, 1297, 5869, 325079, 20389, 29761, 329671, 3181, 10709, 4261, 42223, 14737, 7937, 5351, 343639, 5323, 43397, 2879, 3361, 350731, 355499, 44587, 2309, 44887, 2837, 9803, 4549, 28087, 367559, 1487, 73999, 23201, 16193, 11677, 9403, 29027, 1279, 23971, 384779, 7307, 8293, 24439, 392279, 3433, 1597, 2351, 49823, 399851, 25229, 50777, 1381, 31543, 4111, 4733, 7883, 52387, 3229, 11503, 428231, 53693, 27011, 1933, 11003, 1571, 2531, 10453, 452171, 5669, 19777, 57367, 8369, 5861, 3257, 5839, 468491, 58733, 59077, 2017, 476759, 36887, 6607, 4651, 2137, 97579, 1439, 12373, 45121, 2393, 499159, 15643, 7723, 62927, 1723, 507691, 510551, 2909, 513419, 64717, 22573, 2503, 1531, 524971, 2861, 2003, 16633, 533719, 536651, 41507, 542539, 17093, 548459, 68743, 5059, 3877, 2801, 2687, 70237, 15227, 10687, 569431, 13313, 5519, 115099, 18127, 3061, 1559, 37021, 4153, 2677, 600071, 2347, 121259, 37991, 5591, 13033, 19861, 3389, 27457, 39569, 48823, 79537, 127579, 17327, 40169, 4703, 647531, 650759, 81547, 41179, 16553, 2683, 667019, 134059, 10499, 673579, 7673, 52067, 16963, 683479, 42821, 137359, 1831, 690119, 2011, 8689, 13147, 63649, 2371, 11071, 713611, 89413, 8167, 11083, 45131, 723799, 727211, 18223, 2953, 5281, 22993, 740939, 744391, 57527, 4259, 751319, 150959, 8597, 758279, 95003, 3947, 47939, 154459, 96757, 70529, 2113, 779351, 2441, 782891, 2281, 157999, 61043, 4519, 797131, 19973, 800711, 100313, 10181, 25303, 62423, 101663, 74101, 35597, 12821, 17497, 51511, 829639, 6361, 836951, 6553, 64663, 105767, 26557, 851671, 77761, 66083, 4679, 4013, 4157, 866519, 2467, 21803, 873991, 877739, 176299, 16703, 6217, 22273, 3319, 81509, 112787,

7. Distribution of the primes

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

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 : 199, 13, 11, 5, 1, 1, 31, 53, 101, 73, 661, 23, 809, 1, 1, 127, 47, 1, 241, 79,
Found in Database : 199, 13, 11, 5, 31, 53, 101, 73, 661, 23, 809, 127, 47, 241, 79, 1321, 43, 1429, 37, 139, 197, 1621, 109, 137, 227, 83, 401,
Found in Database : 5, 11, 13, 23, 31, 37, 43, 47, 53, 73, 79, 83, 101, 109, 127, 131, 137, 139, 149,