Inhaltsverzeichnis

Development of
Algorithmic Constructions

15:46:29
Deutsch
28.Mar 2024

Polynom = x^2-156x+347

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) = 347 = 347
f(1) = 3 = 3
f(2) = 39 = 3*13
f(3) = 7 = 7
f(4) = 261 = 3*3*29
f(5) = 51 = 3*17
f(6) = 553 = 7*79
f(7) = 87 = 3*29
f(8) = 837 = 3*3*3*31
f(9) = 61 = 61
f(10) = 1113 = 3*7*53
f(11) = 39 = 3*13
f(12) = 1381 = 1381
f(13) = 189 = 3*3*3*7
f(14) = 1641 = 3*547
f(15) = 221 = 13*17
f(16) = 1893 = 3*631
f(17) = 63 = 3*3*7
f(18) = 2137 = 2137
f(19) = 141 = 3*47
f(20) = 2373 = 3*7*113
f(21) = 311 = 311
f(22) = 2601 = 3*3*17*17
f(23) = 339 = 3*113
f(24) = 2821 = 7*13*31
f(25) = 183 = 3*61
f(26) = 3033 = 3*3*337
f(27) = 49 = 7*7
f(28) = 3237 = 3*13*83
f(29) = 417 = 3*139
f(30) = 3433 = 3433
f(31) = 441 = 3*3*7*7
f(32) = 3621 = 3*17*71
f(33) = 29 = 29
f(34) = 3801 = 3*7*181
f(35) = 243 = 3*3*3*3*3
f(36) = 3973 = 29*137
f(37) = 507 = 3*13*13
f(38) = 4137 = 3*7*197
f(39) = 527 = 17*31
f(40) = 4293 = 3*3*3*3*53
f(41) = 273 = 3*7*13
f(42) = 4441 = 4441
f(43) = 141 = 3*47
f(44) = 4581 = 3*3*509
f(45) = 581 = 7*83
f(46) = 4713 = 3*1571
f(47) = 597 = 3*199
f(48) = 4837 = 7*691
f(49) = 153 = 3*3*17
f(50) = 4953 = 3*13*127
f(51) = 313 = 313
f(52) = 5061 = 3*7*241
f(53) = 639 = 3*3*71
f(54) = 5161 = 13*397
f(55) = 651 = 3*7*31
f(56) = 5253 = 3*17*103
f(57) = 331 = 331
f(58) = 5337 = 3*3*593
f(59) = 21 = 3*7
f(60) = 5413 = 5413
f(61) = 681 = 3*227
f(62) = 5481 = 3*3*3*7*29
f(63) = 689 = 13*53
f(64) = 5541 = 3*1847
f(65) = 87 = 3*29
f(66) = 5593 = 7*17*47
f(67) = 351 = 3*3*3*13
f(68) = 5637 = 3*1879
f(69) = 707 = 7*101
f(70) = 5673 = 3*31*61
f(71) = 711 = 3*3*79
f(72) = 5701 = 5701
f(73) = 357 = 3*7*17
f(74) = 5721 = 3*1907
f(75) = 179 = 179
f(76) = 5733 = 3*3*7*7*13
f(77) = 717 = 3*239
f(78) = 5737 = 5737
f(79) = 717 = 3*239
f(80) = 5733 = 3*3*7*7*13
f(81) = 179 = 179
f(82) = 5721 = 3*1907
f(83) = 357 = 3*7*17
f(84) = 5701 = 5701
f(85) = 711 = 3*3*79
f(86) = 5673 = 3*31*61
f(87) = 707 = 7*101
f(88) = 5637 = 3*1879
f(89) = 351 = 3*3*3*13
f(90) = 5593 = 7*17*47
f(91) = 87 = 3*29
f(92) = 5541 = 3*1847
f(93) = 689 = 13*53
f(94) = 5481 = 3*3*3*7*29
f(95) = 681 = 3*227
f(96) = 5413 = 5413
f(97) = 21 = 3*7
f(98) = 5337 = 3*3*593
f(99) = 331 = 331
f(100) = 5253 = 3*17*103

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-156x+347

f(0)=347
f(1)=3
f(2)=13
f(3)=7
f(4)=29
f(5)=17
f(6)=79
f(7)=1
f(8)=31
f(9)=61
f(10)=53
f(11)=1
f(12)=1381
f(13)=1
f(14)=547
f(15)=1
f(16)=631
f(17)=1
f(18)=2137
f(19)=47
f(20)=113
f(21)=311
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=337
f(27)=1
f(28)=83
f(29)=139
f(30)=3433
f(31)=1
f(32)=71
f(33)=1
f(34)=181
f(35)=1
f(36)=137
f(37)=1
f(38)=197
f(39)=1
f(40)=1
f(41)=1
f(42)=4441
f(43)=1
f(44)=509
f(45)=1
f(46)=1571
f(47)=199
f(48)=691
f(49)=1
f(50)=127
f(51)=313
f(52)=241
f(53)=1
f(54)=397
f(55)=1
f(56)=103
f(57)=331
f(58)=593
f(59)=1
f(60)=5413
f(61)=227
f(62)=1
f(63)=1
f(64)=1847
f(65)=1
f(66)=1
f(67)=1
f(68)=1879
f(69)=101
f(70)=1
f(71)=1
f(72)=5701
f(73)=1
f(74)=1907
f(75)=179
f(76)=1
f(77)=239
f(78)=5737
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-156x+347 could be written as f(y)= y^2-5737 with x=y+78

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-78
f'(x)>2x-157 with x > 76

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

347, 3, 13, 7, 29, 17, 79, 1, 31, 61, 53, 1, 1381, 1, 547, 1, 631, 1, 2137, 47, 113, 311, 1, 1, 1, 1, 337, 1, 83, 139, 3433, 1, 71, 1, 181, 1, 137, 1, 197, 1, 1, 1, 4441, 1, 509, 1, 1571, 199, 691, 1, 127, 313, 241, 1, 397, 1, 103, 331, 593, 1, 5413, 227, 1, 1, 1847, 1, 1, 1, 1879, 101, 1, 1, 5701, 1, 1907, 179, 1, 239, 5737, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1319, 1, 1, 229, 223, 1, 1, 1, 1, 1, 1033, 1, 1, 1, 1289, 1, 1, 1, 359, 1, 1693, 661, 1, 1, 5927, 1, 1, 823, 2269, 293, 1, 1, 1, 1, 2729, 1, 8663, 1, 3049, 587, 1, 1, 10139, 433, 1, 1, 1, 1, 1, 1, 4073, 1, 4253, 1, 1901, 283, 4621, 1, 1, 613, 1, 1, 577, 1, 317, 1, 16763, 1, 827, 1, 461, 1, 2657, 1, 1, 349, 2207, 1, 20507, 1, 2351, 1, 1039, 1, 1, 1, 1103, 1, 7949, 1, 463, 1, 1, 457, 1, 1, 1, 563, 1, 3469, 1, 1187, 28859, 1, 1, 937, 1, 1, 1831, 1, 1, 1009, 3631, 1, 683, 1, 1, 619, 11689, 739, 35879, 1, 941, 4639, 1787, 1, 1, 1, 1867, 2477, 4451, 1, 1, 1723, 4643, 1, 14221, 449, 6221, 1, 14813, 1, 1, 1, 1, 1, 1, 5953, 1, 1, 49019, 1031, 1, 1, 1, 2141, 1, 727, 17609, 1, 1, 1, 54779, 1, 641, 541, 1, 1193, 947, 607, 1, 7411, 643, 1, 4679, 1, 1213, 557, 1613, 881, 9137, 2687, 21673, 1, 1049, 1, 1429, 1, 7583, 8599, 797, 1, 70439, 1, 3407, 9013, 1, 1, 1, 1549, 1, 1, 1, 1, 5939, 1, 8707, 2467, 1, 1669, 1, 1129, 1, 1, 27689, 1, 84263, 1, 919, 1, 9631, 3637, 1, 1, 3301, 1, 1, 1, 907, 1, 2381, 5843, 1, 1, 1, 4001, 4603, 12163, 10883, 1, 14177, 2081, 11171, 1, 1997, 4271, 1453, 1, 1201, 1, 5039, 1, 8243, 4493, 5167, 853, 1, 1, 111227, 4663, 12511, 1, 37993, 2389, 16481, 1, 38921, 14683, 1, 1, 1, 1, 761, 7607, 1, 733, 123863, 1, 1, 7877, 1, 1, 1409, 1, 1, 1, 43721, 1, 132647, 1, 1, 1297, 2153, 5683, 137147, 1, 1, 4357, 1, 839, 141719, 1979, 1, 1, 1, 1, 1, 6131, 3793, 1, 1, 1, 8887, 1, 16963, 19183, 51421, 1, 1973, 1, 7499, 1, 1, 2221, 22961, 1, 54121, 1, 18223, 1, 12743, 991, 6197, 21019, 1, 1, 10039, 1, 1, 21649, 58013, 1, 5669, 1, 59149, 1, 1171, 1, 25841, 7573, 1, 1, 8779, 1, 186107, 1, 4817, 23593, 2039, 1, 14723, 2003, 9199, 1427, 1, 8161, 28109, 1, 22063, 1, 3929, 8387, 1, 1, 1447, 12809, 9803, 1, 3919, 8693, 1, 1, 1, 1, 213287, 4463, 1, 1, 1019, 1, 31277, 1, 73613, 1, 10607, 1, 1, 1, 1607, 1, 25391, 1, 1, 9643, 1, 29173, 78121, 4903, 1, 1, 79433, 4273, 1, 1117, 14251, 1, 81421, 15329, 1303, 10303, 8009, 1, 1, 1, 1, 1, 2251, 3547, 85469, 4597, 1, 1, 37217, 5449, 6733, 1063, 4201, 11071, 1, 1, 3319, 4217, 90313, 1619, 273047, 1, 13103, 1, 5437, 1933, 1, 1, 1, 1, 1087, 1, 1597, 1, 32003, 1, 1, 1, 3701, 1, 1, 1, 3191, 1, 6361, 12503, 100393, 2699, 1, 1, 43661, 12781, 1, 2971, 14767, 1621, 10771, 1, 1, 1361, 1993, 1, 24551, 6673, 15307, 1, 2767, 13537, 1, 13633, 12161, 1471, 110221, 1, 332987, 1, 111773, 42061, 2297, 1, 340007, 1777, 1, 42943, 38303, 1, 347099, 1, 1, 1, 2213, 1, 1, 4937, 1949, 22367, 17099, 1, 361499, 1, 121309, 3511, 4523, 1, 11897, 1, 1, 1, 1, 1, 1, 2621, 1, 1, 1, 1, 22567, 1, 9901, 6053, 1, 8123, 391163, 1, 2083, 49369, 1, 1, 398759, 1, 133769, 1, 1307, 1, 58061, 1, 136333, 25643, 1, 17203, 31859, 2473, 46307, 1, 10753, 1, 14551, 5879, 20219, 53239, 8377, 1, 61409, 1, 144169, 1, 1, 1399, 437819, 1, 2879, 13807, 1, 18521, 445847, 6211, 1, 1, 150413, 1, 34919, 1, 1, 8179, 51043, 1, 9431, 1, 1913, 4483, 3181, 19541, 15173, 1, 9277, 1, 158633, 1, 478679, 1, 1, 1, 4139, 5059, 4093, 20353, 1, 1, 164233, 5147, 495527, 1, 1, 62473, 1, 1, 6073, 10531, 1, 1, 1, 1, 512663, 1, 57283, 1, 2833, 10831, 1, 1, 174749, 65713, 1931, 3671, 530087, 1, 1, 1, 1, 1, 18583, 1, 1, 1, 181609, 1, 1, 2543, 183593, 4931, 1, 1, 556763, 3323, 1, 4127, 8933, 2939, 1, 1, 9029, 71293, 11213, 3413, 574907, 4003, 4099, 1, 1, 1, 1, 1877, 1, 18397, 1, 12329, 2591, 3541, 66271, 4397, 15373, 1789, 1, 1, 1, 1, 202973, 1, 12491, 1, 205069, 5507, 1, 1987, 621527, 3709, 1, 3011, 1, 1, 20357, 1, 30203, 1, 2063, 1, 1, 13381, 3023, 11527, 5531, 27031, 1753, 1, 72623, 5119, 1, 27437, 660119, 1, 1, 10391, 1, 1, 669947, 27983, 32059, 2909, 25057, 1, 1, 1, 5839, 1747, 228829, 1, 1, 1, 231053, 43427, 1951, 9697, 699863, 29231, 33487, 3389, 78511, 1, 1, 2281, 8807, 1, 238921, 1871, 102881, 1, 8317, 5333, 2663, 1, 15541, 2179, 1, 1, 1, 1, 5407, 30937, 11813, 23311, 249229, 1, 107309, 10457, 14797, 1, 252713, 1759, 1, 1, 255049, 5639, 1, 1, 59399, 1, 1, 48593, 1, 4649, 2243, 1, 262121, 1, 1, 2749, 113357, 2549, 15629, 99859, 1, 1, 7963, 2399, 29921, 101209, 270493, 1, 47947, 1, 2999, 12821, 274121, 11447, 1, 2029, 276553, 1, 1, 1, 8287, 4993, 93407, 8101,

6. Sequence of the polynom (only primes)

347, 3, 13, 7, 29, 17, 79, 31, 61, 53, 1381, 547, 631, 2137, 47, 113, 311, 337, 83, 139, 3433, 71, 181, 137, 197, 4441, 509, 1571, 199, 691, 127, 313, 241, 397, 103, 331, 593, 5413, 227, 1847, 1879, 101, 5701, 1907, 179, 239, 5737, 1319, 229, 223, 1033, 1289, 359, 1693, 661, 5927, 823, 2269, 293, 2729, 8663, 3049, 587, 10139, 433, 4073, 4253, 1901, 283, 4621, 613, 577, 317, 16763, 827, 461, 2657, 349, 2207, 20507, 2351, 1039, 1103, 7949, 463, 457, 563, 3469, 1187, 28859, 937, 1831, 1009, 3631, 683, 619, 11689, 739, 35879, 941, 4639, 1787, 1867, 2477, 4451, 1723, 4643, 14221, 449, 6221, 14813, 5953, 49019, 1031, 2141, 727, 17609, 54779, 641, 541, 1193, 947, 607, 7411, 643, 4679, 1213, 557, 1613, 881, 9137, 2687, 21673, 1049, 1429, 7583, 8599, 797, 70439, 3407, 9013, 1549, 5939, 8707, 2467, 1669, 1129, 27689, 84263, 919, 9631, 3637, 3301, 907, 2381, 5843, 4001, 4603, 12163, 10883, 14177, 2081, 11171, 1997, 4271, 1453, 1201, 5039, 8243, 4493, 5167, 853, 111227, 4663, 12511, 37993, 2389, 16481, 38921, 14683, 761, 7607, 733, 123863, 7877, 1409, 43721, 132647, 1297, 2153, 5683, 137147, 4357, 839, 141719, 1979, 6131, 3793, 8887, 16963, 19183, 51421, 1973, 7499, 2221, 22961, 54121, 18223, 12743, 991, 6197, 21019, 10039, 21649, 58013, 5669, 59149, 1171, 25841, 7573, 8779, 186107, 4817, 23593, 2039, 14723, 2003, 9199, 1427, 8161, 28109, 22063, 3929, 8387, 1447, 12809, 9803, 3919, 8693, 213287, 4463, 1019, 31277, 73613, 10607, 1607, 25391, 9643, 29173, 78121, 4903, 79433, 4273, 1117, 14251, 81421, 15329, 1303, 10303, 8009, 2251, 3547, 85469, 4597, 37217, 5449, 6733, 1063, 4201, 11071, 3319, 4217, 90313, 1619, 273047, 13103, 5437, 1933, 1087, 1597, 32003, 3701, 3191, 6361, 12503, 100393, 2699, 43661, 12781, 2971, 14767, 1621, 10771, 1361, 1993, 24551, 6673, 15307, 2767, 13537, 13633, 12161, 1471, 110221, 332987, 111773, 42061, 2297, 340007, 1777, 42943, 38303, 347099, 2213, 4937, 1949, 22367, 17099, 361499, 121309, 3511, 4523, 11897, 2621, 22567, 9901, 6053, 8123, 391163, 2083, 49369, 398759, 133769, 1307, 58061, 136333, 25643, 17203, 31859, 2473, 46307, 10753, 14551, 5879, 20219, 53239, 8377, 61409, 144169, 1399, 437819, 2879, 13807, 18521, 445847, 6211, 150413, 34919, 8179, 51043, 9431, 1913, 4483, 3181, 19541, 15173, 9277, 158633, 478679, 4139, 5059, 4093, 20353, 164233, 5147, 495527, 62473, 6073, 10531, 512663, 57283, 2833, 10831, 174749, 65713, 1931, 3671, 530087, 18583, 181609, 2543, 183593, 4931, 556763, 3323, 4127, 8933, 2939, 9029, 71293, 11213, 3413, 574907, 4003, 4099, 1877, 18397, 12329, 2591, 3541, 66271, 4397, 15373, 1789, 202973, 12491, 205069, 5507, 1987, 621527, 3709, 3011, 20357, 30203, 2063, 13381, 3023, 11527, 5531, 27031, 1753, 72623, 5119, 27437, 660119, 10391, 669947, 27983, 32059, 2909, 25057, 5839, 1747, 228829, 231053, 43427, 1951, 9697, 699863, 29231, 33487, 3389, 78511, 2281, 8807, 238921, 1871, 102881, 8317, 5333, 2663, 15541, 2179, 5407, 30937, 11813, 23311, 249229, 107309, 10457, 14797, 252713, 1759, 255049, 5639, 59399, 48593, 4649, 2243, 262121, 2749, 113357, 2549, 15629, 99859, 7963, 2399, 29921, 101209, 270493, 47947, 2999, 12821, 274121, 11447, 2029, 276553, 8287, 4993, 93407, 8101,

7. Distribution of the primes

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

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 1 2 1.5 0.5 1
2 4 5 1 4 1.25 0.25 1
3 8 8 1 7 1 0.125 0.875
4 16 13 2 11 0.8125 0.125 0.6875
5 32 22 4 18 0.6875 0.125 0.5625
6 64 40 6 34 0.625 0.09375 0.53125
7 128 47 8 39 0.3671875 0.0625 0.3046875
8 256 86 14 72 0.3359375 0.0546875 0.28125
9 512 220 25 195 0.4296875 0.04882813 0.38085938
10 1024 514 46 468 0.50195313 0.04492188 0.45703125
11 2048 1111 71 1040 0.54248047 0.03466797 0.5078125
12 4096 2329 134 2195 0.56860352 0.03271484 0.53588867
13 8192 4796 267 4529 0.58544922 0.03259277 0.55285645
14 16384 9751 503 9248 0.59515381 0.03070068 0.56445313
15 32768 19739 956 18783 0.60238647 0.0291748 0.57321167
16 65536 39929 1757 38172 0.60926819 0.02680969 0.5824585
17 131072 80727 3344 77383 0.61589813 0.0255127 0.59038544
18 262144 162645 6320 156325 0.62044144 0.02410889 0.59633255
19 524288 327536 11930 315606 0.62472534 0.02275467 0.60197067
20 1048576 659288 22466 636822 0.62874603 0.02142525 0.60732079
21 2097152 1325346 42614 1282732 0.63197422 0.02031994 0.61165428
22 4194304 2663070 80682 2582388 0.63492537 0.01923609 0.61568928
23 8388608 5347902 154102 5193800 0.6375196 0.01837039 0.61914921
24 16777216 10737196 294202 10442994 0.63998675 0.01753581 0.62245095


8. Check for existing Integer Sequences by OEIS

Found in Database : 347, 3, 13, 7, 29, 17, 79, 1, 31, 61, 53, 1, 1381, 1, 547, 1, 631, 1, 2137, 47,
Found in Database : 347, 3, 13, 7, 29, 17, 79, 31, 61, 53, 1381, 547, 631, 2137, 47, 113, 311, 337, 83, 139, 3433, 71, 181, 137, 197,
Found in Database : 3, 7, 13, 17, 29, 31, 47, 53, 61, 71, 79, 83, 101, 103, 113, 127, 137, 139,