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-126x+149
f(0)=149
f(1)=3
f(2)=11
f(3)=5
f(4)=113
f(5)=19
f(6)=571
f(7)=1
f(8)=53
f(9)=1
f(10)=337
f(11)=31
f(12)=23
f(13)=1
f(14)=43
f(15)=379
f(16)=179
f(17)=71
f(18)=359
f(19)=157
f(20)=73
f(21)=257
f(22)=1
f(23)=37
f(24)=1
f(25)=1
f(26)=1
f(27)=631
f(28)=173
f(29)=1
f(30)=2731
f(31)=233
f(32)=953
f(33)=1
f(34)=331
f(35)=1
f(36)=281
f(37)=131
f(38)=1
f(39)=811
f(40)=1097
f(41)=139
f(42)=109
f(43)=1
f(44)=1153
f(45)=1
f(46)=107
f(47)=1
f(48)=719
f(49)=151
f(50)=1217
f(51)=919
f(52)=137
f(53)=1
f(54)=3739
f(55)=313
f(56)=419
f(57)=1
f(58)=1
f(59)=317
f(60)=103
f(61)=1
f(62)=67
f(63)=191
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)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-126x+149 could be written as f(y)= y^2-3820 with x=y+63
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-63
f'(x)>2x-127 with x > 62
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 | 2 | 7 | 0.900000 | 0.200000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 42 | 4 | 38 | 0.420000 | 0.040000 | 0.420000 | 4.666667 | 2.000000 | 5.428571 |
3 | 1.000 | 514 | 43 | 471 | 0.514000 | 0.043000 | 0.514000 | 12.238095 | 10.750000 | 12.394737 |
4 | 10.000 | 6.061 | 342 | 5.719 | 0.606100 | 0.034200 | 0.606100 | 11.791829 | 7.953488 | 12.142250 |
5 | 100.000 | 63.218 | 2.530 | 60.688 | 0.632180 | 0.025300 | 0.632180 | 10.430292 | 7.397661 | 10.611646 |
6 | 1.000.000 | 643.268 | 20.832 | 622.436 | 0.643268 | 0.020832 | 0.643268 | 10.175393 | 8.233992 | 10.256328 |
7 | 10.000.000 | 6.506.979 | 176.244 | 6.330.735 | 0.650698 | 0.017624 | 0.650698 | 10.115502 | 8.460254 | 10.170901 |
8 | 100.000.000 | 65.621.399 | 1.527.112 | 64.094.287 | 0.656214 | 0.015271 | 0.656214 | 10.084772 | 8.664761 | 10.124305 |
9 | 1.000.000.000 | 660.384.301 | 13.489.324 | 646.894.977 | 0.660384 | 0.013489 | 0.660384 | 10.063551 | 8.833225 | 10.092865 |
10 | 10.000.000.000 | 6.637.247.914 | 120.720.852 | 6.516.527.062 | 0.663725 | 0.012072 | 0.663725 | 10.050584 | 8.949363 | 10.073547 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 1 | 4 | 1.250000 | 0.250000 | 1.000000 | 1.666667 | 1.000000 | 2.000000 |
3 | 8 | 8 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 1.600000 | 2.000000 | 1.500000 |
4 | 16 | 13 | 2 | 11 | 0.812500 | 0.125000 | 0.687500 | 1.625000 | 1.000000 | 1.833333 |
5 | 32 | 23 | 3 | 20 | 0.718750 | 0.093750 | 0.625000 | 1.769231 | 1.500000 | 1.818182 |
6 | 64 | 42 | 4 | 38 | 0.656250 | 0.062500 | 0.593750 | 1.826087 | 1.333333 | 1.900000 |
7 | 128 | 42 | 4 | 38 | 0.328125 | 0.031250 | 0.296875 | 1.000000 | 1.000000 | 1.000000 |
8 | 256 | 97 | 13 | 84 | 0.378906 | 0.050781 | 0.328125 | 2.309524 | 3.250000 | 2.210526 |
9 | 512 | 230 | 23 | 207 | 0.449219 | 0.044922 | 0.404297 | 2.371134 | 1.769231 | 2.464286 |
10 | 1.024 | 523 | 43 | 480 | 0.510742 | 0.041992 | 0.468750 | 2.273913 | 1.869565 | 2.318841 |
11 | 2.048 | 1.142 | 83 | 1.059 | 0.557617 | 0.040527 | 0.517090 | 2.183556 | 1.930233 | 2.206250 |
12 | 4.096 | 2.389 | 159 | 2.230 | 0.583252 | 0.038818 | 0.544434 | 2.091944 | 1.915663 | 2.105760 |
13 | 8.192 | 4.921 | 292 | 4.629 | 0.600708 | 0.035645 | 0.565063 | 2.059858 | 1.836478 | 2.075785 |
14 | 16.384 | 10.051 | 524 | 9.527 | 0.613464 | 0.031982 | 0.581482 | 2.042471 | 1.794520 | 2.058112 |
15 | 32.768 | 20.418 | 963 | 19.455 | 0.623108 | 0.029388 | 0.593719 | 2.031440 | 1.837786 | 2.042091 |
16 | 65.536 | 41.258 | 1.754 | 39.504 | 0.629547 | 0.026764 | 0.602783 | 2.020668 | 1.821391 | 2.030532 |
17 | 131.072 | 83.032 | 3.237 | 79.795 | 0.633484 | 0.024696 | 0.608788 | 2.012507 | 1.845496 | 2.019922 |
18 | 262.144 | 167.042 | 6.129 | 160.913 | 0.637215 | 0.023380 | 0.613834 | 2.011779 | 1.893420 | 2.016580 |
19 | 524.288 | 335.668 | 11.547 | 324.121 | 0.640236 | 0.022024 | 0.618212 | 2.009483 | 1.883994 | 2.014262 |
20 | 1.048.576 | 674.632 | 21.746 | 652.886 | 0.643379 | 0.020739 | 0.622641 | 2.009819 | 1.883260 | 2.014328 |
21 | 2.097.152 | 1.354.481 | 41.326 | 1.313.155 | 0.645867 | 0.019706 | 0.626161 | 2.007733 | 1.900396 | 2.011308 |
22 | 4.194.304 | 2.718.442 | 78.475 | 2.639.967 | 0.648127 | 0.018710 | 0.629417 | 2.006999 | 1.898926 | 2.010400 |
23 | 8.388.608 | 5.454.198 | 149.540 | 5.304.658 | 0.650191 | 0.017827 | 0.632365 | 2.006369 | 1.905575 | 2.009365 |
24 | 16.777.216 | 10.940.305 | 285.650 | 10.654.655 | 0.652093 | 0.017026 | 0.635067 | 2.005850 | 1.910191 | 2.008547 |
25 | 33.554.432 | 21.938.451 | 546.225 | 21.392.226 | 0.653817 | 0.016279 | 0.637538 | 2.005287 | 1.912218 | 2.007782 |
26 | 67.108.864 | 43.981.939 | 1.048.669 | 42.933.270 | 0.655382 | 0.015626 | 0.639756 | 2.004788 | 1.919848 | 2.006957 |
27 | 134.217.728 | 88.154.171 | 2.015.859 | 86.138.312 | 0.656800 | 0.015019 | 0.641780 | 2.004327 | 1.922302 | 2.006330 |
28 | 268.435.456 | 176.663.998 | 3.881.430 | 172.782.568 | 0.658125 | 0.014459 | 0.643665 | 2.004035 | 1.925447 | 2.005873 |
29 | 536.870.912 | 353.989.367 | 7.479.128 | 346.510.239 | 0.659357 | 0.013931 | 0.645426 | 2.003744 | 1.926900 | 2.005470 |
30 | 1.073.741.824 | 709.207.547 | 14.432.379 | 694.775.168 | 0.660501 | 0.013441 | 0.647060 | 2.003471 | 1.929687 | 2.005064 |
31 | 2.147.483.648 | 1.420.721.746 | 27.885.221 | 1.392.836.525 | 0.661575 | 0.012985 | 0.648590 | 2.003253 | 1.932129 | 2.004730 |
32 | 4.294.967.296 | 2.845.769.543 | 53.935.591 | 2.791.833.952 | 0.662582 | 0.012558 | 0.650024 | 2.003045 | 1.934200 | 2.004423 |
33 | 8.589.934.592 | 5.699.642.943 | 104.425.432 | 5.595.217.511 | 0.663526 | 0.012157 | 0.651369 | 2.002848 | 1.936114 | 2.004137 |
34 | 17.179.869.184 | 11.414.502.370 | 202.396.760 | 11.212.105.610 | 0.664411 | 0.011781 | 0.652630 | 2.002670 | 1.938194 | 2.003873 |
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 | 0 | 0 | 1 | 0 |
2 | 4 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
4 | 16 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
5 | 32 | 3 | 2 | 1 | 0 | 2 | 1 | 0 |
6 | 64 | 4 | 3 | 1 | 0 | 3 | 1 | 0 |
7 | 128 | 4 | 3 | 1 | 0 | 3 | 1 | 0 |
8 | 256 | 13 | 3 | 10 | 0 | 3 | 10 | 0 |
9 | 512 | 23 | 3 | 20 | 0 | 3 | 20 | 0 |
10 | 1.024 | 43 | 3 | 40 | 0 | 3 | 40 | 0 |
11 | 2.048 | 83 | 3 | 80 | 0 | 3 | 80 | 0 |
12 | 4.096 | 159 | 3 | 156 | 0 | 3 | 156 | 0 |
13 | 8.192 | 292 | 3 | 289 | 0 | 3 | 289 | 0 |
14 | 16.384 | 524 | 3 | 521 | 0 | 3 | 521 | 0 |
15 | 32.768 | 963 | 3 | 960 | 0 | 3 | 960 | 0 |
16 | 65.536 | 1.754 | 3 | 1.751 | 0 | 3 | 1.751 | 0 |
17 | 131.072 | 3.237 | 3 | 3.234 | 0 | 3 | 3.234 | 0 |
18 | 262.144 | 6.129 | 3 | 6.126 | 0 | 3 | 6.126 | 0 |
19 | 524.288 | 11.547 | 3 | 11.544 | 0 | 3 | 11.544 | 0 |
20 | 1.048.576 | 21.746 | 3 | 21.743 | 0 | 3 | 21.743 | 0 |
21 | 2.097.152 | 41.326 | 3 | 41.323 | 0 | 3 | 41.323 | 0 |
22 | 4.194.304 | 78.475 | 3 | 78.472 | 0 | 3 | 78.472 | 0 |
23 | 8.388.608 | 149.540 | 3 | 149.537 | 0 | 3 | 149.537 | 0 |
24 | 16.777.216 | 285.650 | 3 | 285.647 | 0 | 3 | 285.647 | 0 |
25 | 33.554.432 | 546.225 | 3 | 546.222 | 0 | 3 | 546.222 | 0 |
26 | 67.108.864 | 1.048.669 | 3 | 1.048.666 | 0 | 3 | 1.048.666 | 0 |
27 | 134.217.728 | 2.015.859 | 3 | 2.015.856 | 0 | 3 | 2.015.856 | 0 |
28 | 268.435.456 | 3.881.430 | 3 | 3.881.427 | 0 | 3 | 3.881.427 | 0 |
29 | 536.870.912 | 7.479.128 | 3 | 7.479.125 | 0 | 3 | 7.479.125 | 0 |
30 | 1.073.741.824 | 14.432.379 | 3 | 14.432.376 | 0 | 3 | 14.432.376 | 0 |
31 | 2.147.483.648 | 27.885.221 | 3 | 27.885.218 | 0 | 3 | 27.885.218 | 0 |
32 | 4.294.967.296 | 53.935.591 | 3 | 53.935.588 | 0 | 3 | 53.935.588 | 0 |
33 | 8.589.934.592 | 104.425.432 | 3 | 104.425.429 | 0 | 3 | 104.425.429 | 0 |
34 | 17.179.869.184 | 202.396.760 | 3 | 202.396.757 | 0 | 3 | 202.396.757 | 0 |
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 | 2 | 0 | 0 |
2 | 4 | 4 | 1 | 2 | 1 | 2 | 0 | 1 |
3 | 8 | 6 | 2 | 3 | 1 | 3 | 1 | 1 |
4 | 16 | 11 | 6 | 4 | 2 | 6 | 1 | 2 |
5 | 32 | 20 | 9 | 10 | 6 | 6 | 3 | 5 |
6 | 64 | 38 | 17 | 20 | 12 | 12 | 5 | 9 |
7 | 128 | 38 | 17 | 20 | 12 | 12 | 5 | 9 |
8 | 256 | 84 | 39 | 44 | 16 | 20 | 17 | 31 |
9 | 512 | 207 | 102 | 104 | 40 | 44 | 45 | 78 |
10 | 1.024 | 480 | 257 | 222 | 104 | 103 | 99 | 174 |
11 | 2.048 | 1.059 | 550 | 508 | 225 | 229 | 250 | 355 |
12 | 4.096 | 2.230 | 1.138 | 1.091 | 491 | 487 | 548 | 704 |
13 | 8.192 | 4.629 | 2.340 | 2.288 | 1.069 | 1.033 | 1.115 | 1.412 |
14 | 16.384 | 9.527 | 4.769 | 4.757 | 2.184 | 2.128 | 2.315 | 2.900 |
15 | 32.768 | 19.455 | 9.771 | 9.683 | 4.506 | 4.392 | 4.767 | 5.790 |
16 | 65.536 | 39.504 | 19.996 | 19.507 | 9.188 | 9.127 | 9.732 | 11.457 |
17 | 131.072 | 79.795 | 40.434 | 39.360 | 18.486 | 18.625 | 19.740 | 22.944 |
18 | 262.144 | 160.913 | 81.317 | 79.595 | 37.492 | 37.891 | 39.599 | 45.931 |
19 | 524.288 | 324.121 | 163.923 | 160.197 | 75.944 | 76.467 | 79.824 | 91.886 |
20 | 1.048.576 | 652.886 | 329.854 | 323.031 | 153.834 | 154.239 | 161.151 | 183.662 |
21 | 2.097.152 | 1.313.155 | 663.453 | 649.701 | 310.595 | 311.015 | 324.702 | 366.843 |
22 | 4.194.304 | 2.639.967 | 1.332.534 | 1.307.432 | 626.444 | 627.596 | 652.387 | 733.540 |
23 | 8.388.608 | 5.304.658 | 2.675.533 | 2.629.124 | 1.263.135 | 1.264.154 | 1.311.978 | 1.465.391 |
24 | 16.777.216 | 10.654.655 | 5.371.089 | 5.283.565 | 2.544.707 | 2.545.798 | 2.636.331 | 2.927.819 |
25 | 33.554.432 | 21.392.226 | 10.780.780 | 10.611.445 | 5.121.802 | 5.121.864 | 5.295.677 | 5.852.883 |
26 | 67.108.864 | 42.933.270 | 21.627.023 | 21.306.246 | 10.298.044 | 10.299.239 | 10.634.601 | 11.701.386 |
27 | 134.217.728 | 86.138.312 | 43.378.556 | 42.759.755 | 20.699.610 | 20.702.243 | 21.343.621 | 23.392.838 |
28 | 268.435.456 | 172.782.568 | 86.975.256 | 85.807.311 | 41.591.121 | 41.600.521 | 42.820.925 | 46.770.001 |
29 | 536.870.912 | 346.510.239 | 174.372.381 | 172.137.857 | 83.539.076 | 83.563.908 | 85.910.517 | 93.496.738 |
30 | 1.073.741.824 | 694.775.168 | 349.551.178 | 345.223.989 | 167.744.921 | 167.789.547 | 172.299.771 | 186.940.929 |
31 | 2.147.483.648 | 1.392.836.525 | 700.597.175 | 692.239.349 | 336.743.329 | 336.815.304 | 345.512.608 | 373.765.284 |
32 | 4.294.967.296 | 2.791.833.952 | 1.403.989.710 | 1.387.844.241 | 675.821.607 | 675.954.411 | 692.727.403 | 747.330.531 |
33 | 8.589.934.592 | 5.595.217.511 | 2.813.233.748 | 2.781.983.762 | 1.355.971.529 | 1.356.186.283 | 1.388.689.865 | 1.494.369.834 |
34 | 17.179.869.184 | 11.212.105.610 | 5.636.271.761 | 5.575.833.848 | 2.720.036.541 | 2.720.479.398 | 2.783.410.320 | 2.988.179.351 |