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-15x-7
f(0)=7
f(1)=3
f(2)=11
f(3)=43
f(4)=17
f(5)=19
f(6)=61
f(7)=1
f(8)=1
f(9)=1
f(10)=1
f(11)=1
f(12)=1
f(13)=1
f(14)=1
f(15)=1
f(16)=1
f(17)=1
f(18)=47
f(19)=23
f(20)=31
f(21)=1
f(22)=1
f(23)=59
f(24)=1
f(25)=1
f(26)=1
f(27)=317
f(28)=1
f(29)=1
f(30)=443
f(31)=163
f(32)=179
f(33)=587
f(34)=71
f(35)=1
f(36)=107
f(37)=269
f(38)=1
f(39)=929
f(40)=331
f(41)=353
f(42)=1
f(43)=1
f(44)=1
f(45)=79
f(46)=1
f(47)=499
f(48)=83
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=223
f(54)=2099
f(55)=1
f(56)=109
f(57)=1
f(58)=829
f(59)=863
f(60)=2693
f(61)=311
f(62)=1
f(63)=431
f(64)=149
f(65)=1
f(66)=3359
f(67)=1
f(68)=1
f(69)=3719
f(70)=1
f(71)=1
f(72)=241
f(73)=1409
f(74)=1453
f(75)=4493
f(76)=1543
f(77)=227
f(78)=701
f(79)=1
f(80)=577
f(81)=281
f(82)=1
f(83)=1879
f(84)=827
f(85)=283
f(86)=1
f(87)=6257
f(88)=1
f(89)=1
f(90)=613
f(91)=1
f(92)=337
f(93)=7247
f(94)=2473
f(95)=2531
f(96)=457
f(97)=883
f(98)=1
f(99)=1187
b) Substitution of the polynom
The polynom f(x)=x^2-15x-7 could be written as f(y)= y^2-63.25 with x=y+7.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-7.5
f'(x)>2x-16 with x > 8
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 | 4 | 3 | 0.700000 | 0.400000 | 0.700000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 53 | 17 | 36 | 0.530000 | 0.170000 | 0.530000 | 7.571429 | 4.250000 | 12.000000 |
3 | 1.000 | 658 | 97 | 561 | 0.658000 | 0.097000 | 0.658000 | 12.415094 | 5.705883 | 15.583333 |
4 | 10.000 | 6.740 | 688 | 6.052 | 0.674000 | 0.068800 | 0.674000 | 10.243161 | 7.092783 | 10.787879 |
5 | 100.000 | 68.041 | 5.164 | 62.877 | 0.680410 | 0.051640 | 0.680410 | 10.095104 | 7.505814 | 10.389458 |
6 | 1.000.000 | 682.330 | 42.003 | 640.327 | 0.682330 | 0.042003 | 0.682330 | 10.028218 | 8.133811 | 10.183804 |
7 | 10.000.000 | 6.837.848 | 355.526 | 6.482.322 | 0.683785 | 0.035553 | 0.683785 | 10.021321 | 8.464300 | 10.123456 |
8 | 100.000.000 | 68.482.519 | 3.079.888 | 65.402.631 | 0.684825 | 0.030799 | 0.684825 | 10.015215 | 8.662905 | 10.089383 |
9 | 1.000.000.000 | 685.644.650 | 27.186.818 | 658.457.832 | 0.685645 | 0.027187 | 0.685645 | 10.011966 | 8.827210 | 10.067758 |
10 | 10.000.000.000 | 6.863.107.954 | 243.320.035 | 6.619.787.919 | 0.686311 | 0.024332 | 0.686311 | 10.009715 | 8.949926 | 10.053473 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 7 | 4 | 3 | 0.875000 | 0.500000 | 0.375000 | 1.400000 | 1.333333 | 1.500000 |
4 | 16 | 7 | 4 | 3 | 0.437500 | 0.250000 | 0.187500 | 1.000000 | 1.000000 | 1.000000 |
5 | 32 | 14 | 8 | 6 | 0.437500 | 0.250000 | 0.187500 | 2.000000 | 2.000000 | 2.000000 |
6 | 64 | 30 | 12 | 18 | 0.468750 | 0.187500 | 0.281250 | 2.142857 | 1.500000 | 3.000000 |
7 | 128 | 72 | 21 | 51 | 0.562500 | 0.164062 | 0.398438 | 2.400000 | 1.750000 | 2.833333 |
8 | 256 | 158 | 29 | 129 | 0.617188 | 0.113281 | 0.503906 | 2.194444 | 1.380952 | 2.529412 |
9 | 512 | 330 | 59 | 271 | 0.644531 | 0.115234 | 0.529297 | 2.088608 | 2.034483 | 2.100775 |
10 | 1.024 | 677 | 99 | 578 | 0.661133 | 0.096680 | 0.564453 | 2.051515 | 1.677966 | 2.132841 |
11 | 2.048 | 1.359 | 181 | 1.178 | 0.663574 | 0.088379 | 0.575195 | 2.007385 | 1.828283 | 2.038062 |
12 | 4.096 | 2.740 | 319 | 2.421 | 0.668945 | 0.077881 | 0.591064 | 2.016188 | 1.762431 | 2.055178 |
13 | 8.192 | 5.518 | 583 | 4.935 | 0.673584 | 0.071167 | 0.602417 | 2.013869 | 1.827586 | 2.038414 |
14 | 16.384 | 11.102 | 1.043 | 10.059 | 0.677612 | 0.063660 | 0.613953 | 2.011961 | 1.789022 | 2.038298 |
15 | 32.768 | 22.216 | 1.960 | 20.256 | 0.677979 | 0.059814 | 0.618164 | 2.001081 | 1.879195 | 2.013719 |
16 | 65.536 | 44.574 | 3.534 | 41.040 | 0.680145 | 0.053925 | 0.626221 | 2.006392 | 1.803061 | 2.026066 |
17 | 131.072 | 89.221 | 6.596 | 82.625 | 0.680702 | 0.050323 | 0.630379 | 2.001638 | 1.866440 | 2.013280 |
18 | 262.144 | 178.660 | 12.275 | 166.385 | 0.681534 | 0.046825 | 0.634708 | 2.002443 | 1.860976 | 2.013737 |
19 | 524.288 | 357.735 | 23.187 | 334.548 | 0.682325 | 0.044226 | 0.638100 | 2.002323 | 1.888961 | 2.010686 |
20 | 1.048.576 | 715.527 | 43.880 | 671.647 | 0.682380 | 0.041847 | 0.640532 | 2.000159 | 1.892440 | 2.007625 |
21 | 2.097.152 | 1.431.988 | 83.600 | 1.348.388 | 0.682825 | 0.039864 | 0.642962 | 2.001305 | 1.905196 | 2.007584 |
22 | 4.194.304 | 2.865.502 | 158.766 | 2.706.736 | 0.683189 | 0.037853 | 0.645336 | 2.001066 | 1.899115 | 2.007387 |
23 | 8.388.608 | 5.735.081 | 302.130 | 5.432.951 | 0.683675 | 0.036017 | 0.647658 | 2.001423 | 1.902989 | 2.007196 |
24 | 16.777.216 | 11.476.156 | 576.375 | 10.899.781 | 0.684032 | 0.034355 | 0.649678 | 2.001045 | 1.907705 | 2.006236 |
25 | 33.554.432 | 22.964.440 | 1.102.994 | 21.861.446 | 0.684394 | 0.032872 | 0.651522 | 2.001057 | 1.913674 | 2.005677 |
26 | 67.108.864 | 45.947.052 | 2.115.328 | 43.831.724 | 0.684664 | 0.031521 | 0.653144 | 2.000791 | 1.917806 | 2.004978 |
27 | 134.217.728 | 91.929.993 | 4.065.069 | 87.864.924 | 0.684932 | 0.030287 | 0.654645 | 2.000781 | 1.921720 | 2.004597 |
28 | 268.435.456 | 183.930.609 | 7.822.929 | 176.107.680 | 0.685195 | 0.029143 | 0.656052 | 2.000768 | 1.924427 | 2.004300 |
29 | 536.870.912 | 367.994.193 | 15.074.902 | 352.919.291 | 0.685443 | 0.028079 | 0.657363 | 2.000723 | 1.927015 | 2.003997 |
30 | 1.073.741.824 | 736.229.956 | 29.085.196 | 707.144.760 | 0.685668 | 0.027088 | 0.658580 | 2.000656 | 1.929379 | 2.003701 |
31 | 2.147.483.648 | 1.472.914.395 | 56.195.383 | 1.416.719.012 | 0.685879 | 0.026168 | 0.659711 | 2.000617 | 1.932096 | 2.003436 |
32 | 4.294.967.296 | 2.946.688.137 | 108.699.517 | 2.837.988.620 | 0.686079 | 0.025309 | 0.660771 | 2.000583 | 1.934314 | 2.003212 |
33 | 8.589.934.592 | 5.894.999.045 | 210.471.644 | 5.684.527.401 | 0.686268 | 0.024502 | 0.661766 | 2.000551 | 1.936270 | 2.003013 |
34 | 17.179.869.184 | 11.793.137.428 | 407.965.511 | 11.385.171.917 | 0.686451 | 0.023747 | 0.662704 | 2.000533 | 1.938339 | 2.002835 |
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 | 1 | 0 | 0 | 1 |
2 | 4 | 3 | 2 | 0 | 1 | 1 | 0 | 1 |
3 | 8 | 4 | 3 | 0 | 1 | 1 | 1 | 1 |
4 | 16 | 4 | 3 | 0 | 1 | 1 | 1 | 1 |
5 | 32 | 8 | 3 | 3 | 1 | 2 | 3 | 2 |
6 | 64 | 12 | 3 | 7 | 2 | 4 | 4 | 2 |
7 | 128 | 21 | 3 | 16 | 3 | 5 | 6 | 7 |
8 | 256 | 29 | 3 | 24 | 5 | 8 | 7 | 9 |
9 | 512 | 59 | 3 | 54 | 11 | 15 | 17 | 16 |
10 | 1.024 | 99 | 3 | 94 | 19 | 24 | 29 | 27 |
11 | 2.048 | 181 | 3 | 176 | 38 | 49 | 49 | 45 |
12 | 4.096 | 319 | 3 | 314 | 74 | 86 | 80 | 79 |
13 | 8.192 | 583 | 3 | 578 | 146 | 151 | 149 | 137 |
14 | 16.384 | 1.043 | 3 | 1.038 | 258 | 259 | 267 | 259 |
15 | 32.768 | 1.960 | 3 | 1.955 | 474 | 493 | 487 | 506 |
16 | 65.536 | 3.534 | 3 | 3.529 | 867 | 884 | 865 | 918 |
17 | 131.072 | 6.596 | 3 | 6.591 | 1.628 | 1.637 | 1.642 | 1.689 |
18 | 262.144 | 12.275 | 3 | 12.270 | 3.046 | 3.055 | 3.071 | 3.103 |
19 | 524.288 | 23.187 | 3 | 23.182 | 5.844 | 5.812 | 5.720 | 5.811 |
20 | 1.048.576 | 43.880 | 3 | 43.875 | 11.024 | 10.945 | 10.904 | 11.007 |
21 | 2.097.152 | 83.600 | 3 | 83.595 | 20.920 | 20.921 | 20.815 | 20.944 |
22 | 4.194.304 | 158.766 | 3 | 158.761 | 39.711 | 39.815 | 39.487 | 39.753 |
23 | 8.388.608 | 302.130 | 3 | 302.125 | 75.630 | 75.578 | 75.236 | 75.686 |
24 | 16.777.216 | 576.375 | 3 | 576.370 | 144.082 | 144.366 | 143.867 | 144.060 |
25 | 33.554.432 | 1.102.994 | 3 | 1.102.989 | 275.411 | 276.199 | 275.790 | 275.594 |
26 | 67.108.864 | 2.115.328 | 3 | 2.115.323 | 528.829 | 528.794 | 528.993 | 528.712 |
27 | 134.217.728 | 4.065.069 | 3 | 4.065.064 | 1.016.323 | 1.015.705 | 1.016.194 | 1.016.847 |
28 | 268.435.456 | 7.822.929 | 3 | 7.822.924 | 1.956.111 | 1.956.141 | 1.954.148 | 1.956.529 |
29 | 536.870.912 | 15.074.902 | 3 | 15.074.897 | 3.769.058 | 3.769.462 | 3.766.443 | 3.769.939 |
30 | 1.073.741.824 | 29.085.196 | 3 | 29.085.191 | 7.270.327 | 7.273.487 | 7.269.325 | 7.272.057 |
31 | 2.147.483.648 | 56.195.383 | 3 | 56.195.378 | 14.049.167 | 14.050.963 | 14.045.143 | 14.050.110 |
32 | 4.294.967.296 | 108.699.517 | 3 | 108.699.512 | 27.175.693 | 27.177.725 | 27.171.852 | 27.174.247 |
33 | 8.589.934.592 | 210.471.644 | 3 | 210.471.639 | 52.623.090 | 52.620.534 | 52.611.307 | 52.616.713 |
34 | 17.179.869.184 | 407.965.511 | 3 | 407.965.506 | 101.998.193 | 101.998.958 | 101.984.889 | 101.983.471 |
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 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 3 | 1 | 1 | 1 | 2 | 0 | 0 |
4 | 16 | 3 | 1 | 1 | 1 | 2 | 0 | 0 |
5 | 32 | 6 | 2 | 3 | 1 | 5 | 0 | 0 |
6 | 64 | 18 | 6 | 11 | 2 | 8 | 3 | 5 |
7 | 128 | 51 | 21 | 29 | 12 | 16 | 14 | 9 |
8 | 256 | 129 | 59 | 69 | 29 | 36 | 30 | 34 |
9 | 512 | 271 | 123 | 147 | 64 | 64 | 72 | 71 |
10 | 1.024 | 578 | 275 | 302 | 129 | 152 | 142 | 155 |
11 | 2.048 | 1.178 | 570 | 607 | 267 | 314 | 295 | 302 |
12 | 4.096 | 2.421 | 1.172 | 1.248 | 570 | 640 | 608 | 603 |
13 | 8.192 | 4.935 | 2.411 | 2.523 | 1.237 | 1.225 | 1.250 | 1.223 |
14 | 16.384 | 10.059 | 4.961 | 5.097 | 2.512 | 2.529 | 2.531 | 2.487 |
15 | 32.768 | 20.256 | 9.999 | 10.256 | 5.047 | 5.115 | 5.111 | 4.983 |
16 | 65.536 | 41.040 | 20.187 | 20.852 | 10.238 | 10.298 | 10.224 | 10.280 |
17 | 131.072 | 82.625 | 40.710 | 41.914 | 20.584 | 20.743 | 20.626 | 20.672 |
18 | 262.144 | 166.385 | 82.026 | 84.358 | 41.524 | 41.495 | 41.662 | 41.704 |
19 | 524.288 | 334.548 | 165.296 | 169.251 | 83.325 | 83.681 | 83.711 | 83.831 |
20 | 1.048.576 | 671.647 | 331.901 | 339.745 | 166.970 | 168.344 | 167.983 | 168.350 |
21 | 2.097.152 | 1.348.388 | 666.754 | 681.633 | 336.174 | 337.674 | 336.877 | 337.663 |
22 | 4.194.304 | 2.706.736 | 1.339.378 | 1.367.357 | 675.841 | 677.963 | 675.618 | 677.314 |
23 | 8.388.608 | 5.432.951 | 2.690.128 | 2.742.822 | 1.357.478 | 1.359.376 | 1.357.194 | 1.358.903 |
24 | 16.777.216 | 10.899.781 | 5.400.071 | 5.499.709 | 2.723.946 | 2.724.553 | 2.725.659 | 2.725.623 |
25 | 33.554.432 | 21.861.446 | 10.835.965 | 11.025.480 | 5.463.969 | 5.467.334 | 5.465.697 | 5.464.446 |
26 | 67.108.864 | 43.831.724 | 21.733.146 | 22.098.577 | 10.955.290 | 10.959.280 | 10.958.336 | 10.958.818 |
27 | 134.217.728 | 87.864.924 | 43.582.253 | 44.282.670 | 21.963.299 | 21.966.033 | 21.966.862 | 21.968.730 |
28 | 268.435.456 | 176.107.680 | 87.381.828 | 88.725.851 | 44.029.452 | 44.026.681 | 44.023.553 | 44.027.994 |
29 | 536.870.912 | 352.919.291 | 175.163.775 | 177.755.515 | 88.235.441 | 88.223.658 | 88.231.009 | 88.229.183 |
30 | 1.073.741.824 | 707.144.760 | 351.065.231 | 356.079.528 | 176.791.594 | 176.787.574 | 176.778.880 | 176.786.712 |
31 | 2.147.483.648 | 1.416.719.012 | 703.507.989 | 713.211.022 | 354.208.383 | 354.165.590 | 354.170.351 | 354.174.688 |
32 | 4.294.967.296 | 2.837.988.620 | 1.409.641.476 | 1.428.347.143 | 709.518.164 | 709.504.505 | 709.483.953 | 709.481.998 |
33 | 8.589.934.592 | 5.684.527.401 | 2.824.149.638 | 2.860.377.762 | 1.421.152.077 | 1.421.152.138 | 1.421.098.418 | 1.421.124.768 |
34 | 17.179.869.184 | 11.385.171.917 | 5.657.473.258 | 5.727.698.658 | 2.846.372.028 | 2.846.333.890 | 2.846.222.810 | 2.846.243.189 |