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+132x+59
f(0)=59
f(1)=3
f(2)=109
f(3)=29
f(4)=67
f(5)=31
f(6)=887
f(7)=43
f(8)=131
f(9)=83
f(10)=17
f(11)=1
f(12)=1787
f(13)=1
f(14)=701
f(15)=283
f(16)=809
f(17)=1
f(18)=89
f(19)=61
f(20)=1033
f(21)=409
f(22)=383
f(23)=151
f(24)=3803
f(25)=1
f(26)=463
f(27)=1
f(28)=1
f(29)=197
f(30)=4919
f(31)=71
f(32)=1
f(33)=1
f(34)=1901
f(35)=41
f(36)=1
f(37)=263
f(38)=53
f(39)=1
f(40)=257
f(41)=149
f(42)=139
f(43)=79
f(44)=1
f(45)=1
f(46)=2749
f(47)=353
f(48)=8699
f(49)=1
f(50)=1
f(51)=587
f(52)=3209
f(53)=137
f(54)=10103
f(55)=431
f(56)=3529
f(57)=677
f(58)=1231
f(59)=1
f(60)=11579
f(61)=1
f(62)=1
f(63)=1543
f(64)=4201
f(65)=1
f(66)=13127
f(67)=1
f(68)=157
f(69)=1741
f(70)=4733
f(71)=1
f(72)=14747
f(73)=313
f(74)=5101
f(75)=487
f(76)=1
f(77)=673
f(78)=967
f(79)=1
f(80)=1
f(81)=541
f(82)=5869
f(83)=373
f(84)=167
f(85)=1
f(86)=6269
f(87)=2389
f(88)=6473
f(89)=1
f(90)=691
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1291
f(97)=1
f(98)=1
f(99)=1433
b) Substitution of the polynom
The polynom f(x)=x^2+132x+59 could be written as f(y)= y^2-4297 with x=y-66
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+66
f'(x)>2x+131
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 | 10 | 5 | 5 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 23 | 41 | 0.640000 | 0.230000 | 0.410000 | 6.400000 | 4.600000 | 8.200000 |
3 | 1.000 | 599 | 148 | 451 | 0.599000 | 0.148000 | 0.451000 | 9.359375 | 6.434783 | 11.000000 |
4 | 10.000 | 6.242 | 1.093 | 5.149 | 0.624200 | 0.109300 | 0.514900 | 10.420701 | 7.385135 | 11.416851 |
5 | 100.000 | 64.057 | 8.210 | 55.847 | 0.640570 | 0.082100 | 0.558470 | 10.262256 | 7.511436 | 10.846184 |
6 | 1.000.000 | 650.176 | 65.740 | 584.436 | 0.650176 | 0.065740 | 0.584436 | 10.149961 | 8.007308 | 10.464949 |
7 | 10.000.000 | 6.565.110 | 551.768 | 6.013.342 | 0.656511 | 0.055177 | 0.601334 | 10.097435 | 8.393186 | 10.289137 |
8 | 100.000.000 | 66.123.692 | 4.746.870 | 61.376.822 | 0.661237 | 0.047469 | 0.613768 | 10.071985 | 8.603018 | 10.206774 |
9 | 1.000.000.000 | 664.854.562 | 41.663.682 | 623.190.880 | 0.664855 | 0.041664 | 0.623191 | 10.054710 | 8.777084 | 10.153522 |
10 | 10.000.000.000 | 6.677.339.766 | 371.229.727 | 6.306.110.039 | 0.667734 | 0.037123 | 0.630611 | 10.043308 | 8.910152 | 10.119066 |
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 | 4 | 5 | 1.125000 | 0.500000 | 0.625000 | 1.800000 | 1.333333 | 2.500000 |
4 | 16 | 14 | 7 | 7 | 0.875000 | 0.437500 | 0.437500 | 1.555556 | 1.750000 | 1.400000 |
5 | 32 | 25 | 10 | 15 | 0.781250 | 0.312500 | 0.468750 | 1.785714 | 1.428571 | 2.142857 |
6 | 64 | 44 | 16 | 28 | 0.687500 | 0.250000 | 0.437500 | 1.760000 | 1.600000 | 1.866667 |
7 | 128 | 78 | 25 | 53 | 0.609375 | 0.195312 | 0.414062 | 1.772727 | 1.562500 | 1.892857 |
8 | 256 | 154 | 47 | 107 | 0.601562 | 0.183594 | 0.417969 | 1.974359 | 1.880000 | 2.018868 |
9 | 512 | 304 | 84 | 220 | 0.593750 | 0.164062 | 0.429688 | 1.974026 | 1.787234 | 2.056075 |
10 | 1.024 | 612 | 153 | 459 | 0.597656 | 0.149414 | 0.448242 | 2.013158 | 1.821429 | 2.086364 |
11 | 2.048 | 1.241 | 270 | 971 | 0.605957 | 0.131836 | 0.474121 | 2.027778 | 1.764706 | 2.115469 |
12 | 4.096 | 2.512 | 508 | 2.004 | 0.613281 | 0.124023 | 0.489258 | 2.024174 | 1.881482 | 2.063852 |
13 | 8.192 | 5.098 | 920 | 4.178 | 0.622314 | 0.112305 | 0.510010 | 2.029459 | 1.811024 | 2.084830 |
14 | 16.384 | 10.323 | 1.640 | 8.683 | 0.630066 | 0.100098 | 0.529968 | 2.024912 | 1.782609 | 2.078267 |
15 | 32.768 | 20.824 | 3.043 | 17.781 | 0.635498 | 0.092865 | 0.542633 | 2.017243 | 1.855488 | 2.047795 |
16 | 65.536 | 41.897 | 5.646 | 36.251 | 0.639297 | 0.086151 | 0.553146 | 2.011957 | 1.855406 | 2.038749 |
17 | 131.072 | 84.167 | 10.448 | 73.719 | 0.642143 | 0.079712 | 0.562431 | 2.008903 | 1.850514 | 2.033571 |
18 | 262.144 | 169.212 | 19.491 | 149.721 | 0.645493 | 0.074352 | 0.571140 | 2.010432 | 1.865525 | 2.030969 |
19 | 524.288 | 339.771 | 36.502 | 303.269 | 0.648062 | 0.069622 | 0.578440 | 2.007960 | 1.872762 | 2.025561 |
20 | 1.048.576 | 681.984 | 68.704 | 613.280 | 0.650391 | 0.065521 | 0.584869 | 2.007187 | 1.882198 | 2.022231 |
21 | 2.097.152 | 1.368.118 | 130.453 | 1.237.665 | 0.652369 | 0.062205 | 0.590165 | 2.006085 | 1.898769 | 2.018108 |
22 | 4.194.304 | 2.744.440 | 246.452 | 2.497.988 | 0.654325 | 0.058759 | 0.595567 | 2.005996 | 1.889202 | 2.018307 |
23 | 8.388.608 | 5.504.162 | 468.590 | 5.035.572 | 0.656147 | 0.055860 | 0.600287 | 2.005568 | 1.901344 | 2.015851 |
24 | 16.777.216 | 11.034.119 | 893.636 | 10.140.483 | 0.657685 | 0.053265 | 0.604420 | 2.004686 | 1.907074 | 2.013770 |
25 | 33.554.432 | 22.118.485 | 1.705.803 | 20.412.682 | 0.659182 | 0.050837 | 0.608345 | 2.004554 | 1.908834 | 2.012989 |
26 | 67.108.864 | 44.325.968 | 3.264.846 | 41.061.122 | 0.660508 | 0.048650 | 0.611858 | 2.004024 | 1.913964 | 2.011549 |
27 | 134.217.728 | 88.818.974 | 6.261.893 | 82.557.081 | 0.661753 | 0.046655 | 0.615098 | 2.003768 | 1.917975 | 2.010590 |
28 | 268.435.456 | 177.944.594 | 12.025.804 | 165.918.790 | 0.662895 | 0.044800 | 0.618096 | 2.003452 | 1.920474 | 2.009746 |
29 | 536.870.912 | 356.461.132 | 23.133.237 | 333.327.895 | 0.663961 | 0.043089 | 0.620872 | 2.003214 | 1.923633 | 2.008982 |
30 | 1.073.741.824 | 713.986.933 | 44.566.428 | 669.420.505 | 0.664952 | 0.041506 | 0.623446 | 2.002987 | 1.926511 | 2.008294 |
31 | 2.147.483.648 | 1.429.960.197 | 85.974.288 | 1.343.985.909 | 0.665877 | 0.040035 | 0.625842 | 2.002782 | 1.929127 | 2.007686 |
32 | 4.294.967.296 | 2.863.653.598 | 166.088.551 | 2.697.565.047 | 0.666746 | 0.038671 | 0.628076 | 2.002611 | 1.931840 | 2.007138 |
33 | 8.589.934.592 | 5.734.320.558 | 321.190.780 | 5.413.129.778 | 0.667563 | 0.037392 | 0.630171 | 2.002449 | 1.933853 | 2.006673 |
34 | 17.179.869.184 | 11.481.816.737 | 621.848.315 | 10.859.968.422 | 0.668330 | 0.036196 | 0.632133 | 2.002298 | 1.936072 | 2.006227 |
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 | 3 | 0 | 2 | 0 | 2 | 1 | 0 |
3 | 8 | 4 | 0 | 3 | 0 | 2 | 1 | 1 |
4 | 16 | 7 | 1 | 5 | 0 | 5 | 1 | 1 |
5 | 32 | 10 | 2 | 7 | 1 | 6 | 1 | 2 |
6 | 64 | 16 | 3 | 12 | 1 | 9 | 2 | 4 |
7 | 128 | 25 | 7 | 17 | 2 | 11 | 5 | 7 |
8 | 256 | 47 | 17 | 29 | 5 | 18 | 9 | 15 |
9 | 512 | 84 | 32 | 51 | 9 | 33 | 16 | 26 |
10 | 1.024 | 153 | 58 | 94 | 18 | 57 | 27 | 51 |
11 | 2.048 | 270 | 100 | 169 | 37 | 99 | 37 | 97 |
12 | 4.096 | 508 | 187 | 320 | 67 | 183 | 70 | 188 |
13 | 8.192 | 920 | 333 | 586 | 115 | 340 | 126 | 339 |
14 | 16.384 | 1.640 | 590 | 1.049 | 234 | 595 | 214 | 597 |
15 | 32.768 | 3.043 | 1.099 | 1.943 | 417 | 1.105 | 415 | 1.106 |
16 | 65.536 | 5.646 | 2.036 | 3.609 | 776 | 2.031 | 767 | 2.072 |
17 | 131.072 | 10.448 | 3.681 | 6.766 | 1.381 | 3.805 | 1.406 | 3.856 |
18 | 262.144 | 19.491 | 6.895 | 12.595 | 2.587 | 7.180 | 2.590 | 7.134 |
19 | 524.288 | 36.502 | 12.778 | 23.723 | 4.835 | 13.398 | 4.838 | 13.431 |
20 | 1.048.576 | 68.704 | 24.039 | 44.664 | 9.169 | 25.212 | 9.111 | 25.212 |
21 | 2.097.152 | 130.453 | 45.594 | 84.858 | 17.354 | 48.039 | 17.159 | 47.901 |
22 | 4.194.304 | 246.452 | 85.810 | 160.641 | 32.613 | 90.785 | 32.437 | 90.617 |
23 | 8.388.608 | 468.590 | 162.706 | 305.883 | 61.811 | 172.616 | 61.593 | 172.570 |
24 | 16.777.216 | 893.636 | 309.653 | 583.982 | 117.159 | 329.837 | 117.231 | 329.409 |
25 | 33.554.432 | 1.705.803 | 589.880 | 1.115.922 | 222.962 | 630.061 | 223.100 | 629.680 |
26 | 67.108.864 | 3.264.846 | 1.127.480 | 2.137.365 | 425.903 | 1.206.641 | 426.123 | 1.206.179 |
27 | 134.217.728 | 6.261.893 | 2.159.941 | 4.101.951 | 815.690 | 2.315.622 | 816.131 | 2.314.450 |
28 | 268.435.456 | 12.025.804 | 4.141.218 | 7.884.585 | 1.563.300 | 4.449.052 | 1.564.088 | 4.449.364 |
29 | 536.870.912 | 23.133.237 | 7.954.833 | 15.178.403 | 3.002.161 | 8.562.253 | 3.003.870 | 8.564.953 |
30 | 1.073.741.824 | 44.566.428 | 15.305.882 | 29.260.545 | 5.776.908 | 16.503.982 | 5.774.887 | 16.510.651 |
31 | 2.147.483.648 | 85.974.288 | 29.493.034 | 56.481.253 | 11.130.518 | 31.862.054 | 11.126.542 | 31.855.174 |
32 | 4.294.967.296 | 166.088.551 | 56.921.650 | 109.166.900 | 21.477.126 | 61.574.264 | 21.472.501 | 61.564.660 |
33 | 8.589.934.592 | 321.190.780 | 109.975.600 | 211.215.179 | 41.483.238 | 119.116.244 | 41.479.558 | 119.111.740 |
34 | 17.179.869.184 | 621.848.315 | 212.755.028 | 409.093.286 | 80.224.056 | 230.696.619 | 80.232.103 | 230.695.537 |
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 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 2 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 5 | 4 | 1 | 0 | 3 | 1 | 1 |
4 | 16 | 7 | 4 | 3 | 1 | 3 | 2 | 1 |
5 | 32 | 15 | 8 | 7 | 3 | 3 | 4 | 5 |
6 | 64 | 28 | 13 | 15 | 9 | 4 | 7 | 8 |
7 | 128 | 53 | 28 | 25 | 18 | 9 | 16 | 10 |
8 | 256 | 107 | 57 | 50 | 32 | 20 | 32 | 23 |
9 | 512 | 220 | 116 | 104 | 63 | 39 | 70 | 48 |
10 | 1.024 | 459 | 229 | 230 | 134 | 86 | 142 | 97 |
11 | 2.048 | 971 | 497 | 474 | 254 | 214 | 288 | 215 |
12 | 4.096 | 2.004 | 1.017 | 987 | 517 | 458 | 589 | 440 |
13 | 8.192 | 4.178 | 2.108 | 2.070 | 1.104 | 955 | 1.177 | 942 |
14 | 16.384 | 8.683 | 4.427 | 4.256 | 2.300 | 1.959 | 2.409 | 2.015 |
15 | 32.768 | 17.781 | 9.028 | 8.753 | 4.727 | 4.137 | 4.788 | 4.129 |
16 | 65.536 | 36.251 | 18.333 | 17.918 | 9.730 | 8.434 | 9.764 | 8.323 |
17 | 131.072 | 73.719 | 37.169 | 36.550 | 19.709 | 17.149 | 19.777 | 17.084 |
18 | 262.144 | 149.721 | 75.392 | 74.329 | 39.826 | 35.080 | 39.901 | 34.914 |
19 | 524.288 | 303.269 | 152.586 | 150.683 | 80.244 | 71.414 | 80.413 | 71.198 |
20 | 1.048.576 | 613.280 | 308.120 | 305.160 | 161.399 | 145.095 | 161.830 | 144.956 |
21 | 2.097.152 | 1.237.665 | 622.105 | 615.560 | 324.874 | 293.588 | 325.644 | 293.559 |
22 | 4.194.304 | 2.497.988 | 1.255.755 | 1.242.233 | 654.261 | 594.812 | 654.926 | 593.989 |
23 | 8.388.608 | 5.035.572 | 2.530.688 | 2.504.884 | 1.315.590 | 1.201.456 | 1.316.715 | 1.201.811 |
24 | 16.777.216 | 10.140.483 | 5.096.427 | 5.044.056 | 2.644.439 | 2.426.182 | 2.644.924 | 2.424.938 |
25 | 33.554.432 | 20.412.682 | 10.258.440 | 10.154.242 | 5.310.924 | 4.893.806 | 5.312.306 | 4.895.646 |
26 | 67.108.864 | 41.061.122 | 20.630.589 | 20.430.533 | 10.667.301 | 9.860.167 | 10.666.501 | 9.867.153 |
27 | 134.217.728 | 82.557.081 | 41.475.680 | 41.081.401 | 21.409.523 | 19.865.305 | 21.405.993 | 19.876.260 |
28 | 268.435.456 | 165.918.790 | 83.331.767 | 82.587.023 | 42.957.701 | 39.994.842 | 42.961.763 | 40.004.484 |
29 | 536.870.912 | 333.327.895 | 167.386.769 | 165.941.126 | 86.183.281 | 80.476.925 | 86.180.792 | 80.486.897 |
30 | 1.073.741.824 | 669.420.505 | 336.089.473 | 333.331.032 | 172.848.491 | 161.856.188 | 172.852.320 | 161.863.506 |
31 | 2.147.483.648 | 1.343.985.909 | 674.623.781 | 669.362.128 | 346.589.059 | 325.412.883 | 346.593.120 | 325.390.847 |
32 | 4.294.967.296 | 2.697.565.047 | 1.353.912.532 | 1.343.652.515 | 694.884.233 | 653.898.749 | 694.898.192 | 653.883.873 |
33 | 8.589.934.592 | 5.413.129.778 | 2.716.548.934 | 2.696.580.844 | 1.392.927.670 | 1.313.646.234 | 1.392.931.508 | 1.313.624.366 |
34 | 17.179.869.184 | 10.859.968.422 | 5.449.318.905 | 5.410.649.517 | 2.791.760.866 | 2.638.219.149 | 2.791.798.080 | 2.638.190.327 |