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+72x+23
f(0)=23
f(1)=3
f(2)=19
f(3)=31
f(4)=109
f(5)=17
f(6)=491
f(7)=1
f(8)=13
f(9)=47
f(10)=281
f(11)=1
f(12)=1031
f(13)=1
f(14)=409
f(15)=83
f(16)=53
f(17)=1
f(18)=1
f(19)=73
f(20)=1
f(21)=1
f(22)=41
f(23)=1
f(24)=179
f(25)=1
f(26)=857
f(27)=337
f(28)=941
f(29)=1
f(30)=3083
f(31)=67
f(32)=1117
f(33)=1
f(34)=1
f(35)=157
f(36)=3911
f(37)=1
f(38)=467
f(39)=1
f(40)=79
f(41)=97
f(42)=283
f(43)=1
f(44)=1709
f(45)=661
f(46)=1
f(47)=1
f(48)=5783
f(49)=1
f(50)=1
f(51)=787
f(52)=719
f(53)=277
f(54)=6827
f(55)=1
f(56)=1
f(57)=461
f(58)=2521
f(59)=1
f(60)=1
f(61)=113
f(62)=2777
f(63)=1
f(64)=2909
f(65)=1
f(66)=397
f(67)=389
f(68)=3181
f(69)=1
f(70)=1
f(71)=1
f(72)=10391
f(73)=1
f(74)=401
f(75)=1381
f(76)=1
f(77)=479
f(78)=617
f(79)=1
f(80)=131
f(81)=1
f(82)=4217
f(83)=1
f(84)=13127
f(85)=557
f(86)=349
f(87)=433
f(88)=1567
f(89)=1
f(90)=859
f(91)=619
f(92)=1
f(93)=1
f(94)=5209
f(95)=331
f(96)=521
f(97)=1
f(98)=1
f(99)=163
b) Substitution of the polynom
The polynom f(x)=x^2+72x+23 could be written as f(y)= y^2-1273 with x=y-36
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+36
f'(x)>2x+71
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 | 3 | 6 | 0.900000 | 0.300000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 57 | 10 | 47 | 0.570000 | 0.100000 | 0.570000 | 6.333333 | 3.333333 | 7.833333 |
3 | 1.000 | 588 | 62 | 526 | 0.588000 | 0.062000 | 0.588000 | 10.315789 | 6.200000 | 11.191489 |
4 | 10.000 | 6.184 | 409 | 5.775 | 0.618400 | 0.040900 | 0.618400 | 10.517007 | 6.596774 | 10.979088 |
5 | 100.000 | 63.498 | 3.360 | 60.138 | 0.634980 | 0.033600 | 0.634980 | 10.268111 | 8.215158 | 10.413507 |
6 | 1.000.000 | 645.874 | 27.582 | 618.292 | 0.645874 | 0.027582 | 0.645874 | 10.171564 | 8.208928 | 10.281219 |
7 | 10.000.000 | 6.526.169 | 233.613 | 6.292.556 | 0.652617 | 0.023361 | 0.652617 | 10.104400 | 8.469763 | 10.177320 |
8 | 100.000.000 | 65.786.423 | 2.017.017 | 63.769.406 | 0.657864 | 0.020170 | 0.657864 | 10.080404 | 8.634010 | 10.134103 |
9 | 1.000.000.000 | 661.857.523 | 17.814.511 | 644.043.012 | 0.661858 | 0.017815 | 0.661858 | 10.060701 | 8.832108 | 10.099561 |
10 | 10.000.000.000 | 6.650.366.591 | 159.411.680 | 6.490.954.911 | 0.665037 | 0.015941 | 0.665037 | 10.048033 | 8.948417 | 10.078449 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.400000 | 1.500000 | 1.333333 |
4 | 16 | 13 | 4 | 9 | 0.812500 | 0.250000 | 0.562500 | 1.857143 | 1.333333 | 2.250000 |
5 | 32 | 21 | 5 | 16 | 0.656250 | 0.156250 | 0.500000 | 1.615385 | 1.250000 | 1.777778 |
6 | 64 | 37 | 8 | 29 | 0.578125 | 0.125000 | 0.453125 | 1.761905 | 1.600000 | 1.812500 |
7 | 128 | 70 | 14 | 56 | 0.546875 | 0.109375 | 0.437500 | 1.891892 | 1.750000 | 1.931034 |
8 | 256 | 145 | 20 | 125 | 0.566406 | 0.078125 | 0.488281 | 2.071429 | 1.428571 | 2.232143 |
9 | 512 | 298 | 35 | 263 | 0.582031 | 0.068359 | 0.513672 | 2.055172 | 1.750000 | 2.104000 |
10 | 1.024 | 605 | 64 | 541 | 0.590820 | 0.062500 | 0.528320 | 2.030201 | 1.828571 | 2.057034 |
11 | 2.048 | 1.237 | 113 | 1.124 | 0.604004 | 0.055176 | 0.548828 | 2.044628 | 1.765625 | 2.077634 |
12 | 4.096 | 2.509 | 200 | 2.309 | 0.612549 | 0.048828 | 0.563721 | 2.028294 | 1.769912 | 2.054271 |
13 | 8.192 | 5.051 | 344 | 4.707 | 0.616577 | 0.041992 | 0.574585 | 2.013153 | 1.720000 | 2.038545 |
14 | 16.384 | 10.230 | 649 | 9.581 | 0.624390 | 0.039612 | 0.584778 | 2.025342 | 1.886628 | 2.035479 |
15 | 32.768 | 20.562 | 1.207 | 19.355 | 0.627502 | 0.036835 | 0.590668 | 2.009971 | 1.859784 | 2.020144 |
16 | 65.536 | 41.460 | 2.266 | 39.194 | 0.632629 | 0.034576 | 0.598053 | 2.016341 | 1.877382 | 2.025007 |
17 | 131.072 | 83.450 | 4.258 | 79.192 | 0.636673 | 0.032486 | 0.604187 | 2.012783 | 1.879082 | 2.020513 |
18 | 262.144 | 167.715 | 8.068 | 159.647 | 0.639782 | 0.030777 | 0.609005 | 2.009766 | 1.894786 | 2.015949 |
19 | 524.288 | 337.313 | 15.201 | 322.112 | 0.643373 | 0.028994 | 0.614380 | 2.011227 | 1.884110 | 2.017652 |
20 | 1.048.576 | 677.500 | 28.791 | 648.709 | 0.646114 | 0.027457 | 0.618657 | 2.008520 | 1.894020 | 2.013924 |
21 | 2.097.152 | 1.359.636 | 54.746 | 1.304.890 | 0.648325 | 0.026105 | 0.622220 | 2.006843 | 1.901497 | 2.011518 |
22 | 4.194.304 | 2.727.669 | 103.869 | 2.623.800 | 0.650327 | 0.024764 | 0.625563 | 2.006176 | 1.897289 | 2.010744 |
23 | 8.388.608 | 5.470.371 | 198.259 | 5.272.112 | 0.652119 | 0.023634 | 0.628485 | 2.005511 | 1.908741 | 2.009342 |
24 | 16.777.216 | 10.971.031 | 378.233 | 10.592.798 | 0.653924 | 0.022544 | 0.631380 | 2.005537 | 1.907772 | 2.009213 |
25 | 33.554.432 | 21.997.347 | 722.757 | 21.274.590 | 0.655572 | 0.021540 | 0.634032 | 2.005039 | 1.910878 | 2.008401 |
26 | 67.108.864 | 44.094.012 | 1.385.282 | 42.708.730 | 0.657052 | 0.020642 | 0.636410 | 2.004515 | 1.916664 | 2.007499 |
27 | 134.217.728 | 88.372.958 | 2.662.056 | 85.710.902 | 0.658430 | 0.019834 | 0.638596 | 2.004194 | 1.921671 | 2.006871 |
28 | 268.435.456 | 177.081.329 | 5.123.351 | 171.957.978 | 0.659679 | 0.019086 | 0.640593 | 2.003795 | 1.924584 | 2.006256 |
29 | 536.870.912 | 354.803.344 | 9.873.366 | 344.929.978 | 0.660873 | 0.018391 | 0.642482 | 2.003618 | 1.927130 | 2.005897 |
30 | 1.073.741.824 | 710.781.487 | 19.058.317 | 691.723.170 | 0.661967 | 0.017749 | 0.644217 | 2.003311 | 1.930275 | 2.005402 |
31 | 2.147.483.648 | 1.423.757.551 | 36.815.785 | 1.386.941.766 | 0.662989 | 0.017144 | 0.645845 | 2.003088 | 1.931744 | 2.005053 |
32 | 4.294.967.296 | 2.851.623.977 | 71.208.212 | 2.780.415.765 | 0.663945 | 0.016579 | 0.647366 | 2.002886 | 1.934176 | 2.004710 |
33 | 8.589.934.592 | 5.710.985.646 | 137.889.902 | 5.573.095.744 | 0.664846 | 0.016052 | 0.648794 | 2.002713 | 1.936433 | 2.004411 |
34 | 17.179.869.184 | 11.436.523.442 | 267.291.834 | 11.169.231.608 | 0.665693 | 0.015558 | 0.650135 | 2.002548 | 1.938444 | 2.004134 |
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 | 0 | 1 |
2 | 4 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 0 | 2 | 0 | 2 | 0 | 1 |
4 | 16 | 4 | 0 | 3 | 0 | 2 | 0 | 2 |
5 | 32 | 5 | 0 | 4 | 0 | 3 | 0 | 2 |
6 | 64 | 8 | 0 | 7 | 0 | 4 | 0 | 4 |
7 | 128 | 14 | 0 | 13 | 0 | 6 | 0 | 8 |
8 | 256 | 20 | 0 | 19 | 0 | 7 | 0 | 13 |
9 | 512 | 35 | 0 | 34 | 0 | 15 | 0 | 20 |
10 | 1.024 | 64 | 0 | 63 | 0 | 31 | 0 | 33 |
11 | 2.048 | 113 | 0 | 112 | 0 | 54 | 0 | 59 |
12 | 4.096 | 200 | 0 | 199 | 0 | 97 | 0 | 103 |
13 | 8.192 | 344 | 0 | 343 | 0 | 167 | 0 | 177 |
14 | 16.384 | 649 | 0 | 648 | 0 | 320 | 0 | 329 |
15 | 32.768 | 1.207 | 0 | 1.206 | 0 | 595 | 0 | 612 |
16 | 65.536 | 2.266 | 0 | 2.265 | 0 | 1.131 | 0 | 1.135 |
17 | 131.072 | 4.258 | 0 | 4.257 | 0 | 2.115 | 0 | 2.143 |
18 | 262.144 | 8.068 | 0 | 8.067 | 0 | 4.045 | 0 | 4.023 |
19 | 524.288 | 15.201 | 0 | 15.200 | 0 | 7.602 | 0 | 7.599 |
20 | 1.048.576 | 28.791 | 0 | 28.790 | 0 | 14.371 | 0 | 14.420 |
21 | 2.097.152 | 54.746 | 0 | 54.745 | 0 | 27.404 | 0 | 27.342 |
22 | 4.194.304 | 103.869 | 0 | 103.868 | 0 | 51.932 | 0 | 51.937 |
23 | 8.388.608 | 198.259 | 0 | 198.258 | 0 | 99.316 | 0 | 98.943 |
24 | 16.777.216 | 378.233 | 0 | 378.232 | 0 | 189.395 | 0 | 188.838 |
25 | 33.554.432 | 722.757 | 0 | 722.756 | 0 | 361.381 | 0 | 361.376 |
26 | 67.108.864 | 1.385.282 | 0 | 1.385.281 | 0 | 692.470 | 0 | 692.812 |
27 | 134.217.728 | 2.662.056 | 0 | 2.662.055 | 0 | 1.331.056 | 0 | 1.331.000 |
28 | 268.435.456 | 5.123.351 | 0 | 5.123.350 | 0 | 2.561.911 | 0 | 2.561.440 |
29 | 536.870.912 | 9.873.366 | 0 | 9.873.365 | 0 | 4.937.725 | 0 | 4.935.641 |
30 | 1.073.741.824 | 19.058.317 | 0 | 19.058.316 | 0 | 9.530.530 | 0 | 9.527.787 |
31 | 2.147.483.648 | 36.815.785 | 0 | 36.815.784 | 0 | 18.409.353 | 0 | 18.406.432 |
32 | 4.294.967.296 | 71.208.212 | 0 | 71.208.211 | 0 | 35.603.916 | 0 | 35.604.296 |
33 | 8.589.934.592 | 137.889.902 | 0 | 137.889.901 | 0 | 68.945.187 | 0 | 68.944.715 |
34 | 17.179.869.184 | 267.291.834 | 0 | 267.291.833 | 0 | 133.648.889 | 0 | 133.642.945 |
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 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 3 | 2 | 0 | 0 | 1 | 1 | 1 |
3 | 8 | 4 | 2 | 1 | 1 | 1 | 1 | 1 |
4 | 16 | 9 | 3 | 5 | 3 | 2 | 2 | 2 |
5 | 32 | 16 | 6 | 8 | 7 | 3 | 4 | 2 |
6 | 64 | 29 | 13 | 14 | 10 | 6 | 10 | 3 |
7 | 128 | 56 | 27 | 27 | 18 | 11 | 17 | 10 |
8 | 256 | 125 | 63 | 60 | 33 | 34 | 40 | 18 |
9 | 512 | 263 | 147 | 114 | 72 | 57 | 76 | 58 |
10 | 1.024 | 541 | 281 | 258 | 163 | 115 | 147 | 116 |
11 | 2.048 | 1.124 | 578 | 544 | 312 | 260 | 303 | 249 |
12 | 4.096 | 2.309 | 1.191 | 1.116 | 608 | 540 | 622 | 539 |
13 | 8.192 | 4.707 | 2.405 | 2.300 | 1.258 | 1.113 | 1.253 | 1.083 |
14 | 16.384 | 9.581 | 4.862 | 4.717 | 2.547 | 2.270 | 2.568 | 2.196 |
15 | 32.768 | 19.355 | 9.814 | 9.539 | 5.124 | 4.560 | 5.173 | 4.498 |
16 | 65.536 | 39.194 | 19.939 | 19.253 | 10.310 | 9.271 | 10.512 | 9.101 |
17 | 131.072 | 79.192 | 40.354 | 38.836 | 20.800 | 18.754 | 21.014 | 18.624 |
18 | 262.144 | 159.647 | 81.232 | 78.413 | 41.810 | 38.083 | 42.034 | 37.720 |
19 | 524.288 | 322.112 | 163.959 | 158.151 | 84.527 | 76.762 | 84.488 | 76.335 |
20 | 1.048.576 | 648.709 | 329.590 | 319.117 | 169.382 | 155.103 | 169.830 | 154.394 |
21 | 2.097.152 | 1.304.890 | 662.630 | 642.258 | 340.340 | 312.164 | 340.842 | 311.544 |
22 | 4.194.304 | 2.623.800 | 1.331.052 | 1.292.746 | 682.073 | 629.884 | 683.323 | 628.520 |
23 | 8.388.608 | 5.272.112 | 2.671.544 | 2.600.566 | 1.367.940 | 1.268.101 | 1.369.362 | 1.266.709 |
24 | 16.777.216 | 10.592.798 | 5.363.555 | 5.229.241 | 2.744.419 | 2.550.886 | 2.746.192 | 2.551.301 |
25 | 33.554.432 | 21.274.590 | 10.766.050 | 10.508.538 | 5.504.304 | 5.132.969 | 5.504.748 | 5.132.569 |
26 | 67.108.864 | 42.708.730 | 21.596.258 | 21.112.470 | 11.032.482 | 10.322.483 | 11.033.350 | 10.320.415 |
27 | 134.217.728 | 85.710.902 | 43.321.809 | 42.389.091 | 22.108.860 | 20.746.696 | 22.109.756 | 20.745.590 |
28 | 268.435.456 | 171.957.978 | 86.865.857 | 85.092.119 | 44.299.571 | 41.676.167 | 44.307.291 | 41.674.949 |
29 | 536.870.912 | 344.929.978 | 174.161.801 | 170.768.175 | 88.756.548 | 83.703.774 | 88.769.547 | 83.700.109 |
30 | 1.073.741.824 | 691.723.170 | 349.120.517 | 342.602.651 | 177.809.898 | 168.048.020 | 177.815.676 | 168.049.576 |
31 | 2.147.483.648 | 1.386.941.766 | 699.744.686 | 687.197.078 | 356.151.545 | 337.316.737 | 356.166.319 | 337.307.165 |
32 | 4.294.967.296 | 2.780.415.765 | 1.402.350.539 | 1.378.065.224 | 713.312.823 | 676.902.532 | 713.326.101 | 676.874.309 |
33 | 8.589.934.592 | 5.573.095.744 | 2.810.042.003 | 2.763.053.739 | 1.428.504.715 | 1.358.042.419 | 1.428.530.129 | 1.358.018.481 |
34 | 17.179.869.184 | 11.169.231.608 | 5.630.095.735 | 5.539.135.871 | 2.860.527.531 | 2.724.091.156 | 2.860.593.153 | 2.724.019.768 |