Inhaltsverzeichnis

Development of
Algorithmic Constructions

21:55:20
Deutsch
28.Mar 2024

Polynom = x^2+16x-193

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) = 193 = 193
f(1) = 11 = 11
f(2) = 157 = 157
f(3) = 17 = 17
f(4) = 113 = 113
f(5) = 11 = 11
f(6) = 61 = 61
f(7) = 1 = 1
f(8) = 1 = 1
f(9) = 1 = 1
f(10) = 67 = 67
f(11) = 13 = 13
f(12) = 143 = 11*13
f(13) = 23 = 23
f(14) = 227 = 227
f(15) = 17 = 17
f(16) = 319 = 11*29
f(17) = 23 = 23
f(18) = 419 = 419
f(19) = 59 = 59
f(20) = 527 = 17*31
f(21) = 73 = 73
f(22) = 643 = 643
f(23) = 11 = 11
f(24) = 767 = 13*59
f(25) = 13 = 13
f(26) = 899 = 29*31
f(27) = 121 = 11*11
f(28) = 1039 = 1039
f(29) = 139 = 139
f(30) = 1187 = 1187
f(31) = 79 = 79
f(32) = 1343 = 17*79
f(33) = 89 = 89
f(34) = 1507 = 11*137
f(35) = 199 = 199
f(36) = 1679 = 23*73
f(37) = 221 = 13*17
f(38) = 1859 = 11*13*13
f(39) = 61 = 61
f(40) = 2047 = 23*89
f(41) = 67 = 67
f(42) = 2243 = 2243
f(43) = 293 = 293
f(44) = 2447 = 2447
f(45) = 319 = 11*29
f(46) = 2659 = 2659
f(47) = 173 = 173
f(48) = 2879 = 2879
f(49) = 187 = 11*17
f(50) = 3107 = 13*239
f(51) = 403 = 13*31
f(52) = 3343 = 3343
f(53) = 433 = 433
f(54) = 3587 = 17*211
f(55) = 29 = 29
f(56) = 3839 = 11*349
f(57) = 31 = 31
f(58) = 4099 = 4099
f(59) = 529 = 23*23
f(60) = 4367 = 11*397
f(61) = 563 = 563
f(62) = 4643 = 4643
f(63) = 299 = 13*23
f(64) = 4927 = 13*379
f(65) = 317 = 317
f(66) = 5219 = 17*307
f(67) = 671 = 11*61
f(68) = 5519 = 5519
f(69) = 709 = 709
f(70) = 5827 = 5827
f(71) = 187 = 11*17
f(72) = 6143 = 6143
f(73) = 197 = 197
f(74) = 6467 = 29*223
f(75) = 829 = 829
f(76) = 6799 = 13*523
f(77) = 871 = 13*67
f(78) = 7139 = 11*11*59
f(79) = 457 = 457
f(80) = 7487 = 7487
f(81) = 479 = 479
f(82) = 7843 = 11*23*31
f(83) = 1003 = 17*59
f(84) = 8207 = 29*283
f(85) = 1049 = 1049
f(86) = 8579 = 23*373
f(87) = 137 = 137
f(88) = 8959 = 17*17*31
f(89) = 143 = 11*13
f(90) = 9347 = 13*719
f(91) = 1193 = 1193
f(92) = 9743 = 9743
f(93) = 1243 = 11*113
f(94) = 10147 = 73*139
f(95) = 647 = 647
f(96) = 10559 = 10559
f(97) = 673 = 673
f(98) = 10979 = 10979
f(99) = 1399 = 1399
f(100) = 11407 = 11*17*61

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+16x-193

f(0)=193
f(1)=11
f(2)=157
f(3)=17
f(4)=113
f(5)=1
f(6)=61
f(7)=1
f(8)=1
f(9)=1
f(10)=67
f(11)=13
f(12)=1
f(13)=23
f(14)=227
f(15)=1
f(16)=29
f(17)=1
f(18)=419
f(19)=59
f(20)=31
f(21)=73
f(22)=643
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1039
f(29)=139
f(30)=1187
f(31)=79
f(32)=1
f(33)=89
f(34)=137
f(35)=199
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=2243
f(43)=293
f(44)=2447
f(45)=1
f(46)=2659
f(47)=173
f(48)=2879
f(49)=1
f(50)=239
f(51)=1
f(52)=3343
f(53)=433
f(54)=211
f(55)=1
f(56)=349
f(57)=1
f(58)=4099
f(59)=1
f(60)=397
f(61)=563
f(62)=4643
f(63)=1
f(64)=379
f(65)=317
f(66)=307
f(67)=1
f(68)=5519
f(69)=709
f(70)=5827
f(71)=1
f(72)=6143
f(73)=197
f(74)=223
f(75)=829
f(76)=523
f(77)=1
f(78)=1
f(79)=457
f(80)=7487
f(81)=479
f(82)=1
f(83)=1
f(84)=283
f(85)=1049
f(86)=373
f(87)=1
f(88)=1
f(89)=1
f(90)=719
f(91)=1193
f(92)=9743
f(93)=1
f(94)=1
f(95)=647
f(96)=10559
f(97)=673
f(98)=10979
f(99)=1399

b) Substitution of the polynom
The polynom f(x)=x^2+16x-193 could be written as f(y)= y^2-257 with x=y-8

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+8
f'(x)>2x+15

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

193, 11, 157, 17, 113, 1, 61, 1, 1, 1, 67, 13, 1, 23, 227, 1, 29, 1, 419, 59, 31, 73, 643, 1, 1, 1, 1, 1, 1039, 139, 1187, 79, 1, 89, 137, 199, 1, 1, 1, 1, 1, 1, 2243, 293, 2447, 1, 2659, 173, 2879, 1, 239, 1, 3343, 433, 211, 1, 349, 1, 4099, 1, 397, 563, 4643, 1, 379, 317, 307, 1, 5519, 709, 5827, 1, 6143, 197, 223, 829, 523, 1, 1, 457, 7487, 479, 1, 1, 283, 1049, 373, 1, 1, 1, 719, 1193, 9743, 1, 1, 647, 10559, 673, 10979, 1399, 1, 1453, 911, 1, 1117, 1, 12739, 1621, 1, 1, 1, 1, 14143, 1, 14627, 1, 1163, 1, 15619, 1, 16127, 1, 1, 2113, 17167, 2179, 1609, 1123, 1, 1, 18787, 2383, 1, 1, 1171, 631, 20479, 1, 21059, 1, 21647, 1, 1, 1409, 1, 1447, 23459, 2971, 1, 3049, 797, 1, 25343, 401, 1999, 1, 1567, 3371, 27299, 1, 27967, 1, 28643, 3623, 29327, 3709, 2729, 1, 1, 971, 2857, 1, 32143, 1, 1429, 1, 33599, 1, 1493, 4339, 2699, 1, 491, 1, 36607, 1, 37379, 4721, 3469, 1, 1, 2459, 3613, 1, 3119, 5119, 701, 1, 42179, 1, 1483, 1, 2579, 503, 44687, 5639, 1, 1, 46399, 2927, 4297, 1, 1553, 6073, 4457, 773, 49919, 787, 571, 1, 1, 593, 863, 3319, 1, 1, 54499, 6871, 55439, 241, 499, 1777, 1, 1, 1, 7349, 1, 1, 60259, 3797, 839, 1, 929, 1, 63247, 613, 4943, 1, 2251, 257, 1087, 8353, 67343, 1, 6217, 1, 69439, 4373, 1, 683, 1213, 9013, 72643, 2287, 73727, 1, 3253, 9421, 1, 1, 1, 1, 6011, 4919, 2557, 587, 7309, 1, 1217, 1283, 7517, 1301, 83843, 1, 1, 823, 86179, 1, 87359, 1, 88547, 1013, 5279, 1, 90947, 2861, 1, 1, 653, 1, 1063, 11903, 8713, 6029, 5711, 1, 3391, 1, 727, 1, 7759, 1, 4441, 1, 1753, 13009, 1, 13171, 106019, 1, 887, 1, 108643, 1051, 769, 13829, 6547, 3499, 1543, 3541, 3677, 1303, 115343, 14503, 116707, 1, 1, 1, 7027, 1, 120847, 15193, 11113, 1, 2027, 1, 11369, 1, 1601, 1223, 9839, 8039, 1, 739, 130787, 967, 1, 1511, 5813, 4201, 7951, 1, 1, 1321, 1, 17359, 139619, 1, 12829, 8867, 1, 17923, 1, 1, 5023, 1, 1, 1, 2521, 1699, 150287, 821, 1, 9539, 153407, 1, 1, 19471, 12043, 1, 1307, 4967, 5153, 1, 9491, 20269, 1831, 1861, 5309, 10337, 166207, 1, 12911, 1, 7369, 1, 10067, 2687, 1, 2713, 174467, 1289, 1, 22123, 13679, 859, 179519, 11273, 181219, 2069, 182927, 22973, 6367, 1, 1, 5851, 2381, 1, 1, 1, 17417, 1, 1, 1, 17737, 24499, 196879, 1, 198659, 1559, 907, 1, 202243, 1, 204047, 1, 1481, 12923, 207679, 13037, 9109, 1, 19213, 1, 1, 6691, 1, 1, 216899, 1, 7057, 947, 12979, 1259, 222527, 13967, 1, 1, 997, 28409, 1, 3581, 230143, 1, 1, 29129, 1109, 1277, 1, 1, 1, 14929, 239843, 30103, 241807, 1, 1, 7649, 245759, 1, 8543, 1, 19211, 2411, 4127, 15797, 1, 15923, 1867, 32099, 1019, 32353, 1319, 1, 261887, 1, 1, 3011, 15647, 1151, 4001, 1, 270143, 1, 272227, 34159, 8849, 34421, 1933, 1, 1249, 8737, 1, 1531, 282767, 2087, 284899, 1, 1201, 1637, 17011, 2791, 1, 3323, 293507, 4603, 1, 4637, 10271, 37369, 27277, 37643, 1, 18959, 2129, 1, 1, 1, 10651, 38749, 5273, 1, 313343, 1, 1, 1, 317839, 3067, 24623, 1181, 1, 20219, 2683, 1, 19231, 1783, 1, 1, 331519, 1, 25679, 3221, 336143, 3833, 3803, 21227, 20047, 1, 11069, 1, 345487, 2549, 2539, 1, 1, 1, 352579, 44221, 1, 44519, 357347, 22409, 15641, 1327, 362147, 4129, 1, 3517, 21587, 1, 369407, 5791, 371843, 46633, 374287, 1, 1, 23623, 379199, 1, 1, 2081, 384143, 1, 6553, 1, 6379, 1, 391619, 49109, 5399, 4493, 2347, 1913, 1, 1, 1, 2963, 36749, 1, 2591, 1, 1, 1, 17909, 1, 31883, 51971, 18133, 2377, 13537, 26309, 422243, 4813, 1, 53269, 13789, 13399, 33083, 1, 1, 1, 435343, 54583, 1373, 27457, 4951, 1, 3923, 55579, 445967, 1, 34511, 1, 1, 1, 1571, 56921, 7741, 57259, 459427, 1, 42013, 1, 35759, 4483, 42509, 1, 1, 14741, 1, 14827, 4211, 1, 20809, 59999, 481379, 1, 37243, 30347, 486947, 61043, 489743, 1, 44777, 1, 495359, 3881, 45289, 1, 2267, 4831, 16253, 1, 506687, 2887, 1, 2777, 16529, 5839, 8447, 1, 1, 1, 3083, 65309, 47629, 3863, 1, 1, 48157, 33199, 18367, 66763, 3853, 67129, 1801, 1, 541439, 1, 23669, 6203, 9277, 2213, 32371, 34487, 553279, 34673, 1, 1, 43019, 2417, 1, 1, 565247, 1, 33427, 1, 571279, 1, 574307, 1, 1, 1, 1663, 72739, 3023, 73121, 586499, 2297, 53597, 2309, 592643, 1, 1747, 5743, 1, 1, 35407, 37717, 1, 1, 1, 76213, 2897, 1741, 26713, 19249, 1, 5953, 1, 77783, 56713, 39089, 1, 2311, 1, 1, 633359, 1, 636547, 1, 49211, 1, 642947, 1, 646159, 1, 649379, 1, 652607, 1, 1, 82183, 1, 6353, 662339, 20749, 60509, 1, 668867, 83813, 672143, 84223, 1, 3847, 678719, 3271, 2281, 1, 2339, 1, 1, 5393, 9479, 5419, 2039, 87121, 24091, 87539, 4909, 1, 1, 44189, 7963, 88799, 41887, 8111, 24671, 1, 718847, 1, 722243, 6961, 55819, 1, 729059, 45673, 3917, 45887, 12473, 92203, 67213, 5449, 1871, 11633, 1, 1, 1, 8539, 12347, 1, 1, 1, 33049, 2801, 763619, 3299, 33353, 7393, 1, 24137, 774143, 24247, 6427, 97429, 781199, 97871, 3457, 49157, 788287, 1, 3583, 1, 7039, 9059, 27551, 1, 25889, 1, 3373, 4391, 73613, 1, 26237, 3919, 1, 1, 3889, 6047, 10433, 1, 827843, 2357, 1, 26041, 835139, 9511, 1, 1, 36629, 52769, 1, 52999, 3359, 3671, 50207, 106921, 77929, 1, 860927, 1, 1, 1, 5531, 1, 872099, 54623, 6301, 4987, 9883, 110183, 883343, 1, 68239, 2137, 80989, 1, 52627, 112069, 81677, 112543, 1, 56509, 1, 56747, 909859, 1, 1, 1, 1, 1, 3823, 7213, 1, 1, 1, 116371, 84809, 58427, 1, 4513, 85513, 1997, 944527, 1, 4253, 1, 16141, 2711, 13099, 119773, 56479, 1, 74159, 1, 967999, 60623, 971939, 1, 1, 3943, 16063, 1, 5261, 1, 75983, 1, 1, 7307, 995747, 5669, 1, 1, 1003747, 1, 1007759, 1, 1011779, 2437,

6. Sequence of the polynom (only primes)

193, 11, 157, 17, 113, 61, 67, 13, 23, 227, 29, 419, 59, 31, 73, 643, 1039, 139, 1187, 79, 89, 137, 199, 2243, 293, 2447, 2659, 173, 2879, 239, 3343, 433, 211, 349, 4099, 397, 563, 4643, 379, 317, 307, 5519, 709, 5827, 6143, 197, 223, 829, 523, 457, 7487, 479, 283, 1049, 373, 719, 1193, 9743, 647, 10559, 673, 10979, 1399, 1453, 911, 1117, 12739, 1621, 14143, 14627, 1163, 15619, 16127, 2113, 17167, 2179, 1609, 1123, 18787, 2383, 1171, 631, 20479, 21059, 21647, 1409, 1447, 23459, 2971, 3049, 797, 25343, 401, 1999, 1567, 3371, 27299, 27967, 28643, 3623, 29327, 3709, 2729, 971, 2857, 32143, 1429, 33599, 1493, 4339, 2699, 491, 36607, 37379, 4721, 3469, 2459, 3613, 3119, 5119, 701, 42179, 1483, 2579, 503, 44687, 5639, 46399, 2927, 4297, 1553, 6073, 4457, 773, 49919, 787, 571, 593, 863, 3319, 54499, 6871, 55439, 241, 499, 1777, 7349, 60259, 3797, 839, 929, 63247, 613, 4943, 2251, 257, 1087, 8353, 67343, 6217, 69439, 4373, 683, 1213, 9013, 72643, 2287, 73727, 3253, 9421, 6011, 4919, 2557, 587, 7309, 1217, 1283, 7517, 1301, 83843, 823, 86179, 87359, 88547, 1013, 5279, 90947, 2861, 653, 1063, 11903, 8713, 6029, 5711, 3391, 727, 7759, 4441, 1753, 13009, 13171, 106019, 887, 108643, 1051, 769, 13829, 6547, 3499, 1543, 3541, 3677, 1303, 115343, 14503, 116707, 7027, 120847, 15193, 11113, 2027, 11369, 1601, 1223, 9839, 8039, 739, 130787, 967, 1511, 5813, 4201, 7951, 1321, 17359, 139619, 12829, 8867, 17923, 5023, 2521, 1699, 150287, 821, 9539, 153407, 19471, 12043, 1307, 4967, 5153, 9491, 20269, 1831, 1861, 5309, 10337, 166207, 12911, 7369, 10067, 2687, 2713, 174467, 1289, 22123, 13679, 859, 179519, 11273, 181219, 2069, 182927, 22973, 6367, 5851, 2381, 17417, 17737, 24499, 196879, 198659, 1559, 907, 202243, 204047, 1481, 12923, 207679, 13037, 9109, 19213, 6691, 216899, 7057, 947, 12979, 1259, 222527, 13967, 997, 28409, 3581, 230143, 29129, 1109, 1277, 14929, 239843, 30103, 241807, 7649, 245759, 8543, 19211, 2411, 4127, 15797, 15923, 1867, 32099, 1019, 32353, 1319, 261887, 3011, 15647, 1151, 4001, 270143, 272227, 34159, 8849, 34421, 1933, 1249, 8737, 1531, 282767, 2087, 284899, 1201, 1637, 17011, 2791, 3323, 293507, 4603, 4637, 10271, 37369, 27277, 37643, 18959, 2129, 10651, 38749, 5273, 313343, 317839, 3067, 24623, 1181, 20219, 2683, 19231, 1783, 331519, 25679, 3221, 336143, 3833, 3803, 21227, 20047, 11069, 345487, 2549, 2539, 352579, 44221, 44519, 357347, 22409, 15641, 1327, 362147, 4129, 3517, 21587, 369407, 5791, 371843, 46633, 374287, 23623, 379199, 2081, 384143, 6553, 6379, 391619, 49109, 5399, 4493, 2347, 1913, 2963, 36749, 2591, 17909, 31883, 51971, 18133, 2377, 13537, 26309, 422243, 4813, 53269, 13789, 13399, 33083, 435343, 54583, 1373, 27457, 4951, 3923, 55579, 445967, 34511, 1571, 56921, 7741, 57259, 459427, 42013, 35759, 4483, 42509, 14741, 14827, 4211, 20809, 59999, 481379, 37243, 30347, 486947, 61043, 489743, 44777, 495359, 3881, 45289, 2267, 4831, 16253, 506687, 2887, 2777, 16529, 5839, 8447, 3083, 65309, 47629, 3863, 48157, 33199, 18367, 66763, 3853, 67129, 1801, 541439, 23669, 6203, 9277, 2213, 32371, 34487, 553279, 34673, 43019, 2417, 565247, 33427, 571279, 574307, 1663, 72739, 3023, 73121, 586499, 2297, 53597, 2309, 592643, 1747, 5743, 35407, 37717, 76213, 2897, 1741, 26713, 19249, 5953, 77783, 56713, 39089, 2311, 633359, 636547, 49211, 642947, 646159, 649379, 652607, 82183, 6353, 662339, 20749, 60509, 668867, 83813, 672143, 84223, 3847, 678719, 3271, 2281, 2339, 5393, 9479, 5419, 2039, 87121, 24091, 87539, 4909, 44189, 7963, 88799, 41887, 8111, 24671, 718847, 722243, 6961, 55819, 729059, 45673, 3917, 45887, 12473, 92203, 67213, 5449, 1871, 11633, 8539, 12347, 33049, 2801, 763619, 3299, 33353, 7393, 24137, 774143, 24247, 6427, 97429, 781199, 97871, 3457, 49157, 788287, 3583, 7039, 9059, 27551, 25889, 3373, 4391, 73613, 26237, 3919, 3889, 6047, 10433, 827843, 2357, 26041, 835139, 9511, 36629, 52769, 52999, 3359, 3671, 50207, 106921, 77929, 860927, 5531, 872099, 54623, 6301, 4987, 9883, 110183, 883343, 68239, 2137, 80989, 52627, 112069, 81677, 112543, 56509, 56747, 909859, 3823, 7213, 116371, 84809, 58427, 4513, 85513, 1997, 944527, 4253, 16141, 2711, 13099, 119773, 56479, 74159, 967999, 60623, 971939, 3943, 16063, 5261, 75983, 7307, 995747, 5669, 1003747, 1007759, 1011779, 2437,

7. Distribution of the primes

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

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

A B C D E F G H
exponent
=log2 (x)
<=x number
of all primes
number of primes
p = f(x)
number of primes
p | f(x)
C / x D / x E / x
1 2 3 2 1 1.5 1 0.5
2 4 5 3 2 1.25 0.75 0.5
3 8 6 4 2 0.75 0.5 0.25
4 16 11 6 5 0.6875 0.375 0.3125
5 32 20 10 10 0.625 0.3125 0.3125
6 64 39 17 22 0.609375 0.265625 0.34375
7 128 78 30 48 0.609375 0.234375 0.375
8 256 161 54 107 0.62890625 0.2109375 0.41796875
9 512 330 88 242 0.64453125 0.171875 0.47265625
10 1024 670 155 515 0.65429688 0.15136719 0.50292969
11 2048 1353 292 1061 0.66064453 0.14257813 0.51806641
12 4096 2715 521 2194 0.6628418 0.12719727 0.53564453
13 8192 5443 966 4477 0.66442871 0.11791992 0.54650879
14 16384 10923 1755 9168 0.66668701 0.1071167 0.55957031
15 32768 21917 3219 18698 0.66885376 0.09823608 0.57061768
16 65536 43991 5965 38026 0.67124939 0.09101868 0.58023071
17 131072 88224 11099 77125 0.6730957 0.08467865 0.58841705
18 262144 176564 20824 155740 0.67353821 0.07943726 0.59410095
19 524288 353772 39220 314552 0.67476654 0.07480621 0.59996033
20 1048576 708386 74193 634193 0.67556953 0.07075596 0.60481358
21 2097152 1418555 140422 1278133 0.67641973 0.06695843 0.60946131
22 4194304 2840018 267098 2572920 0.67711306 0.06368113 0.61343193
23 8388608 5685808 509398 5176410 0.67780113 0.06072497 0.61707616
24 16777216 11382395 972789 10409606 0.67844361 0.05798274 0.62046087


8. Check for existing Integer Sequences by OEIS

Found in Database : 193, 11, 157, 17, 113, 1, 61, 1, 1, 1, 67, 13, 1, 23, 227, 1, 29, 1, 419, 59,
Found in Database : 193, 11, 157, 17, 113, 61, 67, 13, 23, 227, 29, 419, 59, 31, 73, 643, 1039, 139, 1187, 79, 89, 137, 199,
Found in Database : 11, 13, 17, 23, 29, 31, 59, 61, 67, 73, 79, 89, 113, 137, 139,