Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:58:57
Deutsch
29.Mar 2024

Polynom = x^2-180x+227

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) = 227 = 227
f(1) = 3 = 3
f(2) = 129 = 3*43
f(3) = 19 = 19
f(4) = 477 = 3*3*53
f(5) = 81 = 3*3*3*3
f(6) = 817 = 19*43
f(7) = 123 = 3*41
f(8) = 1149 = 3*383
f(9) = 41 = 41
f(10) = 1473 = 3*491
f(11) = 51 = 3*17
f(12) = 1789 = 1789
f(13) = 243 = 3*3*3*3*3
f(14) = 2097 = 3*3*233
f(15) = 281 = 281
f(16) = 2397 = 3*17*47
f(17) = 159 = 3*53
f(18) = 2689 = 2689
f(19) = 177 = 3*59
f(20) = 2973 = 3*991
f(21) = 389 = 389
f(22) = 3249 = 3*3*19*19
f(23) = 423 = 3*3*47
f(24) = 3517 = 3517
f(25) = 57 = 3*19
f(26) = 3777 = 3*1259
f(27) = 61 = 61
f(28) = 4029 = 3*17*79
f(29) = 519 = 3*173
f(30) = 4273 = 4273
f(31) = 549 = 3*3*61
f(32) = 4509 = 3*3*3*167
f(33) = 289 = 17*17
f(34) = 4737 = 3*1579
f(35) = 303 = 3*101
f(36) = 4957 = 4957
f(37) = 633 = 3*211
f(38) = 5169 = 3*1723
f(39) = 659 = 659
f(40) = 5373 = 3*3*3*199
f(41) = 171 = 3*3*19
f(42) = 5569 = 5569
f(43) = 177 = 3*59
f(44) = 5757 = 3*19*101
f(45) = 731 = 17*43
f(46) = 5937 = 3*1979
f(47) = 753 = 3*251
f(48) = 6109 = 41*149
f(49) = 387 = 3*3*43
f(50) = 6273 = 3*3*17*41
f(51) = 397 = 397
f(52) = 6429 = 3*2143
f(53) = 813 = 3*271
f(54) = 6577 = 6577
f(55) = 831 = 3*277
f(56) = 6717 = 3*2239
f(57) = 53 = 53
f(58) = 6849 = 3*3*761
f(59) = 27 = 3*3*3
f(60) = 6973 = 19*367
f(61) = 879 = 3*293
f(62) = 7089 = 3*17*139
f(63) = 893 = 19*47
f(64) = 7197 = 3*2399
f(65) = 453 = 3*151
f(66) = 7297 = 7297
f(67) = 459 = 3*3*3*17
f(68) = 7389 = 3*3*821
f(69) = 929 = 929
f(70) = 7473 = 3*47*53
f(71) = 939 = 3*313
f(72) = 7549 = 7549
f(73) = 237 = 3*79
f(74) = 7617 = 3*2539
f(75) = 239 = 239
f(76) = 7677 = 3*3*853
f(77) = 963 = 3*3*107
f(78) = 7729 = 59*131
f(79) = 969 = 3*17*19
f(80) = 7773 = 3*2591
f(81) = 487 = 487
f(82) = 7809 = 3*19*137
f(83) = 489 = 3*163
f(84) = 7837 = 17*461
f(85) = 981 = 3*3*109
f(86) = 7857 = 3*3*3*3*97
f(87) = 983 = 983
f(88) = 7869 = 3*43*61
f(89) = 123 = 3*41
f(90) = 7873 = 7873
f(91) = 123 = 3*41
f(92) = 7869 = 3*43*61
f(93) = 983 = 983
f(94) = 7857 = 3*3*3*3*97
f(95) = 981 = 3*3*109
f(96) = 7837 = 17*461
f(97) = 489 = 3*163
f(98) = 7809 = 3*19*137
f(99) = 487 = 487
f(100) = 7773 = 3*2591

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-180x+227

f(0)=227
f(1)=3
f(2)=43
f(3)=19
f(4)=53
f(5)=1
f(6)=1
f(7)=41
f(8)=383
f(9)=1
f(10)=491
f(11)=17
f(12)=1789
f(13)=1
f(14)=233
f(15)=281
f(16)=47
f(17)=1
f(18)=2689
f(19)=59
f(20)=991
f(21)=389
f(22)=1
f(23)=1
f(24)=3517
f(25)=1
f(26)=1259
f(27)=61
f(28)=79
f(29)=173
f(30)=4273
f(31)=1
f(32)=167
f(33)=1
f(34)=1579
f(35)=101
f(36)=4957
f(37)=211
f(38)=1723
f(39)=659
f(40)=199
f(41)=1
f(42)=5569
f(43)=1
f(44)=1
f(45)=1
f(46)=1979
f(47)=251
f(48)=149
f(49)=1
f(50)=1
f(51)=397
f(52)=2143
f(53)=271
f(54)=6577
f(55)=277
f(56)=2239
f(57)=1
f(58)=761
f(59)=1
f(60)=367
f(61)=293
f(62)=139
f(63)=1
f(64)=2399
f(65)=151
f(66)=7297
f(67)=1
f(68)=821
f(69)=929
f(70)=1
f(71)=313
f(72)=7549
f(73)=1
f(74)=2539
f(75)=239
f(76)=853
f(77)=107
f(78)=131
f(79)=1
f(80)=2591
f(81)=487
f(82)=137
f(83)=163
f(84)=461
f(85)=109
f(86)=97
f(87)=983
f(88)=1
f(89)=1
f(90)=7873
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-180x+227 could be written as f(y)= y^2-7873 with x=y+90

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-90
f'(x)>2x-181 with x > 89

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

227, 3, 43, 19, 53, 1, 1, 41, 383, 1, 491, 17, 1789, 1, 233, 281, 47, 1, 2689, 59, 991, 389, 1, 1, 3517, 1, 1259, 61, 79, 173, 4273, 1, 167, 1, 1579, 101, 4957, 211, 1723, 659, 199, 1, 5569, 1, 1, 1, 1979, 251, 149, 1, 1, 397, 2143, 271, 6577, 277, 2239, 1, 761, 1, 367, 293, 139, 1, 2399, 151, 7297, 1, 821, 929, 1, 313, 7549, 1, 2539, 239, 853, 107, 131, 1, 2591, 487, 137, 163, 461, 109, 97, 983, 1, 1, 7873, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 197, 1, 1, 1, 1, 1, 577, 241, 709, 1, 2531, 1, 1, 1, 1, 1, 223, 1, 1409, 1, 1, 1, 1, 1, 1861, 727, 2017, 1, 1, 1, 1, 907, 1, 1, 1, 1, 2837, 1, 1, 1, 9551, 409, 3361, 647, 3541, 1, 11171, 1, 1303, 1, 1, 1, 677, 1, 4481, 1, 1559, 1, 14627, 311, 5077, 971, 5281, 673, 1, 1, 1, 1, 1, 1, 18371, 1, 373, 1, 1, 1, 433, 431, 1, 2671, 7237, 919, 521, 1, 1, 733, 7937, 1, 24527, 1, 443, 1601, 2887, 1, 26723, 1129, 9157, 1, 1, 1, 547, 1, 3307, 3769, 10181, 1289, 1, 661, 10709, 1, 3659, 463, 823, 1423, 1, 1093, 1, 1, 2131, 509, 1373, 1, 12641, 1, 38783, 1, 13217, 5011, 1, 569, 41411, 1, 1, 1, 14401, 1, 44111, 619, 5003, 2843, 1, 967, 1, 1973, 839, 6037, 5419, 1, 49727, 523, 1, 6397, 1013, 1, 863, 1, 1, 1, 1, 2297, 55631, 2339, 1, 1, 1, 1, 3089, 2467, 1, 1, 1, 1277, 1, 1, 1, 7927, 21317, 2687, 65027, 683, 22037, 2083, 1, 941, 1, 1, 1361, 4373, 23509, 1481, 1, 1, 8087, 1, 601, 1, 1831, 1, 25409, 9601, 8599, 1, 1, 1, 1399, 5021, 1, 1, 4831, 1, 1, 1, 28181, 887, 617, 1, 1, 1, 9803, 1, 1, 1877, 30241, 1, 30661, 1, 93251, 1, 1, 1487, 1, 4019, 97103, 4073, 32801, 1, 1231, 1, 101027, 1, 1, 1, 1, 1087, 105023, 1, 1, 13381, 1, 4517, 1, 2287, 36821, 6947, 1, 1, 1, 1, 2011, 1, 38677, 1, 117443, 1, 1, 14947, 1, 2521, 121727, 2551, 41057, 911, 1, 1741, 2137, 1321, 1, 1, 1049, 5407, 6869, 1823, 4889, 8297, 44501, 2797, 1709, 5657, 2677, 1, 5113, 1, 1439, 1, 47041, 17737, 2503, 1, 1, 1, 1, 9161, 49121, 6173, 3169, 1, 50177, 4729, 16903, 1, 9043, 1, 977, 1, 52321, 1, 158591, 1, 937, 1, 1, 6779, 9619, 1, 55061, 1297, 18539, 1, 168527, 7057, 56737, 10691, 57301, 1, 9137, 2423, 1, 1, 59009, 1, 4157, 1871, 60161, 22669, 1, 2543, 183971, 3851, 61909, 1, 62497, 1, 3571, 1, 21227, 2999, 1, 1009, 1, 8147, 1597, 1451, 22027, 1, 200063, 1, 1, 1, 1151, 8527, 1, 1, 1213, 1, 69761, 1, 211151, 8837, 4177, 1, 23879, 1499, 216803, 1, 72901, 27457, 1, 1, 222527, 1, 1, 1483, 1279, 9473, 1, 1, 76757, 1, 1, 1, 234191, 1, 78721, 7411, 1, 1, 240131, 1, 26903, 30391, 4283, 5107, 14479, 1, 82721, 31147, 27799, 1163, 4759, 1319, 1, 3989, 1987, 10723, 15199, 1201, 1, 1, 87509, 1, 2473, 11069, 4679, 33469, 29867, 1, 1949, 2833, 91009, 34261, 2237, 1, 6763, 1933, 1, 1, 5521, 11777, 1, 11867, 1, 1, 1, 1, 290243, 1, 1, 36691, 1, 1, 296831, 2069, 1, 2207, 1, 1, 303491, 1, 1, 1, 1801, 1, 310223, 12973, 104161, 1153, 104917, 6581, 4013, 1, 2087, 1, 107201, 1, 323903, 1693, 1, 1, 1, 1, 1, 6917, 1, 20897, 1, 14029, 337871, 1, 12601, 1, 114197, 3581, 344963, 14423, 115781, 2293, 12953, 2437, 1, 1, 2003, 1, 2767, 14923, 21139, 1, 1, 1, 1, 15227, 6011, 15329, 3001, 1, 1, 1, 22003, 1, 125509, 47221, 126337, 1, 1583, 1, 42667, 48157, 128837, 1, 389027, 1, 130517, 24551, 43787, 1, 396623, 1, 1, 6257, 7877, 2099, 404291, 1, 5023, 1, 136481, 1, 412031, 1, 138209, 51991, 1, 5813, 1, 1, 2657, 1, 141697, 1, 427727, 1, 47819, 26981, 144341, 9049, 1, 1, 146117, 1, 49003, 1, 443711, 1, 8753, 1, 7879, 1, 9613, 1, 50503, 28493, 152417, 1, 1, 1, 1, 14503, 51719, 1621, 10889, 1, 8263, 1, 1999, 1, 1, 3319, 1, 60091, 160709, 20147, 2029, 1, 1, 7643, 18169, 6833, 29023, 1, 1, 1637, 166357, 10427, 26417, 6991, 56087, 63277, 169217, 5303, 1, 5333, 3229, 1, 57367, 1, 3109, 10847, 2203, 1, 1, 21937, 1, 1, 1, 4159, 1663, 1, 536771, 1, 179909, 67651, 3547, 3779, 545663, 11399, 1, 68767, 183877, 1, 554627, 1931, 1, 1, 10993, 1, 563663, 23549, 1733, 2089, 21101, 3967, 1, 23929, 1, 72169, 192961, 3023, 1, 1, 65003, 1, 1, 1, 4513, 1, 1, 1, 1619, 1, 1, 25087, 1, 18913, 1, 6337, 609923, 1, 4007, 76831, 1, 1, 619391, 1, 207521, 1, 1, 8713, 4801, 1, 210709, 4951, 211777, 26539, 3691, 1, 1, 1, 1, 1, 2243, 27077, 217157, 81637, 1, 1, 657983, 6871, 1, 1, 221509, 1, 1, 4649, 74567, 2213, 4783, 1657, 1, 28307, 1, 10667, 76039, 1, 687683, 28723, 230341, 86587, 3923, 1, 697727, 1, 77899, 1, 1, 29423, 3557, 1, 1, 22279, 1, 9949, 1, 29989, 2381, 45197, 1, 15137, 16937, 10139, 1, 5393, 1, 1, 738623, 1, 1, 1, 1, 1, 749027, 15641, 250837, 1, 252001, 31573, 759503, 1, 4987, 23899, 1, 1, 40529, 32159, 257861, 5101, 1, 1, 780671, 16301, 15377, 98251, 262597, 1, 791363, 1, 88327, 1, 266177, 33347, 802127, 1, 1, 1, 4733, 1, 812963, 1997, 1, 102301,

6. Sequence of the polynom (only primes)

227, 3, 43, 19, 53, 41, 383, 491, 17, 1789, 233, 281, 47, 2689, 59, 991, 389, 3517, 1259, 61, 79, 173, 4273, 167, 1579, 101, 4957, 211, 1723, 659, 199, 5569, 1979, 251, 149, 397, 2143, 271, 6577, 277, 2239, 761, 367, 293, 139, 2399, 151, 7297, 821, 929, 313, 7549, 2539, 239, 853, 107, 131, 2591, 487, 137, 163, 461, 109, 97, 983, 7873, 197, 577, 241, 709, 2531, 223, 1409, 1861, 727, 2017, 907, 2837, 9551, 409, 3361, 647, 3541, 11171, 1303, 677, 4481, 1559, 14627, 311, 5077, 971, 5281, 673, 18371, 373, 433, 431, 2671, 7237, 919, 521, 733, 7937, 24527, 443, 1601, 2887, 26723, 1129, 9157, 547, 3307, 3769, 10181, 1289, 661, 10709, 3659, 463, 823, 1423, 1093, 2131, 509, 1373, 12641, 38783, 13217, 5011, 569, 41411, 14401, 44111, 619, 5003, 2843, 967, 1973, 839, 6037, 5419, 49727, 523, 6397, 1013, 863, 2297, 55631, 2339, 3089, 2467, 1277, 7927, 21317, 2687, 65027, 683, 22037, 2083, 941, 1361, 4373, 23509, 1481, 8087, 601, 1831, 25409, 9601, 8599, 1399, 5021, 4831, 28181, 887, 617, 9803, 1877, 30241, 30661, 93251, 1487, 4019, 97103, 4073, 32801, 1231, 101027, 1087, 105023, 13381, 4517, 2287, 36821, 6947, 2011, 38677, 117443, 14947, 2521, 121727, 2551, 41057, 911, 1741, 2137, 1321, 1049, 5407, 6869, 1823, 4889, 8297, 44501, 2797, 1709, 5657, 2677, 5113, 1439, 47041, 17737, 2503, 9161, 49121, 6173, 3169, 50177, 4729, 16903, 9043, 977, 52321, 158591, 937, 6779, 9619, 55061, 1297, 18539, 168527, 7057, 56737, 10691, 57301, 9137, 2423, 59009, 4157, 1871, 60161, 22669, 2543, 183971, 3851, 61909, 62497, 3571, 21227, 2999, 1009, 8147, 1597, 1451, 22027, 200063, 1151, 8527, 1213, 69761, 211151, 8837, 4177, 23879, 1499, 216803, 72901, 27457, 222527, 1483, 1279, 9473, 76757, 234191, 78721, 7411, 240131, 26903, 30391, 4283, 5107, 14479, 82721, 31147, 27799, 1163, 4759, 1319, 3989, 1987, 10723, 15199, 1201, 87509, 2473, 11069, 4679, 33469, 29867, 1949, 2833, 91009, 34261, 2237, 6763, 1933, 5521, 11777, 11867, 290243, 36691, 296831, 2069, 2207, 303491, 1801, 310223, 12973, 104161, 1153, 104917, 6581, 4013, 2087, 107201, 323903, 1693, 6917, 20897, 14029, 337871, 12601, 114197, 3581, 344963, 14423, 115781, 2293, 12953, 2437, 2003, 2767, 14923, 21139, 15227, 6011, 15329, 3001, 22003, 125509, 47221, 126337, 1583, 42667, 48157, 128837, 389027, 130517, 24551, 43787, 396623, 6257, 7877, 2099, 404291, 5023, 136481, 412031, 138209, 51991, 5813, 2657, 141697, 427727, 47819, 26981, 144341, 9049, 146117, 49003, 443711, 8753, 7879, 9613, 50503, 28493, 152417, 14503, 51719, 1621, 10889, 8263, 1999, 3319, 60091, 160709, 20147, 2029, 7643, 18169, 6833, 29023, 1637, 166357, 10427, 26417, 6991, 56087, 63277, 169217, 5303, 5333, 3229, 57367, 3109, 10847, 2203, 21937, 4159, 1663, 536771, 179909, 67651, 3547, 3779, 545663, 11399, 68767, 183877, 554627, 1931, 10993, 563663, 23549, 1733, 2089, 21101, 3967, 23929, 72169, 192961, 3023, 65003, 4513, 1619, 25087, 18913, 6337, 609923, 4007, 76831, 619391, 207521, 8713, 4801, 210709, 4951, 211777, 26539, 3691, 2243, 27077, 217157, 81637, 657983, 6871, 221509, 4649, 74567, 2213, 4783, 1657, 28307, 10667, 76039, 687683, 28723, 230341, 86587, 3923, 697727, 77899, 29423, 3557, 22279, 9949, 29989, 2381, 45197, 15137, 16937, 10139, 5393, 738623, 749027, 15641, 250837, 252001, 31573, 759503, 4987, 23899, 40529, 32159, 257861, 5101, 780671, 16301, 15377, 98251, 262597, 791363, 88327, 266177, 33347, 802127, 4733, 812963, 1997, 102301,

7. Distribution of the primes

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

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 7 1 6 0.875 0.125 0.75
4 16 13 2 11 0.8125 0.125 0.6875
5 32 24 5 19 0.75 0.15625 0.59375
6 64 46 8 38 0.71875 0.125 0.59375
7 128 66 11 55 0.515625 0.0859375 0.4296875
8 256 96 16 80 0.375 0.0625 0.3125
9 512 244 32 212 0.4765625 0.0625 0.4140625
10 1024 543 69 474 0.53027344 0.06738281 0.46289063
11 2048 1172 120 1052 0.57226563 0.05859375 0.51367188
12 4096 2451 214 2237 0.59838867 0.05224609 0.54614258
13 8192 5018 400 4618 0.61254883 0.04882813 0.5637207
14 16384 10206 751 9455 0.6229248 0.0458374 0.5770874
15 32768 20675 1392 19283 0.63095093 0.04248047 0.58847046
16 65536 41758 2580 39178 0.63717651 0.03936768 0.59780884
17 131072 84011 4826 79185 0.64095306 0.03681946 0.60413361
18 262144 168926 9073 159853 0.64440155 0.03461075 0.6097908
19 524288 339504 17036 322468 0.64755249 0.03249359 0.6150589
20 1048576 681487 32283 649204 0.64991665 0.03078747 0.61912918
21 2097152 1367406 61161 1306245 0.65202999 0.02916384 0.62286615
22 4194304 2742545 116477 2626068 0.65387368 0.02777028 0.6261034
23 8388608 5499518 221850 5277668 0.65559363 0.02644658 0.62914705
24 16777216 11026355 424116 10602239 0.65722197 0.02527928 0.63194269


8. Check for existing Integer Sequences by OEIS

Found in Database : 227, 3, 43, 19, 53, 1, 1, 41, 383, 1, 491, 17, 1789, 1, 233, 281, 47, 1, 2689, 59,
Found in Database : 227, 3, 43, 19, 53, 41, 383, 491, 17, 1789, 233, 281, 47, 2689, 59, 991, 389, 3517, 1259, 61, 79, 173, 4273, 167, 1579, 101, 4957, 211, 1723, 659,
Found in Database : 3, 17, 19, 41, 43, 47, 53, 59, 61, 79, 97, 101, 107, 109, 131, 137, 139, 149,