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+36x-179
f(0)=179
f(1)=71
f(2)=103
f(3)=31
f(4)=19
f(5)=13
f(6)=73
f(7)=61
f(8)=173
f(9)=113
f(10)=281
f(11)=1
f(12)=397
f(13)=229
f(14)=521
f(15)=293
f(16)=653
f(17)=1
f(18)=1
f(19)=433
f(20)=941
f(21)=509
f(22)=1097
f(23)=1
f(24)=97
f(25)=673
f(26)=1433
f(27)=761
f(28)=1613
f(29)=853
f(30)=1801
f(31)=1
f(32)=1997
f(33)=1049
f(34)=1
f(35)=1153
f(36)=127
f(37)=1
f(38)=2633
f(39)=1373
f(40)=2861
f(41)=1489
f(42)=163
f(43)=1609
f(44)=257
f(45)=1733
f(46)=3593
f(47)=1861
f(48)=3853
f(49)=1993
f(50)=317
f(51)=2129
f(52)=4397
f(53)=2269
f(54)=151
f(55)=1
f(56)=4973
f(57)=197
f(58)=5273
f(59)=2713
f(60)=5581
f(61)=1
f(62)=5897
f(63)=233
f(64)=6221
f(65)=1
f(66)=6553
f(67)=3361
f(68)=1
f(69)=3533
f(70)=557
f(71)=3709
f(72)=107
f(73)=3889
f(74)=419
f(75)=4073
f(76)=641
f(77)=4261
f(78)=8713
f(79)=1
f(80)=479
f(81)=4649
f(82)=9497
f(83)=373
f(84)=9901
f(85)=1
f(86)=10313
f(87)=5261
f(88)=10733
f(89)=421
f(90)=11161
f(91)=5689
f(92)=11597
f(93)=311
f(94)=12041
f(95)=6133
f(96)=1
f(97)=6361
f(98)=12953
f(99)=347
b) Substitution of the polynom
The polynom f(x)=x^2+36x-179 could be written as f(y)= y^2-503 with x=y-18
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+18
f'(x)>2x+35
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 | 11 | 11 | 0 | 1.100000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 86 | 70 | 16 | 0.860000 | 0.700000 | 0.160000 | 7.818182 | 6.363636 | inf |
3 | 1.000 | 787 | 449 | 338 | 0.787000 | 0.449000 | 0.338000 | 9.151163 | 6.414286 | 21.125000 |
4 | 10.000 | 7.678 | 3.143 | 4.535 | 0.767800 | 0.314300 | 0.453500 | 9.756036 | 7.000000 | 13.417160 |
5 | 100.000 | 75.014 | 24.445 | 50.569 | 0.750140 | 0.244450 | 0.505690 | 9.769992 | 7.777601 | 11.150826 |
6 | 1.000.000 | 739.727 | 199.025 | 540.702 | 0.739727 | 0.199025 | 0.540702 | 9.861186 | 8.141747 | 10.692361 |
7 | 10.000.000 | 7.327.817 | 1.681.433 | 5.646.384 | 0.732782 | 0.168143 | 0.564638 | 9.906110 | 8.448351 | 10.442691 |
8 | 100.000.000 | 72.764.089 | 14.542.997 | 58.221.092 | 0.727641 | 0.145430 | 0.582211 | 9.929845 | 8.649168 | 10.311217 |
9 | 1.000.000.000 | 723.636.077 | 128.188.037 | 595.448.040 | 0.723636 | 0.128188 | 0.595448 | 9.944963 | 8.814417 | 10.227360 |
10 | 10.000.000.000 | 7.204.570.741 | 1.146.097.881 | 6.058.472.860 | 0.720457 | 0.114610 | 0.605847 | 9.956069 | 8.940756 | 10.174645 |
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 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 16 | 16 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.777778 | 1.777778 | -nan |
5 | 32 | 28 | 27 | 1 | 0.875000 | 0.843750 | 0.031250 | 1.750000 | 1.687500 | inf |
6 | 64 | 56 | 48 | 8 | 0.875000 | 0.750000 | 0.125000 | 2.000000 | 1.777778 | 8.000000 |
7 | 128 | 109 | 85 | 24 | 0.851562 | 0.664062 | 0.187500 | 1.946429 | 1.770833 | 3.000000 |
8 | 256 | 206 | 144 | 62 | 0.804688 | 0.562500 | 0.242188 | 1.889908 | 1.694118 | 2.583333 |
9 | 512 | 407 | 257 | 150 | 0.794922 | 0.501953 | 0.292969 | 1.975728 | 1.784722 | 2.419355 |
10 | 1.024 | 807 | 460 | 347 | 0.788086 | 0.449219 | 0.338867 | 1.982801 | 1.789883 | 2.313333 |
11 | 2.048 | 1.606 | 796 | 810 | 0.784180 | 0.388672 | 0.395508 | 1.990087 | 1.730435 | 2.334294 |
12 | 4.096 | 3.187 | 1.445 | 1.742 | 0.778076 | 0.352783 | 0.425293 | 1.984433 | 1.815327 | 2.150617 |
13 | 8.192 | 6.306 | 2.652 | 3.654 | 0.769775 | 0.323730 | 0.446045 | 1.978663 | 1.835294 | 2.097589 |
14 | 16.384 | 12.477 | 4.870 | 7.607 | 0.761536 | 0.297241 | 0.464294 | 1.978592 | 1.836350 | 2.081828 |
15 | 32.768 | 24.777 | 9.046 | 15.731 | 0.756134 | 0.276062 | 0.480072 | 1.985814 | 1.857495 | 2.067964 |
16 | 65.536 | 49.272 | 16.711 | 32.561 | 0.751831 | 0.254990 | 0.496841 | 1.988618 | 1.847336 | 2.069862 |
17 | 131.072 | 98.094 | 31.205 | 66.889 | 0.748398 | 0.238075 | 0.510323 | 1.990867 | 1.867333 | 2.054267 |
18 | 262.144 | 195.351 | 58.586 | 136.765 | 0.745205 | 0.223488 | 0.521717 | 1.991467 | 1.877456 | 2.044656 |
19 | 524.288 | 389.121 | 110.090 | 279.031 | 0.742189 | 0.209980 | 0.532209 | 1.991907 | 1.879118 | 2.040222 |
20 | 1.048.576 | 775.425 | 208.000 | 567.425 | 0.739503 | 0.198364 | 0.541139 | 1.992761 | 1.889363 | 2.033556 |
21 | 2.097.152 | 1.545.961 | 394.555 | 1.151.406 | 0.737172 | 0.188138 | 0.549033 | 1.993695 | 1.896899 | 2.029177 |
22 | 4.194.304 | 3.083.271 | 749.217 | 2.334.054 | 0.735109 | 0.178627 | 0.556482 | 1.994404 | 1.898891 | 2.027134 |
23 | 8.388.608 | 6.151.297 | 1.427.215 | 4.724.082 | 0.733292 | 0.170137 | 0.563154 | 1.995056 | 1.904942 | 2.023981 |
24 | 16.777.216 | 12.273.496 | 2.724.155 | 9.549.341 | 0.731557 | 0.162372 | 0.569185 | 1.995270 | 1.908721 | 2.021417 |
25 | 33.554.432 | 24.491.923 | 5.212.836 | 19.279.087 | 0.729916 | 0.155355 | 0.574562 | 1.995513 | 1.913561 | 2.018892 |
26 | 67.108.864 | 48.886.251 | 9.991.248 | 38.895.003 | 0.728462 | 0.148881 | 0.579581 | 1.996015 | 1.916663 | 2.017471 |
27 | 134.217.728 | 97.588.091 | 19.187.877 | 78.400.214 | 0.727088 | 0.142961 | 0.584127 | 1.996228 | 1.920468 | 2.015689 |
28 | 268.435.456 | 194.832.789 | 36.908.152 | 157.924.637 | 0.725809 | 0.137494 | 0.588315 | 1.996481 | 1.923514 | 2.014339 |
29 | 536.870.912 | 389.032.427 | 71.100.029 | 317.932.398 | 0.724629 | 0.132434 | 0.592195 | 1.996750 | 1.926405 | 2.013191 |
30 | 1.073.741.824 | 776.885.338 | 137.137.967 | 639.747.371 | 0.723531 | 0.127720 | 0.595811 | 1.996968 | 1.928803 | 2.012212 |
31 | 2.147.483.648 | 1.551.567.508 | 264.858.300 | 1.286.709.208 | 0.722505 | 0.123334 | 0.599171 | 1.997164 | 1.931327 | 2.011277 |
32 | 4.294.967.296 | 3.099.010.090 | 512.157.334 | 2.586.852.756 | 0.721545 | 0.119246 | 0.602299 | 1.997341 | 1.933703 | 2.010441 |
33 | 8.589.934.592 | 6.190.299.444 | 991.431.722 | 5.198.867.722 | 0.720646 | 0.115418 | 0.605228 | 1.997509 | 1.935795 | 2.009727 |
34 | 17.179.869.184 | 12.366.110.983 | 1.921.158.776 | 10.444.952.207 | 0.719802 | 0.111826 | 0.607976 | 1.997659 | 1.937762 | 2.009082 |
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 | 2 | 0 | 1 | 0 | 2 |
2 | 4 | 5 | 3 | 2 | 0 | 2 | 0 | 3 |
3 | 8 | 9 | 6 | 3 | 1 | 2 | 3 | 3 |
4 | 16 | 16 | 8 | 8 | 4 | 2 | 7 | 3 |
5 | 32 | 27 | 12 | 15 | 10 | 2 | 12 | 3 |
6 | 64 | 48 | 21 | 27 | 21 | 2 | 22 | 3 |
7 | 128 | 85 | 42 | 43 | 40 | 2 | 40 | 3 |
8 | 256 | 144 | 76 | 68 | 68 | 2 | 71 | 3 |
9 | 512 | 257 | 134 | 123 | 125 | 2 | 127 | 3 |
10 | 1.024 | 460 | 235 | 225 | 226 | 2 | 229 | 3 |
11 | 2.048 | 796 | 394 | 402 | 392 | 2 | 399 | 3 |
12 | 4.096 | 1.445 | 729 | 716 | 713 | 2 | 727 | 3 |
13 | 8.192 | 2.652 | 1.327 | 1.325 | 1.325 | 2 | 1.322 | 3 |
14 | 16.384 | 4.870 | 2.435 | 2.435 | 2.432 | 2 | 2.433 | 3 |
15 | 32.768 | 9.046 | 4.519 | 4.527 | 4.515 | 2 | 4.526 | 3 |
16 | 65.536 | 16.711 | 8.410 | 8.301 | 8.324 | 2 | 8.382 | 3 |
17 | 131.072 | 31.205 | 15.710 | 15.495 | 15.618 | 2 | 15.582 | 3 |
18 | 262.144 | 58.586 | 29.444 | 29.142 | 29.330 | 2 | 29.251 | 3 |
19 | 524.288 | 110.090 | 55.299 | 54.791 | 54.956 | 2 | 55.129 | 3 |
20 | 1.048.576 | 208.000 | 104.374 | 103.626 | 103.839 | 2 | 104.156 | 3 |
21 | 2.097.152 | 394.555 | 197.820 | 196.735 | 197.127 | 2 | 197.423 | 3 |
22 | 4.194.304 | 749.217 | 375.773 | 373.444 | 374.333 | 2 | 374.879 | 3 |
23 | 8.388.608 | 1.427.215 | 716.127 | 711.088 | 712.852 | 2 | 714.358 | 3 |
24 | 16.777.216 | 2.724.155 | 1.366.514 | 1.357.641 | 1.360.963 | 2 | 1.363.187 | 3 |
25 | 33.554.432 | 5.212.836 | 2.614.908 | 2.597.928 | 2.605.501 | 2 | 2.607.330 | 3 |
26 | 67.108.864 | 9.991.248 | 5.011.449 | 4.979.799 | 4.995.513 | 2 | 4.995.730 | 3 |
27 | 134.217.728 | 19.187.877 | 9.624.589 | 9.563.288 | 9.594.136 | 2 | 9.593.736 | 3 |
28 | 268.435.456 | 36.908.152 | 18.510.338 | 18.397.814 | 18.455.114 | 2 | 18.453.033 | 3 |
29 | 536.870.912 | 71.100.029 | 35.656.780 | 35.443.249 | 35.549.667 | 2 | 35.550.357 | 3 |
30 | 1.073.741.824 | 137.137.967 | 68.772.695 | 68.365.272 | 68.577.481 | 2 | 68.560.481 | 3 |
31 | 2.147.483.648 | 264.858.300 | 132.801.782 | 132.056.518 | 132.441.013 | 2 | 132.417.282 | 3 |
32 | 4.294.967.296 | 512.157.334 | 256.778.513 | 255.378.821 | 256.092.394 | 2 | 256.064.935 | 3 |
33 | 8.589.934.592 | 991.431.722 | 497.032.254 | 494.399.468 | 495.743.659 | 2 | 495.688.058 | 3 |
34 | 17.179.869.184 | 1.921.158.776 | 963.067.821 | 958.090.955 | 960.592.473 | 2 | 960.566.298 | 3 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
6 | 64 | 8 | 4 | 4 | 3 | 1 | 2 | 2 |
7 | 128 | 24 | 10 | 14 | 6 | 6 | 7 | 5 |
8 | 256 | 62 | 27 | 35 | 16 | 16 | 16 | 14 |
9 | 512 | 150 | 70 | 80 | 36 | 40 | 40 | 34 |
10 | 1.024 | 347 | 161 | 186 | 83 | 100 | 78 | 86 |
11 | 2.048 | 810 | 398 | 412 | 177 | 231 | 187 | 215 |
12 | 4.096 | 1.742 | 889 | 853 | 391 | 486 | 413 | 452 |
13 | 8.192 | 3.654 | 1.856 | 1.798 | 851 | 987 | 849 | 967 |
14 | 16.384 | 7.607 | 3.787 | 3.820 | 1.822 | 2.012 | 1.771 | 2.002 |
15 | 32.768 | 15.731 | 7.840 | 7.891 | 3.737 | 4.113 | 3.710 | 4.171 |
16 | 65.536 | 32.561 | 16.287 | 16.274 | 7.769 | 8.449 | 7.762 | 8.581 |
17 | 131.072 | 66.889 | 33.374 | 33.515 | 15.978 | 17.367 | 16.080 | 17.464 |
18 | 262.144 | 136.765 | 68.436 | 68.329 | 32.963 | 35.331 | 32.954 | 35.517 |
19 | 524.288 | 279.031 | 139.741 | 139.290 | 67.319 | 71.692 | 67.746 | 72.274 |
20 | 1.048.576 | 567.425 | 284.288 | 283.137 | 137.251 | 145.824 | 137.946 | 146.404 |
21 | 2.097.152 | 1.151.406 | 576.498 | 574.908 | 279.713 | 295.309 | 280.362 | 296.022 |
22 | 4.194.304 | 2.334.054 | 1.167.965 | 1.166.089 | 568.643 | 597.653 | 569.458 | 598.300 |
23 | 8.388.608 | 4.724.082 | 2.362.797 | 2.361.285 | 1.153.219 | 1.208.375 | 1.154.018 | 1.208.470 |
24 | 16.777.216 | 9.549.341 | 4.775.236 | 4.774.105 | 2.335.902 | 2.438.381 | 2.335.943 | 2.439.115 |
25 | 33.554.432 | 19.279.087 | 9.641.816 | 9.637.271 | 4.720.869 | 4.917.821 | 4.723.485 | 4.916.912 |
26 | 67.108.864 | 38.895.003 | 19.452.585 | 19.442.418 | 9.535.671 | 9.907.931 | 9.541.953 | 9.909.448 |
27 | 134.217.728 | 78.400.214 | 39.211.421 | 39.188.793 | 19.240.263 | 19.956.369 | 19.252.174 | 19.951.408 |
28 | 268.435.456 | 157.924.637 | 78.981.718 | 78.942.919 | 38.799.839 | 40.159.400 | 38.810.428 | 40.154.970 |
29 | 536.870.912 | 317.932.398 | 159.007.716 | 158.924.682 | 78.181.228 | 80.778.190 | 78.200.952 | 80.772.028 |
30 | 1.073.741.824 | 639.747.371 | 319.952.686 | 319.794.685 | 157.453.559 | 162.403.579 | 157.478.752 | 162.411.481 |
31 | 2.147.483.648 | 1.286.709.208 | 643.503.217 | 643.205.991 | 316.934.009 | 326.409.903 | 316.945.021 | 326.420.275 |
32 | 4.294.967.296 | 2.586.852.756 | 1.293.692.594 | 1.293.160.162 | 637.598.548 | 655.817.815 | 637.617.147 | 655.819.246 |
33 | 8.589.934.592 | 5.198.867.722 | 2.599.946.769 | 2.598.920.953 | 1.282.142.935 | 1.317.234.682 | 1.282.229.904 | 1.317.260.201 |
34 | 17.179.869.184 | 10.444.952.207 | 5.223.470.276 | 5.221.481.931 | 2.577.456.763 | 2.645.021.093 | 2.577.470.036 | 2.645.004.315 |