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+44x-103
f(0)=103
f(1)=29
f(2)=11
f(3)=19
f(4)=89
f(5)=71
f(6)=197
f(7)=127
f(8)=313
f(9)=17
f(10)=23
f(11)=251
f(12)=569
f(13)=1
f(14)=709
f(15)=1
f(16)=857
f(17)=467
f(18)=1013
f(19)=547
f(20)=107
f(21)=631
f(22)=1
f(23)=719
f(24)=139
f(25)=811
f(26)=101
f(27)=907
f(28)=1913
f(29)=53
f(30)=73
f(31)=1
f(32)=137
f(33)=1
f(34)=2549
f(35)=1
f(36)=2777
f(37)=1447
f(38)=131
f(39)=1567
f(40)=3257
f(41)=1
f(42)=1
f(43)=1
f(44)=3769
f(45)=1951
f(46)=367
f(47)=2087
f(48)=227
f(49)=1
f(50)=4597
f(51)=2371
f(52)=4889
f(53)=229
f(54)=5189
f(55)=2671
f(56)=239
f(57)=257
f(58)=5813
f(59)=1
f(60)=1
f(61)=1
f(62)=6469
f(63)=3319
f(64)=619
f(65)=3491
f(66)=421
f(67)=193
f(68)=683
f(69)=3847
f(70)=7877
f(71)=1
f(72)=113
f(73)=4219
f(74)=8629
f(75)=401
f(76)=1
f(77)=271
f(78)=9413
f(79)=1
f(80)=9817
f(81)=5011
f(82)=1
f(83)=307
f(84)=463
f(85)=5431
f(86)=1
f(87)=5647
f(88)=397
f(89)=5867
f(90)=1087
f(91)=6091
f(92)=12409
f(93)=1
f(94)=757
f(95)=6551
f(96)=13337
f(97)=617
f(98)=727
f(99)=7027
b) Substitution of the polynom
The polynom f(x)=x^2+44x-103 could be written as f(y)= y^2-587 with x=y-22
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+22
f'(x)>2x+43
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 | 9 | 1 | 1.000000 | 0.900000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 78 | 53 | 25 | 0.780000 | 0.530000 | 0.250000 | 7.800000 | 5.888889 | 25.000000 |
3 | 1.000 | 722 | 340 | 382 | 0.722000 | 0.340000 | 0.382000 | 9.256411 | 6.415094 | 15.280000 |
4 | 10.000 | 7.191 | 2.392 | 4.799 | 0.719100 | 0.239200 | 0.479900 | 9.959834 | 7.035294 | 12.562827 |
5 | 100.000 | 71.377 | 18.504 | 52.873 | 0.713770 | 0.185040 | 0.528730 | 9.925879 | 7.735786 | 11.017504 |
6 | 1.000.000 | 710.966 | 150.706 | 560.260 | 0.710966 | 0.150706 | 0.560260 | 9.960715 | 8.144509 | 10.596334 |
7 | 10.000.000 | 7.082.576 | 1.271.402 | 5.811.174 | 0.708258 | 0.127140 | 0.581117 | 9.961905 | 8.436306 | 10.372281 |
8 | 100.000.000 | 70.616.162 | 11.010.407 | 59.605.755 | 0.706162 | 0.110104 | 0.596058 | 9.970407 | 8.660051 | 10.257093 |
9 | 1.000.000.000 | 704.599.219 | 97.024.196 | 607.575.023 | 0.704599 | 0.097024 | 0.607575 | 9.977875 | 8.812044 | 10.193228 |
10 | 10.000.000.000 | 7.033.642.024 | 867.462.891 | 6.166.179.133 | 0.703364 | 0.086746 | 0.616618 | 9.982471 | 8.940687 | 10.148836 |
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 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 14 | 13 | 1 | 0.875000 | 0.812500 | 0.062500 | 1.555556 | 1.444444 | inf |
5 | 32 | 27 | 21 | 6 | 0.843750 | 0.656250 | 0.187500 | 1.928571 | 1.615385 | 6.000000 |
6 | 64 | 50 | 37 | 13 | 0.781250 | 0.578125 | 0.203125 | 1.851852 | 1.761905 | 2.166667 |
7 | 128 | 102 | 65 | 37 | 0.796875 | 0.507812 | 0.289062 | 2.040000 | 1.756757 | 2.846154 |
8 | 256 | 198 | 111 | 87 | 0.773438 | 0.433594 | 0.339844 | 1.941176 | 1.707692 | 2.351351 |
9 | 512 | 379 | 197 | 182 | 0.740234 | 0.384766 | 0.355469 | 1.914141 | 1.774775 | 2.091954 |
10 | 1.024 | 737 | 347 | 390 | 0.719727 | 0.338867 | 0.380859 | 1.944591 | 1.761421 | 2.142857 |
11 | 2.048 | 1.478 | 616 | 862 | 0.721680 | 0.300781 | 0.420898 | 2.005427 | 1.775216 | 2.210256 |
12 | 4.096 | 2.943 | 1.108 | 1.835 | 0.718506 | 0.270508 | 0.447998 | 1.991204 | 1.798701 | 2.128770 |
13 | 8.192 | 5.890 | 2.004 | 3.886 | 0.718994 | 0.244629 | 0.474365 | 2.001359 | 1.808664 | 2.117711 |
14 | 16.384 | 11.751 | 3.699 | 8.052 | 0.717224 | 0.225769 | 0.491455 | 1.995076 | 1.845808 | 2.072053 |
15 | 32.768 | 23.452 | 6.831 | 16.621 | 0.715698 | 0.208466 | 0.507233 | 1.995745 | 1.846715 | 2.064208 |
16 | 65.536 | 46.818 | 12.653 | 34.165 | 0.714386 | 0.193069 | 0.521317 | 1.996333 | 1.852291 | 2.055532 |
17 | 131.072 | 93.609 | 23.597 | 70.012 | 0.714180 | 0.180031 | 0.534149 | 1.999423 | 1.864933 | 2.049232 |
18 | 262.144 | 186.777 | 44.393 | 142.384 | 0.712498 | 0.169346 | 0.543152 | 1.995289 | 1.881298 | 2.033709 |
19 | 524.288 | 373.006 | 83.632 | 289.374 | 0.711452 | 0.159515 | 0.551937 | 1.997066 | 1.883901 | 2.032349 |
20 | 1.048.576 | 745.322 | 157.473 | 587.849 | 0.710794 | 0.150178 | 0.560616 | 1.998150 | 1.882928 | 2.031451 |
21 | 2.097.152 | 1.488.868 | 298.408 | 1.190.460 | 0.709948 | 0.142292 | 0.567656 | 1.997617 | 1.894979 | 2.025112 |
22 | 4.194.304 | 2.974.323 | 567.038 | 2.407.285 | 0.709134 | 0.135192 | 0.573941 | 1.997708 | 1.900210 | 2.022147 |
23 | 8.388.608 | 5.942.677 | 1.079.902 | 4.862.775 | 0.708422 | 0.128734 | 0.579688 | 1.997993 | 1.904461 | 2.020025 |
24 | 16.777.216 | 11.873.752 | 2.061.260 | 9.812.492 | 0.707731 | 0.122861 | 0.584870 | 1.998048 | 1.908747 | 2.017879 |
25 | 33.554.432 | 23.724.741 | 3.946.322 | 19.778.419 | 0.707052 | 0.117610 | 0.589443 | 1.998083 | 1.914519 | 2.015637 |
26 | 67.108.864 | 47.411.972 | 7.566.163 | 39.845.809 | 0.706493 | 0.112745 | 0.593749 | 1.998419 | 1.917270 | 2.014610 |
27 | 134.217.728 | 94.750.115 | 14.526.681 | 80.223.434 | 0.705943 | 0.108232 | 0.597711 | 1.998443 | 1.919953 | 2.013347 |
28 | 268.435.456 | 189.365.012 | 27.939.208 | 161.425.804 | 0.705440 | 0.104082 | 0.601358 | 1.998573 | 1.923303 | 2.012203 |
29 | 536.870.912 | 378.487.331 | 53.810.815 | 324.676.516 | 0.704988 | 0.100230 | 0.604757 | 1.998718 | 1.925996 | 2.011305 |
30 | 1.073.741.824 | 756.517.121 | 103.799.140 | 652.717.981 | 0.704561 | 0.096670 | 0.607891 | 1.998791 | 1.928964 | 2.010364 |
31 | 2.147.483.648 | 1.512.161.842 | 200.481.335 | 1.311.680.507 | 0.704155 | 0.093356 | 0.610799 | 1.998847 | 1.931435 | 2.009567 |
32 | 4.294.967.296 | 3.022.741.981 | 387.637.742 | 2.635.104.239 | 0.703787 | 0.090254 | 0.613533 | 1.998954 | 1.933535 | 2.008953 |
33 | 8.589.934.592 | 6.042.485.925 | 750.389.773 | 5.292.096.152 | 0.703438 | 0.087357 | 0.616081 | 1.999008 | 1.935802 | 2.008306 |
34 | 17.179.869.184 | 12.079.354.752 | 1.454.111.668 | 10.625.243.084 | 0.703111 | 0.084640 | 0.618471 | 1.999071 | 1.937808 | 2.007757 |
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 | 1 | 1 |
2 | 4 | 5 | 2 | 3 | 1 | 2 | 1 | 1 |
3 | 8 | 9 | 4 | 5 | 2 | 2 | 2 | 3 |
4 | 16 | 13 | 5 | 8 | 4 | 3 | 3 | 3 |
5 | 32 | 21 | 9 | 12 | 5 | 7 | 4 | 5 |
6 | 64 | 37 | 18 | 19 | 9 | 8 | 9 | 11 |
7 | 128 | 65 | 34 | 31 | 15 | 17 | 17 | 16 |
8 | 256 | 111 | 51 | 60 | 26 | 27 | 28 | 30 |
9 | 512 | 197 | 100 | 97 | 44 | 50 | 50 | 53 |
10 | 1.024 | 347 | 177 | 170 | 81 | 82 | 87 | 97 |
11 | 2.048 | 616 | 314 | 302 | 147 | 159 | 150 | 160 |
12 | 4.096 | 1.108 | 553 | 555 | 273 | 292 | 261 | 282 |
13 | 8.192 | 2.004 | 1.001 | 1.003 | 491 | 525 | 476 | 512 |
14 | 16.384 | 3.699 | 1.858 | 1.841 | 911 | 962 | 883 | 943 |
15 | 32.768 | 6.831 | 3.451 | 3.380 | 1.689 | 1.743 | 1.645 | 1.754 |
16 | 65.536 | 12.653 | 6.340 | 6.313 | 3.114 | 3.212 | 3.093 | 3.234 |
17 | 131.072 | 23.597 | 11.841 | 11.756 | 5.825 | 5.994 | 5.807 | 5.971 |
18 | 262.144 | 44.393 | 22.264 | 22.129 | 10.997 | 11.295 | 10.884 | 11.217 |
19 | 524.288 | 83.632 | 41.951 | 41.681 | 20.712 | 21.206 | 20.508 | 21.206 |
20 | 1.048.576 | 157.473 | 79.093 | 78.380 | 38.940 | 39.940 | 38.692 | 39.901 |
21 | 2.097.152 | 298.408 | 149.680 | 148.728 | 73.883 | 75.545 | 73.362 | 75.618 |
22 | 4.194.304 | 567.038 | 284.542 | 282.496 | 140.235 | 143.622 | 139.772 | 143.409 |
23 | 8.388.608 | 1.079.902 | 541.856 | 538.046 | 267.155 | 273.000 | 266.360 | 273.387 |
24 | 16.777.216 | 2.061.260 | 1.034.095 | 1.027.165 | 509.975 | 520.790 | 509.553 | 520.942 |
25 | 33.554.432 | 3.946.322 | 1.980.089 | 1.966.233 | 976.561 | 996.925 | 976.004 | 996.832 |
26 | 67.108.864 | 7.566.163 | 3.795.879 | 3.770.284 | 1.872.334 | 1.911.456 | 1.870.886 | 1.911.487 |
27 | 134.217.728 | 14.526.681 | 7.288.778 | 7.237.903 | 3.597.667 | 3.668.787 | 3.592.713 | 3.667.514 |
28 | 268.435.456 | 27.939.208 | 14.015.477 | 13.923.731 | 6.919.290 | 7.051.867 | 6.916.815 | 7.051.236 |
29 | 536.870.912 | 53.810.815 | 26.990.534 | 26.820.281 | 13.330.677 | 13.576.032 | 13.327.287 | 13.576.819 |
30 | 1.073.741.824 | 103.799.140 | 52.055.090 | 51.744.050 | 25.718.709 | 26.181.601 | 25.720.257 | 26.178.573 |
31 | 2.147.483.648 | 200.481.335 | 100.527.685 | 99.953.650 | 49.687.743 | 50.551.988 | 49.697.015 | 50.544.589 |
32 | 4.294.967.296 | 387.637.742 | 194.353.386 | 193.284.356 | 96.108.191 | 97.716.301 | 96.112.032 | 97.701.218 |
33 | 8.589.934.592 | 750.389.773 | 376.193.300 | 374.196.473 | 186.089.850 | 189.101.932 | 186.107.712 | 189.090.279 |
34 | 17.179.869.184 | 1.454.111.668 | 728.939.151 | 725.172.517 | 360.704.167 | 366.352.345 | 360.707.447 | 366.347.709 |
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 | 0 | 1 | 0 | 0 | 0 | 1 |
5 | 32 | 6 | 2 | 4 | 2 | 2 | 1 | 1 |
6 | 64 | 13 | 5 | 8 | 3 | 5 | 2 | 3 |
7 | 128 | 37 | 22 | 15 | 10 | 11 | 8 | 8 |
8 | 256 | 87 | 40 | 47 | 19 | 19 | 28 | 21 |
9 | 512 | 182 | 89 | 93 | 41 | 46 | 47 | 48 |
10 | 1.024 | 390 | 191 | 199 | 89 | 102 | 108 | 91 |
11 | 2.048 | 862 | 422 | 440 | 208 | 217 | 215 | 222 |
12 | 4.096 | 1.835 | 907 | 928 | 448 | 472 | 444 | 471 |
13 | 8.192 | 3.886 | 1.915 | 1.971 | 965 | 988 | 968 | 965 |
14 | 16.384 | 8.052 | 4.053 | 3.999 | 2.002 | 2.008 | 1.996 | 2.046 |
15 | 32.768 | 16.621 | 8.304 | 8.317 | 4.140 | 4.154 | 4.147 | 4.180 |
16 | 65.536 | 34.165 | 17.077 | 17.088 | 8.554 | 8.533 | 8.549 | 8.529 |
17 | 131.072 | 70.012 | 34.929 | 35.083 | 17.622 | 17.363 | 17.466 | 17.561 |
18 | 262.144 | 142.384 | 71.104 | 71.280 | 35.808 | 35.491 | 35.475 | 35.610 |
19 | 524.288 | 289.374 | 144.653 | 144.721 | 72.597 | 72.221 | 72.108 | 72.448 |
20 | 1.048.576 | 587.849 | 293.667 | 294.182 | 147.327 | 146.908 | 146.696 | 146.918 |
21 | 2.097.152 | 1.190.460 | 595.576 | 594.884 | 297.894 | 297.528 | 297.674 | 297.364 |
22 | 4.194.304 | 2.407.285 | 1.202.421 | 1.204.864 | 602.209 | 601.462 | 602.155 | 601.459 |
23 | 8.388.608 | 4.862.775 | 2.430.530 | 2.432.245 | 1.215.890 | 1.215.303 | 1.216.340 | 1.215.242 |
24 | 16.777.216 | 9.812.492 | 4.903.481 | 4.909.011 | 2.454.290 | 2.452.638 | 2.453.137 | 2.452.427 |
25 | 33.554.432 | 19.778.419 | 9.884.762 | 9.893.657 | 4.944.395 | 4.943.840 | 4.947.487 | 4.942.697 |
26 | 67.108.864 | 39.845.809 | 19.916.489 | 19.929.320 | 9.960.864 | 9.958.551 | 9.966.894 | 9.959.500 |
27 | 134.217.728 | 80.223.434 | 40.095.005 | 40.128.429 | 20.055.708 | 20.050.408 | 20.063.467 | 20.053.851 |
28 | 268.435.456 | 161.425.804 | 80.686.050 | 80.739.754 | 40.359.767 | 40.346.219 | 40.362.316 | 40.357.502 |
29 | 536.870.912 | 324.676.516 | 162.292.935 | 162.383.581 | 81.181.485 | 81.154.847 | 81.177.398 | 81.162.786 |
30 | 1.073.741.824 | 652.717.981 | 326.278.667 | 326.439.314 | 163.203.232 | 163.151.709 | 163.207.643 | 163.155.397 |
31 | 2.147.483.648 | 1.311.680.507 | 655.707.140 | 655.973.367 | 327.980.186 | 327.850.267 | 327.986.035 | 327.864.019 |
32 | 4.294.967.296 | 2.635.104.239 | 1.317.296.533 | 1.317.807.706 | 658.900.470 | 658.661.982 | 658.903.273 | 658.638.514 |
33 | 8.589.934.592 | 5.292.096.152 | 2.645.571.944 | 2.646.524.208 | 1.323.246.602 | 1.322.797.966 | 1.323.292.946 | 1.322.758.638 |
34 | 17.179.869.184 | 10.625.243.084 | 5.311.782.368 | 5.313.460.716 | 2.656.710.312 | 2.655.915.745 | 2.656.789.235 | 2.655.827.792 |