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+22x-37
f(0)=37
f(1)=7
f(2)=11
f(3)=19
f(4)=67
f(5)=1
f(6)=131
f(7)=83
f(8)=29
f(9)=1
f(10)=283
f(11)=163
f(12)=53
f(13)=1
f(14)=467
f(15)=1
f(16)=571
f(17)=313
f(18)=683
f(19)=1
f(20)=73
f(21)=433
f(22)=1
f(23)=499
f(24)=97
f(25)=569
f(26)=173
f(27)=643
f(28)=47
f(29)=103
f(30)=1523
f(31)=1
f(32)=89
f(33)=127
f(34)=1867
f(35)=1
f(36)=293
f(37)=1
f(38)=2243
f(39)=1171
f(40)=349
f(41)=1
f(42)=241
f(43)=197
f(44)=61
f(45)=1489
f(46)=281
f(47)=229
f(48)=3323
f(49)=1721
f(50)=509
f(51)=1
f(52)=1
f(53)=179
f(54)=1
f(55)=2099
f(56)=71
f(57)=1
f(58)=4603
f(59)=2371
f(60)=257
f(61)=359
f(62)=5171
f(63)=2659
f(64)=1
f(65)=1
f(66)=199
f(67)=2963
f(68)=79
f(69)=3121
f(70)=337
f(71)=1
f(72)=1
f(73)=3449
f(74)=191
f(75)=1
f(76)=7411
f(77)=3793
f(78)=1109
f(79)=1
f(80)=8123
f(81)=4153
f(82)=1213
f(83)=4339
f(84)=8867
f(85)=647
f(86)=1
f(87)=4723
f(88)=9643
f(89)=1
f(90)=1
f(91)=109
f(92)=1493
f(93)=1
f(94)=10867
f(95)=1
f(96)=1613
f(97)=523
f(98)=617
f(99)=853
b) Substitution of the polynom
The polynom f(x)=x^2+22x-37 could be written as f(y)= y^2-158 with x=y-11
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+11
f'(x)>2x+21
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 | 8 | 1 | 0.900000 | 0.800000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 71 | 42 | 29 | 0.710000 | 0.420000 | 0.710000 | 7.888889 | 5.250000 | 29.000000 |
3 | 1.000 | 695 | 249 | 446 | 0.695000 | 0.249000 | 0.695000 | 9.788733 | 5.928571 | 15.379311 |
4 | 10.000 | 6.981 | 1.897 | 5.084 | 0.698100 | 0.189700 | 0.698100 | 10.044604 | 7.618474 | 11.399103 |
5 | 100.000 | 69.870 | 14.534 | 55.336 | 0.698700 | 0.145340 | 0.698700 | 10.008595 | 7.661571 | 10.884343 |
6 | 1.000.000 | 696.953 | 118.182 | 578.771 | 0.696953 | 0.118182 | 0.696953 | 9.974997 | 8.131416 | 10.459213 |
7 | 10.000.000 | 6.962.770 | 995.606 | 5.967.164 | 0.696277 | 0.099561 | 0.696277 | 9.990300 | 8.424346 | 10.310061 |
8 | 100.000.000 | 69.574.101 | 8.609.594 | 60.964.507 | 0.695741 | 0.086096 | 0.695741 | 9.992303 | 8.647592 | 10.216663 |
9 | 1.000.000.000 | 695.330.057 | 75.880.389 | 619.449.668 | 0.695330 | 0.075880 | 0.695330 | 9.994093 | 8.813469 | 10.160825 |
10 | 10.000.000.000 | 6.950.255.142 | 678.481.681 | 6.271.773.461 | 0.695026 | 0.067848 | 0.695026 | 9.995620 | 8.941463 | 10.124751 |
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 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.400000 | inf |
4 | 16 | 13 | 11 | 2 | 0.812500 | 0.687500 | 0.125000 | 1.625000 | 1.571429 | 2.000000 |
5 | 32 | 25 | 18 | 7 | 0.781250 | 0.562500 | 0.218750 | 1.923077 | 1.636364 | 3.500000 |
6 | 64 | 47 | 29 | 18 | 0.734375 | 0.453125 | 0.281250 | 1.880000 | 1.611111 | 2.571429 |
7 | 128 | 89 | 48 | 41 | 0.695312 | 0.375000 | 0.320312 | 1.893617 | 1.655172 | 2.277778 |
8 | 256 | 176 | 85 | 91 | 0.687500 | 0.332031 | 0.355469 | 1.977528 | 1.770833 | 2.219512 |
9 | 512 | 350 | 147 | 203 | 0.683594 | 0.287109 | 0.396484 | 1.988636 | 1.729412 | 2.230769 |
10 | 1.024 | 712 | 258 | 454 | 0.695312 | 0.251953 | 0.443359 | 2.034286 | 1.755102 | 2.236453 |
11 | 2.048 | 1.421 | 474 | 947 | 0.693848 | 0.231445 | 0.462402 | 1.995787 | 1.837209 | 2.085903 |
12 | 4.096 | 2.853 | 880 | 1.973 | 0.696533 | 0.214844 | 0.481689 | 2.007741 | 1.856540 | 2.083421 |
13 | 8.192 | 5.711 | 1.595 | 4.116 | 0.697144 | 0.194702 | 0.502441 | 2.001753 | 1.812500 | 2.086163 |
14 | 16.384 | 11.443 | 2.925 | 8.518 | 0.698425 | 0.178528 | 0.519897 | 2.003677 | 1.833856 | 2.069485 |
15 | 32.768 | 22.895 | 5.332 | 17.563 | 0.698700 | 0.162720 | 0.535980 | 2.000787 | 1.822906 | 2.061869 |
16 | 65.536 | 45.808 | 9.921 | 35.887 | 0.698975 | 0.151382 | 0.547592 | 2.000786 | 1.860653 | 2.043330 |
17 | 131.072 | 91.491 | 18.548 | 72.943 | 0.698021 | 0.141510 | 0.556511 | 1.997271 | 1.869570 | 2.032574 |
18 | 262.144 | 182.953 | 34.527 | 148.426 | 0.697910 | 0.131710 | 0.566200 | 1.999683 | 1.861495 | 2.034822 |
19 | 524.288 | 365.570 | 65.096 | 300.474 | 0.697269 | 0.124161 | 0.573109 | 1.998163 | 1.885365 | 2.024403 |
20 | 1.048.576 | 730.729 | 123.483 | 607.246 | 0.696877 | 0.117763 | 0.579115 | 1.998876 | 1.896937 | 2.020960 |
21 | 2.097.152 | 1.460.708 | 233.661 | 1.227.047 | 0.696520 | 0.111418 | 0.585102 | 1.998974 | 1.892252 | 2.020675 |
22 | 4.194.304 | 2.920.683 | 444.201 | 2.476.482 | 0.696345 | 0.105906 | 0.590439 | 1.999498 | 1.901049 | 2.018245 |
23 | 8.388.608 | 5.840.708 | 845.015 | 4.995.693 | 0.696267 | 0.100734 | 0.595533 | 1.999775 | 1.902326 | 2.017254 |
24 | 16.777.216 | 11.679.070 | 1.612.972 | 10.066.098 | 0.696127 | 0.096141 | 0.599986 | 1.999598 | 1.908809 | 2.014955 |
25 | 33.554.432 | 23.352.616 | 3.086.254 | 20.266.362 | 0.695962 | 0.091978 | 0.603985 | 1.999527 | 1.913396 | 2.013329 |
26 | 67.108.864 | 46.694.455 | 5.915.601 | 40.778.854 | 0.695802 | 0.088149 | 0.607652 | 1.999539 | 1.916758 | 2.012145 |
27 | 134.217.728 | 93.371.136 | 11.361.583 | 82.009.553 | 0.695669 | 0.084650 | 0.611019 | 1.999619 | 1.920614 | 2.011080 |
28 | 268.435.456 | 186.710.583 | 21.850.831 | 164.859.752 | 0.695551 | 0.081401 | 0.614150 | 1.999660 | 1.923221 | 2.010251 |
29 | 536.870.912 | 373.355.478 | 42.090.757 | 331.264.721 | 0.695429 | 0.078400 | 0.617029 | 1.999648 | 1.926277 | 2.009373 |
30 | 1.073.741.824 | 746.598.592 | 81.178.418 | 665.420.174 | 0.695324 | 0.075603 | 0.619721 | 1.999699 | 1.928652 | 2.008726 |
31 | 2.147.483.648 | 1.492.977.358 | 156.789.904 | 1.336.187.454 | 0.695222 | 0.073011 | 0.622211 | 1.999706 | 1.931424 | 2.008036 |
32 | 4.294.967.296 | 2.985.563.642 | 303.188.963 | 2.682.374.679 | 0.695131 | 0.070592 | 0.624539 | 1.999738 | 1.933728 | 2.007484 |
33 | 8.589.934.592 | 5.970.382.836 | 586.909.393 | 5.383.473.443 | 0.695044 | 0.068325 | 0.626719 | 1.999751 | 1.935787 | 2.006980 |
34 | 17.179.869.184 | 11.939.422.574 | 1.137.332.513 | 10.802.090.061 | 0.694966 | 0.066201 | 0.628764 | 1.999775 | 1.937833 | 2.006528 |
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 | 2 | 1 | 0 | 1 | 1 | 1 |
2 | 4 | 5 | 4 | 1 | 0 | 3 | 1 | 1 |
3 | 8 | 7 | 4 | 3 | 0 | 5 | 1 | 1 |
4 | 16 | 11 | 7 | 4 | 0 | 9 | 1 | 1 |
5 | 32 | 18 | 11 | 7 | 3 | 13 | 1 | 1 |
6 | 64 | 29 | 17 | 12 | 5 | 22 | 1 | 1 |
7 | 128 | 48 | 27 | 21 | 10 | 36 | 1 | 1 |
8 | 256 | 85 | 42 | 43 | 20 | 63 | 1 | 1 |
9 | 512 | 147 | 74 | 73 | 34 | 111 | 1 | 1 |
10 | 1.024 | 258 | 130 | 128 | 66 | 190 | 1 | 1 |
11 | 2.048 | 474 | 229 | 245 | 121 | 351 | 1 | 1 |
12 | 4.096 | 880 | 425 | 455 | 212 | 666 | 1 | 1 |
13 | 8.192 | 1.595 | 785 | 810 | 392 | 1.201 | 1 | 1 |
14 | 16.384 | 2.925 | 1.471 | 1.454 | 737 | 2.186 | 1 | 1 |
15 | 32.768 | 5.332 | 2.707 | 2.625 | 1.316 | 4.014 | 1 | 1 |
16 | 65.536 | 9.921 | 5.017 | 4.904 | 2.477 | 7.442 | 1 | 1 |
17 | 131.072 | 18.548 | 9.377 | 9.171 | 4.698 | 13.848 | 1 | 1 |
18 | 262.144 | 34.527 | 17.410 | 17.117 | 8.773 | 25.752 | 1 | 1 |
19 | 524.288 | 65.096 | 32.792 | 32.304 | 16.524 | 48.570 | 1 | 1 |
20 | 1.048.576 | 123.483 | 62.165 | 61.318 | 31.338 | 92.143 | 1 | 1 |
21 | 2.097.152 | 233.661 | 117.463 | 116.198 | 59.268 | 174.391 | 1 | 1 |
22 | 4.194.304 | 444.201 | 223.187 | 221.014 | 112.329 | 331.870 | 1 | 1 |
23 | 8.388.608 | 845.015 | 424.650 | 420.365 | 213.716 | 631.297 | 1 | 1 |
24 | 16.777.216 | 1.612.972 | 809.916 | 803.056 | 407.485 | 1.205.485 | 1 | 1 |
25 | 33.554.432 | 3.086.254 | 1.548.980 | 1.537.274 | 778.968 | 2.307.284 | 1 | 1 |
26 | 67.108.864 | 5.915.601 | 2.968.463 | 2.947.138 | 1.493.122 | 4.422.477 | 1 | 1 |
27 | 134.217.728 | 11.361.583 | 5.699.332 | 5.662.251 | 2.867.410 | 8.494.171 | 1 | 1 |
28 | 268.435.456 | 21.850.831 | 10.958.675 | 10.892.156 | 5.513.875 | 16.336.954 | 1 | 1 |
29 | 536.870.912 | 42.090.757 | 21.109.482 | 20.981.275 | 10.619.397 | 31.471.358 | 1 | 1 |
30 | 1.073.741.824 | 81.178.418 | 40.709.128 | 40.469.290 | 20.474.523 | 60.703.893 | 1 | 1 |
31 | 2.147.483.648 | 156.789.904 | 78.614.485 | 78.175.419 | 39.532.973 | 117.256.929 | 1 | 1 |
32 | 4.294.967.296 | 303.188.963 | 152.010.469 | 151.178.494 | 76.423.748 | 226.765.213 | 1 | 1 |
33 | 8.589.934.592 | 586.909.393 | 294.231.776 | 292.677.617 | 147.902.656 | 439.006.735 | 1 | 1 |
34 | 17.179.869.184 | 1.137.332.513 | 570.132.700 | 567.199.813 | 286.534.404 | 850.798.107 | 1 | 1 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
4 | 16 | 2 | 0 | 2 | 0 | 0 | 2 | 0 |
5 | 32 | 7 | 3 | 4 | 3 | 0 | 3 | 1 |
6 | 64 | 18 | 7 | 11 | 6 | 1 | 8 | 3 |
7 | 128 | 41 | 16 | 25 | 11 | 4 | 16 | 10 |
8 | 256 | 91 | 41 | 50 | 26 | 10 | 37 | 18 |
9 | 512 | 203 | 94 | 109 | 58 | 26 | 70 | 49 |
10 | 1.024 | 454 | 211 | 243 | 111 | 74 | 151 | 118 |
11 | 2.048 | 947 | 462 | 485 | 236 | 162 | 301 | 248 |
12 | 4.096 | 1.973 | 1.002 | 971 | 484 | 370 | 595 | 524 |
13 | 8.192 | 4.116 | 2.061 | 2.055 | 1.014 | 807 | 1.199 | 1.096 |
14 | 16.384 | 8.518 | 4.313 | 4.205 | 2.114 | 1.732 | 2.418 | 2.254 |
15 | 32.768 | 17.563 | 8.782 | 8.781 | 4.403 | 3.659 | 4.893 | 4.608 |
16 | 65.536 | 35.887 | 18.012 | 17.875 | 8.947 | 7.652 | 9.914 | 9.374 |
17 | 131.072 | 72.943 | 36.505 | 36.438 | 18.158 | 15.700 | 20.127 | 18.958 |
18 | 262.144 | 148.426 | 74.248 | 74.178 | 37.079 | 32.140 | 40.806 | 38.401 |
19 | 524.288 | 300.474 | 150.103 | 150.371 | 75.121 | 65.995 | 81.969 | 77.389 |
20 | 1.048.576 | 607.246 | 303.781 | 303.465 | 152.297 | 134.501 | 164.241 | 156.207 |
21 | 2.097.152 | 1.227.047 | 613.863 | 613.184 | 307.899 | 274.146 | 331.141 | 313.861 |
22 | 4.194.304 | 2.476.482 | 1.239.408 | 1.237.074 | 621.510 | 557.088 | 665.085 | 632.799 |
23 | 8.388.608 | 4.995.693 | 2.498.485 | 2.497.208 | 1.253.479 | 1.130.477 | 1.337.014 | 1.274.723 |
24 | 16.777.216 | 10.066.098 | 5.034.007 | 5.032.091 | 2.526.203 | 2.291.935 | 2.683.782 | 2.564.178 |
25 | 33.554.432 | 20.266.362 | 10.135.269 | 10.131.093 | 5.085.666 | 4.637.368 | 5.386.229 | 5.157.099 |
26 | 67.108.864 | 40.778.854 | 20.389.036 | 20.389.818 | 10.229.611 | 9.373.346 | 10.804.391 | 10.371.506 |
27 | 134.217.728 | 82.009.553 | 41.005.969 | 41.003.584 | 20.573.406 | 18.925.785 | 21.672.415 | 20.837.947 |
28 | 268.435.456 | 164.859.752 | 82.439.005 | 82.420.747 | 41.345.970 | 38.197.172 | 43.458.657 | 41.857.953 |
29 | 536.870.912 | 331.264.721 | 165.655.032 | 165.609.689 | 83.063.145 | 77.027.121 | 87.136.023 | 84.038.432 |
30 | 1.073.741.824 | 665.420.174 | 332.737.406 | 332.682.768 | 166.845.061 | 155.223.702 | 174.669.638 | 168.681.773 |
31 | 2.147.483.648 | 1.336.187.454 | 668.141.139 | 668.046.315 | 335.003.879 | 312.595.938 | 350.073.058 | 338.514.579 |
32 | 4.294.967.296 | 2.682.374.679 | 1.341.279.649 | 1.341.095.030 | 672.474.966 | 629.224.595 | 701.524.083 | 679.151.035 |
33 | 8.589.934.592 | 5.383.473.443 | 2.691.924.124 | 2.691.549.319 | 1.349.520.820 | 1.265.949.294 | 1.405.683.509 | 1.362.319.820 |
34 | 17.179.869.184 | 10.802.090.061 | 5.401.382.274 | 5.400.707.787 | 2.707.681.949 | 2.545.884.967 | 2.816.252.776 | 2.732.270.369 |