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+96x-5
f(0)=5
f(1)=23
f(2)=191
f(3)=73
f(4)=79
f(5)=1
f(6)=607
f(7)=179
f(8)=827
f(9)=47
f(10)=211
f(11)=293
f(12)=1291
f(13)=353
f(14)=307
f(15)=83
f(16)=1787
f(17)=479
f(18)=89
f(19)=109
f(20)=463
f(21)=613
f(22)=2591
f(23)=683
f(24)=1
f(25)=151
f(26)=3167
f(27)=829
f(28)=3467
f(29)=181
f(30)=1
f(31)=983
f(32)=4091
f(33)=1063
f(34)=883
f(35)=229
f(36)=101
f(37)=1229
f(38)=5087
f(39)=263
f(40)=1087
f(41)=61
f(42)=5791
f(43)=1493
f(44)=1231
f(45)=317
f(46)=107
f(47)=1
f(48)=6907
f(49)=71
f(50)=1459
f(51)=1873
f(52)=7691
f(53)=1973
f(54)=1619
f(55)=1
f(56)=1
f(57)=2179
f(58)=113
f(59)=457
f(60)=1871
f(61)=2393
f(62)=9791
f(63)=2503
f(64)=1
f(65)=523
f(66)=10687
f(67)=2729
f(68)=157
f(69)=569
f(70)=1
f(71)=2963
f(72)=1
f(73)=3083
f(74)=503
f(75)=641
f(76)=1
f(77)=3329
f(78)=13567
f(79)=691
f(80)=563
f(81)=3583
f(82)=14591
f(83)=1
f(84)=3023
f(85)=769
f(86)=15647
f(87)=173
f(88)=16187
f(89)=823
f(90)=3347
f(91)=4253
f(92)=17291
f(93)=1
f(94)=3571
f(95)=907
f(96)=18427
f(97)=4679
f(98)=1
f(99)=193
b) Substitution of the polynom
The polynom f(x)=x^2+96x-5 could be written as f(y)= y^2-2309 with x=y-48
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+48
f'(x)>2x+95
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 | 7 | 3 | 1.000000 | 0.700000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 83 | 47 | 36 | 0.830000 | 0.470000 | 0.360000 | 8.300000 | 6.714286 | 12.000000 |
3 | 1.000 | 742 | 329 | 413 | 0.742000 | 0.329000 | 0.413000 | 8.939759 | 7.000000 | 11.472222 |
4 | 10.000 | 7.272 | 2.335 | 4.937 | 0.727200 | 0.233500 | 0.493700 | 9.800539 | 7.097264 | 11.953995 |
5 | 100.000 | 71.881 | 17.927 | 53.954 | 0.718810 | 0.179270 | 0.539540 | 9.884626 | 7.677516 | 10.928499 |
6 | 1.000.000 | 713.917 | 145.881 | 568.036 | 0.713917 | 0.145881 | 0.568036 | 9.931930 | 8.137502 | 10.528153 |
7 | 10.000.000 | 7.107.015 | 1.228.089 | 5.878.926 | 0.710702 | 0.122809 | 0.587893 | 9.954960 | 8.418430 | 10.349566 |
8 | 100.000.000 | 70.828.648 | 10.608.189 | 60.220.459 | 0.708286 | 0.106082 | 0.602205 | 9.966020 | 8.637964 | 10.243445 |
9 | 1.000.000.000 | 706.431.190 | 93.394.345 | 613.036.845 | 0.706431 | 0.093394 | 0.613037 | 9.973805 | 8.803986 | 10.179877 |
10 | 10.000.000.000 | 7.049.754.375 | 834.081.679 | 6.215.672.696 | 0.704975 | 0.083408 | 0.621567 | 9.979394 | 8.930752 | 10.139151 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.750000 | 1.000000 |
4 | 16 | 16 | 11 | 5 | 1.000000 | 0.687500 | 0.312500 | 2.000000 | 1.571429 | 5.000000 |
5 | 32 | 30 | 20 | 10 | 0.937500 | 0.625000 | 0.312500 | 1.875000 | 1.818182 | 2.000000 |
6 | 64 | 55 | 33 | 22 | 0.859375 | 0.515625 | 0.343750 | 1.833333 | 1.650000 | 2.200000 |
7 | 128 | 105 | 60 | 45 | 0.820312 | 0.468750 | 0.351562 | 1.909091 | 1.818182 | 2.045455 |
8 | 256 | 203 | 106 | 97 | 0.792969 | 0.414062 | 0.378906 | 1.933333 | 1.766667 | 2.155555 |
9 | 512 | 383 | 193 | 190 | 0.748047 | 0.376953 | 0.371094 | 1.886700 | 1.820755 | 1.958763 |
10 | 1.024 | 760 | 334 | 426 | 0.742188 | 0.326172 | 0.416016 | 1.984334 | 1.730570 | 2.242105 |
11 | 2.048 | 1.516 | 597 | 919 | 0.740234 | 0.291504 | 0.448730 | 1.994737 | 1.787425 | 2.157277 |
12 | 4.096 | 3.003 | 1.080 | 1.923 | 0.733154 | 0.263672 | 0.469482 | 1.980871 | 1.809045 | 2.092492 |
13 | 8.192 | 5.967 | 1.974 | 3.993 | 0.728394 | 0.240967 | 0.487427 | 1.987013 | 1.827778 | 2.076443 |
14 | 16.384 | 11.890 | 3.584 | 8.306 | 0.725708 | 0.218750 | 0.506958 | 1.992626 | 1.815603 | 2.080140 |
15 | 32.768 | 23.685 | 6.607 | 17.078 | 0.722809 | 0.201630 | 0.521179 | 1.992010 | 1.843471 | 2.056104 |
16 | 65.536 | 47.194 | 12.304 | 34.890 | 0.720123 | 0.187744 | 0.532379 | 1.992569 | 1.862267 | 2.042979 |
17 | 131.072 | 94.084 | 22.929 | 71.155 | 0.717804 | 0.174934 | 0.542870 | 1.993559 | 1.863540 | 2.039410 |
18 | 262.144 | 187.728 | 43.008 | 144.720 | 0.716125 | 0.164062 | 0.552063 | 1.995323 | 1.875703 | 2.033870 |
19 | 524.288 | 374.781 | 80.794 | 293.987 | 0.714838 | 0.154102 | 0.560736 | 1.996404 | 1.878581 | 2.031419 |
20 | 1.048.576 | 748.421 | 152.420 | 596.001 | 0.713750 | 0.145359 | 0.568391 | 1.996956 | 1.886526 | 2.027304 |
21 | 2.097.152 | 1.494.814 | 288.623 | 1.206.191 | 0.712783 | 0.137626 | 0.575157 | 1.997290 | 1.893603 | 2.023807 |
22 | 4.194.304 | 2.985.285 | 547.916 | 2.437.369 | 0.711747 | 0.130633 | 0.581114 | 1.997095 | 1.898380 | 2.020716 |
23 | 8.388.608 | 5.963.124 | 1.042.730 | 4.920.394 | 0.710860 | 0.124303 | 0.586557 | 1.997506 | 1.903084 | 2.018732 |
24 | 16.777.216 | 11.912.936 | 1.990.206 | 9.922.730 | 0.710066 | 0.118626 | 0.591441 | 1.997768 | 1.908649 | 2.016654 |
25 | 33.554.432 | 23.799.724 | 3.807.594 | 19.992.130 | 0.709287 | 0.113475 | 0.595812 | 1.997805 | 1.913166 | 2.014781 |
26 | 67.108.864 | 47.556.235 | 7.291.775 | 40.264.460 | 0.708643 | 0.108656 | 0.599987 | 1.998184 | 1.915061 | 2.014015 |
27 | 134.217.728 | 95.027.613 | 13.996.393 | 81.031.220 | 0.708011 | 0.104281 | 0.603730 | 1.998216 | 1.919477 | 2.012475 |
28 | 268.435.456 | 189.898.060 | 26.910.968 | 162.987.092 | 0.707425 | 0.100251 | 0.607174 | 1.998346 | 1.922707 | 2.011411 |
29 | 536.870.912 | 379.504.165 | 51.817.395 | 327.686.770 | 0.706882 | 0.096517 | 0.610364 | 1.998463 | 1.925512 | 2.010508 |
30 | 1.073.741.824 | 758.470.238 | 99.910.577 | 658.559.661 | 0.706380 | 0.093049 | 0.613331 | 1.998582 | 1.928128 | 2.009723 |
31 | 2.147.483.648 | 1.515.925.594 | 192.884.497 | 1.323.041.097 | 0.705908 | 0.089819 | 0.616089 | 1.998662 | 1.930571 | 2.008992 |
32 | 4.294.967.296 | 3.029.969.930 | 372.861.964 | 2.657.107.966 | 0.705470 | 0.086814 | 0.618656 | 1.998759 | 1.933084 | 2.008334 |
33 | 8.589.934.592 | 6.056.433.417 | 721.566.450 | 5.334.866.967 | 0.705062 | 0.084001 | 0.621060 | 1.998843 | 1.935211 | 2.007772 |
34 | 17.179.869.184 | 12.106.237.802 | 1.397.894.283 | 10.708.343.519 | 0.704676 | 0.081368 | 0.623308 | 1.998905 | 1.937305 | 2.007237 |
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 | 3 | 0 | 3 | 0 | 0 | 1 | 2 |
2 | 4 | 4 | 1 | 3 | 1 | 0 | 1 | 2 |
3 | 8 | 7 | 2 | 5 | 1 | 2 | 1 | 3 |
4 | 16 | 11 | 3 | 8 | 2 | 4 | 2 | 3 |
5 | 32 | 20 | 5 | 15 | 2 | 7 | 4 | 7 |
6 | 64 | 33 | 11 | 22 | 4 | 10 | 7 | 12 |
7 | 128 | 60 | 20 | 40 | 6 | 18 | 11 | 25 |
8 | 256 | 106 | 33 | 73 | 15 | 36 | 15 | 40 |
9 | 512 | 193 | 60 | 133 | 23 | 71 | 26 | 73 |
10 | 1.024 | 334 | 106 | 228 | 42 | 119 | 43 | 130 |
11 | 2.048 | 597 | 201 | 396 | 75 | 213 | 72 | 237 |
12 | 4.096 | 1.080 | 366 | 714 | 142 | 400 | 125 | 413 |
13 | 8.192 | 1.974 | 670 | 1.304 | 256 | 715 | 249 | 754 |
14 | 16.384 | 3.584 | 1.203 | 2.381 | 480 | 1.304 | 452 | 1.348 |
15 | 32.768 | 6.607 | 2.186 | 4.421 | 868 | 2.442 | 849 | 2.448 |
16 | 65.536 | 12.304 | 4.113 | 8.191 | 1.589 | 4.590 | 1.536 | 4.589 |
17 | 131.072 | 22.929 | 7.702 | 15.227 | 3.010 | 8.532 | 2.891 | 8.496 |
18 | 262.144 | 43.008 | 14.256 | 28.752 | 5.625 | 15.991 | 5.520 | 15.872 |
19 | 524.288 | 80.794 | 26.922 | 53.872 | 10.537 | 30.036 | 10.351 | 29.870 |
20 | 1.048.576 | 152.420 | 50.857 | 101.563 | 19.697 | 56.590 | 19.548 | 56.585 |
21 | 2.097.152 | 288.623 | 96.321 | 192.302 | 37.290 | 107.309 | 37.048 | 106.976 |
22 | 4.194.304 | 547.916 | 182.941 | 364.975 | 70.528 | 203.859 | 70.101 | 203.428 |
23 | 8.388.608 | 1.042.730 | 347.769 | 694.961 | 133.856 | 388.068 | 133.206 | 387.600 |
24 | 16.777.216 | 1.990.206 | 663.378 | 1.326.828 | 255.199 | 739.911 | 254.125 | 740.971 |
25 | 33.554.432 | 3.807.594 | 1.270.022 | 2.537.572 | 487.354 | 1.416.585 | 486.128 | 1.417.527 |
26 | 67.108.864 | 7.291.775 | 2.431.739 | 4.860.036 | 931.574 | 2.713.794 | 930.478 | 2.715.929 |
27 | 134.217.728 | 13.996.393 | 4.666.759 | 9.329.634 | 1.785.088 | 5.211.591 | 1.784.582 | 5.215.132 |
28 | 268.435.456 | 26.910.968 | 8.970.925 | 17.940.043 | 3.428.730 | 10.024.937 | 3.429.304 | 10.027.997 |
29 | 536.870.912 | 51.817.395 | 17.274.318 | 34.543.077 | 6.598.497 | 19.306.635 | 6.596.779 | 19.315.484 |
30 | 1.073.741.824 | 99.910.577 | 33.307.833 | 66.602.744 | 12.714.936 | 37.236.394 | 12.710.956 | 37.248.291 |
31 | 2.147.483.648 | 192.884.497 | 64.300.844 | 128.583.653 | 24.528.361 | 71.909.809 | 24.528.415 | 71.917.912 |
32 | 4.294.967.296 | 372.861.964 | 124.291.315 | 248.570.649 | 47.383.661 | 139.041.344 | 47.388.412 | 139.048.547 |
33 | 8.589.934.592 | 721.566.450 | 240.520.321 | 481.046.129 | 91.654.874 | 269.117.417 | 91.653.876 | 269.140.283 |
34 | 17.179.869.184 | 1.397.894.283 | 465.963.857 | 931.930.426 | 177.473.331 | 521.464.548 | 177.472.163 | 521.484.241 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
4 | 16 | 5 | 3 | 2 | 0 | 3 | 0 | 2 |
5 | 32 | 10 | 7 | 3 | 1 | 3 | 2 | 4 |
6 | 64 | 22 | 13 | 9 | 2 | 7 | 5 | 8 |
7 | 128 | 45 | 28 | 17 | 5 | 16 | 10 | 14 |
8 | 256 | 97 | 61 | 36 | 11 | 35 | 19 | 32 |
9 | 512 | 190 | 114 | 76 | 30 | 66 | 33 | 61 |
10 | 1.024 | 426 | 248 | 178 | 73 | 129 | 84 | 140 |
11 | 2.048 | 919 | 511 | 408 | 182 | 275 | 189 | 273 |
12 | 4.096 | 1.923 | 1.079 | 844 | 411 | 561 | 394 | 557 |
13 | 8.192 | 3.993 | 2.193 | 1.800 | 848 | 1.131 | 874 | 1.140 |
14 | 16.384 | 8.306 | 4.486 | 3.820 | 1.816 | 2.330 | 1.831 | 2.329 |
15 | 32.768 | 17.078 | 9.116 | 7.962 | 3.839 | 4.731 | 3.802 | 4.706 |
16 | 65.536 | 34.890 | 18.536 | 16.354 | 7.828 | 9.534 | 7.936 | 9.592 |
17 | 131.072 | 71.155 | 37.592 | 33.563 | 16.170 | 19.282 | 16.256 | 19.447 |
18 | 262.144 | 144.720 | 76.276 | 68.444 | 33.202 | 39.089 | 33.305 | 39.124 |
19 | 524.288 | 293.987 | 154.340 | 139.647 | 67.910 | 79.045 | 68.145 | 78.887 |
20 | 1.048.576 | 596.001 | 311.672 | 284.329 | 138.395 | 159.422 | 138.891 | 159.293 |
21 | 2.097.152 | 1.206.191 | 628.888 | 577.303 | 281.525 | 320.939 | 283.036 | 320.691 |
22 | 4.194.304 | 2.437.369 | 1.266.848 | 1.170.521 | 572.351 | 645.473 | 574.072 | 645.473 |
23 | 8.388.608 | 4.920.394 | 2.552.021 | 2.368.373 | 1.160.879 | 1.299.597 | 1.161.250 | 1.298.668 |
24 | 16.777.216 | 9.922.730 | 5.138.878 | 4.783.852 | 2.349.041 | 2.613.365 | 2.348.269 | 2.612.055 |
25 | 33.554.432 | 19.992.130 | 10.332.109 | 9.660.021 | 4.747.004 | 5.251.696 | 4.743.262 | 5.250.168 |
26 | 67.108.864 | 40.264.460 | 20.777.229 | 19.487.231 | 9.584.940 | 10.549.225 | 9.581.746 | 10.548.549 |
27 | 134.217.728 | 81.031.220 | 41.754.616 | 39.276.604 | 19.334.874 | 21.181.102 | 19.332.928 | 21.182.316 |
28 | 268.435.456 | 162.987.092 | 83.871.276 | 79.115.816 | 38.969.889 | 42.523.007 | 38.966.008 | 42.528.188 |
29 | 536.870.912 | 327.686.770 | 168.412.537 | 159.274.233 | 78.503.339 | 85.341.207 | 78.501.380 | 85.340.844 |
30 | 1.073.741.824 | 658.559.661 | 338.065.301 | 320.494.360 | 158.052.178 | 171.235.803 | 158.043.543 | 171.228.137 |
31 | 2.147.483.648 | 1.323.041.097 | 678.452.130 | 644.588.967 | 318.046.139 | 343.476.138 | 318.037.589 | 343.481.231 |
32 | 4.294.967.296 | 2.657.107.966 | 1.361.262.374 | 1.295.845.592 | 639.721.991 | 688.832.114 | 639.730.882 | 688.822.979 |
33 | 8.589.934.592 | 5.334.866.967 | 2.730.613.469 | 2.604.253.498 | 1.286.190.454 | 1.381.219.029 | 1.286.223.105 | 1.381.234.379 |
34 | 17.179.869.184 | 10.708.343.519 | 5.476.470.392 | 5.231.873.127 | 2.585.080.137 | 2.769.091.524 | 2.585.094.497 | 2.769.077.361 |