Inhaltsverzeichnis

Development of
Algorithmic Constructions

06:23:28
Deutsch
29.Mar 2024

Polynom = x^2-268x+683

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) = 683 = 683
f(1) = 13 = 13
f(2) = 151 = 151
f(3) = 7 = 7
f(4) = 373 = 373
f(5) = 79 = 79
f(6) = 889 = 7*127
f(7) = 143 = 11*13
f(8) = 1397 = 11*127
f(9) = 103 = 103
f(10) = 1897 = 7*271
f(11) = 67 = 67
f(12) = 2389 = 2389
f(13) = 329 = 7*47
f(14) = 2873 = 13*13*17
f(15) = 389 = 389
f(16) = 3349 = 17*197
f(17) = 7 = 7
f(18) = 3817 = 11*347
f(19) = 253 = 11*23
f(20) = 4277 = 7*13*47
f(21) = 563 = 563
f(22) = 4729 = 4729
f(23) = 619 = 619
f(24) = 5173 = 7*739
f(25) = 337 = 337
f(26) = 5609 = 71*79
f(27) = 91 = 7*13
f(28) = 6037 = 6037
f(29) = 781 = 11*71
f(30) = 6457 = 11*587
f(31) = 833 = 7*7*17
f(32) = 6869 = 6869
f(33) = 221 = 13*17
f(34) = 7273 = 7*1039
f(35) = 467 = 467
f(36) = 7669 = 7669
f(37) = 983 = 983
f(38) = 8057 = 7*1151
f(39) = 1031 = 1031
f(40) = 8437 = 11*13*59
f(41) = 539 = 7*7*11
f(42) = 8809 = 23*383
f(43) = 281 = 281
f(44) = 9173 = 9173
f(45) = 1169 = 7*167
f(46) = 9529 = 13*733
f(47) = 1213 = 1213
f(48) = 9877 = 7*17*83
f(49) = 157 = 157
f(50) = 10217 = 17*601
f(51) = 649 = 11*59
f(52) = 10549 = 7*11*137
f(53) = 1339 = 13*103
f(54) = 10873 = 83*131
f(55) = 1379 = 7*197
f(56) = 11189 = 67*167
f(57) = 709 = 709
f(58) = 11497 = 11497
f(59) = 91 = 7*13
f(60) = 11797 = 47*251
f(61) = 1493 = 1493
f(62) = 12089 = 7*11*157
f(63) = 1529 = 11*139
f(64) = 12373 = 12373
f(65) = 391 = 17*23
f(66) = 12649 = 7*13*139
f(67) = 799 = 17*47
f(68) = 12917 = 12917
f(69) = 1631 = 7*233
f(70) = 13177 = 13177
f(71) = 1663 = 1663
f(72) = 13429 = 13*1033
f(73) = 847 = 7*11*11
f(74) = 13673 = 11*11*113
f(75) = 431 = 431
f(76) = 13909 = 7*1987
f(77) = 1753 = 1753
f(78) = 14137 = 67*211
f(79) = 1781 = 13*137
f(80) = 14357 = 7*7*293
f(81) = 113 = 113
f(82) = 14569 = 17*857
f(83) = 917 = 7*131
f(84) = 14773 = 11*17*79
f(85) = 1859 = 11*13*13
f(86) = 14969 = 14969
f(87) = 1883 = 7*269
f(88) = 15157 = 23*659
f(89) = 953 = 953
f(90) = 15337 = 7*7*313
f(91) = 241 = 241
f(92) = 15509 = 13*1193
f(93) = 1949 = 1949
f(94) = 15673 = 7*2239
f(95) = 1969 = 11*179
f(96) = 15829 = 11*1439
f(97) = 497 = 7*71
f(98) = 15977 = 13*1229
f(99) = 1003 = 17*59
f(100) = 16117 = 71*227

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-268x+683

f(0)=683
f(1)=13
f(2)=151
f(3)=7
f(4)=373
f(5)=79
f(6)=127
f(7)=11
f(8)=1
f(9)=103
f(10)=271
f(11)=67
f(12)=2389
f(13)=47
f(14)=17
f(15)=389
f(16)=197
f(17)=1
f(18)=347
f(19)=23
f(20)=1
f(21)=563
f(22)=4729
f(23)=619
f(24)=739
f(25)=337
f(26)=71
f(27)=1
f(28)=6037
f(29)=1
f(30)=587
f(31)=1
f(32)=6869
f(33)=1
f(34)=1039
f(35)=467
f(36)=7669
f(37)=983
f(38)=1151
f(39)=1031
f(40)=59
f(41)=1
f(42)=383
f(43)=281
f(44)=9173
f(45)=167
f(46)=733
f(47)=1213
f(48)=83
f(49)=157
f(50)=601
f(51)=1
f(52)=137
f(53)=1
f(54)=131
f(55)=1
f(56)=1
f(57)=709
f(58)=11497
f(59)=1
f(60)=251
f(61)=1493
f(62)=1
f(63)=139
f(64)=12373
f(65)=1
f(66)=1
f(67)=1
f(68)=12917
f(69)=233
f(70)=13177
f(71)=1663
f(72)=1033
f(73)=1
f(74)=113
f(75)=431
f(76)=1987
f(77)=1753
f(78)=211
f(79)=1
f(80)=293
f(81)=1
f(82)=857
f(83)=1
f(84)=1
f(85)=1
f(86)=14969
f(87)=269
f(88)=659
f(89)=953
f(90)=313
f(91)=241
f(92)=1193
f(93)=1949
f(94)=2239
f(95)=179
f(96)=1439
f(97)=1
f(98)=1229
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2-268x+683 could be written as f(y)= y^2-17273 with x=y+134

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-134
f'(x)>2x-269 with x > 131

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

683, 13, 151, 7, 373, 79, 127, 11, 1, 103, 271, 67, 2389, 47, 17, 389, 197, 1, 347, 23, 1, 563, 4729, 619, 739, 337, 71, 1, 6037, 1, 587, 1, 6869, 1, 1039, 467, 7669, 983, 1151, 1031, 59, 1, 383, 281, 9173, 167, 733, 1213, 83, 157, 601, 1, 137, 1, 131, 1, 1, 709, 11497, 1, 251, 1493, 1, 139, 12373, 1, 1, 1, 12917, 233, 13177, 1663, 1033, 1, 113, 431, 1987, 1753, 211, 1, 293, 1, 857, 1, 1, 1, 14969, 269, 659, 953, 313, 241, 1193, 1949, 2239, 179, 1439, 1, 1229, 1, 227, 1, 16249, 2039, 2339, 1, 1499, 1, 2371, 2081, 283, 1, 163, 263, 359, 1, 997, 193, 1, 2131, 17077, 1069, 2447, 1, 1321, 307, 17209, 2153, 1567, 1, 17257, 1, 2467, 1, 751, 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, 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, 1223, 1, 1, 1, 1, 1, 1, 397, 3463, 1, 311, 1, 421, 1, 5227, 691, 1, 1, 379, 1, 1009, 461, 7691, 1, 757, 1, 8971, 1, 9623, 1, 1, 1327, 1, 1, 1, 1, 947, 1, 13003, 1669, 1, 1, 14411, 1, 2161, 1, 1, 2027, 1, 1, 1019, 1, 1063, 1153, 1, 1, 1, 1, 2909, 1297, 21143, 673, 1, 2791, 22727, 1, 23531, 1, 2213, 1, 25163, 1, 1, 3301, 1, 1, 1, 439, 2593, 1, 29383, 3727, 1, 1, 1831, 1973, 1, 4057, 2531, 1, 1, 2141, 1, 1, 1549, 1, 36551, 661, 37483, 593, 499, 1, 39371, 1, 823, 5101, 1, 1, 3251, 1, 521, 1, 4021, 5591, 1, 1429, 557, 1, 1, 1, 1, 1, 4481, 1, 853, 1, 1093, 1, 7489, 6619, 677, 1, 7793, 1, 1, 1, 56711, 1, 57803, 1, 1, 929, 8573, 1, 5557, 701, 8893, 1, 1, 571, 1, 1, 3863, 1, 3931, 1, 883, 2143, 69163, 8719, 773, 8867, 1, 1, 72727, 4583, 1, 1, 1, 1, 10909, 1, 77591, 1, 11261, 9931, 80071, 1, 7393, 1, 1, 743, 1181, 1, 12161, 1, 1, 5441, 1, 1, 89003, 1601, 6947, 1, 1553, 1, 92951, 5851, 13469, 1, 8693, 12037, 1979, 1, 98327, 1, 761, 12547, 101063, 1, 1, 1, 1, 1, 105227, 13241, 15233, 13417, 8311, 971, 1, 1, 1, 1993, 112327, 1087, 16253, 1789, 115223, 7247, 1, 1129, 1, 1, 119627, 7523, 1, 1, 9431, 907, 17729, 15607, 2129, 1, 1, 7993, 1013, 2311, 130183, 16369, 839, 1, 133271, 1, 1, 1, 1, 1319, 19709, 1, 2969, 1, 141131, 1, 10979, 1, 13121, 1, 20849, 2293, 11351, 1091, 21313, 1103, 150827, 1, 1, 1, 6701, 2767, 155783, 19577, 1, 1, 1, 4999, 22973, 1, 1, 2917, 1, 2579, 1, 1489, 167627, 21061, 1861, 21277, 1, 977, 3527, 1, 174571, 1, 176327, 1303, 178091, 1, 1373, 1, 1, 22817, 3109, 23041, 1, 11633, 14387, 1, 188843, 23719, 17333, 1, 1, 1511, 1, 12203, 196171, 1, 28289, 1913, 1459, 1, 18341, 3167, 203627, 1, 1361, 1, 29629, 1, 1, 1, 1, 2411, 3181, 3823, 215051, 1, 16691, 1, 218923, 27487, 1, 2521, 1, 1, 1889, 1, 13339, 1, 3877, 1, 1289, 2069, 21157, 1, 33533, 1, 18211, 1, 1483, 1, 1, 1, 18679, 1, 1, 4391, 246923, 15497, 35569, 1, 251051, 31511, 36161, 31771, 23201, 1, 3257, 1, 15259, 4651, 15383, 1427, 2897, 1, 1, 1, 1, 33619, 20771, 1, 272171, 8539, 1, 2459, 1, 1, 1, 1, 280843, 1, 40433, 1, 285227, 5113, 12497, 36067, 289643, 1, 1, 18311, 42013, 36901, 17431, 37181, 1, 18731, 300823, 1, 1, 3457, 305351, 1, 307627, 9649, 44273, 19441, 312203, 1, 1, 1, 1, 1, 319127, 10009, 1, 1, 1, 1, 46589, 2557, 2297, 1873, 1, 1, 4973, 1, 19739, 1619, 1, 1, 14797, 3881, 4451, 3307, 4861, 1, 1, 1, 349963, 6271, 27107, 44201, 32257, 1, 357271, 1, 1, 45119, 1, 45427, 1, 5717, 367127, 1, 33601, 1, 2677, 1, 374603, 1, 3169, 1, 1, 1, 1, 4357, 1, 1723, 3049, 24281, 8293, 6983, 1, 49201, 8059, 2251, 1571, 1, 57149, 1, 402631, 7213, 405227, 1, 1, 1, 37313, 4679, 59009, 51797, 415691, 1, 4597, 1, 24763, 7541, 24919, 1, 1, 1, 428951, 26893, 1, 54121, 434311, 1, 1, 27397, 1, 1, 9413, 1, 1847, 1, 5669, 7019, 1, 1, 34871, 5167, 5923, 1, 19949, 1, 35507, 3617, 1, 8317, 27479, 58567, 1, 1, 3011, 29633, 67933, 59617, 478343, 1, 3673, 30161, 483991, 1, 44257, 61031, 5381, 1, 492523, 1, 70769, 31051, 38327, 8923, 45557, 5711, 504011, 4513, 506903, 1, 1, 63907, 512711, 64271, 1, 1, 1, 4643, 521483, 1, 1, 9391, 1, 33053, 1, 16619, 48481, 1, 1, 67219, 3229, 1, 8093, 1999, 6569, 1, 1951, 6247, 7159, 1, 554263, 1, 79613, 3037, 2083, 1, 1, 1, 1, 1, 1, 1, 1, 71761, 44279, 36073, 1759, 18133, 3853, 1, 53173, 5639, 588011, 1, 591127, 2179, 3691, 1, 597383, 74869, 1, 1, 2861, 1, 46679, 1, 609991, 1, 613163, 19211, 1, 3511, 3313, 77641, 5233, 78041, 1, 1, 629143, 1, 632363, 11321, 57781, 1, 1, 10007, 642071, 40231, 92189, 1, 49891, 1, 9181, 1, 59557, 1, 50647, 82507, 94529, 1, 14149, 1, 1, 3221, 61057, 1, 39703, 1, 2347, 1, 681623, 1, 1997, 85831, 8713, 7841, 1, 5417, 6151, 6221, 6781, 87517, 53987, 1, 11953, 1, 9203, 1, 2647, 6863, 1, 1, 1877, 3217, 10781, 1, 1, 1, 66293, 91369,

6. Sequence of the polynom (only primes)

683, 13, 151, 7, 373, 79, 127, 11, 103, 271, 67, 2389, 47, 17, 389, 197, 347, 23, 563, 4729, 619, 739, 337, 71, 6037, 587, 6869, 1039, 467, 7669, 983, 1151, 1031, 59, 383, 281, 9173, 167, 733, 1213, 83, 157, 601, 137, 131, 709, 11497, 251, 1493, 139, 12373, 12917, 233, 13177, 1663, 1033, 113, 431, 1987, 1753, 211, 293, 857, 14969, 269, 659, 953, 313, 241, 1193, 1949, 2239, 179, 1439, 1229, 227, 16249, 2039, 2339, 1499, 2371, 2081, 283, 163, 263, 359, 997, 193, 2131, 17077, 1069, 2447, 1321, 307, 17209, 2153, 1567, 17257, 2467, 751, 1223, 397, 3463, 311, 421, 5227, 691, 379, 1009, 461, 7691, 757, 8971, 9623, 1327, 947, 13003, 1669, 14411, 2161, 2027, 1019, 1063, 1153, 2909, 1297, 21143, 673, 2791, 22727, 23531, 2213, 25163, 3301, 439, 2593, 29383, 3727, 1831, 1973, 4057, 2531, 2141, 1549, 36551, 661, 37483, 593, 499, 39371, 823, 5101, 3251, 521, 4021, 5591, 1429, 557, 4481, 853, 1093, 7489, 6619, 677, 7793, 56711, 57803, 929, 8573, 5557, 701, 8893, 571, 3863, 3931, 883, 2143, 69163, 8719, 773, 8867, 72727, 4583, 10909, 77591, 11261, 9931, 80071, 7393, 743, 1181, 12161, 5441, 89003, 1601, 6947, 1553, 92951, 5851, 13469, 8693, 12037, 1979, 98327, 761, 12547, 101063, 105227, 13241, 15233, 13417, 8311, 971, 1993, 112327, 1087, 16253, 1789, 115223, 7247, 1129, 119627, 7523, 9431, 907, 17729, 15607, 2129, 7993, 1013, 2311, 130183, 16369, 839, 133271, 1319, 19709, 2969, 141131, 10979, 13121, 20849, 2293, 11351, 1091, 21313, 1103, 150827, 6701, 2767, 155783, 19577, 4999, 22973, 2917, 2579, 1489, 167627, 21061, 1861, 21277, 977, 3527, 174571, 176327, 1303, 178091, 1373, 22817, 3109, 23041, 11633, 14387, 188843, 23719, 17333, 1511, 12203, 196171, 28289, 1913, 1459, 18341, 3167, 203627, 1361, 29629, 2411, 3181, 3823, 215051, 16691, 218923, 27487, 2521, 1889, 13339, 3877, 1289, 2069, 21157, 33533, 18211, 1483, 18679, 4391, 246923, 15497, 35569, 251051, 31511, 36161, 31771, 23201, 3257, 15259, 4651, 15383, 1427, 2897, 33619, 20771, 272171, 8539, 2459, 280843, 40433, 285227, 5113, 12497, 36067, 289643, 18311, 42013, 36901, 17431, 37181, 18731, 300823, 3457, 305351, 307627, 9649, 44273, 19441, 312203, 319127, 10009, 46589, 2557, 2297, 1873, 4973, 19739, 1619, 14797, 3881, 4451, 3307, 4861, 349963, 6271, 27107, 44201, 32257, 357271, 45119, 45427, 5717, 367127, 33601, 2677, 374603, 3169, 4357, 1723, 3049, 24281, 8293, 6983, 49201, 8059, 2251, 1571, 57149, 402631, 7213, 405227, 37313, 4679, 59009, 51797, 415691, 4597, 24763, 7541, 24919, 428951, 26893, 54121, 434311, 27397, 9413, 1847, 5669, 7019, 34871, 5167, 5923, 19949, 35507, 3617, 8317, 27479, 58567, 3011, 29633, 67933, 59617, 478343, 3673, 30161, 483991, 44257, 61031, 5381, 492523, 70769, 31051, 38327, 8923, 45557, 5711, 504011, 4513, 506903, 63907, 512711, 64271, 4643, 521483, 9391, 33053, 16619, 48481, 67219, 3229, 8093, 1999, 6569, 1951, 6247, 7159, 554263, 79613, 3037, 2083, 71761, 44279, 36073, 1759, 18133, 3853, 53173, 5639, 588011, 591127, 2179, 3691, 597383, 74869, 2861, 46679, 609991, 613163, 19211, 3511, 3313, 77641, 5233, 78041, 629143, 632363, 11321, 57781, 10007, 642071, 40231, 92189, 49891, 9181, 59557, 50647, 82507, 94529, 14149, 3221, 61057, 39703, 2347, 681623, 1997, 85831, 8713, 7841, 5417, 6151, 6221, 6781, 87517, 53987, 11953, 9203, 2647, 6863, 1877, 3217, 10781, 66293, 91369,

7. Distribution of the primes

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

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 : 683, 13, 151, 7, 373, 79, 127, 11, 1, 103, 271, 67, 2389, 47, 17, 389, 197, 1, 347, 23,
Found in Database : 683, 13, 151, 7, 373, 79, 127, 11, 103, 271, 67, 2389, 47, 17, 389, 197, 347, 23, 563, 4729, 619, 739, 337, 71, 6037, 587, 6869, 1039, 467, 7669, 983, 1151, 1031,
Found in Database : 7, 11, 13, 17, 23, 47, 59, 67, 71, 79, 83, 103, 113, 127, 131, 137, 139,