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+68x-61
f(0)=61
f(1)=1
f(2)=79
f(3)=19
f(4)=227
f(5)=1
f(6)=383
f(7)=29
f(8)=547
f(9)=1
f(10)=719
f(11)=101
f(12)=31
f(13)=1
f(14)=1087
f(15)=37
f(16)=1283
f(17)=173
f(18)=1487
f(19)=199
f(20)=1699
f(21)=113
f(22)=1
f(23)=127
f(24)=1
f(25)=283
f(26)=2383
f(27)=313
f(28)=71
f(29)=43
f(30)=2879
f(31)=47
f(32)=73
f(33)=409
f(34)=3407
f(35)=443
f(36)=1
f(37)=239
f(38)=3967
f(39)=257
f(40)=4259
f(41)=1
f(42)=97
f(43)=1
f(44)=157
f(45)=1
f(46)=1
f(47)=167
f(48)=5507
f(49)=709
f(50)=5839
f(51)=751
f(52)=1
f(53)=397
f(54)=107
f(55)=419
f(56)=6883
f(57)=883
f(58)=7247
f(59)=929
f(60)=401
f(61)=1
f(62)=421
f(63)=1
f(64)=8387
f(65)=1
f(66)=8783
f(67)=1123
f(68)=9187
f(69)=587
f(70)=331
f(71)=613
f(72)=233
f(73)=1279
f(74)=337
f(75)=1
f(76)=10883
f(77)=347
f(78)=241
f(79)=1
f(80)=11779
f(81)=1
f(82)=12239
f(83)=1559
f(84)=131
f(85)=809
f(86)=13183
f(87)=839
f(88)=1
f(89)=1
f(90)=14159
f(91)=1801
f(92)=137
f(93)=1
f(94)=523
f(95)=1
f(96)=15683
f(97)=1993
f(98)=853
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+68x-61 could be written as f(y)= y^2-1217 with x=y-34
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+34
f'(x)>2x+67
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 | 8 | 8 | 0 | 0.800000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 73 | 59 | 14 | 0.730000 | 0.590000 | 0.140000 | 9.125000 | 7.375000 | inf |
3 | 1.000 | 680 | 451 | 229 | 0.680000 | 0.451000 | 0.229000 | 9.315068 | 7.644068 | 16.357143 |
4 | 10.000 | 6.849 | 3.234 | 3.615 | 0.684900 | 0.323400 | 0.361500 | 10.072059 | 7.170732 | 15.786026 |
5 | 100.000 | 68.851 | 24.707 | 44.144 | 0.688510 | 0.247070 | 0.441440 | 10.052709 | 7.639765 | 12.211342 |
6 | 1.000.000 | 690.121 | 198.180 | 491.941 | 0.690121 | 0.198180 | 0.491941 | 10.023398 | 8.021209 | 11.144006 |
7 | 10.000.000 | 6.902.795 | 1.658.098 | 5.244.697 | 0.690279 | 0.165810 | 0.524470 | 10.002296 | 8.366627 | 10.661232 |
8 | 100.000.000 | 69.054.184 | 14.267.495 | 54.786.689 | 0.690542 | 0.142675 | 0.547867 | 10.003800 | 8.604735 | 10.446111 |
9 | 1.000.000.000 | 690.784.421 | 125.208.698 | 565.575.723 | 0.690784 | 0.125209 | 0.565576 | 10.003513 | 8.775801 | 10.323233 |
10 | 10.000.000.000 | 6.909.762.534 | 1.115.755.142 | 5.794.007.392 | 0.690976 | 0.111576 | 0.579401 | 10.002777 | 8.911163 | 10.244441 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 2.000000 | 2.000000 | -nan |
3 | 8 | 7 | 7 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.750000 | 1.750000 | -nan |
4 | 16 | 13 | 12 | 1 | 0.812500 | 0.750000 | 0.062500 | 1.857143 | 1.714286 | inf |
5 | 32 | 25 | 22 | 3 | 0.781250 | 0.687500 | 0.093750 | 1.923077 | 1.833333 | 3.000000 |
6 | 64 | 48 | 41 | 7 | 0.750000 | 0.640625 | 0.109375 | 1.920000 | 1.863636 | 2.333333 |
7 | 128 | 90 | 70 | 20 | 0.703125 | 0.546875 | 0.156250 | 1.875000 | 1.707317 | 2.857143 |
8 | 256 | 180 | 139 | 41 | 0.703125 | 0.542969 | 0.160156 | 2.000000 | 1.985714 | 2.050000 |
9 | 512 | 352 | 261 | 91 | 0.687500 | 0.509766 | 0.177734 | 1.955556 | 1.877698 | 2.219512 |
10 | 1.024 | 694 | 463 | 231 | 0.677734 | 0.452148 | 0.225586 | 1.971591 | 1.773946 | 2.538461 |
11 | 2.048 | 1.403 | 803 | 600 | 0.685059 | 0.392090 | 0.292969 | 2.021614 | 1.734341 | 2.597403 |
12 | 4.096 | 2.812 | 1.483 | 1.329 | 0.686523 | 0.362061 | 0.324463 | 2.004277 | 1.846824 | 2.215000 |
13 | 8.192 | 5.603 | 2.728 | 2.875 | 0.683960 | 0.333008 | 0.350952 | 1.992532 | 1.839514 | 2.163281 |
14 | 16.384 | 11.233 | 5.012 | 6.221 | 0.685608 | 0.305908 | 0.379700 | 2.004819 | 1.837243 | 2.163826 |
15 | 32.768 | 22.530 | 9.164 | 13.366 | 0.687561 | 0.279663 | 0.407898 | 2.005697 | 1.828412 | 2.148529 |
16 | 65.536 | 45.097 | 16.933 | 28.164 | 0.688126 | 0.258377 | 0.429749 | 2.001642 | 1.847774 | 2.107137 |
17 | 131.072 | 90.294 | 31.466 | 58.828 | 0.688889 | 0.240067 | 0.448822 | 2.002218 | 1.858265 | 2.088766 |
18 | 262.144 | 180.744 | 58.575 | 122.169 | 0.689484 | 0.223446 | 0.466038 | 2.001728 | 1.861533 | 2.076715 |
19 | 524.288 | 361.613 | 109.959 | 251.654 | 0.689722 | 0.209730 | 0.479992 | 2.000692 | 1.877234 | 2.059884 |
20 | 1.048.576 | 723.610 | 206.873 | 516.737 | 0.690088 | 0.197289 | 0.492799 | 2.001062 | 1.881365 | 2.053363 |
21 | 2.097.152 | 1.447.327 | 390.786 | 1.056.541 | 0.690139 | 0.186341 | 0.503798 | 2.000148 | 1.889014 | 2.044640 |
22 | 4.194.304 | 2.894.763 | 740.955 | 2.153.808 | 0.690165 | 0.176657 | 0.513508 | 2.000075 | 1.896063 | 2.038547 |
23 | 8.388.608 | 5.790.183 | 1.408.494 | 4.381.689 | 0.690244 | 0.167906 | 0.522338 | 2.000227 | 1.900917 | 2.034392 |
24 | 16.777.216 | 11.581.910 | 2.684.489 | 8.897.421 | 0.690336 | 0.160008 | 0.530328 | 2.000267 | 1.905929 | 2.030592 |
25 | 33.554.432 | 23.166.608 | 5.126.626 | 18.039.982 | 0.690419 | 0.152785 | 0.537633 | 2.000241 | 1.909721 | 2.027552 |
26 | 67.108.864 | 46.338.504 | 9.810.930 | 36.527.574 | 0.690498 | 0.146194 | 0.544303 | 2.000228 | 1.913721 | 2.024812 |
27 | 134.217.728 | 92.688.237 | 18.813.551 | 73.874.686 | 0.690581 | 0.140172 | 0.550409 | 2.000242 | 1.917611 | 2.022436 |
28 | 268.435.456 | 185.396.959 | 36.135.394 | 149.261.565 | 0.690657 | 0.134615 | 0.556043 | 2.000221 | 1.920711 | 2.020470 |
29 | 536.870.912 | 370.831.292 | 69.520.702 | 301.310.590 | 0.690727 | 0.129492 | 0.561235 | 2.000202 | 1.923895 | 2.018675 |
30 | 1.073.741.824 | 741.730.251 | 133.937.302 | 607.792.949 | 0.690790 | 0.124739 | 0.566051 | 2.000182 | 1.926582 | 2.017164 |
31 | 2.147.483.648 | 1.483.594.077 | 258.400.433 | 1.225.193.644 | 0.690852 | 0.120327 | 0.570525 | 2.000180 | 1.929264 | 2.015807 |
32 | 4.294.967.296 | 2.967.434.950 | 499.149.250 | 2.468.285.700 | 0.690910 | 0.116217 | 0.574693 | 2.000166 | 1.931689 | 2.014609 |
33 | 8.589.934.592 | 5.935.347.546 | 965.351.277 | 4.969.996.269 | 0.690965 | 0.112382 | 0.578584 | 2.000161 | 1.933993 | 2.013542 |
34 | 17.179.869.184 | 11.871.603.307 | 1.869.073.196 | 10.002.530.111 | 0.691018 | 0.108794 | 0.582224 | 2.000153 | 1.936159 | 2.012583 |
35 | 34.359.738.368 | 23.744.888.810 | 3.622.516.397 | 20.122.372.413 | 0.691067 | 0.105429 | 0.585638 | 2.000142 | 1.938135 | 2.011728 |
36 | 68.719.476.736 | 47.493.090.300 | 7.027.632.610 | 40.465.457.690 | 0.691115 | 0.102266 | 0.588850 | 2.000139 | 1.939986 | 2.010968 |
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 | 2 | 0 | 0 | 0 | 1 | 1 |
2 | 4 | 4 | 3 | 1 | 0 | 2 | 1 | 1 |
3 | 8 | 7 | 4 | 3 | 0 | 3 | 2 | 2 |
4 | 16 | 12 | 6 | 6 | 0 | 4 | 4 | 4 |
5 | 32 | 22 | 12 | 10 | 2 | 6 | 5 | 9 |
6 | 64 | 41 | 20 | 21 | 5 | 13 | 7 | 16 |
7 | 128 | 70 | 34 | 36 | 10 | 26 | 10 | 24 |
8 | 256 | 139 | 66 | 73 | 15 | 54 | 22 | 48 |
9 | 512 | 261 | 120 | 141 | 37 | 94 | 38 | 92 |
10 | 1.024 | 463 | 209 | 254 | 62 | 167 | 74 | 160 |
11 | 2.048 | 803 | 368 | 435 | 110 | 292 | 122 | 279 |
12 | 4.096 | 1.483 | 676 | 807 | 206 | 528 | 219 | 530 |
13 | 8.192 | 2.728 | 1.228 | 1.500 | 361 | 979 | 397 | 991 |
14 | 16.384 | 5.012 | 2.274 | 2.738 | 670 | 1.820 | 706 | 1.816 |
15 | 32.768 | 9.164 | 4.129 | 5.035 | 1.208 | 3.375 | 1.275 | 3.306 |
16 | 65.536 | 16.933 | 7.680 | 9.253 | 2.251 | 6.213 | 2.329 | 6.140 |
17 | 131.072 | 31.466 | 14.173 | 17.293 | 4.156 | 11.550 | 4.236 | 11.524 |
18 | 262.144 | 58.575 | 26.390 | 32.185 | 7.812 | 21.451 | 7.852 | 21.460 |
19 | 524.288 | 109.959 | 49.423 | 60.536 | 14.642 | 40.271 | 14.727 | 40.319 |
20 | 1.048.576 | 206.873 | 92.962 | 113.911 | 27.243 | 76.059 | 27.495 | 76.076 |
21 | 2.097.152 | 390.786 | 175.526 | 215.260 | 51.533 | 143.782 | 51.489 | 143.982 |
22 | 4.194.304 | 740.955 | 332.633 | 408.322 | 97.507 | 272.830 | 97.498 | 273.120 |
23 | 8.388.608 | 1.408.494 | 631.830 | 776.664 | 184.911 | 519.620 | 184.374 | 519.589 |
24 | 16.777.216 | 2.684.489 | 1.203.675 | 1.480.814 | 352.008 | 990.635 | 350.852 | 990.994 |
25 | 33.554.432 | 5.126.626 | 2.298.017 | 2.828.609 | 669.868 | 1.893.220 | 668.909 | 1.894.629 |
26 | 67.108.864 | 9.810.930 | 4.397.448 | 5.413.482 | 1.280.010 | 3.626.689 | 1.278.055 | 3.626.176 |
27 | 134.217.728 | 18.813.551 | 8.430.717 | 10.382.834 | 2.449.287 | 6.958.210 | 2.448.049 | 6.958.005 |
28 | 268.435.456 | 36.135.394 | 16.190.064 | 19.945.330 | 4.697.551 | 13.372.377 | 4.694.755 | 13.370.711 |
29 | 536.870.912 | 69.520.702 | 31.139.773 | 38.380.929 | 9.023.822 | 25.739.092 | 9.021.020 | 25.736.768 |
30 | 1.073.741.824 | 133.937.302 | 59.976.404 | 73.960.898 | 17.360.022 | 49.604.943 | 17.361.244 | 49.611.093 |
31 | 2.147.483.648 | 258.400.433 | 115.678.683 | 142.721.750 | 33.450.858 | 95.748.509 | 33.448.901 | 95.752.165 |
32 | 4.294.967.296 | 499.149.250 | 223.405.324 | 275.743.926 | 64.536.512 | 185.045.008 | 64.533.005 | 185.034.725 |
33 | 8.589.934.592 | 965.351.277 | 431.967.360 | 533.383.917 | 124.671.376 | 357.999.990 | 124.678.631 | 358.001.280 |
34 | 17.179.869.184 | 1.869.073.196 | 836.185.012 | 1.032.888.184 | 241.139.559 | 693.393.984 | 241.150.383 | 693.389.270 |
35 | 34.359.738.368 | 3.622.516.397 | 1.620.313.197 | 2.002.203.200 | 466.907.674 | 1.344.347.533 | 466.919.873 | 1.344.341.317 |
36 | 68.719.476.736 | 7.027.632.610 | 3.142.780.932 | 3.884.851.678 | 904.950.840 | 2.608.843.695 | 904.992.536 | 2.608.845.539 |
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 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
5 | 32 | 3 | 2 | 1 | 1 | 0 | 0 | 2 |
6 | 64 | 7 | 5 | 2 | 3 | 0 | 2 | 2 |
7 | 128 | 20 | 11 | 9 | 8 | 5 | 4 | 3 |
8 | 256 | 41 | 18 | 23 | 14 | 9 | 11 | 7 |
9 | 512 | 91 | 35 | 56 | 28 | 20 | 25 | 18 |
10 | 1.024 | 231 | 106 | 125 | 67 | 52 | 62 | 50 |
11 | 2.048 | 600 | 283 | 317 | 155 | 152 | 159 | 134 |
12 | 4.096 | 1.329 | 632 | 697 | 340 | 328 | 345 | 316 |
13 | 8.192 | 2.875 | 1.376 | 1.499 | 722 | 712 | 733 | 708 |
14 | 16.384 | 6.221 | 3.036 | 3.185 | 1.576 | 1.503 | 1.611 | 1.531 |
15 | 32.768 | 13.366 | 6.567 | 6.799 | 3.396 | 3.212 | 3.442 | 3.316 |
16 | 65.536 | 28.164 | 13.937 | 14.227 | 7.138 | 6.857 | 7.237 | 6.932 |
17 | 131.072 | 58.828 | 29.088 | 29.740 | 15.041 | 14.309 | 15.104 | 14.374 |
18 | 262.144 | 122.169 | 60.469 | 61.700 | 31.272 | 29.754 | 31.307 | 29.836 |
19 | 524.288 | 251.654 | 124.644 | 127.010 | 63.824 | 61.644 | 64.427 | 61.759 |
20 | 1.048.576 | 516.737 | 256.215 | 260.522 | 131.104 | 126.813 | 131.910 | 126.910 |
21 | 2.097.152 | 1.056.541 | 524.130 | 532.411 | 268.151 | 259.441 | 269.146 | 259.803 |
22 | 4.194.304 | 2.153.808 | 1.069.829 | 1.083.979 | 546.007 | 530.350 | 547.543 | 529.908 |
23 | 8.388.608 | 4.381.689 | 2.176.496 | 2.205.193 | 1.110.843 | 1.080.134 | 1.111.554 | 1.079.158 |
24 | 16.777.216 | 8.897.421 | 4.422.784 | 4.474.637 | 2.254.457 | 2.193.972 | 2.254.655 | 2.194.337 |
25 | 33.554.432 | 18.039.982 | 8.969.027 | 9.070.955 | 4.569.446 | 4.451.251 | 4.568.112 | 4.451.173 |
26 | 67.108.864 | 36.527.574 | 18.167.340 | 18.360.234 | 9.245.261 | 9.018.738 | 9.244.244 | 9.019.331 |
27 | 134.217.728 | 73.874.686 | 36.752.896 | 37.121.790 | 18.687.751 | 18.253.556 | 18.682.069 | 18.251.310 |
28 | 268.435.456 | 149.261.565 | 74.287.022 | 74.974.543 | 37.729.451 | 36.901.623 | 37.730.485 | 36.900.006 |
29 | 536.870.912 | 301.310.590 | 150.000.601 | 151.309.989 | 76.121.104 | 74.535.240 | 76.129.486 | 74.524.760 |
30 | 1.073.741.824 | 607.792.949 | 302.627.699 | 305.165.250 | 153.477.312 | 150.416.624 | 153.490.526 | 150.408.487 |
31 | 2.147.483.648 | 1.225.193.644 | 610.147.928 | 615.045.716 | 309.253.981 | 303.340.364 | 309.271.710 | 303.327.589 |
32 | 4.294.967.296 | 2.468.285.700 | 1.229.415.052 | 1.238.870.648 | 622.777.577 | 611.364.676 | 622.791.188 | 611.352.259 |
33 | 8.589.934.592 | 4.969.996.269 | 2.475.844.749 | 2.494.151.520 | 1.253.542.417 | 1.231.478.831 | 1.253.536.060 | 1.231.438.961 |
34 | 17.179.869.184 | 10.002.530.111 | 4.983.531.102 | 5.018.999.009 | 2.521.996.080 | 2.479.292.338 | 2.522.009.475 | 2.479.232.218 |
35 | 34.359.738.368 | 20.122.372.413 | 10.026.877.385 | 10.095.495.028 | 5.071.997.563 | 4.989.209.912 | 5.071.929.825 | 4.989.235.113 |
36 | 68.719.476.736 | 40.465.457.690 | 20.166.138.735 | 20.299.318.955 | 10.196.607.240 | 10.036.213.231 | 10.196.370.683 | 10.036.266.536 |