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+55x-3
f(0)=3
f(1)=53
f(2)=37
f(3)=19
f(4)=233
f(5)=11
f(6)=1
f(7)=431
f(8)=167
f(9)=191
f(10)=647
f(11)=241
f(12)=89
f(13)=881
f(14)=107
f(15)=349
f(16)=103
f(17)=1
f(18)=23
f(19)=61
f(20)=499
f(21)=59
f(22)=1
f(23)=199
f(24)=631
f(25)=1997
f(26)=701
f(27)=67
f(28)=211
f(29)=811
f(30)=283
f(31)=2663
f(32)=1
f(33)=967
f(34)=3023
f(35)=1049
f(36)=1091
f(37)=179
f(38)=1
f(39)=1
f(40)=3797
f(41)=1
f(42)=1
f(43)=4211
f(44)=1451
f(45)=1499
f(46)=4643
f(47)=1597
f(48)=1
f(49)=463
f(50)=1
f(51)=1801
f(52)=83
f(53)=1907
f(54)=1
f(55)=6047
f(56)=109
f(57)=709
f(58)=6551
f(59)=1
f(60)=1
f(61)=643
f(62)=2417
f(63)=2477
f(64)=331
f(65)=113
f(66)=887
f(67)=8171
f(68)=929
f(69)=2851
f(70)=8747
f(71)=271
f(72)=277
f(73)=9341
f(74)=3181
f(75)=1
f(76)=269
f(77)=1129
f(78)=3457
f(79)=557
f(80)=1
f(81)=3671
f(82)=1021
f(83)=347
f(84)=1297
f(85)=11897
f(86)=449
f(87)=1
f(88)=547
f(89)=4271
f(90)=4349
f(91)=359
f(92)=4507
f(93)=139
f(94)=1
f(95)=1583
f(96)=4831
f(97)=14741
f(98)=263
f(99)=5081
b) Substitution of the polynom
The polynom f(x)=x^2+55x-3 could be written as f(y)= y^2-759.25 with x=y-27.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+27.5
f'(x)>2x+54
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 | 10 | 5 | 5 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 79 | 20 | 59 | 0.790000 | 0.200000 | 0.590000 | 7.900000 | 4.000000 | 11.800000 |
3 | 1.000 | 679 | 125 | 554 | 0.679000 | 0.125000 | 0.554000 | 8.594936 | 6.250000 | 9.389831 |
4 | 10.000 | 6.889 | 865 | 6.024 | 0.688900 | 0.086500 | 0.602400 | 10.145802 | 6.920000 | 10.873646 |
5 | 100.000 | 69.181 | 6.712 | 62.469 | 0.691810 | 0.067120 | 0.624690 | 10.042241 | 7.759538 | 10.370020 |
6 | 1.000.000 | 692.700 | 54.627 | 638.073 | 0.692700 | 0.054627 | 0.638073 | 10.012865 | 8.138707 | 10.214234 |
7 | 10.000.000 | 6.926.457 | 463.092 | 6.463.365 | 0.692646 | 0.046309 | 0.646336 | 9.999216 | 8.477346 | 10.129507 |
8 | 100.000.000 | 69.253.496 | 4.013.633 | 65.239.863 | 0.692535 | 0.040136 | 0.652399 | 9.998402 | 8.667031 | 10.093792 |
9 | 1.000.000.000 | 692.496.589 | 35.413.634 | 657.082.955 | 0.692497 | 0.035414 | 0.657083 | 9.999446 | 8.823336 | 10.071801 |
10 | 10.000.000.000 | 6.924.919.599 | 316.909.908 | 6.608.009.691 | 0.692492 | 0.031691 | 0.660801 | 9.999933 | 8.948812 | 10.056583 |
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 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 1.333333 | 2.000000 |
4 | 16 | 16 | 6 | 10 | 1.000000 | 0.375000 | 0.625000 | 2.000000 | 1.500000 | 2.500000 |
5 | 32 | 28 | 8 | 20 | 0.875000 | 0.250000 | 0.625000 | 1.750000 | 1.333333 | 2.000000 |
6 | 64 | 49 | 14 | 35 | 0.765625 | 0.218750 | 0.546875 | 1.750000 | 1.750000 | 1.750000 |
7 | 128 | 96 | 23 | 73 | 0.750000 | 0.179688 | 0.570312 | 1.959184 | 1.642857 | 2.085714 |
8 | 256 | 180 | 40 | 140 | 0.703125 | 0.156250 | 0.546875 | 1.875000 | 1.739130 | 1.917808 |
9 | 512 | 350 | 73 | 277 | 0.683594 | 0.142578 | 0.541016 | 1.944444 | 1.825000 | 1.978571 |
10 | 1.024 | 696 | 129 | 567 | 0.679688 | 0.125977 | 0.553711 | 1.988571 | 1.767123 | 2.046932 |
11 | 2.048 | 1.401 | 226 | 1.175 | 0.684082 | 0.110352 | 0.573730 | 2.012931 | 1.751938 | 2.072310 |
12 | 4.096 | 2.834 | 385 | 2.449 | 0.691895 | 0.093994 | 0.597900 | 2.022841 | 1.703540 | 2.084255 |
13 | 8.192 | 5.658 | 726 | 4.932 | 0.690674 | 0.088623 | 0.602051 | 1.996471 | 1.885714 | 2.013883 |
14 | 16.384 | 11.332 | 1.306 | 10.026 | 0.691650 | 0.079712 | 0.611938 | 2.002828 | 1.798898 | 2.032847 |
15 | 32.768 | 22.640 | 2.438 | 20.202 | 0.690918 | 0.074402 | 0.616516 | 1.997882 | 1.866769 | 2.014961 |
16 | 65.536 | 45.324 | 4.580 | 40.744 | 0.691589 | 0.069885 | 0.621704 | 2.001943 | 1.878589 | 2.016830 |
17 | 131.072 | 90.785 | 8.568 | 82.217 | 0.692635 | 0.065369 | 0.627266 | 2.003023 | 1.870742 | 2.017892 |
18 | 262.144 | 181.595 | 16.119 | 165.476 | 0.692730 | 0.061489 | 0.631241 | 2.000275 | 1.881302 | 2.012674 |
19 | 524.288 | 363.208 | 30.169 | 333.039 | 0.692764 | 0.057543 | 0.635221 | 2.000099 | 1.871642 | 2.012612 |
20 | 1.048.576 | 726.338 | 57.108 | 669.230 | 0.692690 | 0.054462 | 0.638227 | 1.999785 | 1.892936 | 2.009464 |
21 | 2.097.152 | 1.452.934 | 108.268 | 1.344.666 | 0.692813 | 0.051626 | 0.641187 | 2.000355 | 1.895846 | 2.009273 |
22 | 4.194.304 | 2.905.244 | 206.071 | 2.699.173 | 0.692664 | 0.049131 | 0.643533 | 1.999570 | 1.903342 | 2.007318 |
23 | 8.388.608 | 5.810.144 | 393.095 | 5.417.049 | 0.692623 | 0.046861 | 0.645763 | 1.999882 | 1.907571 | 2.006929 |
24 | 16.777.216 | 11.619.401 | 750.659 | 10.868.742 | 0.692570 | 0.044743 | 0.647828 | 1.999847 | 1.909612 | 2.006395 |
25 | 33.554.432 | 23.237.942 | 1.437.123 | 21.800.819 | 0.692545 | 0.042830 | 0.649715 | 1.999926 | 1.914482 | 2.005827 |
26 | 67.108.864 | 46.475.597 | 2.756.687 | 43.718.910 | 0.692540 | 0.041078 | 0.651463 | 1.999988 | 1.918198 | 2.005379 |
27 | 134.217.728 | 92.947.784 | 5.297.845 | 87.649.939 | 0.692515 | 0.039472 | 0.653043 | 1.999927 | 1.921816 | 2.004852 |
28 | 268.435.456 | 185.898.153 | 10.190.757 | 175.707.396 | 0.692525 | 0.037964 | 0.654561 | 2.000028 | 1.923566 | 2.004649 |
29 | 536.870.912 | 371.782.034 | 19.634.891 | 352.147.143 | 0.692498 | 0.036573 | 0.655925 | 1.999923 | 1.926735 | 2.004168 |
30 | 1.073.741.824 | 743.561.973 | 37.887.495 | 705.674.478 | 0.692496 | 0.035285 | 0.657211 | 1.999994 | 1.929600 | 2.003919 |
31 | 2.147.483.648 | 1.487.120.522 | 73.193.260 | 1.413.927.262 | 0.692494 | 0.034083 | 0.658411 | 1.999995 | 1.931858 | 2.003654 |
32 | 4.294.967.296 | 2.974.243.894 | 141.561.189 | 2.832.682.705 | 0.692495 | 0.032960 | 0.659535 | 2.000002 | 1.934074 | 2.003415 |
33 | 8.589.934.592 | 5.948.456.890 | 274.119.322 | 5.674.337.568 | 0.692492 | 0.031912 | 0.660580 | 1.999990 | 1.936402 | 2.003167 |
34 | 17.179.869.184 | 11.896.932.058 | 531.313.840 | 11.365.618.218 | 0.692493 | 0.030927 | 0.661566 | 2.000003 | 1.938258 | 2.002986 |
35 | 34.359.738.368 | 23.793.956.076 | 1.030.820.077 | 22.763.135.999 | 0.692495 | 0.030001 | 0.662494 | 2.000008 | 1.940134 | 2.002806 |
36 | 68.719.476.736 | 47.588.148.954 | 2.001.690.898 | 45.586.458.056 | 0.692499 | 0.029128 | 0.663370 | 2.000010 | 1.941843 | 2.002644 |
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 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 1 | 0 |
3 | 8 | 4 | 0 | 3 | 1 | 1 | 1 | 1 |
4 | 16 | 6 | 0 | 5 | 2 | 1 | 1 | 2 |
5 | 32 | 8 | 0 | 7 | 2 | 1 | 2 | 3 |
6 | 64 | 14 | 0 | 13 | 2 | 3 | 3 | 6 |
7 | 128 | 23 | 0 | 22 | 5 | 6 | 6 | 6 |
8 | 256 | 40 | 0 | 39 | 10 | 10 | 11 | 9 |
9 | 512 | 73 | 0 | 72 | 18 | 20 | 18 | 17 |
10 | 1.024 | 129 | 0 | 128 | 30 | 33 | 33 | 33 |
11 | 2.048 | 226 | 0 | 224 | 60 | 56 | 55 | 55 |
12 | 4.096 | 385 | 0 | 383 | 103 | 98 | 92 | 92 |
13 | 8.192 | 726 | 0 | 724 | 191 | 182 | 178 | 175 |
14 | 16.384 | 1.306 | 0 | 1.304 | 333 | 332 | 313 | 328 |
15 | 32.768 | 2.438 | 0 | 2.436 | 603 | 611 | 610 | 614 |
16 | 65.536 | 4.580 | 0 | 4.578 | 1.145 | 1.153 | 1.118 | 1.164 |
17 | 131.072 | 8.568 | 0 | 8.566 | 2.146 | 2.117 | 2.129 | 2.176 |
18 | 262.144 | 16.119 | 0 | 16.117 | 4.029 | 4.006 | 4.042 | 4.042 |
19 | 524.288 | 30.169 | 0 | 30.167 | 7.621 | 7.537 | 7.426 | 7.585 |
20 | 1.048.576 | 57.108 | 0 | 57.106 | 14.343 | 14.342 | 14.189 | 14.234 |
21 | 2.097.152 | 108.268 | 0 | 108.266 | 27.166 | 27.054 | 26.967 | 27.081 |
22 | 4.194.304 | 206.071 | 0 | 206.069 | 51.620 | 51.722 | 51.265 | 51.464 |
23 | 8.388.608 | 393.095 | 0 | 393.093 | 98.286 | 98.529 | 98.167 | 98.113 |
24 | 16.777.216 | 750.659 | 0 | 750.657 | 187.723 | 187.959 | 187.881 | 187.096 |
25 | 33.554.432 | 1.437.123 | 0 | 1.437.121 | 359.308 | 359.774 | 359.321 | 358.720 |
26 | 67.108.864 | 2.756.687 | 0 | 2.756.685 | 688.760 | 689.823 | 689.111 | 688.993 |
27 | 134.217.728 | 5.297.845 | 0 | 5.297.843 | 1.324.585 | 1.325.898 | 1.324.365 | 1.322.997 |
28 | 268.435.456 | 10.190.757 | 0 | 10.190.755 | 2.547.887 | 2.549.205 | 2.547.712 | 2.545.953 |
29 | 536.870.912 | 19.634.891 | 0 | 19.634.889 | 4.907.300 | 4.911.029 | 4.908.989 | 4.907.573 |
30 | 1.073.741.824 | 37.887.495 | 0 | 37.887.493 | 9.471.875 | 9.473.385 | 9.471.582 | 9.470.653 |
31 | 2.147.483.648 | 73.193.260 | 0 | 73.193.258 | 18.297.772 | 18.296.346 | 18.300.517 | 18.298.625 |
32 | 4.294.967.296 | 141.561.189 | 0 | 141.561.187 | 35.383.762 | 35.394.710 | 35.393.121 | 35.389.596 |
33 | 8.589.934.592 | 274.119.322 | 0 | 274.119.320 | 68.527.484 | 68.533.872 | 68.526.007 | 68.531.959 |
34 | 17.179.869.184 | 531.313.840 | 0 | 531.313.838 | 132.815.943 | 132.822.783 | 132.833.070 | 132.842.044 |
35 | 34.359.738.368 | 1.030.820.077 | 0 | 1.030.820.075 | 257.694.483 | 257.699.441 | 257.694.451 | 257.731.702 |
36 | 68.719.476.736 | 2.001.690.898 | 0 | 2.001.690.896 | 500.399.160 | 500.414.412 | 500.425.965 | 500.451.361 |
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 | 1 | 0 |
2 | 4 | 2 | 2 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 4 | 2 | 2 | 0 | 2 | 1 | 1 |
4 | 16 | 10 | 5 | 5 | 2 | 3 | 2 | 3 |
5 | 32 | 20 | 13 | 7 | 2 | 9 | 4 | 5 |
6 | 64 | 35 | 20 | 15 | 5 | 16 | 7 | 7 |
7 | 128 | 73 | 37 | 36 | 16 | 24 | 17 | 16 |
8 | 256 | 140 | 67 | 73 | 29 | 41 | 36 | 34 |
9 | 512 | 277 | 138 | 139 | 59 | 71 | 69 | 78 |
10 | 1.024 | 567 | 290 | 277 | 130 | 147 | 145 | 145 |
11 | 2.048 | 1.175 | 602 | 573 | 282 | 305 | 299 | 289 |
12 | 4.096 | 2.449 | 1.260 | 1.189 | 604 | 627 | 617 | 601 |
13 | 8.192 | 4.932 | 2.506 | 2.426 | 1.215 | 1.249 | 1.231 | 1.237 |
14 | 16.384 | 10.026 | 5.066 | 4.960 | 2.502 | 2.556 | 2.484 | 2.484 |
15 | 32.768 | 20.202 | 10.220 | 9.982 | 4.995 | 5.133 | 5.047 | 5.027 |
16 | 65.536 | 40.744 | 20.689 | 20.055 | 10.171 | 10.263 | 10.111 | 10.199 |
17 | 131.072 | 82.217 | 41.652 | 40.565 | 20.489 | 20.607 | 20.551 | 20.570 |
18 | 262.144 | 165.476 | 83.916 | 81.560 | 41.089 | 41.437 | 41.493 | 41.457 |
19 | 524.288 | 333.039 | 168.834 | 164.205 | 82.927 | 83.368 | 83.271 | 83.473 |
20 | 1.048.576 | 669.230 | 339.039 | 330.191 | 166.925 | 167.497 | 167.407 | 167.401 |
21 | 2.097.152 | 1.344.666 | 681.324 | 663.342 | 335.480 | 336.358 | 336.573 | 336.255 |
22 | 4.194.304 | 2.699.173 | 1.365.879 | 1.333.294 | 674.476 | 675.217 | 674.960 | 674.520 |
23 | 8.388.608 | 5.417.049 | 2.739.367 | 2.677.682 | 1.353.379 | 1.354.796 | 1.354.994 | 1.353.880 |
24 | 16.777.216 | 10.868.742 | 5.495.751 | 5.372.991 | 2.715.214 | 2.717.837 | 2.718.601 | 2.717.090 |
25 | 33.554.432 | 21.800.819 | 11.013.353 | 10.787.466 | 5.450.396 | 5.449.827 | 5.449.396 | 5.451.200 |
26 | 67.108.864 | 43.718.910 | 22.075.346 | 21.643.564 | 10.932.778 | 10.928.651 | 10.929.025 | 10.928.456 |
27 | 134.217.728 | 87.649.939 | 44.239.056 | 43.410.883 | 21.911.638 | 21.917.739 | 21.912.772 | 21.907.790 |
28 | 268.435.456 | 175.707.396 | 88.640.076 | 87.067.320 | 43.929.594 | 43.928.049 | 43.929.680 | 43.920.073 |
29 | 536.870.912 | 352.147.143 | 177.594.585 | 174.552.558 | 88.039.223 | 88.040.284 | 88.034.424 | 88.033.212 |
30 | 1.073.741.824 | 705.674.478 | 355.762.044 | 349.912.434 | 176.427.492 | 176.407.883 | 176.411.494 | 176.427.609 |
31 | 2.147.483.648 | 1.413.927.262 | 712.631.038 | 701.296.224 | 353.502.163 | 353.459.934 | 353.468.718 | 353.496.447 |
32 | 4.294.967.296 | 2.832.682.705 | 1.427.285.651 | 1.405.397.054 | 708.169.903 | 708.171.136 | 708.155.924 | 708.185.742 |
33 | 8.589.934.592 | 5.674.337.568 | 2.858.324.411 | 2.816.013.157 | 1.418.584.889 | 1.418.546.962 | 1.418.567.826 | 1.418.637.891 |
34 | 17.179.869.184 | 11.365.618.218 | 5.723.782.653 | 5.641.835.565 | 2.841.391.925 | 2.841.414.822 | 2.841.397.773 | 2.841.413.698 |
35 | 34.359.738.368 | 22.763.135.999 | 11.460.855.190 | 11.302.280.809 | 5.690.791.902 | 5.690.808.562 | 5.690.709.995 | 5.690.825.540 |
36 | 68.719.476.736 | 45.586.458.056 | 22.946.999.950 | 22.639.458.106 | 11.396.652.534 | 11.396.664.573 | 11.396.553.641 | 11.396.587.308 |