Development of |
|
liste_max:=100000; sieving:=proc (stelle, p) begin while (stelle<=liste_max) do erg:=liste[stelle]; while(erg mod p=0) do // Divison of the stored f(x) by the prime erg:=erg /p; end_while; liste[stelle]:=erg; stelle:=stelle+p; end_while; end_proc; // Calculation of the values of the polynom for x from 0 to liste_max for x from 0 to liste_max do p:=abs (a*x^2+b*x+c); while (p mod 2=0) p:=p/2; liste [x]:=p; end_for; for x from 0 to liste_max do p:=liste[x]; if (p>1) then // Printing the Primes print (x, p); // 1. Sieving sieving (x+p, p); t:=(-x-b/a) mod p;If you are interested in some better algorithms have a look at quadr_Sieb_x^2+1.php.
if t=0 then t:=p; end_if; // 2. Sieving sieving (t, p); end_if; end_for;
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-276x+11
f(0)=11
f(1)=3
f(2)=179
f(3)=101
f(4)=359
f(5)=7
f(6)=1609
f(7)=13
f(8)=79
f(9)=23
f(10)=883
f(11)=1
f(12)=41
f(13)=71
f(14)=53
f(15)=61
f(16)=461
f(17)=1
f(18)=113
f(19)=29
f(20)=131
f(21)=167
f(22)=1
f(23)=1
f(24)=6037
f(25)=1
f(26)=103
f(27)=839
f(28)=2311
f(29)=149
f(30)=7369
f(31)=1
f(32)=1
f(33)=1
f(34)=83
f(35)=1
f(36)=8629
f(37)=1
f(38)=3011
f(39)=577
f(40)=449
f(41)=401
f(42)=9817
f(43)=139
f(44)=1
f(45)=59
f(46)=271
f(47)=1
f(48)=1
f(49)=463
f(50)=1
f(51)=1433
f(52)=431
f(53)=1
f(54)=1
f(55)=1
f(56)=373
f(57)=1559
f(58)=4211
f(59)=1
f(60)=563
f(61)=1
f(62)=491
f(63)=419
f(64)=4519
f(65)=571
f(66)=1259
f(67)=1
f(68)=673
f(69)=223
f(70)=1601
f(71)=1
f(72)=1129
f(73)=617
f(74)=383
f(75)=269
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1741
f(81)=1973
f(82)=757
f(83)=1
f(84)=227
f(85)=1
f(86)=5443
f(87)=1
f(88)=1
f(89)=1
f(90)=16729
f(91)=701
f(92)=5639
f(93)=1063
f(94)=1
f(95)=1
f(96)=2467
f(97)=241
f(98)=1
f(99)=199
b) Substitution of the polynom
The polynom f(x)=x^2-276x+11 could be written as f(y)= y^2-19033 with x=y+138
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-138
f'(x)>2x-277 with x > 138
A | B | C | D | E | F | G | H | I | J | K |
exponent =log10 (x) | <=x | number of all primes | number of primes p = f(x) | number of primes p | f(x) | C/x | D/x | E/x | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
1 | 10 | 10 | 2 | 8 | 1.000000 | 0.200000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 7 | 57 | 0.640000 | 0.070000 | 0.640000 | 6.400000 | 3.500000 | 7.125000 |
3 | 1.000 | 419 | 43 | 376 | 0.419000 | 0.043000 | 0.419000 | 6.546875 | 6.142857 | 6.596491 |
4 | 10.000 | 5.708 | 332 | 5.376 | 0.570800 | 0.033200 | 0.570800 | 13.622911 | 7.720930 | 14.297873 |
5 | 100.000 | 60.777 | 2.666 | 58.111 | 0.607770 | 0.026660 | 0.607770 | 10.647688 | 8.030121 | 10.809338 |
6 | 1.000.000 | 625.029 | 21.891 | 603.138 | 0.625029 | 0.021891 | 0.625029 | 10.283973 | 8.211178 | 10.379067 |
7 | 10.000.000 | 6.355.646 | 184.951 | 6.170.695 | 0.635565 | 0.018495 | 0.635565 | 10.168562 | 8.448723 | 10.230984 |
8 | 100.000.000 | 64.317.331 | 1.601.065 | 62.716.266 | 0.643173 | 0.016011 | 0.643173 | 10.119716 | 8.656698 | 10.163566 |
9 | 1.000.000.000 | 648.940.627 | 14.132.036 | 634.808.591 | 0.648941 | 0.014132 | 0.648941 | 10.089669 | 8.826647 | 10.121913 |
10 | 10.000.000.000 | 6.535.220.056 | 126.469.892 | 6.408.750.164 | 0.653522 | 0.012647 | 0.653522 | 10.070599 | 8.949162 | 10.095563 |
A | B | C | D | E | F | G | H | I | J | K |
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 | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
1 | 2 | 3 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 1 | 4 | 1.250000 | 0.250000 | 1.000000 | 1.666667 | 1.000000 | 2.000000 |
3 | 8 | 8 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 1.600000 | 2.000000 | 1.500000 |
4 | 16 | 15 | 2 | 13 | 0.937500 | 0.125000 | 0.812500 | 1.875000 | 1.000000 | 2.166667 |
5 | 32 | 24 | 4 | 20 | 0.750000 | 0.125000 | 0.625000 | 1.600000 | 2.000000 | 1.538462 |
6 | 64 | 43 | 6 | 37 | 0.671875 | 0.093750 | 0.578125 | 1.791667 | 1.500000 | 1.850000 |
7 | 128 | 78 | 10 | 68 | 0.609375 | 0.078125 | 0.531250 | 1.813954 | 1.666667 | 1.837838 |
8 | 256 | 82 | 10 | 72 | 0.320312 | 0.039062 | 0.281250 | 1.051282 | 1.000000 | 1.058824 |
9 | 512 | 173 | 22 | 151 | 0.337891 | 0.042969 | 0.294922 | 2.109756 | 2.200000 | 2.097222 |
10 | 1.024 | 434 | 44 | 390 | 0.423828 | 0.042969 | 0.380859 | 2.508671 | 2.000000 | 2.582782 |
11 | 2.048 | 1.000 | 81 | 919 | 0.488281 | 0.039551 | 0.448730 | 2.304147 | 1.840909 | 2.356410 |
12 | 4.096 | 2.193 | 152 | 2.041 | 0.535400 | 0.037109 | 0.498291 | 2.193000 | 1.876543 | 2.220892 |
13 | 8.192 | 4.633 | 280 | 4.353 | 0.565552 | 0.034180 | 0.531372 | 2.112631 | 1.842105 | 2.132778 |
14 | 16.384 | 9.554 | 537 | 9.017 | 0.583130 | 0.032776 | 0.550354 | 2.062163 | 1.917857 | 2.071445 |
15 | 32.768 | 19.481 | 964 | 18.517 | 0.594513 | 0.029419 | 0.565094 | 2.039041 | 1.795158 | 2.053566 |
16 | 65.536 | 39.559 | 1.820 | 37.739 | 0.603622 | 0.027771 | 0.575851 | 2.030645 | 1.887967 | 2.038073 |
17 | 131.072 | 80.013 | 3.396 | 76.617 | 0.610451 | 0.025909 | 0.584541 | 2.022624 | 1.865934 | 2.030181 |
18 | 262.144 | 161.671 | 6.383 | 155.288 | 0.616726 | 0.024349 | 0.592377 | 2.020559 | 1.879564 | 2.026809 |
19 | 524.288 | 325.816 | 12.111 | 313.705 | 0.621445 | 0.023100 | 0.598345 | 2.015303 | 1.897384 | 2.020150 |
20 | 1.048.576 | 655.759 | 22.904 | 632.855 | 0.625381 | 0.021843 | 0.603538 | 2.012667 | 1.891173 | 2.017357 |
21 | 2.097.152 | 1.318.882 | 43.444 | 1.275.438 | 0.628892 | 0.020716 | 0.608176 | 2.011230 | 1.896787 | 2.015372 |
22 | 4.194.304 | 2.651.185 | 82.392 | 2.568.793 | 0.632092 | 0.019644 | 0.612448 | 2.010176 | 1.896510 | 2.014048 |
23 | 8.388.608 | 5.326.129 | 156.854 | 5.169.275 | 0.634924 | 0.018698 | 0.616226 | 2.008962 | 1.903753 | 2.012336 |
24 | 16.777.216 | 10.695.151 | 299.249 | 10.395.902 | 0.637481 | 0.017837 | 0.619644 | 2.008053 | 1.907819 | 2.011095 |
25 | 33.554.432 | 21.469.945 | 573.140 | 20.896.805 | 0.639854 | 0.017081 | 0.622773 | 2.007447 | 1.915261 | 2.010100 |
26 | 67.108.864 | 43.083.610 | 1.099.168 | 41.984.442 | 0.641996 | 0.016379 | 0.625617 | 2.006694 | 1.917800 | 2.009132 |
27 | 134.217.728 | 86.432.429 | 2.113.427 | 84.319.002 | 0.643972 | 0.015746 | 0.628226 | 2.006156 | 1.922752 | 2.008339 |
28 | 268.435.456 | 173.358.048 | 4.066.184 | 169.291.864 | 0.645809 | 0.015148 | 0.630661 | 2.005706 | 1.923977 | 2.007755 |
29 | 536.870.912 | 347.631.583 | 7.836.982 | 339.794.601 | 0.647514 | 0.014598 | 0.632917 | 2.005281 | 1.927356 | 2.007152 |
30 | 1.073.741.824 | 696.962.787 | 15.120.558 | 681.842.229 | 0.649097 | 0.014082 | 0.635015 | 2.004889 | 1.929385 | 2.006631 |
31 | 2.147.483.648 | 1.397.090.561 | 29.209.464 | 1.367.881.097 | 0.650571 | 0.013602 | 0.636969 | 2.004541 | 1.931772 | 2.006155 |
32 | 4.294.967.296 | 2.800.122.701 | 56.499.841 | 2.743.622.860 | 0.651954 | 0.013155 | 0.638799 | 2.004253 | 1.934299 | 2.005747 |
33 | 8.589.934.592 | 5.611.373.165 | 109.393.558 | 5.501.979.607 | 0.653250 | 0.012735 | 0.640515 | 2.003974 | 1.936175 | 2.005370 |
34 | 17.179.869.184 | 11.243.593.803 | 212.037.824 | 11.031.555.979 | 0.654463 | 0.012342 | 0.642121 | 2.003715 | 1.938303 | 2.005016 |
A | B | C | D | E | F | G | H | I |
exponent =log2 (x) | <=x | number of primes with p=f(x) | number of primes with p=f(x) and p%6=1 | number of primes with p=f(x) and p%6=5 | number of primes with p=f(x) and p%8=1 | number of primes with p=f(x) and p%8=3 | number of primes with p=f(x) and p%8=5 | number of primes with p=f(x) and p%8=7 |
1 | 2 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
2 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
3 | 8 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
4 | 16 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
5 | 32 | 4 | 3 | 1 | 2 | 1 | 1 | 0 |
6 | 64 | 6 | 5 | 1 | 3 | 1 | 2 | 0 |
7 | 128 | 10 | 9 | 1 | 6 | 1 | 3 | 0 |
8 | 256 | 10 | 9 | 1 | 6 | 1 | 3 | 0 |
9 | 512 | 22 | 9 | 13 | 6 | 6 | 3 | 7 |
10 | 1.024 | 44 | 9 | 35 | 6 | 16 | 3 | 19 |
11 | 2.048 | 81 | 9 | 72 | 6 | 36 | 3 | 36 |
12 | 4.096 | 152 | 9 | 143 | 6 | 66 | 3 | 77 |
13 | 8.192 | 280 | 9 | 271 | 6 | 129 | 3 | 142 |
14 | 16.384 | 537 | 9 | 528 | 6 | 263 | 3 | 265 |
15 | 32.768 | 964 | 9 | 955 | 6 | 488 | 3 | 467 |
16 | 65.536 | 1.820 | 9 | 1.811 | 6 | 915 | 3 | 896 |
17 | 131.072 | 3.396 | 9 | 3.387 | 6 | 1.724 | 3 | 1.663 |
18 | 262.144 | 6.383 | 9 | 6.374 | 6 | 3.219 | 3 | 3.155 |
19 | 524.288 | 12.111 | 9 | 12.102 | 6 | 6.122 | 3 | 5.980 |
20 | 1.048.576 | 22.904 | 9 | 22.895 | 6 | 11.534 | 3 | 11.361 |
21 | 2.097.152 | 43.444 | 9 | 43.435 | 6 | 21.706 | 3 | 21.729 |
22 | 4.194.304 | 82.392 | 9 | 82.383 | 6 | 41.316 | 3 | 41.067 |
23 | 8.388.608 | 156.854 | 9 | 156.845 | 6 | 78.617 | 3 | 78.228 |
24 | 16.777.216 | 299.249 | 9 | 299.240 | 6 | 149.872 | 3 | 149.368 |
25 | 33.554.432 | 573.140 | 9 | 573.131 | 6 | 286.958 | 3 | 286.173 |
26 | 67.108.864 | 1.099.168 | 9 | 1.099.159 | 6 | 550.092 | 3 | 549.067 |
27 | 134.217.728 | 2.113.427 | 9 | 2.113.418 | 6 | 1.057.187 | 3 | 1.056.231 |
28 | 268.435.456 | 4.066.184 | 9 | 4.066.175 | 6 | 2.033.290 | 3 | 2.032.885 |
29 | 536.870.912 | 7.836.982 | 9 | 7.836.973 | 6 | 3.918.677 | 3 | 3.918.296 |
30 | 1.073.741.824 | 15.120.558 | 9 | 15.120.549 | 6 | 7.560.246 | 3 | 7.560.303 |
31 | 2.147.483.648 | 29.209.464 | 9 | 29.209.455 | 6 | 14.603.110 | 3 | 14.606.345 |
32 | 4.294.967.296 | 56.499.841 | 9 | 56.499.832 | 6 | 28.249.544 | 3 | 28.250.288 |
33 | 8.589.934.592 | 109.393.558 | 9 | 109.393.549 | 6 | 54.697.133 | 3 | 54.696.416 |
34 | 17.179.869.184 | 212.037.824 | 9 | 212.037.815 | 6 | 106.019.146 | 3 | 106.018.669 |
A | B | C | D | E | F | G | H | I |
exponent =log2 (x) | <=x | number of primes with p|f(x) | number of primes with p=f(x) and p%6=1 | number of primes with p=f(x) and p%6=5 | number of primes with p=f(x) and p%8=1 | number of primes with p=f(x) and p%8=3 | number of primes with p=f(x) and p%8=5 | number of primes with p=f(x) and p%8=7 |
1 | 2 | 2 | 0 | 1 | 0 | 2 | 0 | 0 |
2 | 4 | 4 | 0 | 3 | 0 | 2 | 1 | 1 |
3 | 8 | 6 | 1 | 3 | 0 | 2 | 2 | 2 |
4 | 16 | 13 | 3 | 8 | 1 | 3 | 5 | 4 |
5 | 32 | 20 | 5 | 13 | 2 | 4 | 6 | 8 |
6 | 64 | 37 | 11 | 24 | 6 | 11 | 7 | 13 |
7 | 128 | 68 | 25 | 41 | 14 | 20 | 14 | 20 |
8 | 256 | 72 | 28 | 42 | 15 | 21 | 14 | 22 |
9 | 512 | 151 | 69 | 80 | 38 | 36 | 39 | 38 |
10 | 1.024 | 390 | 185 | 203 | 110 | 91 | 105 | 84 |
11 | 2.048 | 919 | 472 | 445 | 261 | 218 | 240 | 200 |
12 | 4.096 | 2.041 | 1.052 | 987 | 532 | 481 | 553 | 475 |
13 | 8.192 | 4.353 | 2.253 | 2.098 | 1.147 | 1.041 | 1.155 | 1.010 |
14 | 16.384 | 9.017 | 4.616 | 4.399 | 2.336 | 2.147 | 2.382 | 2.152 |
15 | 32.768 | 18.517 | 9.568 | 8.947 | 4.895 | 4.392 | 4.848 | 4.382 |
16 | 65.536 | 37.739 | 19.311 | 18.426 | 10.008 | 8.926 | 9.786 | 9.019 |
17 | 131.072 | 76.617 | 39.065 | 37.550 | 19.990 | 18.354 | 19.978 | 18.295 |
18 | 262.144 | 155.288 | 79.245 | 76.041 | 40.363 | 37.202 | 40.437 | 37.286 |
19 | 524.288 | 313.705 | 159.740 | 153.963 | 81.476 | 75.163 | 81.644 | 75.422 |
20 | 1.048.576 | 632.855 | 322.369 | 310.484 | 164.146 | 152.104 | 164.179 | 152.426 |
21 | 2.097.152 | 1.275.438 | 648.775 | 626.661 | 329.903 | 308.152 | 329.558 | 307.825 |
22 | 4.194.304 | 2.568.793 | 1.305.604 | 1.263.187 | 663.208 | 621.119 | 662.963 | 621.503 |
23 | 8.388.608 | 5.169.275 | 2.624.419 | 2.544.854 | 1.331.815 | 1.252.083 | 1.332.614 | 1.252.763 |
24 | 16.777.216 | 10.395.902 | 5.274.692 | 5.121.208 | 2.674.327 | 2.521.983 | 2.675.564 | 2.524.028 |
25 | 33.554.432 | 20.896.805 | 10.594.781 | 10.302.022 | 5.367.011 | 5.078.108 | 5.371.389 | 5.080.297 |
26 | 67.108.864 | 41.984.442 | 21.273.004 | 20.711.436 | 10.772.149 | 10.217.131 | 10.777.793 | 10.217.369 |
27 | 134.217.728 | 84.319.002 | 42.700.054 | 41.618.946 | 21.614.803 | 20.546.695 | 21.617.178 | 20.540.326 |
28 | 268.435.456 | 169.291.864 | 85.683.948 | 83.607.914 | 43.351.779 | 41.291.991 | 43.356.671 | 41.291.423 |
29 | 536.870.912 | 339.794.601 | 171.890.384 | 167.904.215 | 86.933.171 | 82.952.656 | 86.951.520 | 82.957.254 |
30 | 1.073.741.824 | 681.842.229 | 344.758.695 | 337.083.532 | 174.293.769 | 166.612.370 | 174.318.673 | 166.617.417 |
31 | 2.147.483.648 | 1.367.881.097 | 691.337.575 | 676.543.520 | 349.371.892 | 334.552.470 | 349.394.909 | 334.561.826 |
32 | 4.294.967.296 | 2.743.622.860 | 1.386.104.351 | 1.357.518.507 | 700.228.185 | 671.572.602 | 700.245.399 | 671.576.674 |
33 | 8.589.934.592 | 5.501.979.607 | 2.778.632.856 | 2.723.346.749 | 1.403.206.629 | 1.347.761.242 | 1.403.250.937 | 1.347.760.799 |
34 | 17.179.869.184 | 11.031.555.979 | 5.569.257.579 | 5.462.298.398 | 2.811.676.135 | 2.704.078.840 | 2.811.668.142 | 2.704.132.862 |