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+49x-3
f(0)=3
f(1)=47
f(2)=11
f(3)=17
f(4)=19
f(5)=89
f(6)=109
f(7)=389
f(8)=151
f(9)=173
f(10)=587
f(11)=73
f(12)=1
f(13)=1
f(14)=293
f(15)=29
f(16)=61
f(17)=373
f(18)=401
f(19)=1289
f(20)=1
f(21)=163
f(22)=1559
f(23)=1
f(24)=53
f(25)=1847
f(26)=59
f(27)=683
f(28)=2153
f(29)=251
f(30)=263
f(31)=2477
f(32)=863
f(33)=1
f(34)=2819
f(35)=1
f(36)=1019
f(37)=1
f(38)=367
f(39)=127
f(40)=3557
f(41)=1229
f(42)=67
f(43)=1
f(44)=1
f(45)=1409
f(46)=397
f(47)=167
f(48)=1
f(49)=4799
f(50)=97
f(51)=1699
f(52)=181
f(53)=1801
f(54)=1
f(55)=5717
f(56)=653
f(57)=1
f(58)=6203
f(59)=193
f(60)=2179
f(61)=353
f(62)=2293
f(63)=2351
f(64)=7229
f(65)=823
f(66)=281
f(67)=457
f(68)=241
f(69)=2713
f(70)=757
f(71)=1
f(72)=2903
f(73)=307
f(74)=337
f(75)=1033
f(76)=9497
f(77)=1
f(78)=3301
f(79)=919
f(80)=1
f(81)=1
f(82)=10739
f(83)=1217
f(84)=1
f(85)=1
f(86)=1
f(87)=3943
f(88)=709
f(89)=4093
f(90)=379
f(91)=271
f(92)=131
f(93)=1
f(94)=1
f(95)=1
f(96)=4639
f(97)=14159
f(98)=4801
f(99)=257
b) Substitution of the polynom
The polynom f(x)=x^2+49x-3 could be written as f(y)= y^2-603.25 with x=y-24.5
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+24.5
f'(x)>2x+48
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 | 11 | 5 | 6 | 1.100000 | 0.500000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 75 | 21 | 54 | 0.750000 | 0.210000 | 0.750000 | 6.818182 | 4.200000 | 9.000000 |
3 | 1.000 | 681 | 117 | 564 | 0.681000 | 0.117000 | 0.681000 | 9.080000 | 5.571429 | 10.444445 |
4 | 10.000 | 6.872 | 846 | 6.026 | 0.687200 | 0.084600 | 0.687200 | 10.091043 | 7.230769 | 10.684397 |
5 | 100.000 | 68.930 | 6.582 | 62.348 | 0.689300 | 0.065820 | 0.689300 | 10.030559 | 7.780142 | 10.346498 |
6 | 1.000.000 | 690.209 | 53.175 | 637.034 | 0.690209 | 0.053175 | 0.690209 | 10.013187 | 8.078852 | 10.217393 |
7 | 10.000.000 | 6.903.779 | 448.499 | 6.455.280 | 0.690378 | 0.044850 | 0.690378 | 10.002447 | 8.434396 | 10.133337 |
8 | 100.000.000 | 69.056.426 | 3.886.909 | 65.169.517 | 0.690564 | 0.038869 | 0.690564 | 10.002699 | 8.666483 | 10.095536 |
9 | 1.000.000.000 | 690.775.685 | 34.288.468 | 656.487.217 | 0.690776 | 0.034288 | 0.690776 | 10.003062 | 8.821526 | 10.073532 |
10 | 10.000.000.000 | 6.909.513.439 | 306.887.996 | 6.602.625.443 | 0.690951 | 0.030689 | 0.690951 | 10.002542 | 8.950181 | 10.057508 |
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 | 5 | 9 | 0.875000 | 0.312500 | 0.562500 | 1.555556 | 1.250000 | 1.800000 |
5 | 32 | 28 | 10 | 18 | 0.875000 | 0.312500 | 0.562500 | 2.000000 | 2.000000 | 2.000000 |
6 | 64 | 50 | 17 | 33 | 0.781250 | 0.265625 | 0.515625 | 1.785714 | 1.700000 | 1.833333 |
7 | 128 | 94 | 23 | 71 | 0.734375 | 0.179688 | 0.554688 | 1.880000 | 1.352941 | 2.151515 |
8 | 256 | 177 | 37 | 140 | 0.691406 | 0.144531 | 0.546875 | 1.882979 | 1.608696 | 1.971831 |
9 | 512 | 353 | 71 | 282 | 0.689453 | 0.138672 | 0.550781 | 1.994350 | 1.918919 | 2.014286 |
10 | 1.024 | 699 | 120 | 579 | 0.682617 | 0.117188 | 0.565430 | 1.980170 | 1.690141 | 2.053191 |
11 | 2.048 | 1.402 | 219 | 1.183 | 0.684570 | 0.106934 | 0.577637 | 2.005723 | 1.825000 | 2.043178 |
12 | 4.096 | 2.795 | 403 | 2.392 | 0.682373 | 0.098389 | 0.583984 | 1.993581 | 1.840183 | 2.021978 |
13 | 8.192 | 5.617 | 720 | 4.897 | 0.685669 | 0.087891 | 0.597778 | 2.009660 | 1.786600 | 2.047241 |
14 | 16.384 | 11.287 | 1.300 | 9.987 | 0.688904 | 0.079346 | 0.609558 | 2.009436 | 1.805556 | 2.039412 |
15 | 32.768 | 22.521 | 2.427 | 20.094 | 0.687286 | 0.074066 | 0.613220 | 1.995304 | 1.866923 | 2.012016 |
16 | 65.536 | 45.170 | 4.477 | 40.693 | 0.689240 | 0.068314 | 0.620926 | 2.005684 | 1.844664 | 2.025132 |
17 | 131.072 | 90.339 | 8.421 | 81.918 | 0.689232 | 0.064247 | 0.624985 | 1.999978 | 1.880947 | 2.013073 |
18 | 262.144 | 180.822 | 15.722 | 165.100 | 0.689781 | 0.059975 | 0.629807 | 2.001594 | 1.866999 | 2.015430 |
19 | 524.288 | 361.730 | 29.533 | 332.197 | 0.689945 | 0.056330 | 0.633615 | 2.000476 | 1.878451 | 2.012096 |
20 | 1.048.576 | 723.663 | 55.507 | 668.156 | 0.690139 | 0.052936 | 0.637203 | 2.000561 | 1.879491 | 2.011325 |
21 | 2.097.152 | 1.447.414 | 105.228 | 1.342.186 | 0.690181 | 0.050177 | 0.640004 | 2.000122 | 1.895761 | 2.008791 |
22 | 4.194.304 | 2.894.817 | 199.974 | 2.694.843 | 0.690178 | 0.047678 | 0.642501 | 1.999992 | 1.900388 | 2.007802 |
23 | 8.388.608 | 5.791.217 | 380.874 | 5.410.343 | 0.690367 | 0.045404 | 0.644963 | 2.000547 | 1.904618 | 2.007665 |
24 | 16.777.216 | 11.582.579 | 727.615 | 10.854.964 | 0.690376 | 0.043369 | 0.647006 | 2.000025 | 1.910382 | 2.006336 |
25 | 33.554.432 | 23.166.971 | 1.392.092 | 21.774.879 | 0.690430 | 0.041488 | 0.648942 | 2.000157 | 1.913226 | 2.005984 |
26 | 67.108.864 | 46.339.163 | 2.670.145 | 43.669.018 | 0.690507 | 0.039788 | 0.650719 | 2.000225 | 1.918081 | 2.005477 |
27 | 134.217.728 | 92.690.174 | 5.129.678 | 87.560.496 | 0.690596 | 0.038219 | 0.652377 | 2.000256 | 1.921123 | 2.005094 |
28 | 268.435.456 | 185.397.164 | 9.869.251 | 175.527.913 | 0.690658 | 0.036766 | 0.653892 | 2.000181 | 1.923951 | 2.004647 |
29 | 536.870.912 | 370.830.852 | 19.015.221 | 351.815.631 | 0.690726 | 0.035419 | 0.655308 | 2.000197 | 1.926714 | 2.004328 |
30 | 1.073.741.824 | 741.720.641 | 36.683.121 | 705.037.520 | 0.690781 | 0.034164 | 0.656617 | 2.000159 | 1.929145 | 2.003997 |
31 | 2.147.483.648 | 1.483.560.149 | 70.880.047 | 1.412.680.102 | 0.690837 | 0.033006 | 0.657830 | 2.000160 | 1.932225 | 2.003695 |
32 | 4.294.967.296 | 2.967.360.727 | 137.099.514 | 2.830.261.213 | 0.690893 | 0.031921 | 0.658972 | 2.000162 | 1.934247 | 2.003469 |
33 | 8.589.934.592 | 5.935.145.048 | 265.458.881 | 5.669.686.167 | 0.690942 | 0.030903 | 0.660038 | 2.000143 | 1.936249 | 2.003238 |
34 | 17.179.869.184 | 11.871.087.965 | 514.517.237 | 11.356.570.728 | 0.690988 | 0.029949 | 0.661039 | 2.000134 | 1.938218 | 2.003033 |
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 | 1 | 0 | 1 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 0 | 1 |
3 | 8 | 4 | 0 | 3 | 1 | 1 | 1 | 1 |
4 | 16 | 5 | 0 | 4 | 1 | 2 | 1 | 1 |
5 | 32 | 10 | 0 | 9 | 3 | 2 | 2 | 3 |
6 | 64 | 17 | 0 | 15 | 3 | 4 | 6 | 4 |
7 | 128 | 23 | 0 | 21 | 5 | 6 | 7 | 5 |
8 | 256 | 37 | 0 | 35 | 8 | 13 | 9 | 7 |
9 | 512 | 71 | 0 | 69 | 18 | 19 | 16 | 18 |
10 | 1.024 | 120 | 0 | 118 | 30 | 31 | 28 | 31 |
11 | 2.048 | 219 | 0 | 217 | 62 | 55 | 49 | 53 |
12 | 4.096 | 403 | 0 | 401 | 106 | 102 | 94 | 101 |
13 | 8.192 | 720 | 0 | 718 | 182 | 181 | 181 | 176 |
14 | 16.384 | 1.300 | 0 | 1.298 | 323 | 337 | 329 | 311 |
15 | 32.768 | 2.427 | 0 | 2.425 | 602 | 615 | 616 | 594 |
16 | 65.536 | 4.477 | 0 | 4.475 | 1.131 | 1.129 | 1.127 | 1.090 |
17 | 131.072 | 8.421 | 0 | 8.419 | 2.140 | 2.126 | 2.119 | 2.036 |
18 | 262.144 | 15.722 | 0 | 15.720 | 4.008 | 3.945 | 3.944 | 3.825 |
19 | 524.288 | 29.533 | 0 | 29.531 | 7.467 | 7.457 | 7.352 | 7.257 |
20 | 1.048.576 | 55.507 | 0 | 55.505 | 13.931 | 13.931 | 13.845 | 13.800 |
21 | 2.097.152 | 105.228 | 0 | 105.226 | 26.330 | 26.380 | 26.246 | 26.272 |
22 | 4.194.304 | 199.974 | 0 | 199.972 | 49.872 | 49.991 | 50.099 | 50.012 |
23 | 8.388.608 | 380.874 | 0 | 380.872 | 95.114 | 95.083 | 95.191 | 95.486 |
24 | 16.777.216 | 727.615 | 0 | 727.613 | 181.581 | 182.142 | 181.914 | 181.978 |
25 | 33.554.432 | 1.392.092 | 0 | 1.392.090 | 347.604 | 348.307 | 348.064 | 348.117 |
26 | 67.108.864 | 2.670.145 | 0 | 2.670.143 | 667.543 | 667.366 | 667.321 | 667.915 |
27 | 134.217.728 | 5.129.678 | 0 | 5.129.676 | 1.282.787 | 1.282.022 | 1.282.088 | 1.282.781 |
28 | 268.435.456 | 9.869.251 | 0 | 9.869.249 | 2.466.959 | 2.466.598 | 2.467.236 | 2.468.458 |
29 | 536.870.912 | 19.015.221 | 0 | 19.015.219 | 4.754.498 | 4.753.041 | 4.752.731 | 4.754.951 |
30 | 1.073.741.824 | 36.683.121 | 0 | 36.683.119 | 9.168.480 | 9.173.577 | 9.169.383 | 9.171.681 |
31 | 2.147.483.648 | 70.880.047 | 0 | 70.880.045 | 17.718.495 | 17.720.815 | 17.717.594 | 17.723.143 |
32 | 4.294.967.296 | 137.099.514 | 0 | 137.099.512 | 34.267.239 | 34.275.573 | 34.275.951 | 34.280.751 |
33 | 8.589.934.592 | 265.458.881 | 0 | 265.458.879 | 66.354.626 | 66.364.984 | 66.367.240 | 66.372.031 |
34 | 17.179.869.184 | 514.517.237 | 0 | 514.517.235 | 128.617.841 | 128.633.810 | 128.630.478 | 128.635.108 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 2 | 1 | 1 | 0 | 0 |
3 | 8 | 5 | 2 | 3 | 2 | 1 | 1 | 1 |
4 | 16 | 9 | 4 | 5 | 3 | 1 | 4 | 1 |
5 | 32 | 18 | 6 | 12 | 4 | 5 | 6 | 3 |
6 | 64 | 33 | 14 | 19 | 8 | 8 | 11 | 6 |
7 | 128 | 71 | 37 | 34 | 20 | 15 | 20 | 16 |
8 | 256 | 140 | 76 | 64 | 38 | 32 | 32 | 38 |
9 | 512 | 282 | 160 | 122 | 67 | 66 | 74 | 75 |
10 | 1.024 | 579 | 307 | 272 | 152 | 136 | 141 | 150 |
11 | 2.048 | 1.183 | 617 | 566 | 306 | 276 | 292 | 309 |
12 | 4.096 | 2.392 | 1.249 | 1.143 | 609 | 573 | 591 | 619 |
13 | 8.192 | 4.897 | 2.548 | 2.349 | 1.236 | 1.216 | 1.217 | 1.228 |
14 | 16.384 | 9.987 | 5.182 | 4.805 | 2.534 | 2.480 | 2.480 | 2.493 |
15 | 32.768 | 20.094 | 10.334 | 9.760 | 5.009 | 5.046 | 5.079 | 4.960 |
16 | 65.536 | 40.693 | 21.062 | 19.631 | 10.162 | 10.168 | 10.252 | 10.111 |
17 | 131.072 | 81.918 | 42.292 | 39.626 | 20.443 | 20.501 | 20.468 | 20.506 |
18 | 262.144 | 165.100 | 85.070 | 80.030 | 41.157 | 41.220 | 41.197 | 41.526 |
19 | 524.288 | 332.197 | 170.800 | 161.397 | 82.721 | 82.992 | 83.134 | 83.350 |
20 | 1.048.576 | 668.156 | 342.819 | 325.337 | 166.709 | 167.074 | 167.086 | 167.287 |
21 | 2.097.152 | 1.342.186 | 687.290 | 654.896 | 335.281 | 335.651 | 335.221 | 336.033 |
22 | 4.194.304 | 2.694.843 | 1.378.552 | 1.316.291 | 672.810 | 673.993 | 673.851 | 674.189 |
23 | 8.388.608 | 5.410.343 | 2.765.056 | 2.645.287 | 1.352.689 | 1.352.535 | 1.352.567 | 1.352.552 |
24 | 16.777.216 | 10.854.964 | 5.539.719 | 5.315.245 | 2.715.393 | 2.712.989 | 2.712.733 | 2.713.849 |
25 | 33.554.432 | 21.774.879 | 11.100.708 | 10.674.171 | 5.443.724 | 5.445.255 | 5.443.279 | 5.442.621 |
26 | 67.108.864 | 43.669.018 | 22.241.648 | 21.427.370 | 10.918.100 | 10.916.968 | 10.915.838 | 10.918.112 |
27 | 134.217.728 | 87.560.496 | 44.567.457 | 42.993.039 | 21.894.436 | 21.885.637 | 21.890.367 | 21.890.056 |
28 | 268.435.456 | 175.527.913 | 89.277.984 | 86.249.929 | 43.887.513 | 43.869.838 | 43.883.895 | 43.886.667 |
29 | 536.870.912 | 351.815.631 | 178.813.363 | 173.002.268 | 87.961.340 | 87.942.248 | 87.949.960 | 87.962.083 |
30 | 1.073.741.824 | 705.037.520 | 358.116.643 | 346.920.877 | 176.271.132 | 176.237.464 | 176.253.724 | 176.275.200 |
31 | 2.147.483.648 | 1.412.680.102 | 717.160.909 | 695.519.193 | 353.174.401 | 353.140.745 | 353.191.898 | 353.173.058 |
32 | 4.294.967.296 | 2.830.261.213 | 1.436.023.429 | 1.394.237.784 | 707.573.920 | 707.542.948 | 707.573.758 | 707.570.587 |
33 | 8.589.934.592 | 5.669.686.167 | 2.875.249.551 | 2.794.436.616 | 1.417.403.905 | 1.417.407.842 | 1.417.435.359 | 1.417.439.061 |
34 | 17.179.869.184 | 11.356.570.728 | 5.756.539.609 | 5.600.031.119 | 2.839.065.805 | 2.839.119.754 | 2.839.162.144 | 2.839.223.025 |