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-118x+3
f(0)=3
f(1)=19
f(2)=229
f(3)=1
f(4)=151
f(5)=281
f(6)=223
f(7)=43
f(8)=877
f(9)=163
f(10)=359
f(11)=587
f(12)=47
f(13)=227
f(14)=1453
f(15)=257
f(16)=181
f(17)=857
f(18)=599
f(19)=313
f(20)=103
f(21)=113
f(22)=37
f(23)=1091
f(24)=751
f(25)=1
f(26)=2389
f(27)=409
f(28)=839
f(29)=1289
f(30)=293
f(31)=449
f(32)=2749
f(33)=467
f(34)=317
f(35)=1451
f(36)=983
f(37)=499
f(38)=3037
f(39)=1
f(40)=1039
f(41)=83
f(42)=1063
f(43)=179
f(44)=3253
f(45)=547
f(46)=1103
f(47)=1667
f(48)=373
f(49)=563
f(50)=79
f(51)=569
f(52)=127
f(53)=1721
f(54)=1151
f(55)=577
f(56)=3469
f(57)=193
f(58)=61
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
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-118x+3 could be written as f(y)= y^2-3478 with x=y+59
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-59
f'(x)>2x-119 with x > 59
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 54 | 11 | 43 | 0.540000 | 0.110000 | 0.540000 | 5.400000 | 3.666667 | 6.142857 |
3 | 1.000 | 702 | 90 | 612 | 0.702000 | 0.090000 | 0.702000 | 13.000000 | 8.181818 | 14.232558 |
4 | 10.000 | 7.385 | 658 | 6.727 | 0.738500 | 0.065800 | 0.738500 | 10.519943 | 7.311111 | 10.991830 |
5 | 100.000 | 73.287 | 5.005 | 68.282 | 0.732870 | 0.050050 | 0.732870 | 9.923764 | 7.606383 | 10.150438 |
6 | 1.000.000 | 725.772 | 40.718 | 685.054 | 0.725772 | 0.040718 | 0.725772 | 9.903148 | 8.135465 | 10.032718 |
7 | 10.000.000 | 7.204.703 | 344.887 | 6.859.816 | 0.720470 | 0.034489 | 0.720470 | 9.926950 | 8.470136 | 10.013540 |
8 | 100.000.000 | 71.677.749 | 2.984.615 | 68.693.134 | 0.716778 | 0.029846 | 0.716778 | 9.948745 | 8.653893 | 10.013845 |
9 | 1.000.000.000 | 713.919.801 | 26.347.074 | 687.572.727 | 0.713920 | 0.026347 | 0.713920 | 9.960131 | 8.827629 | 10.009336 |
10 | 10.000.000.000 | 7.116.721.696 | 235.789.018 | 6.880.932.678 | 0.711672 | 0.023579 | 0.711672 | 9.968517 | 8.949344 | 10.007571 |
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 | 2 | 1 | 1.500000 | 1.000000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 2.000000 | 1.500000 | 2.500000 |
4 | 16 | 16 | 5 | 11 | 1.000000 | 0.312500 | 0.687500 | 2.000000 | 1.666667 | 2.200000 |
5 | 32 | 31 | 8 | 23 | 0.968750 | 0.250000 | 0.718750 | 1.937500 | 1.600000 | 2.090909 |
6 | 64 | 54 | 11 | 43 | 0.843750 | 0.171875 | 0.671875 | 1.741935 | 1.375000 | 1.869565 |
7 | 128 | 58 | 13 | 45 | 0.453125 | 0.101562 | 0.351562 | 1.074074 | 1.181818 | 1.046512 |
8 | 256 | 150 | 27 | 123 | 0.585938 | 0.105469 | 0.480469 | 2.586207 | 2.076923 | 2.733333 |
9 | 512 | 339 | 53 | 286 | 0.662109 | 0.103516 | 0.558594 | 2.260000 | 1.962963 | 2.325203 |
10 | 1.024 | 722 | 90 | 632 | 0.705078 | 0.087891 | 0.617188 | 2.129793 | 1.698113 | 2.209790 |
11 | 2.048 | 1.476 | 168 | 1.308 | 0.720703 | 0.082031 | 0.638672 | 2.044321 | 1.866667 | 2.069620 |
12 | 4.096 | 2.995 | 297 | 2.698 | 0.731201 | 0.072510 | 0.658691 | 2.029133 | 1.767857 | 2.062691 |
13 | 8.192 | 6.038 | 545 | 5.493 | 0.737061 | 0.066528 | 0.670532 | 2.016027 | 1.835017 | 2.035953 |
14 | 16.384 | 12.095 | 1.010 | 11.085 | 0.738220 | 0.061646 | 0.676575 | 2.003147 | 1.853211 | 2.018023 |
15 | 32.768 | 24.137 | 1.856 | 22.281 | 0.736603 | 0.056641 | 0.679962 | 1.995618 | 1.837624 | 2.010014 |
16 | 65.536 | 48.128 | 3.458 | 44.670 | 0.734375 | 0.052765 | 0.681610 | 1.993951 | 1.863147 | 2.004847 |
17 | 131.072 | 95.898 | 6.451 | 89.447 | 0.731644 | 0.049217 | 0.682426 | 1.992561 | 1.865529 | 2.002395 |
18 | 262.144 | 191.239 | 11.992 | 179.247 | 0.729519 | 0.045746 | 0.683773 | 1.994192 | 1.858937 | 2.003947 |
19 | 524.288 | 381.526 | 22.500 | 359.026 | 0.727703 | 0.042915 | 0.684788 | 1.995022 | 1.876251 | 2.002968 |
20 | 1.048.576 | 760.805 | 42.584 | 718.221 | 0.725560 | 0.040611 | 0.684949 | 1.994110 | 1.892622 | 2.000471 |
21 | 2.097.152 | 1.517.727 | 80.772 | 1.436.955 | 0.723709 | 0.038515 | 0.685194 | 1.994896 | 1.896769 | 2.000714 |
22 | 4.194.304 | 3.029.448 | 153.486 | 2.875.962 | 0.722277 | 0.036594 | 0.685683 | 1.996043 | 1.900238 | 2.001428 |
23 | 8.388.608 | 6.046.200 | 292.805 | 5.753.395 | 0.720763 | 0.034905 | 0.685858 | 1.995809 | 1.907698 | 2.000511 |
24 | 16.777.216 | 12.072.053 | 558.853 | 11.513.200 | 0.719550 | 0.033310 | 0.686240 | 1.996635 | 1.908618 | 2.001114 |
25 | 33.554.432 | 24.105.712 | 1.069.491 | 23.036.221 | 0.718406 | 0.031873 | 0.686533 | 1.996820 | 1.913725 | 2.000853 |
26 | 67.108.864 | 48.141.451 | 2.050.576 | 46.090.875 | 0.717364 | 0.030556 | 0.686808 | 1.997097 | 1.917338 | 2.000800 |
27 | 134.217.728 | 96.152.725 | 3.938.805 | 92.213.920 | 0.716394 | 0.029346 | 0.687047 | 1.997296 | 1.920829 | 2.000698 |
28 | 268.435.456 | 192.056.924 | 7.580.767 | 184.476.157 | 0.715468 | 0.028241 | 0.687227 | 1.997415 | 1.924636 | 2.000524 |
29 | 536.870.912 | 383.661.773 | 14.605.635 | 369.056.138 | 0.714626 | 0.027205 | 0.687421 | 1.997646 | 1.926670 | 2.000563 |
30 | 1.073.741.824 | 766.481.734 | 28.187.287 | 738.294.447 | 0.713842 | 0.026251 | 0.687590 | 1.997806 | 1.929891 | 2.000494 |
31 | 2.147.483.648 | 1.531.398.468 | 54.459.561 | 1.476.938.907 | 0.713113 | 0.025360 | 0.687753 | 1.997958 | 1.932061 | 2.000474 |
32 | 4.294.967.296 | 3.059.903.426 | 105.336.997 | 2.954.566.429 | 0.712439 | 0.024526 | 0.687914 | 1.998111 | 1.934224 | 2.000466 |
33 | 8.589.934.592 | 6.114.376.542 | 203.950.336 | 5.910.426.206 | 0.711807 | 0.023743 | 0.688064 | 1.998225 | 1.936170 | 2.000438 |
34 | 17.179.869.184 | 12.218.533.975 | 395.321.694 | 11.823.212.281 | 0.711212 | 0.023011 | 0.688202 | 1.998329 | 1.938323 | 2.000399 |
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 | 1 | 0 | 0 | 1 | 1 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 3 | 2 | 0 | 0 | 1 | 2 | 0 |
4 | 16 | 5 | 3 | 0 | 0 | 1 | 4 | 0 |
5 | 32 | 8 | 5 | 0 | 0 | 1 | 7 | 0 |
6 | 64 | 11 | 8 | 0 | 0 | 1 | 10 | 0 |
7 | 128 | 13 | 8 | 2 | 0 | 3 | 10 | 0 |
8 | 256 | 27 | 8 | 16 | 0 | 17 | 10 | 0 |
9 | 512 | 53 | 8 | 42 | 0 | 43 | 10 | 0 |
10 | 1.024 | 90 | 8 | 79 | 0 | 80 | 10 | 0 |
11 | 2.048 | 168 | 8 | 157 | 0 | 158 | 10 | 0 |
12 | 4.096 | 297 | 8 | 286 | 0 | 287 | 10 | 0 |
13 | 8.192 | 545 | 8 | 534 | 0 | 535 | 10 | 0 |
14 | 16.384 | 1.010 | 8 | 999 | 0 | 1.000 | 10 | 0 |
15 | 32.768 | 1.856 | 8 | 1.845 | 0 | 1.846 | 10 | 0 |
16 | 65.536 | 3.458 | 8 | 3.447 | 0 | 3.448 | 10 | 0 |
17 | 131.072 | 6.451 | 8 | 6.440 | 0 | 6.441 | 10 | 0 |
18 | 262.144 | 11.992 | 8 | 11.981 | 0 | 11.982 | 10 | 0 |
19 | 524.288 | 22.500 | 8 | 22.489 | 0 | 22.490 | 10 | 0 |
20 | 1.048.576 | 42.584 | 8 | 42.573 | 0 | 42.574 | 10 | 0 |
21 | 2.097.152 | 80.772 | 8 | 80.761 | 0 | 80.762 | 10 | 0 |
22 | 4.194.304 | 153.486 | 8 | 153.475 | 0 | 153.476 | 10 | 0 |
23 | 8.388.608 | 292.805 | 8 | 292.794 | 0 | 292.795 | 10 | 0 |
24 | 16.777.216 | 558.853 | 8 | 558.842 | 0 | 558.843 | 10 | 0 |
25 | 33.554.432 | 1.069.491 | 8 | 1.069.480 | 0 | 1.069.481 | 10 | 0 |
26 | 67.108.864 | 2.050.576 | 8 | 2.050.565 | 0 | 2.050.566 | 10 | 0 |
27 | 134.217.728 | 3.938.805 | 8 | 3.938.794 | 0 | 3.938.795 | 10 | 0 |
28 | 268.435.456 | 7.580.767 | 8 | 7.580.756 | 0 | 7.580.757 | 10 | 0 |
29 | 536.870.912 | 14.605.635 | 8 | 14.605.624 | 0 | 14.605.625 | 10 | 0 |
30 | 1.073.741.824 | 28.187.287 | 8 | 28.187.276 | 0 | 28.187.277 | 10 | 0 |
31 | 2.147.483.648 | 54.459.561 | 8 | 54.459.550 | 0 | 54.459.551 | 10 | 0 |
32 | 4.294.967.296 | 105.336.997 | 8 | 105.336.986 | 0 | 105.336.987 | 10 | 0 |
33 | 8.589.934.592 | 203.950.336 | 8 | 203.950.325 | 0 | 203.950.326 | 10 | 0 |
34 | 17.179.869.184 | 395.321.694 | 8 | 395.321.683 | 0 | 395.321.684 | 10 | 0 |
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 | 1 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 2 | 0 | 0 | 1 | 0 | 1 |
3 | 8 | 5 | 4 | 1 | 1 | 2 | 0 | 2 |
4 | 16 | 11 | 6 | 5 | 2 | 5 | 1 | 3 |
5 | 32 | 23 | 10 | 13 | 8 | 6 | 2 | 7 |
6 | 64 | 43 | 18 | 25 | 12 | 14 | 4 | 13 |
7 | 128 | 45 | 20 | 25 | 13 | 14 | 4 | 14 |
8 | 256 | 123 | 62 | 61 | 37 | 22 | 26 | 38 |
9 | 512 | 286 | 155 | 131 | 85 | 45 | 76 | 80 |
10 | 1.024 | 632 | 345 | 287 | 183 | 101 | 169 | 179 |
11 | 2.048 | 1.308 | 730 | 578 | 368 | 210 | 340 | 390 |
12 | 4.096 | 2.698 | 1.482 | 1.216 | 753 | 465 | 716 | 764 |
13 | 8.192 | 5.493 | 2.981 | 2.512 | 1.501 | 967 | 1.498 | 1.527 |
14 | 16.384 | 11.085 | 6.015 | 5.070 | 2.969 | 2.038 | 3.038 | 3.040 |
15 | 32.768 | 22.281 | 12.059 | 10.222 | 5.995 | 4.149 | 6.070 | 6.067 |
16 | 65.536 | 44.670 | 24.165 | 20.505 | 11.885 | 8.514 | 12.109 | 12.162 |
17 | 131.072 | 89.447 | 47.971 | 41.476 | 23.703 | 17.399 | 24.160 | 24.185 |
18 | 262.144 | 179.247 | 95.647 | 83.600 | 47.630 | 35.285 | 48.171 | 48.161 |
19 | 524.288 | 359.026 | 191.266 | 167.760 | 95.147 | 71.996 | 95.795 | 96.088 |
20 | 1.048.576 | 718.221 | 381.398 | 336.823 | 189.444 | 146.336 | 191.601 | 190.840 |
21 | 2.097.152 | 1.436.955 | 760.365 | 676.590 | 377.898 | 296.444 | 381.291 | 381.322 |
22 | 4.194.304 | 2.875.962 | 1.517.177 | 1.358.785 | 755.663 | 599.217 | 760.731 | 760.351 |
23 | 8.388.608 | 5.753.395 | 3.028.199 | 2.725.196 | 1.508.172 | 1.210.627 | 1.516.868 | 1.517.728 |
24 | 16.777.216 | 11.513.200 | 6.045.493 | 5.467.707 | 3.012.537 | 2.443.286 | 3.028.432 | 3.028.945 |
25 | 33.554.432 | 23.036.221 | 12.070.744 | 10.965.477 | 6.016.491 | 4.928.490 | 6.045.445 | 6.045.795 |
26 | 67.108.864 | 46.090.875 | 24.101.540 | 21.989.335 | 12.020.637 | 9.929.562 | 12.071.944 | 12.068.732 |
27 | 134.217.728 | 92.213.920 | 48.130.968 | 44.082.952 | 24.010.972 | 19.998.601 | 24.102.451 | 24.101.896 |
28 | 268.435.456 | 184.476.157 | 96.120.383 | 88.355.774 | 47.962.434 | 40.251.474 | 48.134.513 | 48.127.736 |
29 | 536.870.912 | 369.056.138 | 192.002.953 | 177.053.185 | 95.822.669 | 80.963.752 | 96.132.472 | 96.137.245 |
30 | 1.073.741.824 | 738.294.447 | 383.555.131 | 354.739.316 | 191.456.545 | 162.789.312 | 192.010.863 | 192.037.727 |
31 | 2.147.483.648 | 1.476.938.907 | 766.312.561 | 710.626.346 | 382.539.938 | 327.177.427 | 383.581.143 | 383.640.399 |
32 | 4.294.967.296 | 2.954.566.429 | 1.531.077.342 | 1.423.489.087 | 764.384.435 | 657.375.556 | 766.364.916 | 766.441.522 |
33 | 8.589.934.592 | 5.910.426.206 | 3.059.296.542 | 2.851.129.664 | 1.527.542.442 | 1.320.379.477 | 1.531.171.408 | 1.531.332.879 |
34 | 17.179.869.184 | 11.823.212.281 | 6.113.199.124 | 5.710.013.157 | 3.052.645.419 | 2.651.343.901 | 3.059.512.872 | 3.059.710.089 |