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+80x-41
f(0)=41
f(1)=5
f(2)=3
f(3)=13
f(4)=59
f(5)=1
f(6)=19
f(7)=71
f(8)=17
f(9)=1
f(10)=859
f(11)=1
f(12)=1063
f(13)=73
f(14)=1
f(15)=173
f(16)=23
f(17)=67
f(18)=1723
f(19)=1
f(20)=653
f(21)=1
f(22)=2203
f(23)=97
f(24)=491
f(25)=1
f(26)=181
f(27)=89
f(28)=157
f(29)=1
f(30)=3259
f(31)=1
f(32)=1181
f(33)=461
f(34)=1
f(35)=83
f(36)=827
f(37)=1
f(38)=1481
f(39)=1
f(40)=4759
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=349
f(46)=1151
f(47)=1
f(48)=359
f(49)=1
f(50)=2153
f(51)=1
f(52)=6823
f(53)=1
f(54)=1439
f(55)=1
f(56)=101
f(57)=971
f(58)=7963
f(59)=1
f(60)=643
f(61)=107
f(62)=127
f(63)=1
f(64)=367
f(65)=1
f(66)=1
f(67)=613
f(68)=257
f(69)=1
f(70)=10459
f(71)=1
f(72)=10903
f(73)=1
f(74)=757
f(75)=1
f(76)=139
f(77)=251
f(78)=1
f(79)=313
f(80)=4253
f(81)=1
f(82)=1
f(83)=281
f(84)=1
f(85)=1
f(86)=1
f(87)=1811
f(88)=641
f(89)=1
f(90)=15259
f(91)=1
f(92)=5261
f(93)=1
f(94)=1
f(95)=691
f(96)=3371
f(97)=2141
f(98)=5801
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+80x-41 could be written as f(y)= y^2-1641 with x=y-40
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+40
f'(x)>2x+79
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.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 57 | 14 | 43 | 0.570000 | 0.140000 | 0.570000 | 6.333333 | 4.666667 | 7.166667 |
3 | 1.000 | 596 | 73 | 523 | 0.596000 | 0.073000 | 0.596000 | 10.456141 | 5.214286 | 12.162790 |
4 | 10.000 | 6.150 | 531 | 5.619 | 0.615000 | 0.053100 | 0.615000 | 10.318792 | 7.273973 | 10.743786 |
5 | 100.000 | 63.397 | 4.101 | 59.296 | 0.633970 | 0.041010 | 0.633970 | 10.308455 | 7.723164 | 10.552768 |
6 | 1.000.000 | 644.487 | 33.492 | 610.995 | 0.644487 | 0.033492 | 0.644487 | 10.165891 | 8.166789 | 10.304152 |
7 | 10.000.000 | 6.516.611 | 283.190 | 6.233.421 | 0.651661 | 0.028319 | 0.651661 | 10.111315 | 8.455452 | 10.202082 |
8 | 100.000.000 | 65.700.249 | 2.450.927 | 63.249.322 | 0.657003 | 0.024509 | 0.657003 | 10.081965 | 8.654709 | 10.146807 |
9 | 1.000.000.000 | 661.114.426 | 21.618.161 | 639.496.265 | 0.661114 | 0.021618 | 0.661114 | 10.062587 | 8.820401 | 10.110722 |
10 | 10.000.000.000 | 6.643.826.284 | 193.463.962 | 6.450.362.322 | 0.664383 | 0.019346 | 0.664383 | 10.049435 | 8.949142 | 10.086631 |
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 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 1.600000 | 1.000000 | 2.000000 |
4 | 16 | 12 | 4 | 8 | 0.750000 | 0.250000 | 0.500000 | 1.500000 | 2.000000 | 1.333333 |
5 | 32 | 23 | 7 | 16 | 0.718750 | 0.218750 | 0.500000 | 1.916667 | 1.750000 | 2.000000 |
6 | 64 | 39 | 10 | 29 | 0.609375 | 0.156250 | 0.453125 | 1.695652 | 1.428571 | 1.812500 |
7 | 128 | 70 | 15 | 55 | 0.546875 | 0.117188 | 0.429688 | 1.794872 | 1.500000 | 1.896552 |
8 | 256 | 145 | 25 | 120 | 0.566406 | 0.097656 | 0.468750 | 2.071429 | 1.666667 | 2.181818 |
9 | 512 | 300 | 42 | 258 | 0.585938 | 0.082031 | 0.503906 | 2.068965 | 1.680000 | 2.150000 |
10 | 1.024 | 611 | 74 | 537 | 0.596680 | 0.072266 | 0.524414 | 2.036667 | 1.761905 | 2.081395 |
11 | 2.048 | 1.233 | 137 | 1.096 | 0.602051 | 0.066895 | 0.535156 | 2.018003 | 1.851351 | 2.040968 |
12 | 4.096 | 2.506 | 235 | 2.271 | 0.611816 | 0.057373 | 0.554443 | 2.032441 | 1.715328 | 2.072080 |
13 | 8.192 | 5.041 | 441 | 4.600 | 0.615356 | 0.053833 | 0.561523 | 2.011572 | 1.876596 | 2.025539 |
14 | 16.384 | 10.162 | 854 | 9.308 | 0.620239 | 0.052124 | 0.568115 | 2.015870 | 1.936508 | 2.023478 |
15 | 32.768 | 20.508 | 1.544 | 18.964 | 0.625854 | 0.047119 | 0.578735 | 2.018107 | 1.807963 | 2.037387 |
16 | 65.536 | 41.354 | 2.815 | 38.539 | 0.631012 | 0.042953 | 0.588058 | 2.016481 | 1.823187 | 2.032219 |
17 | 131.072 | 83.337 | 5.201 | 78.136 | 0.635811 | 0.039680 | 0.596130 | 2.015210 | 1.847602 | 2.027453 |
18 | 262.144 | 167.544 | 9.796 | 157.748 | 0.639130 | 0.037369 | 0.601761 | 2.010440 | 1.883484 | 2.018890 |
19 | 524.288 | 336.615 | 18.426 | 318.189 | 0.642042 | 0.035145 | 0.606897 | 2.009114 | 1.880972 | 2.017071 |
20 | 1.048.576 | 675.864 | 34.972 | 640.892 | 0.644554 | 0.033352 | 0.611202 | 2.007825 | 1.897970 | 2.014187 |
21 | 2.097.152 | 1.356.547 | 66.197 | 1.290.350 | 0.646852 | 0.031565 | 0.615287 | 2.007130 | 1.892857 | 2.013366 |
22 | 4.194.304 | 2.722.981 | 125.909 | 2.597.072 | 0.649209 | 0.030019 | 0.619190 | 2.007288 | 1.902035 | 2.012688 |
23 | 8.388.608 | 5.462.752 | 240.212 | 5.222.540 | 0.651211 | 0.028636 | 0.622575 | 2.006166 | 1.907822 | 2.010934 |
24 | 16.777.216 | 10.956.220 | 458.336 | 10.497.884 | 0.653042 | 0.027319 | 0.625723 | 2.005623 | 1.908048 | 2.010111 |
25 | 33.554.432 | 21.966.855 | 877.613 | 21.089.242 | 0.654663 | 0.026155 | 0.628508 | 2.004967 | 1.914781 | 2.008904 |
26 | 67.108.864 | 44.036.949 | 1.683.534 | 42.353.415 | 0.656202 | 0.025087 | 0.631115 | 2.004700 | 1.918310 | 2.008295 |
27 | 134.217.728 | 88.260.754 | 3.234.095 | 85.026.659 | 0.657594 | 0.024096 | 0.633498 | 2.004243 | 1.921016 | 2.007551 |
28 | 268.435.456 | 176.871.911 | 6.220.989 | 170.650.922 | 0.658899 | 0.023175 | 0.635724 | 2.003970 | 1.923564 | 2.007029 |
29 | 536.870.912 | 354.386.178 | 11.989.187 | 342.396.991 | 0.660096 | 0.022332 | 0.637764 | 2.003632 | 1.927216 | 2.006418 |
30 | 1.073.741.824 | 709.987.759 | 23.127.453 | 686.860.306 | 0.661228 | 0.021539 | 0.639688 | 2.003430 | 1.929026 | 2.006035 |
31 | 2.147.483.648 | 1.422.234.224 | 44.680.943 | 1.377.553.281 | 0.662279 | 0.020806 | 0.641473 | 2.003181 | 1.931944 | 2.005580 |
32 | 4.294.967.296 | 2.848.698.898 | 86.420.398 | 2.762.278.500 | 0.663264 | 0.020121 | 0.643143 | 2.002975 | 1.934167 | 2.005206 |
33 | 8.589.934.592 | 5.705.323.278 | 167.339.746 | 5.537.983.532 | 0.664187 | 0.019481 | 0.644706 | 2.002782 | 1.936345 | 2.004861 |
34 | 17.179.869.184 | 11.425.558.910 | 324.372.298 | 11.101.186.612 | 0.665055 | 0.018881 | 0.646174 | 2.002614 | 1.938406 | 2.004554 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
4 | 16 | 4 | 2 | 1 | 1 | 2 | 0 | 1 |
5 | 32 | 7 | 5 | 1 | 1 | 5 | 0 | 1 |
6 | 64 | 10 | 8 | 1 | 1 | 6 | 0 | 3 |
7 | 128 | 15 | 13 | 1 | 1 | 9 | 0 | 5 |
8 | 256 | 25 | 23 | 1 | 1 | 14 | 0 | 10 |
9 | 512 | 42 | 40 | 1 | 1 | 23 | 0 | 18 |
10 | 1.024 | 74 | 72 | 1 | 1 | 34 | 0 | 39 |
11 | 2.048 | 137 | 135 | 1 | 1 | 70 | 0 | 66 |
12 | 4.096 | 235 | 233 | 1 | 1 | 116 | 0 | 118 |
13 | 8.192 | 441 | 439 | 1 | 1 | 227 | 0 | 213 |
14 | 16.384 | 854 | 852 | 1 | 1 | 437 | 0 | 416 |
15 | 32.768 | 1.544 | 1.542 | 1 | 1 | 756 | 0 | 787 |
16 | 65.536 | 2.815 | 2.813 | 1 | 1 | 1.365 | 0 | 1.449 |
17 | 131.072 | 5.201 | 5.199 | 1 | 1 | 2.563 | 0 | 2.637 |
18 | 262.144 | 9.796 | 9.794 | 1 | 1 | 4.861 | 0 | 4.934 |
19 | 524.288 | 18.426 | 18.424 | 1 | 1 | 9.176 | 0 | 9.249 |
20 | 1.048.576 | 34.972 | 34.970 | 1 | 1 | 17.318 | 0 | 17.653 |
21 | 2.097.152 | 66.197 | 66.195 | 1 | 1 | 32.934 | 0 | 33.262 |
22 | 4.194.304 | 125.909 | 125.907 | 1 | 1 | 62.731 | 0 | 63.177 |
23 | 8.388.608 | 240.212 | 240.210 | 1 | 1 | 119.793 | 0 | 120.418 |
24 | 16.777.216 | 458.336 | 458.334 | 1 | 1 | 228.958 | 0 | 229.377 |
25 | 33.554.432 | 877.613 | 877.611 | 1 | 1 | 438.848 | 0 | 438.764 |
26 | 67.108.864 | 1.683.534 | 1.683.532 | 1 | 1 | 841.400 | 0 | 842.133 |
27 | 134.217.728 | 3.234.095 | 3.234.093 | 1 | 1 | 1.616.230 | 0 | 1.617.864 |
28 | 268.435.456 | 6.220.989 | 6.220.987 | 1 | 1 | 3.109.568 | 0 | 3.111.420 |
29 | 536.870.912 | 11.989.187 | 11.989.185 | 1 | 1 | 5.994.623 | 0 | 5.994.563 |
30 | 1.073.741.824 | 23.127.453 | 23.127.451 | 1 | 1 | 11.563.465 | 0 | 11.563.987 |
31 | 2.147.483.648 | 44.680.943 | 44.680.941 | 1 | 1 | 22.342.713 | 0 | 22.338.229 |
32 | 4.294.967.296 | 86.420.398 | 86.420.396 | 1 | 1 | 43.213.535 | 0 | 43.206.862 |
33 | 8.589.934.592 | 167.339.746 | 167.339.744 | 1 | 1 | 83.671.479 | 0 | 83.668.266 |
34 | 17.179.869.184 | 324.372.298 | 324.372.296 | 1 | 1 | 162.188.952 | 0 | 162.183.345 |
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 | 3 | 1 | 2 | 0 | 1 | 2 | 0 |
3 | 8 | 6 | 2 | 4 | 1 | 2 | 2 | 1 |
4 | 16 | 8 | 3 | 5 | 2 | 2 | 3 | 1 |
5 | 32 | 16 | 7 | 9 | 4 | 4 | 7 | 1 |
6 | 64 | 29 | 11 | 18 | 6 | 8 | 9 | 6 |
7 | 128 | 55 | 21 | 34 | 13 | 16 | 15 | 11 |
8 | 256 | 120 | 51 | 69 | 26 | 32 | 33 | 29 |
9 | 512 | 258 | 108 | 150 | 62 | 61 | 66 | 69 |
10 | 1.024 | 537 | 242 | 295 | 135 | 135 | 134 | 133 |
11 | 2.048 | 1.096 | 489 | 607 | 259 | 278 | 284 | 275 |
12 | 4.096 | 2.271 | 1.009 | 1.262 | 539 | 584 | 585 | 563 |
13 | 8.192 | 4.600 | 2.101 | 2.499 | 1.105 | 1.134 | 1.196 | 1.165 |
14 | 16.384 | 9.308 | 4.313 | 4.995 | 2.279 | 2.291 | 2.388 | 2.350 |
15 | 32.768 | 18.964 | 8.817 | 10.147 | 4.696 | 4.698 | 4.828 | 4.742 |
16 | 65.536 | 38.539 | 18.073 | 20.466 | 9.517 | 9.595 | 9.768 | 9.659 |
17 | 131.072 | 78.136 | 36.815 | 41.321 | 19.476 | 19.395 | 19.678 | 19.587 |
18 | 262.144 | 157.748 | 74.537 | 83.211 | 39.410 | 39.226 | 39.718 | 39.394 |
19 | 524.288 | 318.189 | 151.174 | 167.015 | 79.635 | 79.188 | 80.213 | 79.153 |
20 | 1.048.576 | 640.892 | 305.534 | 335.358 | 160.563 | 159.876 | 161.174 | 159.279 |
21 | 2.097.152 | 1.290.350 | 616.969 | 673.381 | 323.604 | 321.439 | 324.767 | 320.540 |
22 | 4.194.304 | 2.597.072 | 1.245.960 | 1.351.112 | 651.752 | 647.111 | 652.503 | 645.706 |
23 | 8.388.608 | 5.222.540 | 2.511.669 | 2.710.871 | 1.310.401 | 1.300.295 | 1.311.459 | 1.300.385 |
24 | 16.777.216 | 10.497.884 | 5.059.303 | 5.438.581 | 2.635.063 | 2.613.456 | 2.633.638 | 2.615.727 |
25 | 33.554.432 | 21.089.242 | 10.182.185 | 10.907.057 | 5.291.290 | 5.253.827 | 5.291.350 | 5.252.775 |
26 | 67.108.864 | 42.353.415 | 20.480.088 | 21.873.327 | 10.626.087 | 10.550.166 | 10.625.798 | 10.551.364 |
27 | 134.217.728 | 85.026.659 | 41.171.789 | 43.854.870 | 21.329.480 | 21.183.546 | 21.330.674 | 21.182.959 |
28 | 268.435.456 | 170.650.922 | 82.732.270 | 87.918.652 | 42.803.440 | 42.518.210 | 42.808.176 | 42.521.096 |
29 | 536.870.912 | 342.396.991 | 166.214.120 | 176.182.871 | 85.866.198 | 85.326.992 | 85.872.053 | 85.331.748 |
30 | 1.073.741.824 | 686.860.306 | 333.836.491 | 353.023.815 | 172.231.936 | 171.189.721 | 172.240.068 | 171.198.581 |
31 | 2.147.483.648 | 1.377.553.281 | 670.273.897 | 707.279.384 | 345.390.018 | 343.368.003 | 345.414.106 | 343.381.154 |
32 | 4.294.967.296 | 2.762.278.500 | 1.345.382.992 | 1.416.895.508 | 692.504.021 | 688.624.664 | 692.529.879 | 688.619.936 |
33 | 8.589.934.592 | 5.537.983.532 | 2.699.804.709 | 2.838.178.823 | 1.388.262.984 | 1.380.753.184 | 1.388.279.351 | 1.380.688.013 |
34 | 17.179.869.184 | 11.101.186.612 | 5.416.511.776 | 5.684.674.836 | 2.782.623.729 | 2.767.989.607 | 2.782.683.128 | 2.767.890.148 |