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+19x+3
f(0)=3
f(1)=23
f(2)=5
f(3)=1
f(4)=19
f(5)=41
f(6)=17
f(7)=37
f(8)=73
f(9)=1
f(10)=293
f(11)=1
f(12)=1
f(13)=419
f(14)=31
f(15)=1
f(16)=563
f(17)=1
f(18)=223
f(19)=29
f(20)=1
f(21)=281
f(22)=181
f(23)=1
f(24)=1
f(25)=1103
f(26)=1
f(27)=83
f(28)=1319
f(29)=1
f(30)=491
f(31)=1553
f(32)=109
f(33)=191
f(34)=1
f(35)=631
f(36)=661
f(37)=1
f(38)=241
f(39)=151
f(40)=139
f(41)=821
f(42)=1
f(43)=157
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1151
f(51)=397
f(52)=739
f(53)=67
f(54)=263
f(55)=4073
f(56)=467
f(57)=1
f(58)=1
f(59)=307
f(60)=1
f(61)=257
f(62)=1
f(63)=1723
f(64)=1063
f(65)=607
f(66)=1871
f(67)=1153
f(68)=1973
f(69)=1
f(70)=271
f(71)=2131
f(72)=1
f(73)=6719
f(74)=1
f(75)=2351
f(76)=233
f(77)=1
f(78)=1
f(79)=1549
f(80)=1
f(81)=1
f(82)=1657
f(83)=941
f(84)=577
f(85)=239
f(86)=3011
f(87)=1
f(88)=9419
f(89)=641
f(90)=3271
f(91)=1
f(92)=227
f(93)=1
f(94)=1
f(95)=1
f(96)=409
f(97)=2251
f(98)=3823
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+19x+3 could be written as f(y)= y^2-87.25 with x=y-9.5
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+9.5
f'(x)>2x+18
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 | 9 | 3 | 6 | 0.900000 | 0.300000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 62 | 12 | 50 | 0.620000 | 0.120000 | 0.500000 | 6.888889 | 4.000000 | 8.333333 |
3 | 1.000 | 661 | 81 | 580 | 0.661000 | 0.081000 | 0.580000 | 10.661290 | 6.750000 | 11.600000 |
4 | 10.000 | 6.659 | 591 | 6.068 | 0.665900 | 0.059100 | 0.606800 | 10.074130 | 7.296296 | 10.462069 |
5 | 100.000 | 67.361 | 4.435 | 62.926 | 0.673610 | 0.044350 | 0.629260 | 10.115783 | 7.504230 | 10.370138 |
6 | 1.000.000 | 676.688 | 35.948 | 640.740 | 0.676688 | 0.035948 | 0.640740 | 10.045694 | 8.105524 | 10.182437 |
7 | 10.000.000 | 6.788.362 | 303.670 | 6.484.692 | 0.678836 | 0.030367 | 0.648469 | 10.031746 | 8.447479 | 10.120629 |
8 | 100.000.000 | 68.048.806 | 2.633.032 | 65.415.774 | 0.680488 | 0.026330 | 0.654158 | 10.024334 | 8.670702 | 10.087723 |
9 | 1.000.000.000 | 681.812.168 | 23.226.947 | 658.585.221 | 0.681812 | 0.023227 | 0.658585 | 10.019458 | 8.821369 | 10.067681 |
10 | 10.000.000.000 | 6.828.786.929 | 207.875.276 | 6.620.911.653 | 0.682879 | 0.020788 | 0.662091 | 10.015642 | 8.949746 | 10.053234 |
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 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 2.000000 | 1.000000 | 3.000000 |
4 | 16 | 12 | 5 | 7 | 0.750000 | 0.312500 | 0.437500 | 1.500000 | 2.500000 | 1.166667 |
5 | 32 | 21 | 8 | 13 | 0.656250 | 0.250000 | 0.406250 | 1.750000 | 1.600000 | 1.857143 |
6 | 64 | 39 | 9 | 30 | 0.609375 | 0.140625 | 0.468750 | 1.857143 | 1.125000 | 2.307692 |
7 | 128 | 82 | 15 | 67 | 0.640625 | 0.117188 | 0.523438 | 2.102564 | 1.666667 | 2.233333 |
8 | 256 | 164 | 29 | 135 | 0.640625 | 0.113281 | 0.527344 | 2.000000 | 1.933333 | 2.014925 |
9 | 512 | 333 | 50 | 283 | 0.650391 | 0.097656 | 0.552734 | 2.030488 | 1.724138 | 2.096296 |
10 | 1.024 | 676 | 81 | 595 | 0.660156 | 0.079102 | 0.581055 | 2.030030 | 1.620000 | 2.102473 |
11 | 2.048 | 1.354 | 150 | 1.204 | 0.661133 | 0.073242 | 0.587891 | 2.002959 | 1.851852 | 2.023530 |
12 | 4.096 | 2.721 | 274 | 2.447 | 0.664307 | 0.066895 | 0.597412 | 2.009601 | 1.826667 | 2.032392 |
13 | 8.192 | 5.454 | 497 | 4.957 | 0.665771 | 0.060669 | 0.605103 | 2.004410 | 1.813869 | 2.025746 |
14 | 16.384 | 10.949 | 913 | 10.036 | 0.668274 | 0.055725 | 0.612549 | 2.007517 | 1.837022 | 2.024612 |
15 | 32.768 | 21.985 | 1.618 | 20.367 | 0.670929 | 0.049377 | 0.621552 | 2.007946 | 1.772180 | 2.029394 |
16 | 65.536 | 44.065 | 3.039 | 41.026 | 0.672379 | 0.046371 | 0.626007 | 2.004321 | 1.878245 | 2.014337 |
17 | 131.072 | 88.330 | 5.623 | 82.707 | 0.673904 | 0.042900 | 0.631004 | 2.004539 | 1.850280 | 2.015965 |
18 | 262.144 | 176.873 | 10.566 | 166.307 | 0.674717 | 0.040306 | 0.634411 | 2.002411 | 1.879068 | 2.010797 |
19 | 524.288 | 354.370 | 19.862 | 334.508 | 0.675907 | 0.037884 | 0.638023 | 2.003528 | 1.879803 | 2.011389 |
20 | 1.048.576 | 709.590 | 37.532 | 672.058 | 0.676718 | 0.035793 | 0.640924 | 2.002399 | 1.889639 | 2.009094 |
21 | 2.097.152 | 1.420.574 | 71.154 | 1.349.420 | 0.677382 | 0.033929 | 0.643454 | 2.001965 | 1.895822 | 2.007892 |
22 | 4.194.304 | 2.843.915 | 135.163 | 2.708.752 | 0.678042 | 0.032225 | 0.645817 | 2.001948 | 1.899584 | 2.007345 |
23 | 8.388.608 | 5.693.417 | 257.622 | 5.435.795 | 0.678708 | 0.030711 | 0.647997 | 2.001965 | 1.906010 | 2.006752 |
24 | 16.777.216 | 11.395.857 | 492.115 | 10.903.742 | 0.679246 | 0.029332 | 0.649914 | 2.001585 | 1.910221 | 2.005915 |
25 | 33.554.432 | 22.810.056 | 942.439 | 21.867.617 | 0.679793 | 0.028087 | 0.651706 | 2.001610 | 1.915079 | 2.005515 |
26 | 67.108.864 | 45.649.259 | 1.809.234 | 43.840.025 | 0.680227 | 0.026960 | 0.653267 | 2.001278 | 1.919736 | 2.004792 |
27 | 134.217.728 | 91.358.811 | 3.474.787 | 87.884.024 | 0.680676 | 0.025889 | 0.654787 | 2.001321 | 1.920585 | 2.004653 |
28 | 268.435.456 | 182.828.739 | 6.685.902 | 176.142.837 | 0.681090 | 0.024907 | 0.656183 | 2.001216 | 1.924119 | 2.004265 |
29 | 536.870.912 | 365.864.751 | 12.878.348 | 352.986.403 | 0.681476 | 0.023988 | 0.657488 | 2.001134 | 1.926195 | 2.003978 |
30 | 1.073.741.824 | 732.128.047 | 24.850.719 | 707.277.328 | 0.681847 | 0.023144 | 0.658703 | 2.001089 | 1.929651 | 2.003696 |
31 | 2.147.483.648 | 1.464.992.294 | 48.007.907 | 1.416.984.387 | 0.682190 | 0.022355 | 0.659835 | 2.001005 | 1.931852 | 2.003435 |
32 | 4.294.967.296 | 2.931.360.973 | 92.863.809 | 2.838.497.164 | 0.682511 | 0.021622 | 0.660889 | 2.000940 | 1.934344 | 2.003196 |
33 | 8.589.934.592 | 5.865.333.813 | 179.803.744 | 5.685.530.069 | 0.682815 | 0.020932 | 0.661883 | 2.000891 | 1.936209 | 2.003007 |
34 | 17.179.869.184 | 11.735.560.069 | 348.534.699 | 11.387.025.370 | 0.683100 | 0.020287 | 0.662812 | 2.000834 | 1.938417 | 2.002808 |
35 | 34.359.738.368 | 23.480.407.489 | 676.216.482 | 22.804.191.007 | 0.683370 | 0.019680 | 0.663689 | 2.000791 | 1.940170 | 2.002647 |
36 | 68.719.476.736 | 46.978.510.619 | 1.313.136.447 | 45.665.374.172 | 0.683627 | 0.019109 | 0.664519 | 2.000754 | 1.941887 | 2.002499 |
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 | 1 | 0 | 1 |
2 | 4 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
4 | 16 | 5 | 0 | 4 | 0 | 3 | 1 | 1 |
5 | 32 | 8 | 0 | 7 | 1 | 3 | 1 | 3 |
6 | 64 | 9 | 0 | 8 | 2 | 3 | 1 | 3 |
7 | 128 | 15 | 0 | 14 | 3 | 4 | 2 | 6 |
8 | 256 | 29 | 0 | 27 | 6 | 8 | 8 | 7 |
9 | 512 | 50 | 0 | 48 | 11 | 14 | 12 | 13 |
10 | 1.024 | 81 | 0 | 79 | 18 | 22 | 20 | 21 |
11 | 2.048 | 150 | 0 | 148 | 37 | 39 | 38 | 36 |
12 | 4.096 | 274 | 0 | 272 | 69 | 65 | 74 | 66 |
13 | 8.192 | 497 | 0 | 495 | 130 | 113 | 123 | 131 |
14 | 16.384 | 913 | 0 | 911 | 232 | 216 | 232 | 233 |
15 | 32.768 | 1.618 | 0 | 1.616 | 406 | 395 | 409 | 408 |
16 | 65.536 | 3.039 | 0 | 3.037 | 756 | 758 | 751 | 774 |
17 | 131.072 | 5.623 | 0 | 5.621 | 1.396 | 1.442 | 1.364 | 1.421 |
18 | 262.144 | 10.566 | 0 | 10.564 | 2.618 | 2.689 | 2.598 | 2.661 |
19 | 524.288 | 19.862 | 0 | 19.860 | 4.974 | 4.984 | 4.885 | 5.019 |
20 | 1.048.576 | 37.532 | 0 | 37.530 | 9.434 | 9.304 | 9.311 | 9.483 |
21 | 2.097.152 | 71.154 | 0 | 71.152 | 17.807 | 17.735 | 17.757 | 17.855 |
22 | 4.194.304 | 135.163 | 0 | 135.161 | 33.783 | 33.593 | 33.808 | 33.979 |
23 | 8.388.608 | 257.622 | 0 | 257.620 | 64.265 | 64.373 | 64.379 | 64.605 |
24 | 16.777.216 | 492.115 | 0 | 492.113 | 122.859 | 122.840 | 122.887 | 123.529 |
25 | 33.554.432 | 942.439 | 0 | 942.437 | 235.171 | 235.773 | 235.335 | 236.160 |
26 | 67.108.864 | 1.809.234 | 0 | 1.809.232 | 451.750 | 452.193 | 452.051 | 453.240 |
27 | 134.217.728 | 3.474.787 | 0 | 3.474.785 | 867.615 | 869.201 | 869.233 | 868.738 |
28 | 268.435.456 | 6.685.902 | 0 | 6.685.900 | 1.670.549 | 1.672.676 | 1.671.496 | 1.671.181 |
29 | 536.870.912 | 12.878.348 | 0 | 12.878.346 | 3.218.942 | 3.221.651 | 3.219.296 | 3.218.459 |
30 | 1.073.741.824 | 24.850.719 | 0 | 24.850.717 | 6.210.220 | 6.214.338 | 6.214.015 | 6.212.146 |
31 | 2.147.483.648 | 48.007.907 | 0 | 48.007.905 | 11.999.552 | 12.002.839 | 12.004.638 | 12.000.878 |
32 | 4.294.967.296 | 92.863.809 | 0 | 92.863.807 | 23.213.576 | 23.218.585 | 23.217.677 | 23.213.971 |
33 | 8.589.934.592 | 179.803.744 | 0 | 179.803.742 | 44.950.913 | 44.952.980 | 44.951.878 | 44.947.973 |
34 | 17.179.869.184 | 348.534.699 | 0 | 348.534.697 | 87.132.987 | 87.136.042 | 87.138.318 | 87.127.352 |
35 | 34.359.738.368 | 676.216.482 | 0 | 676.216.480 | 169.054.924 | 169.049.739 | 169.062.255 | 169.049.564 |
36 | 68.719.476.736 | 1.313.136.447 | 0 | 1.313.136.445 | 328.276.537 | 328.286.433 | 328.287.114 | 328.286.363 |
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 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
3 | 8 | 6 | 3 | 3 | 3 | 1 | 2 | 0 |
4 | 16 | 7 | 4 | 3 | 3 | 1 | 2 | 1 |
5 | 32 | 13 | 7 | 6 | 4 | 3 | 4 | 2 |
6 | 64 | 30 | 18 | 12 | 6 | 8 | 8 | 8 |
7 | 128 | 67 | 39 | 28 | 16 | 16 | 16 | 19 |
8 | 256 | 135 | 76 | 59 | 26 | 37 | 41 | 31 |
9 | 512 | 283 | 146 | 137 | 72 | 70 | 70 | 71 |
10 | 1.024 | 595 | 303 | 292 | 142 | 155 | 145 | 153 |
11 | 2.048 | 1.204 | 610 | 594 | 284 | 301 | 318 | 301 |
12 | 4.096 | 2.447 | 1.282 | 1.165 | 591 | 611 | 630 | 615 |
13 | 8.192 | 4.957 | 2.569 | 2.388 | 1.215 | 1.241 | 1.244 | 1.257 |
14 | 16.384 | 10.036 | 5.165 | 4.871 | 2.477 | 2.494 | 2.506 | 2.559 |
15 | 32.768 | 20.367 | 10.481 | 9.886 | 5.059 | 5.042 | 5.074 | 5.192 |
16 | 65.536 | 41.026 | 21.128 | 19.898 | 10.221 | 10.280 | 10.168 | 10.357 |
17 | 131.072 | 82.707 | 42.695 | 40.012 | 20.620 | 20.682 | 20.621 | 20.784 |
18 | 262.144 | 166.307 | 85.549 | 80.758 | 41.516 | 41.572 | 41.684 | 41.535 |
19 | 524.288 | 334.508 | 171.928 | 162.580 | 83.703 | 83.494 | 83.649 | 83.662 |
20 | 1.048.576 | 672.058 | 344.600 | 327.458 | 168.172 | 167.875 | 167.711 | 168.300 |
21 | 2.097.152 | 1.349.420 | 691.795 | 657.625 | 337.704 | 337.473 | 336.797 | 337.446 |
22 | 4.194.304 | 2.708.752 | 1.387.600 | 1.321.152 | 677.156 | 677.490 | 676.328 | 677.778 |
23 | 8.388.608 | 5.435.795 | 2.781.196 | 2.654.599 | 1.358.864 | 1.358.902 | 1.357.660 | 1.360.369 |
24 | 16.777.216 | 10.903.742 | 5.573.075 | 5.330.667 | 2.725.686 | 2.726.031 | 2.723.965 | 2.728.060 |
25 | 33.554.432 | 21.867.617 | 11.162.627 | 10.704.990 | 5.467.172 | 5.468.747 | 5.464.144 | 5.467.554 |
26 | 67.108.864 | 43.840.025 | 22.359.401 | 21.480.624 | 10.959.657 | 10.961.115 | 10.958.712 | 10.960.541 |
27 | 134.217.728 | 87.884.024 | 44.785.362 | 43.098.662 | 21.972.090 | 21.975.615 | 21.966.834 | 21.969.485 |
28 | 268.435.456 | 176.142.837 | 89.692.436 | 86.450.401 | 44.034.297 | 44.042.291 | 44.038.096 | 44.028.153 |
29 | 536.870.912 | 352.986.403 | 179.608.853 | 173.377.550 | 88.238.991 | 88.259.462 | 88.248.789 | 88.239.161 |
30 | 1.073.741.824 | 707.277.328 | 359.654.010 | 347.623.318 | 176.803.971 | 176.837.025 | 176.814.757 | 176.821.575 |
31 | 2.147.483.648 | 1.416.984.387 | 720.093.710 | 696.890.677 | 354.237.971 | 354.262.604 | 354.231.249 | 354.252.563 |
32 | 4.294.967.296 | 2.838.497.164 | 1.441.666.652 | 1.396.830.512 | 709.618.553 | 709.648.503 | 709.606.317 | 709.623.791 |
33 | 8.589.934.592 | 5.685.530.069 | 2.886.128.349 | 2.799.401.720 | 1.421.382.158 | 1.421.376.674 | 1.421.363.609 | 1.421.407.628 |
34 | 17.179.869.184 | 11.387.025.370 | 5.777.567.255 | 5.609.458.115 | 2.846.784.376 | 2.846.723.475 | 2.846.725.546 | 2.846.791.973 |
35 | 34.359.738.368 | 22.804.191.007 | 11.565.042.212 | 11.239.148.795 | 5.700.999.370 | 5.701.073.664 | 5.701.067.055 | 5.701.050.918 |
36 | 68.719.476.736 | 45.665.374.172 | 23.148.846.029 | 22.516.528.143 | 11.416.336.613 | 11.416.361.840 | 11.416.339.136 | 11.416.336.583 |