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+11x-5
f(0)=5
f(1)=7
f(2)=3
f(3)=37
f(4)=11
f(5)=1
f(6)=97
f(7)=1
f(8)=1
f(9)=1
f(10)=41
f(11)=79
f(12)=271
f(13)=307
f(14)=23
f(15)=1
f(16)=61
f(17)=157
f(18)=47
f(19)=113
f(20)=1
f(21)=29
f(22)=103
f(23)=1
f(24)=167
f(25)=179
f(26)=1
f(27)=1021
f(28)=1087
f(29)=1
f(30)=1
f(31)=1297
f(32)=457
f(33)=1447
f(34)=1
f(35)=107
f(36)=241
f(37)=1
f(38)=619
f(39)=389
f(40)=1
f(41)=709
f(42)=2221
f(43)=331
f(44)=1
f(45)=503
f(46)=2617
f(47)=907
f(48)=257
f(49)=587
f(50)=1
f(51)=1
f(52)=3271
f(53)=1129
f(54)=701
f(55)=1
f(56)=1249
f(57)=1
f(58)=571
f(59)=1
f(60)=1
f(61)=1
f(62)=137
f(63)=4657
f(64)=1
f(65)=1
f(66)=5077
f(67)=227
f(68)=1789
f(69)=1103
f(70)=1
f(71)=277
f(72)=853
f(73)=557
f(74)=419
f(75)=1289
f(76)=6607
f(77)=1
f(78)=991
f(79)=1
f(80)=1
f(81)=677
f(82)=7621
f(83)=1
f(84)=1
f(85)=233
f(86)=397
f(87)=8521
f(88)=8707
f(89)=593
f(90)=1
f(91)=9277
f(92)=1
f(93)=1381
f(94)=1973
f(95)=1
f(96)=10267
f(97)=283
f(98)=3559
f(99)=311
b) Substitution of the polynom
The polynom f(x)=x^2+11x-5 could be written as f(y)= y^2-35.25 with x=y-5.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+5.5
f'(x)>2x+10
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 | 7 | 5 | 2 | 0.700000 | 0.500000 | 0.700000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 67 | 23 | 44 | 0.670000 | 0.230000 | 0.670000 | 9.571428 | 4.600000 | 22.000000 |
3 | 1.000 | 679 | 123 | 556 | 0.679000 | 0.123000 | 0.679000 | 10.134328 | 5.347826 | 12.636364 |
4 | 10.000 | 6.850 | 842 | 6.008 | 0.685000 | 0.084200 | 0.685000 | 10.088366 | 6.845529 | 10.805756 |
5 | 100.000 | 68.701 | 6.622 | 62.079 | 0.687010 | 0.066220 | 0.687010 | 10.029343 | 7.864608 | 10.332723 |
6 | 1.000.000 | 687.903 | 54.107 | 633.796 | 0.687903 | 0.054107 | 0.687903 | 10.012999 | 8.170794 | 10.209507 |
7 | 10.000.000 | 6.883.590 | 457.059 | 6.426.531 | 0.688359 | 0.045706 | 0.688359 | 10.006629 | 8.447317 | 10.139747 |
8 | 100.000.000 | 68.881.415 | 3.961.855 | 64.919.560 | 0.688814 | 0.039619 | 0.688814 | 10.006612 | 8.668148 | 10.101805 |
9 | 1.000.000.000 | 689.172.291 | 34.963.728 | 654.208.563 | 0.689172 | 0.034964 | 0.689172 | 10.005199 | 8.825090 | 10.077218 |
10 | 10.000.000.000 | 6.894.762.034 | 312.914.776 | 6.581.847.258 | 0.689476 | 0.031291 | 0.689476 | 10.004410 | 8.949697 | 10.060778 |
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 | 6 | 5 | 1 | 0.750000 | 0.625000 | 0.125000 | 1.200000 | 1.250000 | 1.000000 |
4 | 16 | 11 | 7 | 4 | 0.687500 | 0.437500 | 0.250000 | 1.833333 | 1.400000 | 4.000000 |
5 | 32 | 21 | 11 | 10 | 0.656250 | 0.343750 | 0.312500 | 1.909091 | 1.571429 | 2.500000 |
6 | 64 | 41 | 16 | 25 | 0.640625 | 0.250000 | 0.390625 | 1.952381 | 1.454545 | 2.500000 |
7 | 128 | 89 | 27 | 62 | 0.695312 | 0.210938 | 0.484375 | 2.170732 | 1.687500 | 2.480000 |
8 | 256 | 175 | 43 | 132 | 0.683594 | 0.167969 | 0.515625 | 1.966292 | 1.592593 | 2.129032 |
9 | 512 | 346 | 72 | 274 | 0.675781 | 0.140625 | 0.535156 | 1.977143 | 1.674419 | 2.075758 |
10 | 1.024 | 695 | 123 | 572 | 0.678711 | 0.120117 | 0.558594 | 2.008671 | 1.708333 | 2.087591 |
11 | 2.048 | 1.403 | 223 | 1.180 | 0.685059 | 0.108887 | 0.576172 | 2.018705 | 1.813008 | 2.062937 |
12 | 4.096 | 2.794 | 392 | 2.402 | 0.682129 | 0.095703 | 0.586426 | 1.991447 | 1.757848 | 2.035593 |
13 | 8.192 | 5.601 | 718 | 4.883 | 0.683716 | 0.087646 | 0.596069 | 2.004653 | 1.831633 | 2.032889 |
14 | 16.384 | 11.246 | 1.329 | 9.917 | 0.686401 | 0.081116 | 0.605286 | 2.007856 | 1.850975 | 2.030924 |
15 | 32.768 | 22.472 | 2.461 | 20.011 | 0.685791 | 0.075104 | 0.610687 | 1.998222 | 1.851768 | 2.017848 |
16 | 65.536 | 44.995 | 4.548 | 40.447 | 0.686569 | 0.069397 | 0.617172 | 2.002270 | 1.848029 | 2.021238 |
17 | 131.072 | 90.052 | 8.408 | 81.644 | 0.687042 | 0.064148 | 0.622894 | 2.001378 | 1.848725 | 2.018543 |
18 | 262.144 | 180.249 | 15.883 | 164.366 | 0.687595 | 0.060589 | 0.627007 | 2.001610 | 1.889034 | 2.013204 |
19 | 524.288 | 360.657 | 29.883 | 330.774 | 0.687899 | 0.056997 | 0.630901 | 2.000882 | 1.881446 | 2.012424 |
20 | 1.048.576 | 721.415 | 56.468 | 664.947 | 0.687995 | 0.053852 | 0.634143 | 2.000280 | 1.889636 | 2.010276 |
21 | 2.097.152 | 1.443.027 | 107.008 | 1.336.019 | 0.688089 | 0.051025 | 0.637064 | 2.000273 | 1.895020 | 2.009211 |
22 | 4.194.304 | 2.886.669 | 203.677 | 2.682.992 | 0.688236 | 0.048560 | 0.639675 | 2.000426 | 1.903381 | 2.008199 |
23 | 8.388.608 | 5.774.161 | 387.910 | 5.386.251 | 0.688334 | 0.046242 | 0.642091 | 2.000285 | 1.904535 | 2.007554 |
24 | 16.777.216 | 11.550.928 | 741.509 | 10.809.419 | 0.688489 | 0.044197 | 0.644292 | 2.000451 | 1.911549 | 2.006854 |
25 | 33.554.432 | 23.105.879 | 1.419.719 | 21.686.160 | 0.688609 | 0.042311 | 0.646298 | 2.000348 | 1.914635 | 2.006228 |
26 | 67.108.864 | 46.222.086 | 2.721.859 | 43.500.227 | 0.688763 | 0.040559 | 0.648204 | 2.000447 | 1.917181 | 2.005898 |
27 | 134.217.728 | 92.459.166 | 5.228.416 | 87.230.750 | 0.688874 | 0.038955 | 0.649920 | 2.000324 | 1.920899 | 2.005294 |
28 | 268.435.456 | 184.944.897 | 10.060.756 | 174.884.141 | 0.688973 | 0.037479 | 0.651494 | 2.000287 | 1.924245 | 2.004845 |
29 | 536.870.912 | 369.944.290 | 19.388.442 | 350.555.848 | 0.689075 | 0.036114 | 0.652961 | 2.000295 | 1.927136 | 2.004503 |
30 | 1.073.741.824 | 740.000.986 | 37.408.412 | 702.592.574 | 0.689180 | 0.034839 | 0.654340 | 2.000304 | 1.929418 | 2.004225 |
31 | 2.147.483.648 | 1.480.206.260 | 72.269.227 | 1.407.937.033 | 0.689275 | 0.033653 | 0.655622 | 2.000276 | 1.931898 | 2.003917 |
32 | 4.294.967.296 | 2.960.821.649 | 139.786.534 | 2.821.035.115 | 0.689370 | 0.032547 | 0.656823 | 2.000277 | 1.934247 | 2.003666 |
33 | 8.589.934.592 | 5.922.385.898 | 270.668.558 | 5.651.717.340 | 0.689456 | 0.031510 | 0.657946 | 2.000251 | 1.936299 | 2.003420 |
34 | 17.179.869.184 | 11.846.218.562 | 524.623.262 | 11.321.595.300 | 0.689541 | 0.030537 | 0.659004 | 2.000244 | 1.938250 | 2.003213 |
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 | 1 | 1 | 0 | 0 | 2 | 1 |
2 | 4 | 4 | 2 | 1 | 0 | 0 | 3 | 1 |
3 | 8 | 5 | 3 | 1 | 1 | 0 | 3 | 1 |
4 | 16 | 7 | 5 | 1 | 1 | 1 | 3 | 2 |
5 | 32 | 11 | 9 | 1 | 2 | 1 | 5 | 3 |
6 | 64 | 16 | 14 | 1 | 4 | 1 | 6 | 5 |
7 | 128 | 27 | 25 | 1 | 8 | 3 | 10 | 6 |
8 | 256 | 43 | 41 | 1 | 12 | 7 | 14 | 10 |
9 | 512 | 72 | 70 | 1 | 19 | 14 | 23 | 16 |
10 | 1.024 | 123 | 121 | 1 | 33 | 30 | 33 | 27 |
11 | 2.048 | 223 | 221 | 1 | 65 | 52 | 54 | 52 |
12 | 4.096 | 392 | 390 | 1 | 99 | 90 | 100 | 103 |
13 | 8.192 | 718 | 716 | 1 | 169 | 178 | 180 | 191 |
14 | 16.384 | 1.329 | 1.327 | 1 | 321 | 348 | 328 | 332 |
15 | 32.768 | 2.461 | 2.459 | 1 | 591 | 636 | 610 | 624 |
16 | 65.536 | 4.548 | 4.546 | 1 | 1.114 | 1.142 | 1.134 | 1.158 |
17 | 131.072 | 8.408 | 8.406 | 1 | 2.054 | 2.096 | 2.132 | 2.126 |
18 | 262.144 | 15.883 | 15.881 | 1 | 3.932 | 3.975 | 4.023 | 3.953 |
19 | 524.288 | 29.883 | 29.881 | 1 | 7.449 | 7.538 | 7.448 | 7.448 |
20 | 1.048.576 | 56.468 | 56.466 | 1 | 14.094 | 14.232 | 14.169 | 13.973 |
21 | 2.097.152 | 107.008 | 107.006 | 1 | 26.748 | 26.856 | 26.699 | 26.705 |
22 | 4.194.304 | 203.677 | 203.675 | 1 | 50.831 | 50.989 | 50.794 | 51.063 |
23 | 8.388.608 | 387.910 | 387.908 | 1 | 96.584 | 97.031 | 97.012 | 97.283 |
24 | 16.777.216 | 741.509 | 741.507 | 1 | 184.870 | 185.631 | 185.383 | 185.625 |
25 | 33.554.432 | 1.419.719 | 1.419.717 | 1 | 354.187 | 355.450 | 355.080 | 355.002 |
26 | 67.108.864 | 2.721.859 | 2.721.857 | 1 | 679.416 | 681.050 | 680.909 | 680.484 |
27 | 134.217.728 | 5.228.416 | 5.228.414 | 1 | 1.306.873 | 1.307.419 | 1.306.894 | 1.307.230 |
28 | 268.435.456 | 10.060.756 | 10.060.754 | 1 | 2.515.435 | 2.515.313 | 2.514.435 | 2.515.573 |
29 | 536.870.912 | 19.388.442 | 19.388.440 | 1 | 4.846.705 | 4.847.785 | 4.847.269 | 4.846.683 |
30 | 1.073.741.824 | 37.408.412 | 37.408.410 | 1 | 9.354.203 | 9.349.587 | 9.350.997 | 9.353.625 |
31 | 2.147.483.648 | 72.269.227 | 72.269.225 | 1 | 18.069.515 | 18.066.953 | 18.063.564 | 18.069.195 |
32 | 4.294.967.296 | 139.786.534 | 139.786.532 | 1 | 34.948.832 | 34.943.700 | 34.943.433 | 34.950.569 |
33 | 8.589.934.592 | 270.668.558 | 270.668.556 | 1 | 67.669.612 | 67.661.973 | 67.659.606 | 67.677.367 |
34 | 17.179.869.184 | 524.623.262 | 524.623.260 | 1 | 131.159.992 | 131.151.110 | 131.148.653 | 131.163.507 |
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 | 0 | 1 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
4 | 16 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
5 | 32 | 10 | 5 | 5 | 3 | 2 | 2 | 3 |
6 | 64 | 25 | 13 | 12 | 8 | 8 | 5 | 4 |
7 | 128 | 62 | 29 | 33 | 18 | 14 | 17 | 13 |
8 | 256 | 132 | 61 | 71 | 35 | 32 | 33 | 32 |
9 | 512 | 274 | 126 | 148 | 71 | 71 | 64 | 68 |
10 | 1.024 | 572 | 250 | 322 | 140 | 144 | 153 | 135 |
11 | 2.048 | 1.180 | 547 | 633 | 271 | 304 | 322 | 283 |
12 | 4.096 | 2.402 | 1.137 | 1.265 | 575 | 605 | 619 | 603 |
13 | 8.192 | 4.883 | 2.334 | 2.549 | 1.193 | 1.224 | 1.238 | 1.228 |
14 | 16.384 | 9.917 | 4.792 | 5.125 | 2.443 | 2.442 | 2.509 | 2.523 |
15 | 32.768 | 20.011 | 9.692 | 10.319 | 4.906 | 4.993 | 5.025 | 5.087 |
16 | 65.536 | 40.447 | 19.645 | 20.802 | 9.929 | 10.150 | 10.148 | 10.220 |
17 | 131.072 | 81.644 | 39.657 | 41.987 | 20.337 | 20.415 | 20.365 | 20.527 |
18 | 262.144 | 164.366 | 80.159 | 84.207 | 40.934 | 41.194 | 40.980 | 41.258 |
19 | 524.288 | 330.774 | 161.803 | 168.971 | 82.458 | 82.887 | 82.781 | 82.648 |
20 | 1.048.576 | 664.947 | 325.582 | 339.365 | 165.840 | 165.943 | 166.487 | 166.677 |
21 | 2.097.152 | 1.336.019 | 654.891 | 681.128 | 334.142 | 333.640 | 334.109 | 334.128 |
22 | 4.194.304 | 2.682.992 | 1.317.473 | 1.365.519 | 670.761 | 670.496 | 671.177 | 670.558 |
23 | 8.388.608 | 5.386.251 | 2.648.094 | 2.738.157 | 1.346.512 | 1.346.847 | 1.346.285 | 1.346.607 |
24 | 16.777.216 | 10.809.419 | 5.319.543 | 5.489.876 | 2.701.708 | 2.702.491 | 2.702.294 | 2.702.926 |
25 | 33.554.432 | 21.686.160 | 10.682.830 | 11.003.330 | 5.422.849 | 5.419.682 | 5.420.568 | 5.423.061 |
26 | 67.108.864 | 43.500.227 | 21.443.659 | 22.056.568 | 10.873.803 | 10.876.616 | 10.872.316 | 10.877.492 |
27 | 134.217.728 | 87.230.750 | 43.030.746 | 44.200.004 | 21.805.421 | 21.811.001 | 21.804.293 | 21.810.035 |
28 | 268.435.456 | 174.884.141 | 86.321.005 | 88.563.136 | 43.713.842 | 43.723.744 | 43.722.968 | 43.723.587 |
29 | 536.870.912 | 350.555.848 | 173.124.642 | 177.431.206 | 87.628.638 | 87.641.889 | 87.640.003 | 87.645.318 |
30 | 1.073.741.824 | 702.592.574 | 347.164.094 | 355.428.480 | 175.635.781 | 175.663.897 | 175.639.332 | 175.653.564 |
31 | 2.147.483.648 | 1.407.937.033 | 696.006.929 | 711.930.104 | 351.979.280 | 351.999.559 | 351.974.940 | 351.983.254 |
32 | 4.294.967.296 | 2.821.035.115 | 1.395.186.761 | 1.425.848.354 | 705.255.057 | 705.280.491 | 705.234.063 | 705.265.504 |
33 | 8.589.934.592 | 5.651.717.340 | 2.796.341.945 | 2.855.375.395 | 1.412.917.827 | 1.412.947.674 | 1.412.913.595 | 1.412.938.244 |
34 | 17.179.869.184 | 11.321.595.300 | 5.603.818.147 | 5.717.777.153 | 2.830.339.394 | 2.830.419.318 | 2.830.372.822 | 2.830.463.766 |