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-68x+11
f(0)=11
f(1)=7
f(2)=1
f(3)=23
f(4)=5
f(5)=19
f(6)=1
f(7)=13
f(8)=67
f(9)=1
f(10)=569
f(11)=1
f(12)=661
f(13)=1
f(14)=149
f(15)=1
f(16)=821
f(17)=107
f(18)=127
f(19)=1
f(20)=73
f(21)=61
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=47
f(27)=137
f(28)=1109
f(29)=1
f(30)=1129
f(31)=71
f(32)=163
f(33)=1
f(34)=229
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=151
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=619
f(77)=1
f(78)=113
f(79)=1
f(80)=971
f(81)=1
f(82)=1
f(83)=157
f(84)=271
f(85)=1
f(86)=1559
f(87)=1
f(88)=1
f(89)=1
f(90)=181
f(91)=263
f(92)=317
f(93)=1
f(94)=491
f(95)=1
f(96)=2699
f(97)=353
f(98)=227
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-68x+11 could be written as f(y)= y^2-1145 with x=y+34
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-34
f'(x)>2x-69 with x > 34
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 | 3 | 4 | 0.700000 | 0.300000 | 0.700000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 32 | 12 | 20 | 0.320000 | 0.120000 | 0.320000 | 4.571429 | 4.000000 | 5.000000 |
3 | 1.000 | 569 | 95 | 474 | 0.569000 | 0.095000 | 0.569000 | 17.781250 | 7.916667 | 23.700001 |
4 | 10.000 | 6.213 | 716 | 5.497 | 0.621300 | 0.071600 | 0.621300 | 10.919156 | 7.536842 | 11.597047 |
5 | 100.000 | 64.274 | 5.498 | 58.776 | 0.642740 | 0.054980 | 0.642740 | 10.345083 | 7.678771 | 10.692378 |
6 | 1.000.000 | 651.695 | 45.734 | 605.961 | 0.651695 | 0.045734 | 0.651695 | 10.139325 | 8.318297 | 10.309668 |
7 | 10.000.000 | 6.577.868 | 387.342 | 6.190.526 | 0.657787 | 0.038734 | 0.657787 | 10.093476 | 8.469454 | 10.216047 |
8 | 100.000.000 | 66.232.272 | 3.356.210 | 62.876.062 | 0.662323 | 0.033562 | 0.662323 | 10.068957 | 8.664721 | 10.156821 |
9 | 1.000.000.000 | 665.807.512 | 29.620.777 | 636.186.735 | 0.665807 | 0.029621 | 0.665807 | 10.052614 | 8.825663 | 10.118107 |
10 | 10.000.000.000 | 6.685.841.269 | 265.078.733 | 6.420.762.536 | 0.668584 | 0.026508 | 0.668584 | 10.041703 | 8.949081 | 10.092575 |
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 | 2 | 1 | 1 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 2.000000 | 2.000000 | 2.000000 |
3 | 8 | 6 | 2 | 4 | 0.750000 | 0.250000 | 0.500000 | 1.500000 | 1.000000 | 2.000000 |
4 | 16 | 10 | 5 | 5 | 0.625000 | 0.312500 | 0.312500 | 1.666667 | 2.500000 | 1.250000 |
5 | 32 | 19 | 7 | 12 | 0.593750 | 0.218750 | 0.375000 | 1.900000 | 1.400000 | 2.400000 |
6 | 64 | 20 | 7 | 13 | 0.312500 | 0.109375 | 0.203125 | 1.052632 | 1.000000 | 1.083333 |
7 | 128 | 46 | 14 | 32 | 0.359375 | 0.109375 | 0.250000 | 2.300000 | 2.000000 | 2.461539 |
8 | 256 | 112 | 28 | 84 | 0.437500 | 0.109375 | 0.328125 | 2.434783 | 2.000000 | 2.625000 |
9 | 512 | 263 | 60 | 203 | 0.513672 | 0.117188 | 0.396484 | 2.348214 | 2.142857 | 2.416667 |
10 | 1.024 | 584 | 98 | 486 | 0.570312 | 0.095703 | 0.474609 | 2.220532 | 1.633333 | 2.394089 |
11 | 2.048 | 1.214 | 177 | 1.037 | 0.592773 | 0.086426 | 0.506348 | 2.078767 | 1.806122 | 2.133745 |
12 | 4.096 | 2.486 | 319 | 2.167 | 0.606934 | 0.077881 | 0.529053 | 2.047776 | 1.802260 | 2.089682 |
13 | 8.192 | 5.074 | 604 | 4.470 | 0.619385 | 0.073730 | 0.545654 | 2.041030 | 1.893417 | 2.062760 |
14 | 16.384 | 10.300 | 1.105 | 9.195 | 0.628662 | 0.067444 | 0.561218 | 2.029957 | 1.829470 | 2.057047 |
15 | 32.768 | 20.818 | 2.042 | 18.776 | 0.635315 | 0.062317 | 0.572998 | 2.021165 | 1.847964 | 2.041979 |
16 | 65.536 | 41.959 | 3.780 | 38.179 | 0.640244 | 0.057678 | 0.582565 | 2.015515 | 1.851126 | 2.033394 |
17 | 131.072 | 84.386 | 7.078 | 77.308 | 0.643814 | 0.054001 | 0.589813 | 2.011154 | 1.872487 | 2.024883 |
18 | 262.144 | 169.516 | 13.506 | 156.010 | 0.646652 | 0.051521 | 0.595131 | 2.008817 | 1.908166 | 2.018032 |
19 | 524.288 | 340.480 | 25.304 | 315.176 | 0.649414 | 0.048264 | 0.601151 | 2.008542 | 1.873538 | 2.020230 |
20 | 1.048.576 | 683.527 | 47.898 | 635.629 | 0.651862 | 0.045679 | 0.606183 | 2.007539 | 1.892902 | 2.016743 |
21 | 2.097.152 | 1.371.252 | 90.961 | 1.280.291 | 0.653864 | 0.043374 | 0.610490 | 2.006142 | 1.899056 | 2.014211 |
22 | 4.194.304 | 2.750.283 | 172.852 | 2.577.431 | 0.655719 | 0.041211 | 0.614507 | 2.005673 | 1.900287 | 2.013160 |
23 | 8.388.608 | 5.514.447 | 328.795 | 5.185.652 | 0.657373 | 0.039195 | 0.618178 | 2.005047 | 1.902176 | 2.011946 |
24 | 16.777.216 | 11.055.829 | 627.484 | 10.428.345 | 0.658979 | 0.037401 | 0.621578 | 2.004884 | 1.908435 | 2.011000 |
25 | 33.554.432 | 22.156.574 | 1.201.723 | 20.954.851 | 0.660317 | 0.035814 | 0.624503 | 2.004063 | 1.915145 | 2.009413 |
26 | 67.108.864 | 44.399.176 | 2.305.315 | 42.093.861 | 0.661599 | 0.034352 | 0.627247 | 2.003883 | 1.918341 | 2.008788 |
27 | 134.217.728 | 88.961.519 | 4.429.016 | 84.532.503 | 0.662815 | 0.032999 | 0.629816 | 2.003675 | 1.921219 | 2.008191 |
28 | 268.435.456 | 178.222.478 | 8.520.505 | 169.701.973 | 0.663930 | 0.031741 | 0.632189 | 2.003366 | 1.923792 | 2.007535 |
29 | 536.870.912 | 356.990.762 | 16.422.160 | 340.568.602 | 0.664947 | 0.030589 | 0.634358 | 2.003062 | 1.927369 | 2.006863 |
30 | 1.073.741.824 | 715.007.344 | 31.692.316 | 683.315.028 | 0.665902 | 0.029516 | 0.636387 | 2.002874 | 1.929851 | 2.006395 |
31 | 2.147.483.648 | 1.431.928.369 | 61.230.421 | 1.370.697.948 | 0.666794 | 0.028513 | 0.638281 | 2.002676 | 1.932027 | 2.005953 |
32 | 4.294.967.296 | 2.867.456.117 | 118.421.725 | 2.749.034.392 | 0.667632 | 0.027572 | 0.640059 | 2.002514 | 1.934034 | 2.005573 |
33 | 8.589.934.592 | 5.741.657.563 | 229.292.309 | 5.512.365.254 | 0.668417 | 0.026693 | 0.641724 | 2.002352 | 1.936235 | 2.005200 |
34 | 17.179.869.184 | 11.495.982.378 | 444.423.593 | 11.051.558.785 | 0.669154 | 0.025869 | 0.643285 | 2.002206 | 1.938240 | 2.004867 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 2 | 0 | 1 | 1 | 0 |
3 | 8 | 2 | 0 | 2 | 0 | 1 | 1 | 0 |
4 | 16 | 5 | 1 | 4 | 1 | 1 | 3 | 0 |
5 | 32 | 7 | 2 | 5 | 2 | 1 | 4 | 0 |
6 | 64 | 7 | 2 | 5 | 2 | 1 | 4 | 0 |
7 | 128 | 14 | 4 | 10 | 2 | 5 | 4 | 3 |
8 | 256 | 28 | 7 | 21 | 2 | 14 | 4 | 8 |
9 | 512 | 60 | 19 | 41 | 2 | 28 | 4 | 26 |
10 | 1.024 | 98 | 35 | 63 | 2 | 47 | 4 | 45 |
11 | 2.048 | 177 | 59 | 118 | 2 | 91 | 4 | 80 |
12 | 4.096 | 319 | 105 | 214 | 2 | 154 | 4 | 159 |
13 | 8.192 | 604 | 203 | 401 | 2 | 294 | 4 | 304 |
14 | 16.384 | 1.105 | 367 | 738 | 2 | 538 | 4 | 561 |
15 | 32.768 | 2.042 | 686 | 1.356 | 2 | 999 | 4 | 1.037 |
16 | 65.536 | 3.780 | 1.264 | 2.516 | 2 | 1.845 | 4 | 1.929 |
17 | 131.072 | 7.078 | 2.392 | 4.686 | 2 | 3.498 | 4 | 3.574 |
18 | 262.144 | 13.506 | 4.519 | 8.987 | 2 | 6.740 | 4 | 6.760 |
19 | 524.288 | 25.304 | 8.441 | 16.863 | 2 | 12.675 | 4 | 12.623 |
20 | 1.048.576 | 47.898 | 16.017 | 31.881 | 2 | 24.014 | 4 | 23.878 |
21 | 2.097.152 | 90.961 | 30.306 | 60.655 | 2 | 45.443 | 4 | 45.512 |
22 | 4.194.304 | 172.852 | 57.581 | 115.271 | 2 | 86.386 | 4 | 86.460 |
23 | 8.388.608 | 328.795 | 109.670 | 219.125 | 2 | 164.485 | 4 | 164.304 |
24 | 16.777.216 | 627.484 | 209.286 | 418.198 | 2 | 313.973 | 4 | 313.505 |
25 | 33.554.432 | 1.201.723 | 400.608 | 801.115 | 2 | 601.281 | 4 | 600.436 |
26 | 67.108.864 | 2.305.315 | 768.561 | 1.536.754 | 2 | 1.153.240 | 4 | 1.152.069 |
27 | 134.217.728 | 4.429.016 | 1.475.432 | 2.953.584 | 2 | 2.215.984 | 4 | 2.213.026 |
28 | 268.435.456 | 8.520.505 | 2.838.050 | 5.682.455 | 2 | 4.262.743 | 4 | 4.257.756 |
29 | 536.870.912 | 16.422.160 | 5.470.542 | 10.951.618 | 2 | 8.211.934 | 4 | 8.210.220 |
30 | 1.073.741.824 | 31.692.316 | 10.561.946 | 21.130.370 | 2 | 15.845.901 | 4 | 15.846.409 |
31 | 2.147.483.648 | 61.230.421 | 20.404.894 | 40.825.527 | 2 | 30.613.355 | 4 | 30.617.060 |
32 | 4.294.967.296 | 118.421.725 | 39.471.842 | 78.949.883 | 2 | 59.209.009 | 4 | 59.212.710 |
33 | 8.589.934.592 | 229.292.309 | 76.430.449 | 152.861.860 | 2 | 114.640.320 | 4 | 114.651.983 |
34 | 17.179.869.184 | 444.423.593 | 148.139.629 | 296.283.964 | 2 | 222.202.690 | 4 | 222.220.897 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
3 | 8 | 4 | 3 | 1 | 0 | 2 | 0 | 2 |
4 | 16 | 5 | 3 | 2 | 0 | 2 | 1 | 2 |
5 | 32 | 12 | 7 | 5 | 2 | 4 | 2 | 4 |
6 | 64 | 13 | 8 | 5 | 2 | 4 | 3 | 4 |
7 | 128 | 32 | 16 | 16 | 6 | 9 | 8 | 9 |
8 | 256 | 84 | 51 | 33 | 24 | 21 | 19 | 20 |
9 | 512 | 203 | 115 | 88 | 53 | 46 | 54 | 50 |
10 | 1.024 | 486 | 254 | 232 | 121 | 117 | 139 | 109 |
11 | 2.048 | 1.037 | 522 | 515 | 274 | 243 | 286 | 234 |
12 | 4.096 | 2.167 | 1.089 | 1.078 | 586 | 497 | 579 | 505 |
13 | 8.192 | 4.470 | 2.275 | 2.195 | 1.183 | 1.065 | 1.184 | 1.038 |
14 | 16.384 | 9.195 | 4.616 | 4.579 | 2.458 | 2.210 | 2.395 | 2.132 |
15 | 32.768 | 18.776 | 9.459 | 9.317 | 4.909 | 4.527 | 4.862 | 4.478 |
16 | 65.536 | 38.179 | 19.264 | 18.915 | 9.931 | 9.125 | 9.879 | 9.244 |
17 | 131.072 | 77.308 | 38.795 | 38.513 | 20.070 | 18.605 | 19.876 | 18.757 |
18 | 262.144 | 156.010 | 78.642 | 77.368 | 40.323 | 37.822 | 40.003 | 37.862 |
19 | 524.288 | 315.176 | 159.022 | 156.154 | 81.080 | 76.531 | 80.857 | 76.708 |
20 | 1.048.576 | 635.629 | 320.610 | 315.019 | 163.033 | 154.427 | 163.461 | 154.708 |
21 | 2.097.152 | 1.280.291 | 645.325 | 634.966 | 327.818 | 311.417 | 328.646 | 312.410 |
22 | 4.194.304 | 2.577.431 | 1.298.778 | 1.278.653 | 658.568 | 629.378 | 659.746 | 629.739 |
23 | 8.388.608 | 5.185.652 | 2.612.439 | 2.573.213 | 1.323.697 | 1.268.011 | 1.325.204 | 1.268.740 |
24 | 16.777.216 | 10.428.345 | 5.248.517 | 5.179.828 | 2.660.979 | 2.551.992 | 2.661.650 | 2.553.724 |
25 | 33.554.432 | 20.954.851 | 10.542.455 | 10.412.396 | 5.342.398 | 5.134.316 | 5.341.825 | 5.136.312 |
26 | 67.108.864 | 42.093.861 | 21.171.827 | 20.922.034 | 10.720.096 | 10.323.765 | 10.723.751 | 10.326.249 |
27 | 134.217.728 | 84.532.503 | 42.504.110 | 42.028.393 | 21.515.599 | 20.745.918 | 21.515.741 | 20.755.245 |
28 | 268.435.456 | 169.701.973 | 85.312.094 | 84.389.879 | 43.164.758 | 41.683.641 | 43.160.020 | 41.693.554 |
29 | 536.870.912 | 340.568.602 | 171.165.659 | 169.402.943 | 86.565.406 | 83.713.063 | 86.558.351 | 83.731.782 |
30 | 1.073.741.824 | 683.315.028 | 343.360.039 | 339.954.989 | 173.567.721 | 168.070.427 | 173.567.585 | 168.109.295 |
31 | 2.147.483.648 | 1.370.697.948 | 688.615.745 | 682.082.203 | 347.951.245 | 337.382.377 | 347.941.005 | 337.423.321 |
32 | 4.294.967.296 | 2.749.034.392 | 1.380.845.937 | 1.368.188.455 | 697.434.159 | 677.068.057 | 697.448.764 | 677.083.412 |
33 | 8.589.934.592 | 5.512.365.254 | 2.768.436.921 | 2.743.928.333 | 1.397.764.485 | 1.358.401.774 | 1.397.793.365 | 1.358.405.630 |
34 | 17.179.869.184 | 11.051.558.785 | 5.549.595.535 | 5.501.963.250 | 2.800.936.617 | 2.724.809.820 | 2.801.013.919 | 2.724.798.429 |