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-88x+53
f(0)=53
f(1)=17
f(2)=7
f(3)=101
f(4)=283
f(5)=181
f(6)=439
f(7)=257
f(8)=587
f(9)=47
f(10)=727
f(11)=397
f(12)=859
f(13)=461
f(14)=983
f(15)=521
f(16)=157
f(17)=577
f(18)=71
f(19)=37
f(20)=1307
f(21)=677
f(22)=1399
f(23)=103
f(24)=1483
f(25)=761
f(26)=1559
f(27)=797
f(28)=1627
f(29)=829
f(30)=241
f(31)=857
f(32)=1
f(33)=881
f(34)=1783
f(35)=1
f(36)=107
f(37)=131
f(38)=1847
f(39)=929
f(40)=1867
f(41)=937
f(42)=1879
f(43)=941
f(44)=269
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)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=233
f(91)=163
f(92)=421
f(93)=1
f(94)=617
f(95)=359
f(96)=821
f(97)=463
f(98)=1033
f(99)=571
b) Substitution of the polynom
The polynom f(x)=x^2-88x+53 could be written as f(y)= y^2-1883 with x=y+44
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-44
f'(x)>2x-89 with x > 43
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 | 6 | 5 | 1.100000 | 0.600000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 50 | 22 | 28 | 0.500000 | 0.220000 | 0.500000 | 4.545455 | 3.666667 | 5.600000 |
3 | 1.000 | 779 | 229 | 550 | 0.779000 | 0.229000 | 0.779000 | 15.580000 | 10.409091 | 19.642857 |
4 | 10.000 | 7.948 | 1.677 | 6.271 | 0.794800 | 0.167700 | 0.794800 | 10.202825 | 7.323144 | 11.401818 |
5 | 100.000 | 77.902 | 13.120 | 64.782 | 0.779020 | 0.131200 | 0.779020 | 9.801459 | 7.823494 | 10.330410 |
6 | 1.000.000 | 763.688 | 107.110 | 656.578 | 0.763688 | 0.107110 | 0.763688 | 9.803188 | 8.163872 | 10.135192 |
7 | 10.000.000 | 7.529.189 | 905.278 | 6.623.911 | 0.752919 | 0.090528 | 0.752919 | 9.858986 | 8.451853 | 10.088536 |
8 | 100.000.000 | 74.505.447 | 7.844.770 | 66.660.677 | 0.745054 | 0.078448 | 0.745054 | 9.895548 | 8.665592 | 10.063643 |
9 | 1.000.000.000 | 738.988.215 | 69.238.510 | 669.749.705 | 0.738988 | 0.069239 | 0.738988 | 9.918580 | 8.826073 | 10.047149 |
10 | 10.000.000.000 | 7.342.030.820 | 619.656.320 | 6.722.374.500 | 0.734203 | 0.061966 | 0.734203 | 9.935247 | 8.949591 | 10.037145 |
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 | 9 | 5 | 4 | 1.125000 | 0.625000 | 0.500000 | 1.800000 | 1.666667 | 2.000000 |
4 | 16 | 17 | 8 | 9 | 1.062500 | 0.500000 | 0.562500 | 1.888889 | 1.600000 | 2.250000 |
5 | 32 | 31 | 13 | 18 | 0.968750 | 0.406250 | 0.562500 | 1.823529 | 1.625000 | 2.000000 |
6 | 64 | 42 | 17 | 25 | 0.656250 | 0.265625 | 0.390625 | 1.354839 | 1.307692 | 1.388889 |
7 | 128 | 71 | 30 | 41 | 0.554688 | 0.234375 | 0.320312 | 1.690476 | 1.764706 | 1.640000 |
8 | 256 | 175 | 66 | 109 | 0.683594 | 0.257812 | 0.425781 | 2.464789 | 2.200000 | 2.658537 |
9 | 512 | 389 | 129 | 260 | 0.759766 | 0.251953 | 0.507812 | 2.222857 | 1.954545 | 2.385321 |
10 | 1.024 | 799 | 233 | 566 | 0.780273 | 0.227539 | 0.552734 | 2.053985 | 1.806202 | 2.176923 |
11 | 2.048 | 1.617 | 421 | 1.196 | 0.789551 | 0.205566 | 0.583984 | 2.023780 | 1.806867 | 2.113074 |
12 | 4.096 | 3.248 | 758 | 2.490 | 0.792969 | 0.185059 | 0.607910 | 2.008658 | 1.800475 | 2.081940 |
13 | 8.192 | 6.505 | 1.419 | 5.086 | 0.794067 | 0.173218 | 0.620850 | 2.002771 | 1.872032 | 2.042570 |
14 | 16.384 | 12.976 | 2.607 | 10.369 | 0.791992 | 0.159119 | 0.632874 | 1.994773 | 1.837209 | 2.038734 |
15 | 32.768 | 25.764 | 4.834 | 20.930 | 0.786255 | 0.147522 | 0.638733 | 1.985512 | 1.854239 | 2.018517 |
16 | 65.536 | 51.210 | 8.960 | 42.250 | 0.781403 | 0.136719 | 0.644684 | 1.987657 | 1.853537 | 2.018634 |
17 | 131.072 | 101.809 | 16.736 | 85.073 | 0.776741 | 0.127686 | 0.649055 | 1.988069 | 1.867857 | 2.013562 |
18 | 262.144 | 202.413 | 31.358 | 171.055 | 0.772144 | 0.119621 | 0.652523 | 1.988164 | 1.873685 | 2.010685 |
19 | 524.288 | 402.330 | 59.156 | 343.174 | 0.767384 | 0.112831 | 0.654552 | 1.987669 | 1.886472 | 2.006220 |
20 | 1.048.576 | 800.658 | 111.834 | 688.824 | 0.763567 | 0.106653 | 0.656914 | 1.990053 | 1.890493 | 2.007215 |
21 | 2.097.152 | 1.593.416 | 212.001 | 1.381.415 | 0.759800 | 0.101090 | 0.658710 | 1.990133 | 1.895676 | 2.005469 |
22 | 4.194.304 | 3.173.408 | 403.439 | 2.769.969 | 0.756599 | 0.096187 | 0.660412 | 1.991575 | 1.903005 | 2.005168 |
23 | 8.388.608 | 6.321.845 | 768.480 | 5.553.365 | 0.753623 | 0.091610 | 0.662013 | 1.992131 | 1.904823 | 2.004847 |
24 | 16.777.216 | 12.599.268 | 1.468.327 | 11.130.941 | 0.750975 | 0.087519 | 0.663456 | 1.992973 | 1.910690 | 2.004360 |
25 | 33.554.432 | 25.116.039 | 2.809.322 | 22.306.717 | 0.748516 | 0.083724 | 0.664792 | 1.993452 | 1.913281 | 2.004028 |
26 | 67.108.864 | 50.082.130 | 5.389.643 | 44.692.487 | 0.746282 | 0.080312 | 0.665970 | 1.994030 | 1.918485 | 2.003544 |
27 | 134.217.728 | 99.885.179 | 10.351.684 | 89.533.495 | 0.744203 | 0.077126 | 0.667077 | 1.994428 | 1.920662 | 2.003323 |
28 | 268.435.456 | 199.252.273 | 19.922.101 | 179.330.172 | 0.742273 | 0.074216 | 0.668057 | 1.994813 | 1.924527 | 2.002939 |
29 | 536.870.912 | 397.546.226 | 38.388.402 | 359.157.824 | 0.740488 | 0.071504 | 0.668984 | 1.995191 | 1.926925 | 2.002774 |
30 | 1.073.741.824 | 793.301.598 | 74.079.157 | 719.222.441 | 0.738820 | 0.068992 | 0.669828 | 1.995495 | 1.929728 | 2.002525 |
31 | 2.147.483.648 | 1.583.298.854 | 143.113.851 | 1.440.185.003 | 0.737281 | 0.066643 | 0.670638 | 1.995835 | 1.931904 | 2.002419 |
32 | 4.294.967.296 | 3.160.398.419 | 276.813.320 | 2.883.585.099 | 0.735838 | 0.064451 | 0.671387 | 1.996085 | 1.934217 | 2.002232 |
33 | 8.589.934.592 | 6.309.207.098 | 535.996.516 | 5.773.210.582 | 0.734488 | 0.062398 | 0.672090 | 1.996333 | 1.936310 | 2.002095 |
34 | 17.179.869.184 | 12.596.617.043 | 1.038.889.352 | 11.557.727.691 | 0.733220 | 0.060471 | 0.672748 | 1.996545 | 1.938239 | 2.001958 |
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 | 2 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 1 | 2 | 0 | 1 | 1 | 1 |
3 | 8 | 5 | 2 | 3 | 0 | 2 | 1 | 2 |
4 | 16 | 8 | 4 | 4 | 0 | 3 | 1 | 4 |
5 | 32 | 13 | 7 | 6 | 0 | 6 | 1 | 6 |
6 | 64 | 17 | 10 | 7 | 0 | 7 | 1 | 9 |
7 | 128 | 30 | 15 | 15 | 7 | 7 | 7 | 9 |
8 | 256 | 66 | 29 | 37 | 24 | 7 | 26 | 9 |
9 | 512 | 129 | 49 | 80 | 52 | 7 | 61 | 9 |
10 | 1.024 | 233 | 80 | 153 | 101 | 7 | 116 | 9 |
11 | 2.048 | 421 | 148 | 273 | 199 | 7 | 206 | 9 |
12 | 4.096 | 758 | 264 | 494 | 377 | 7 | 365 | 9 |
13 | 8.192 | 1.419 | 483 | 936 | 708 | 7 | 695 | 9 |
14 | 16.384 | 2.607 | 883 | 1.724 | 1.303 | 7 | 1.288 | 9 |
15 | 32.768 | 4.834 | 1.602 | 3.232 | 2.404 | 7 | 2.414 | 9 |
16 | 65.536 | 8.960 | 2.988 | 5.972 | 4.463 | 7 | 4.481 | 9 |
17 | 131.072 | 16.736 | 5.587 | 11.149 | 8.361 | 7 | 8.359 | 9 |
18 | 262.144 | 31.358 | 10.470 | 20.888 | 15.709 | 7 | 15.633 | 9 |
19 | 524.288 | 59.156 | 19.828 | 39.328 | 29.547 | 7 | 29.593 | 9 |
20 | 1.048.576 | 111.834 | 37.344 | 74.490 | 55.964 | 7 | 55.854 | 9 |
21 | 2.097.152 | 212.001 | 70.672 | 141.329 | 106.011 | 7 | 105.974 | 9 |
22 | 4.194.304 | 403.439 | 134.587 | 268.852 | 201.801 | 7 | 201.622 | 9 |
23 | 8.388.608 | 768.480 | 256.162 | 512.318 | 384.295 | 7 | 384.169 | 9 |
24 | 16.777.216 | 1.468.327 | 489.505 | 978.822 | 734.575 | 7 | 733.736 | 9 |
25 | 33.554.432 | 2.809.322 | 936.749 | 1.872.573 | 1.404.317 | 7 | 1.404.989 | 9 |
26 | 67.108.864 | 5.389.643 | 1.796.929 | 3.592.714 | 2.694.156 | 7 | 2.695.471 | 9 |
27 | 134.217.728 | 10.351.684 | 3.449.867 | 6.901.817 | 5.175.672 | 7 | 5.175.996 | 9 |
28 | 268.435.456 | 19.922.101 | 6.641.467 | 13.280.634 | 9.959.727 | 7 | 9.962.358 | 9 |
29 | 536.870.912 | 38.388.402 | 12.795.693 | 25.592.709 | 19.192.664 | 7 | 19.195.722 | 9 |
30 | 1.073.741.824 | 74.079.157 | 24.695.959 | 49.383.198 | 37.036.445 | 7 | 37.042.696 | 9 |
31 | 2.147.483.648 | 143.113.851 | 47.702.088 | 95.411.763 | 71.553.942 | 7 | 71.559.893 | 9 |
32 | 4.294.967.296 | 276.813.320 | 92.271.466 | 184.541.854 | 138.404.342 | 7 | 138.408.962 | 9 |
33 | 8.589.934.592 | 535.996.516 | 178.658.667 | 357.337.849 | 267.997.605 | 7 | 267.998.895 | 9 |
34 | 17.179.869.184 | 1.038.889.352 | 346.300.894 | 692.588.458 | 519.454.841 | 7 | 519.434.495 | 9 |
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 | 1 | 0 | 0 | 0 |
2 | 4 | 2 | 0 | 2 | 1 | 0 | 1 | 0 |
3 | 8 | 4 | 1 | 3 | 2 | 0 | 2 | 0 |
4 | 16 | 9 | 3 | 6 | 3 | 0 | 5 | 1 |
5 | 32 | 18 | 7 | 11 | 7 | 0 | 8 | 3 |
6 | 64 | 25 | 8 | 17 | 10 | 2 | 10 | 3 |
7 | 128 | 41 | 18 | 23 | 10 | 10 | 10 | 11 |
8 | 256 | 109 | 59 | 50 | 20 | 38 | 16 | 35 |
9 | 512 | 260 | 150 | 110 | 45 | 90 | 33 | 92 |
10 | 1.024 | 566 | 315 | 251 | 93 | 191 | 85 | 197 |
11 | 2.048 | 1.196 | 663 | 533 | 201 | 413 | 183 | 399 |
12 | 4.096 | 2.490 | 1.385 | 1.105 | 436 | 801 | 427 | 826 |
13 | 8.192 | 5.086 | 2.755 | 2.331 | 886 | 1.616 | 939 | 1.645 |
14 | 16.384 | 10.369 | 5.583 | 4.786 | 1.868 | 3.237 | 1.982 | 3.282 |
15 | 32.768 | 20.930 | 11.248 | 9.682 | 3.974 | 6.407 | 4.006 | 6.543 |
16 | 65.536 | 42.250 | 22.629 | 19.621 | 8.236 | 12.877 | 8.230 | 12.907 |
17 | 131.072 | 85.073 | 45.325 | 39.748 | 16.903 | 25.716 | 16.910 | 25.544 |
18 | 262.144 | 171.055 | 90.872 | 80.183 | 34.657 | 50.980 | 34.589 | 50.829 |
19 | 524.288 | 343.174 | 181.686 | 161.488 | 70.336 | 101.184 | 70.495 | 101.159 |
20 | 1.048.576 | 688.824 | 363.296 | 325.528 | 143.147 | 201.034 | 143.376 | 201.267 |
21 | 2.097.152 | 1.381.415 | 726.781 | 654.634 | 290.353 | 399.816 | 291.199 | 400.047 |
22 | 4.194.304 | 2.769.969 | 1.454.043 | 1.315.926 | 588.480 | 795.372 | 589.520 | 796.597 |
23 | 8.388.608 | 5.553.365 | 2.906.722 | 2.646.643 | 1.191.477 | 1.584.930 | 1.191.382 | 1.585.576 |
24 | 16.777.216 | 11.130.941 | 5.812.936 | 5.318.005 | 2.407.486 | 3.157.674 | 2.407.793 | 3.157.988 |
25 | 33.554.432 | 22.306.717 | 11.628.325 | 10.678.392 | 4.858.513 | 6.292.837 | 4.858.174 | 6.297.193 |
26 | 67.108.864 | 44.692.487 | 23.259.038 | 21.433.449 | 9.797.112 | 12.545.583 | 9.799.621 | 12.550.171 |
27 | 134.217.728 | 89.533.495 | 46.518.504 | 43.014.991 | 19.742.456 | 25.017.478 | 19.751.485 | 25.022.076 |
28 | 268.435.456 | 179.330.172 | 93.041.463 | 86.288.709 | 39.758.212 | 49.900.364 | 39.766.533 | 49.905.063 |
29 | 536.870.912 | 359.157.824 | 186.085.840 | 173.071.984 | 80.019.934 | 99.554.242 | 80.028.180 | 99.555.468 |
30 | 1.073.741.824 | 719.222.441 | 372.167.305 | 347.055.136 | 160.972.706 | 198.640.634 | 160.970.584 | 198.638.517 |
31 | 2.147.483.648 | 1.440.185.003 | 744.353.614 | 695.831.389 | 323.676.189 | 396.407.428 | 323.684.523 | 396.416.863 |
32 | 4.294.967.296 | 2.883.585.099 | 1.488.674.897 | 1.394.910.202 | 650.575.199 | 791.164.891 | 650.620.799 | 791.224.210 |
33 | 8.589.934.592 | 5.773.210.582 | 2.977.345.463 | 2.795.865.119 | 1.307.233.087 | 1.579.335.803 | 1.307.278.861 | 1.579.362.831 |
34 | 17.179.869.184 | 11.557.727.691 | 5.954.680.374 | 5.603.047.317 | 2.625.860.066 | 3.152.980.568 | 2.625.880.998 | 3.153.006.059 |