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-47
f(0)=47
f(1)=23
f(2)=43
f(3)=19
f(4)=31
f(5)=11
f(6)=1
f(7)=1
f(8)=17
f(9)=1
f(10)=53
f(11)=37
f(12)=97
f(13)=61
f(14)=149
f(15)=89
f(16)=1
f(17)=1
f(18)=277
f(19)=157
f(20)=353
f(21)=197
f(22)=1
f(23)=241
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=67
f(29)=397
f(30)=853
f(31)=457
f(32)=977
f(33)=521
f(34)=1109
f(35)=1
f(36)=1249
f(37)=661
f(38)=127
f(39)=1
f(40)=1553
f(41)=1
f(42)=101
f(43)=1
f(44)=1889
f(45)=1
f(46)=2069
f(47)=1
f(48)=1
f(49)=107
f(50)=223
f(51)=1277
f(52)=2657
f(53)=1381
f(54)=151
f(55)=1489
f(56)=3089
f(57)=1601
f(58)=1
f(59)=1
f(60)=1
f(61)=167
f(62)=3797
f(63)=1
f(64)=4049
f(65)=2089
f(66)=139
f(67)=2221
f(68)=199
f(69)=2357
f(70)=211
f(71)=227
f(72)=467
f(73)=1
f(74)=1
f(75)=2789
f(76)=337
f(77)=173
f(78)=6037
f(79)=163
f(80)=6353
f(81)=3257
f(82)=607
f(83)=311
f(84)=1
f(85)=1
f(86)=7349
f(87)=3761
f(88)=179
f(89)=1
f(90)=8053
f(91)=1
f(92)=443
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=503
f(99)=4877
b) Substitution of the polynom
The polynom f(x)=x^2-47 could be written as f(y)= y^2-47 with x=y+0
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+0
f'(x)>2x-1 with x > 7
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.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 69 | 48 | 21 | 0.690000 | 0.480000 | 0.690000 | 8.625000 | 6.000000 | inf |
3 | 1.000 | 706 | 318 | 388 | 0.706000 | 0.318000 | 0.706000 | 10.231884 | 6.625000 | 18.476191 |
4 | 10.000 | 7.159 | 2.223 | 4.936 | 0.715900 | 0.222300 | 0.715900 | 10.140226 | 6.990566 | 12.721649 |
5 | 100.000 | 71.040 | 17.336 | 53.704 | 0.710400 | 0.173360 | 0.710400 | 9.923174 | 7.798470 | 10.880065 |
6 | 1.000.000 | 707.058 | 141.016 | 566.042 | 0.707058 | 0.141016 | 0.707058 | 9.952956 | 8.134287 | 10.540034 |
7 | 10.000.000 | 7.049.492 | 1.191.996 | 5.857.496 | 0.704949 | 0.119200 | 0.704949 | 9.970175 | 8.452913 | 10.348165 |
8 | 100.000.000 | 70.324.877 | 10.315.660 | 60.009.217 | 0.703249 | 0.103157 | 0.703249 | 9.975879 | 8.654106 | 10.244858 |
9 | 1.000.000.000 | 701.992.637 | 90.912.540 | 611.080.097 | 0.701993 | 0.090913 | 0.701993 | 9.982138 | 8.813062 | 10.183105 |
10 | 10.000.000.000 | 7.010.059.102 | 812.747.885 | 6.197.311.217 | 0.701006 | 0.081275 | 0.701006 | 9.985944 | 8.939887 | 10.141568 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 7 | 7 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.400000 | 1.400000 | -nan |
4 | 16 | 13 | 13 | 0 | 0.812500 | 0.812500 | 0.000000 | 1.857143 | 1.857143 | -nan |
5 | 32 | 23 | 22 | 1 | 0.718750 | 0.687500 | 0.031250 | 1.769231 | 1.692308 | inf |
6 | 64 | 44 | 37 | 7 | 0.687500 | 0.578125 | 0.109375 | 1.913043 | 1.681818 | 7.000000 |
7 | 128 | 90 | 61 | 29 | 0.703125 | 0.476562 | 0.226562 | 2.045455 | 1.648649 | 4.142857 |
8 | 256 | 181 | 110 | 71 | 0.707031 | 0.429688 | 0.277344 | 2.011111 | 1.803279 | 2.448276 |
9 | 512 | 362 | 185 | 177 | 0.707031 | 0.361328 | 0.345703 | 2.000000 | 1.681818 | 2.492958 |
10 | 1.024 | 723 | 325 | 398 | 0.706055 | 0.317383 | 0.388672 | 1.997238 | 1.756757 | 2.248588 |
11 | 2.048 | 1.461 | 573 | 888 | 0.713379 | 0.279785 | 0.433594 | 2.020747 | 1.763077 | 2.231156 |
12 | 4.096 | 2.923 | 1.041 | 1.882 | 0.713623 | 0.254150 | 0.459473 | 2.000684 | 1.816754 | 2.119369 |
13 | 8.192 | 5.880 | 1.869 | 4.011 | 0.717773 | 0.228149 | 0.489624 | 2.011632 | 1.795389 | 2.131243 |
14 | 16.384 | 11.710 | 3.430 | 8.280 | 0.714722 | 0.209351 | 0.505371 | 1.991497 | 1.835206 | 2.064323 |
15 | 32.768 | 23.355 | 6.380 | 16.975 | 0.712738 | 0.194702 | 0.518036 | 1.994449 | 1.860058 | 2.050121 |
16 | 65.536 | 46.593 | 11.892 | 34.701 | 0.710953 | 0.181458 | 0.529495 | 1.994990 | 1.863950 | 2.044241 |
17 | 131.072 | 93.066 | 22.123 | 70.943 | 0.710037 | 0.168785 | 0.541252 | 1.997424 | 1.860326 | 2.044408 |
18 | 262.144 | 185.815 | 41.571 | 144.244 | 0.708828 | 0.158581 | 0.550247 | 1.996594 | 1.879085 | 2.033238 |
19 | 524.288 | 371.173 | 78.064 | 293.109 | 0.707956 | 0.148895 | 0.559061 | 1.997541 | 1.877848 | 2.032036 |
20 | 1.048.576 | 741.374 | 147.348 | 594.026 | 0.707029 | 0.140522 | 0.566507 | 1.997381 | 1.887528 | 2.026639 |
21 | 2.097.152 | 1.481.520 | 279.683 | 1.201.837 | 0.706444 | 0.133363 | 0.573081 | 1.998344 | 1.898112 | 2.023206 |
22 | 4.194.304 | 2.959.886 | 531.441 | 2.428.445 | 0.705692 | 0.126705 | 0.578986 | 1.997871 | 1.900155 | 2.020611 |
23 | 8.388.608 | 5.914.760 | 1.012.144 | 4.902.616 | 0.705094 | 0.120657 | 0.584437 | 1.998307 | 1.904528 | 2.018829 |
24 | 16.777.216 | 11.819.716 | 1.932.582 | 9.887.134 | 0.704510 | 0.115191 | 0.589319 | 1.998342 | 1.909394 | 2.016706 |
25 | 33.554.432 | 23.622.506 | 3.698.355 | 19.924.151 | 0.704006 | 0.110220 | 0.593786 | 1.998568 | 1.913686 | 2.015160 |
26 | 67.108.864 | 47.212.797 | 7.089.095 | 40.123.702 | 0.703525 | 0.105636 | 0.597890 | 1.998636 | 1.916824 | 2.013822 |
27 | 134.217.728 | 94.364.074 | 13.609.333 | 80.754.741 | 0.703067 | 0.101397 | 0.601670 | 1.998697 | 1.919756 | 2.012644 |
28 | 268.435.456 | 188.621.698 | 26.177.621 | 162.444.077 | 0.702671 | 0.097519 | 0.605151 | 1.998872 | 1.923505 | 2.011573 |
29 | 536.870.912 | 377.044.443 | 50.417.784 | 326.626.659 | 0.702300 | 0.093910 | 0.608390 | 1.998945 | 1.925988 | 2.010702 |
30 | 1.073.741.824 | 753.722.162 | 97.261.479 | 656.460.683 | 0.701958 | 0.090582 | 0.611377 | 1.999027 | 1.929111 | 2.009820 |
31 | 2.147.483.648 | 1.506.751.752 | 187.831.864 | 1.318.919.888 | 0.701636 | 0.087466 | 0.614170 | 1.999081 | 1.931205 | 2.009138 |
32 | 4.294.967.296 | 3.012.237.361 | 363.195.082 | 2.649.042.279 | 0.701341 | 0.084563 | 0.616778 | 1.999160 | 1.933618 | 2.008494 |
33 | 8.589.934.592 | 6.022.089.441 | 703.068.878 | 5.319.020.563 | 0.701063 | 0.081848 | 0.619215 | 1.999208 | 1.935789 | 2.007903 |
34 | 17.179.869.184 | 12.039.735.488 | 1.362.370.048 | 10.677.365.440 | 0.700805 | 0.079300 | 0.621504 | 1.999262 | 1.937748 | 2.007393 |
35 | 34.359.738.368 | 24.071.154.088 | 2.642.526.258 | 21.428.627.830 | 0.700563 | 0.076908 | 0.623655 | 1.999309 | 1.939654 | 2.006921 |
36 | 68.719.476.736 | 48.126.644.701 | 5.130.296.233 | 42.996.348.468 | 0.700335 | 0.074656 | 0.625679 | 1.999349 | 1.941436 | 2.006491 |
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 | 3 | 1 | 2 | 0 | 1 | 0 | 2 |
2 | 4 | 5 | 3 | 2 | 0 | 2 | 0 | 3 |
3 | 8 | 7 | 3 | 4 | 1 | 3 | 0 | 3 |
4 | 16 | 13 | 6 | 7 | 3 | 3 | 4 | 3 |
5 | 32 | 22 | 12 | 10 | 7 | 3 | 9 | 3 |
6 | 64 | 37 | 16 | 21 | 16 | 3 | 15 | 3 |
7 | 128 | 61 | 29 | 32 | 27 | 3 | 28 | 3 |
8 | 256 | 110 | 51 | 59 | 52 | 3 | 52 | 3 |
9 | 512 | 185 | 90 | 95 | 88 | 3 | 91 | 3 |
10 | 1.024 | 325 | 151 | 174 | 157 | 3 | 162 | 3 |
11 | 2.048 | 573 | 282 | 291 | 277 | 3 | 290 | 3 |
12 | 4.096 | 1.041 | 511 | 530 | 509 | 3 | 526 | 3 |
13 | 8.192 | 1.869 | 933 | 936 | 920 | 3 | 943 | 3 |
14 | 16.384 | 3.430 | 1.731 | 1.699 | 1.685 | 3 | 1.739 | 3 |
15 | 32.768 | 6.380 | 3.207 | 3.173 | 3.144 | 3 | 3.230 | 3 |
16 | 65.536 | 11.892 | 5.959 | 5.933 | 5.829 | 3 | 6.057 | 3 |
17 | 131.072 | 22.123 | 11.086 | 11.037 | 10.921 | 3 | 11.196 | 3 |
18 | 262.144 | 41.571 | 20.831 | 20.740 | 20.670 | 3 | 20.895 | 3 |
19 | 524.288 | 78.064 | 39.263 | 38.801 | 39.002 | 3 | 39.056 | 3 |
20 | 1.048.576 | 147.348 | 74.067 | 73.281 | 73.698 | 3 | 73.644 | 3 |
21 | 2.097.152 | 279.683 | 140.425 | 139.258 | 139.647 | 3 | 140.030 | 3 |
22 | 4.194.304 | 531.441 | 266.712 | 264.729 | 265.230 | 3 | 266.205 | 3 |
23 | 8.388.608 | 1.012.144 | 507.864 | 504.280 | 505.676 | 3 | 506.462 | 3 |
24 | 16.777.216 | 1.932.582 | 970.065 | 962.517 | 966.783 | 3 | 965.793 | 3 |
25 | 33.554.432 | 3.698.355 | 1.856.871 | 1.841.484 | 1.849.504 | 3 | 1.848.845 | 3 |
26 | 67.108.864 | 7.089.095 | 3.558.224 | 3.530.871 | 3.545.109 | 3 | 3.543.980 | 3 |
27 | 134.217.728 | 13.609.333 | 6.829.945 | 6.779.388 | 6.805.257 | 3 | 6.804.070 | 3 |
28 | 268.435.456 | 26.177.621 | 13.134.027 | 13.043.594 | 13.087.399 | 3 | 13.090.216 | 3 |
29 | 536.870.912 | 50.417.784 | 25.289.460 | 25.128.324 | 25.209.532 | 3 | 25.208.246 | 3 |
30 | 1.073.741.824 | 97.261.479 | 48.774.048 | 48.487.431 | 48.634.097 | 3 | 48.627.376 | 3 |
31 | 2.147.483.648 | 187.831.864 | 94.187.440 | 93.644.424 | 93.919.262 | 3 | 93.912.596 | 3 |
32 | 4.294.967.296 | 363.195.082 | 182.106.181 | 181.088.901 | 181.599.143 | 3 | 181.595.933 | 3 |
33 | 8.589.934.592 | 703.068.878 | 352.474.395 | 350.594.483 | 351.524.509 | 3 | 351.544.363 | 3 |
34 | 17.179.869.184 | 1.362.370.048 | 682.948.834 | 679.421.214 | 681.183.174 | 3 | 681.186.868 | 3 |
35 | 34.359.738.368 | 2.642.526.258 | 1.324.585.531 | 1.317.940.727 | 1.321.250.538 | 3 | 1.321.275.714 | 3 |
36 | 68.719.476.736 | 5.130.296.233 | 2.571.386.321 | 2.558.909.912 | 2.565.125.449 | 3 | 2.565.170.778 | 3 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
6 | 64 | 7 | 4 | 3 | 0 | 2 | 1 | 4 |
7 | 128 | 29 | 13 | 16 | 2 | 11 | 4 | 12 |
8 | 256 | 71 | 37 | 34 | 8 | 26 | 11 | 26 |
9 | 512 | 177 | 88 | 89 | 22 | 61 | 34 | 60 |
10 | 1.024 | 398 | 197 | 201 | 57 | 135 | 77 | 129 |
11 | 2.048 | 888 | 446 | 442 | 167 | 290 | 169 | 262 |
12 | 4.096 | 1.882 | 942 | 940 | 361 | 567 | 380 | 574 |
13 | 8.192 | 4.011 | 2.025 | 1.986 | 818 | 1.185 | 846 | 1.162 |
14 | 16.384 | 8.280 | 4.150 | 4.130 | 1.731 | 2.383 | 1.792 | 2.374 |
15 | 32.768 | 16.975 | 8.464 | 8.511 | 3.676 | 4.797 | 3.707 | 4.795 |
16 | 65.536 | 34.701 | 17.358 | 17.343 | 7.624 | 9.692 | 7.694 | 9.691 |
17 | 131.072 | 70.943 | 35.459 | 35.484 | 15.995 | 19.533 | 15.880 | 19.535 |
18 | 262.144 | 144.244 | 72.233 | 72.011 | 32.688 | 39.521 | 32.561 | 39.474 |
19 | 524.288 | 293.109 | 146.343 | 146.766 | 66.930 | 79.603 | 66.913 | 79.663 |
20 | 1.048.576 | 594.026 | 296.859 | 297.167 | 136.683 | 160.126 | 136.562 | 160.655 |
21 | 2.097.152 | 1.201.837 | 600.883 | 600.954 | 278.457 | 322.604 | 278.094 | 322.682 |
22 | 4.194.304 | 2.428.445 | 1.213.950 | 1.214.495 | 564.048 | 649.925 | 564.481 | 649.991 |
23 | 8.388.608 | 4.902.616 | 2.451.634 | 2.450.982 | 1.144.130 | 1.306.303 | 1.144.716 | 1.307.467 |
24 | 16.777.216 | 9.887.134 | 4.943.629 | 4.943.505 | 2.317.914 | 2.624.046 | 2.319.113 | 2.626.061 |
25 | 33.554.432 | 19.924.151 | 9.960.770 | 9.963.381 | 4.689.357 | 5.272.366 | 4.689.323 | 5.273.105 |
26 | 67.108.864 | 40.123.702 | 20.056.575 | 20.067.127 | 9.472.337 | 10.586.780 | 9.475.210 | 10.589.375 |
27 | 134.217.728 | 80.754.741 | 40.369.030 | 40.385.711 | 19.119.452 | 21.250.980 | 19.121.518 | 21.262.791 |
28 | 268.435.456 | 162.444.077 | 81.209.245 | 81.234.832 | 38.566.644 | 42.648.984 | 38.564.567 | 42.663.882 |
29 | 536.870.912 | 326.626.659 | 163.284.874 | 163.341.785 | 77.727.507 | 85.580.755 | 77.723.335 | 85.595.062 |
30 | 1.073.741.824 | 656.460.683 | 328.196.192 | 328.264.491 | 156.544.953 | 171.682.610 | 156.554.821 | 171.678.299 |
31 | 2.147.483.648 | 1.318.919.888 | 659.405.641 | 659.514.247 | 315.160.517 | 344.291.807 | 315.163.315 | 344.304.249 |
32 | 4.294.967.296 | 2.649.042.279 | 1.324.436.234 | 1.324.606.045 | 634.168.413 | 690.372.816 | 634.143.315 | 690.357.735 |
33 | 8.589.934.592 | 5.319.020.563 | 2.659.356.078 | 2.659.664.485 | 1.275.456.074 | 1.384.051.620 | 1.275.467.144 | 1.384.045.725 |
34 | 17.179.869.184 | 10.677.365.440 | 5.338.404.530 | 5.338.960.910 | 2.564.345.616 | 2.774.342.621 | 2.564.392.075 | 2.774.285.128 |
35 | 34.359.738.368 | 21.428.627.830 | 10.713.780.959 | 10.714.846.871 | 5.153.893.955 | 5.560.406.417 | 5.153.935.609 | 5.560.391.849 |
36 | 68.719.476.736 | 42.996.348.468 | 21.497.041.192 | 21.499.307.276 | 10.355.118.653 | 11.143.073.644 | 10.355.092.459 | 11.143.063.712 |