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-140x-3
f(0)=3
f(1)=71
f(2)=31
f(3)=23
f(4)=547
f(5)=113
f(6)=269
f(7)=467
f(8)=353
f(9)=197
f(10)=1303
f(11)=79
f(12)=19
f(13)=827
f(14)=1
f(15)=313
f(16)=1987
f(17)=349
f(18)=733
f(19)=1151
f(20)=89
f(21)=139
f(22)=1
f(23)=449
f(24)=929
f(25)=1439
f(26)=43
f(27)=509
f(28)=73
f(29)=179
f(30)=367
f(31)=1
f(32)=1153
f(33)=1
f(34)=3607
f(35)=613
f(36)=1249
f(37)=1907
f(38)=431
f(39)=1
f(40)=4003
f(41)=677
f(42)=1373
f(43)=2087
f(44)=1409
f(45)=1
f(46)=4327
f(47)=1
f(48)=491
f(49)=97
f(50)=1
f(51)=757
f(52)=241
f(53)=769
f(54)=1549
f(55)=2339
f(56)=523
f(57)=263
f(58)=4759
f(59)=797
f(60)=1601
f(61)=2411
f(62)=1613
f(63)=809
f(64)=157
f(65)=271
f(66)=181
f(67)=2447
f(68)=1
f(69)=1
f(70)=4903
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-140x-3 could be written as f(y)= y^2-4903 with x=y+70
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-70
f'(x)>2x-141 with x > 70
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 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 19 | 39 | 0.580000 | 0.190000 | 0.390000 | 5.272727 | 3.800000 | 6.500000 |
3 | 1.000 | 662 | 154 | 508 | 0.662000 | 0.154000 | 0.508000 | 11.413794 | 8.105263 | 13.025641 |
4 | 10.000 | 7.101 | 1.108 | 5.993 | 0.710100 | 0.110800 | 0.599300 | 10.726586 | 7.194805 | 11.797244 |
5 | 100.000 | 71.130 | 8.962 | 62.168 | 0.711300 | 0.089620 | 0.621680 | 10.016899 | 8.088448 | 10.373436 |
6 | 1.000.000 | 708.609 | 72.353 | 636.256 | 0.708609 | 0.072353 | 0.636256 | 9.962168 | 8.073310 | 10.234462 |
7 | 10.000.000 | 7.061.189 | 612.778 | 6.448.411 | 0.706119 | 0.061278 | 0.644841 | 9.964859 | 8.469282 | 10.134932 |
8 | 100.000.000 | 70.423.289 | 5.306.987 | 65.116.302 | 0.704233 | 0.053070 | 0.651163 | 9.973290 | 8.660538 | 10.098039 |
9 | 1.000.000.000 | 702.867.949 | 46.768.012 | 656.099.937 | 0.702868 | 0.046768 | 0.656100 | 9.980618 | 8.812535 | 10.075817 |
10 | 10.000.000.000 | 7.017.664.883 | 418.105.376 | 6.599.559.507 | 0.701766 | 0.041811 | 0.659956 | 9.984329 | 8.939986 | 10.058771 |
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 | 15 | 7 | 8 | 0.937500 | 0.437500 | 0.500000 | 1.666667 | 1.750000 | 1.600000 |
5 | 32 | 28 | 9 | 19 | 0.875000 | 0.281250 | 0.593750 | 1.866667 | 1.285714 | 2.375000 |
6 | 64 | 54 | 17 | 37 | 0.843750 | 0.265625 | 0.578125 | 1.928571 | 1.888889 | 1.947368 |
7 | 128 | 58 | 19 | 39 | 0.453125 | 0.148438 | 0.304688 | 1.074074 | 1.117647 | 1.054054 |
8 | 256 | 129 | 42 | 87 | 0.503906 | 0.164062 | 0.339844 | 2.224138 | 2.210526 | 2.230769 |
9 | 512 | 317 | 83 | 234 | 0.619141 | 0.162109 | 0.457031 | 2.457364 | 1.976190 | 2.689655 |
10 | 1.024 | 680 | 158 | 522 | 0.664062 | 0.154297 | 0.509766 | 2.145110 | 1.903614 | 2.230769 |
11 | 2.048 | 1.410 | 294 | 1.116 | 0.688477 | 0.143555 | 0.544922 | 2.073529 | 1.860759 | 2.137931 |
12 | 4.096 | 2.862 | 526 | 2.336 | 0.698730 | 0.128418 | 0.570312 | 2.029787 | 1.789116 | 2.093190 |
13 | 8.192 | 5.820 | 944 | 4.876 | 0.710449 | 0.115234 | 0.595215 | 2.033543 | 1.794677 | 2.087329 |
14 | 16.384 | 11.647 | 1.751 | 9.896 | 0.710876 | 0.106873 | 0.604004 | 2.001203 | 1.854873 | 2.029532 |
15 | 32.768 | 23.312 | 3.251 | 20.061 | 0.711426 | 0.099213 | 0.612213 | 2.001545 | 1.856653 | 2.027183 |
16 | 65.536 | 46.670 | 6.152 | 40.518 | 0.712128 | 0.093872 | 0.618256 | 2.001973 | 1.892341 | 2.019740 |
17 | 131.072 | 93.172 | 11.445 | 81.727 | 0.710846 | 0.087318 | 0.623528 | 1.996400 | 1.860371 | 2.017054 |
18 | 262.144 | 186.084 | 21.380 | 164.704 | 0.709854 | 0.081558 | 0.628296 | 1.997209 | 1.868065 | 2.015295 |
19 | 524.288 | 371.926 | 40.061 | 331.865 | 0.709393 | 0.076410 | 0.632982 | 1.998700 | 1.873761 | 2.014918 |
20 | 1.048.576 | 742.926 | 75.532 | 667.394 | 0.708509 | 0.072033 | 0.636477 | 1.997510 | 1.885425 | 2.011041 |
21 | 2.097.152 | 1.484.079 | 143.570 | 1.340.509 | 0.707664 | 0.068460 | 0.639205 | 1.997614 | 1.900784 | 2.008572 |
22 | 4.194.304 | 2.965.301 | 272.936 | 2.692.365 | 0.706983 | 0.065073 | 0.641910 | 1.998075 | 1.901066 | 2.008465 |
23 | 8.388.608 | 5.924.332 | 520.727 | 5.403.605 | 0.706235 | 0.062075 | 0.644160 | 1.997886 | 1.907872 | 2.007010 |
24 | 16.777.216 | 11.838.997 | 994.175 | 10.844.822 | 0.705659 | 0.059257 | 0.646402 | 1.998368 | 1.909206 | 2.006961 |
25 | 33.554.432 | 23.657.202 | 1.902.513 | 21.754.689 | 0.705040 | 0.056699 | 0.648340 | 1.998244 | 1.913660 | 2.005998 |
26 | 67.108.864 | 47.279.231 | 3.646.158 | 43.633.073 | 0.704515 | 0.054332 | 0.650183 | 1.998513 | 1.916496 | 2.005686 |
27 | 134.217.728 | 94.497.006 | 7.003.141 | 87.493.865 | 0.704058 | 0.052177 | 0.651880 | 1.998700 | 1.920691 | 2.005219 |
28 | 268.435.456 | 188.876.725 | 13.468.792 | 175.407.933 | 0.703621 | 0.050175 | 0.653445 | 1.998759 | 1.923250 | 2.004803 |
29 | 536.870.912 | 377.533.694 | 25.940.182 | 351.593.512 | 0.703211 | 0.048317 | 0.654894 | 1.998837 | 1.925947 | 2.004433 |
30 | 1.073.741.824 | 754.658.904 | 50.032.043 | 704.626.861 | 0.702831 | 0.046596 | 0.656235 | 1.998918 | 1.928747 | 2.004095 |
31 | 2.147.483.648 | 1.508.559.377 | 96.629.216 | 1.411.930.161 | 0.702478 | 0.044996 | 0.657481 | 1.998995 | 1.931347 | 2.003798 |
32 | 4.294.967.296 | 3.015.669.283 | 186.843.704 | 2.828.825.579 | 0.702140 | 0.043503 | 0.658637 | 1.999039 | 1.933615 | 2.003517 |
33 | 8.589.934.592 | 6.028.689.809 | 361.677.437 | 5.667.012.372 | 0.701832 | 0.042105 | 0.659727 | 1.999122 | 1.935722 | 2.003309 |
34 | 17.179.869.184 | 12.052.423.733 | 700.842.127 | 11.351.581.606 | 0.701543 | 0.040794 | 0.660749 | 1.999178 | 1.937755 | 2.003098 |
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 | 1 | 1 | 0 | 2 | 0 | 1 |
3 | 8 | 4 | 1 | 2 | 0 | 3 | 0 | 1 |
4 | 16 | 7 | 3 | 3 | 0 | 5 | 0 | 2 |
5 | 32 | 9 | 3 | 5 | 0 | 5 | 0 | 4 |
6 | 64 | 17 | 7 | 9 | 0 | 9 | 0 | 8 |
7 | 128 | 19 | 8 | 10 | 0 | 9 | 0 | 10 |
8 | 256 | 42 | 19 | 22 | 10 | 9 | 13 | 10 |
9 | 512 | 83 | 40 | 42 | 30 | 9 | 34 | 10 |
10 | 1.024 | 158 | 78 | 79 | 66 | 9 | 73 | 10 |
11 | 2.048 | 294 | 147 | 146 | 136 | 9 | 139 | 10 |
12 | 4.096 | 526 | 264 | 261 | 259 | 9 | 248 | 10 |
13 | 8.192 | 944 | 483 | 460 | 468 | 9 | 457 | 10 |
14 | 16.384 | 1.751 | 882 | 868 | 881 | 9 | 851 | 10 |
15 | 32.768 | 3.251 | 1.642 | 1.608 | 1.625 | 9 | 1.607 | 10 |
16 | 65.536 | 6.152 | 3.107 | 3.044 | 3.067 | 9 | 3.066 | 10 |
17 | 131.072 | 11.445 | 5.833 | 5.611 | 5.719 | 9 | 5.707 | 10 |
18 | 262.144 | 21.380 | 10.913 | 10.466 | 10.708 | 9 | 10.653 | 10 |
19 | 524.288 | 40.061 | 20.431 | 19.629 | 19.998 | 9 | 20.044 | 10 |
20 | 1.048.576 | 75.532 | 38.463 | 37.068 | 37.680 | 9 | 37.833 | 10 |
21 | 2.097.152 | 143.570 | 72.991 | 70.578 | 71.790 | 9 | 71.761 | 10 |
22 | 4.194.304 | 272.936 | 138.533 | 134.402 | 136.476 | 9 | 136.441 | 10 |
23 | 8.388.608 | 520.727 | 263.717 | 257.009 | 260.321 | 9 | 260.387 | 10 |
24 | 16.777.216 | 994.175 | 503.067 | 491.107 | 497.256 | 9 | 496.900 | 10 |
25 | 33.554.432 | 1.902.513 | 962.081 | 940.431 | 951.549 | 9 | 950.945 | 10 |
26 | 67.108.864 | 3.646.158 | 1.842.612 | 1.803.545 | 1.823.641 | 9 | 1.822.498 | 10 |
27 | 134.217.728 | 7.003.141 | 3.536.282 | 3.466.858 | 3.501.219 | 9 | 3.501.903 | 10 |
28 | 268.435.456 | 13.468.792 | 6.798.204 | 6.670.587 | 6.735.444 | 9 | 6.733.329 | 10 |
29 | 536.870.912 | 25.940.182 | 13.089.113 | 12.851.068 | 12.971.699 | 9 | 12.968.464 | 10 |
30 | 1.073.741.824 | 50.032.043 | 25.237.919 | 24.794.123 | 25.022.435 | 9 | 25.009.589 | 10 |
31 | 2.147.483.648 | 96.629.216 | 48.726.733 | 47.902.482 | 48.321.645 | 9 | 48.307.552 | 10 |
32 | 4.294.967.296 | 186.843.704 | 94.197.910 | 92.645.793 | 93.428.345 | 9 | 93.415.340 | 10 |
33 | 8.589.934.592 | 361.677.437 | 182.292.584 | 179.384.852 | 180.834.047 | 9 | 180.843.371 | 10 |
34 | 17.179.869.184 | 700.842.127 | 353.144.922 | 347.697.204 | 350.415.565 | 9 | 350.426.543 | 10 |
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 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
3 | 8 | 5 | 1 | 4 | 2 | 0 | 1 | 2 |
4 | 16 | 8 | 3 | 5 | 3 | 0 | 2 | 3 |
5 | 32 | 19 | 9 | 10 | 8 | 2 | 5 | 4 |
6 | 64 | 37 | 17 | 20 | 14 | 4 | 13 | 6 |
7 | 128 | 39 | 19 | 20 | 14 | 4 | 14 | 7 |
8 | 256 | 87 | 39 | 48 | 18 | 25 | 18 | 26 |
9 | 512 | 234 | 107 | 127 | 40 | 73 | 48 | 73 |
10 | 1.024 | 522 | 244 | 278 | 100 | 153 | 104 | 165 |
11 | 2.048 | 1.116 | 540 | 576 | 207 | 338 | 218 | 353 |
12 | 4.096 | 2.336 | 1.168 | 1.168 | 452 | 702 | 459 | 723 |
13 | 8.192 | 4.876 | 2.445 | 2.431 | 949 | 1.461 | 1.016 | 1.450 |
14 | 16.384 | 9.896 | 4.957 | 4.939 | 1.963 | 2.937 | 2.062 | 2.934 |
15 | 32.768 | 20.061 | 10.042 | 10.019 | 4.123 | 5.848 | 4.197 | 5.893 |
16 | 65.536 | 40.518 | 20.241 | 20.277 | 8.607 | 11.694 | 8.517 | 11.700 |
17 | 131.072 | 81.727 | 40.828 | 40.899 | 17.523 | 23.415 | 17.423 | 23.366 |
18 | 262.144 | 164.704 | 82.381 | 82.323 | 35.547 | 46.861 | 35.622 | 46.674 |
19 | 524.288 | 331.865 | 165.750 | 166.115 | 72.378 | 93.533 | 72.461 | 93.493 |
20 | 1.048.576 | 667.394 | 333.560 | 333.834 | 147.079 | 186.456 | 147.207 | 186.652 |
21 | 2.097.152 | 1.340.509 | 670.523 | 669.986 | 297.757 | 372.241 | 298.333 | 372.178 |
22 | 4.194.304 | 2.692.365 | 1.346.634 | 1.345.731 | 602.777 | 743.627 | 602.422 | 743.539 |
23 | 8.388.608 | 5.403.605 | 2.704.342 | 2.699.263 | 1.218.525 | 1.484.130 | 1.216.820 | 1.484.130 |
24 | 16.777.216 | 10.844.822 | 5.425.085 | 5.419.737 | 2.458.066 | 2.963.742 | 2.457.083 | 2.965.931 |
25 | 33.554.432 | 21.754.689 | 10.880.628 | 10.874.061 | 4.955.116 | 5.920.901 | 4.952.768 | 5.925.904 |
26 | 67.108.864 | 43.633.073 | 21.820.999 | 21.812.074 | 9.979.637 | 11.834.003 | 9.979.903 | 11.839.530 |
27 | 134.217.728 | 87.493.865 | 43.750.008 | 43.743.857 | 20.091.685 | 23.653.714 | 20.092.569 | 23.655.897 |
28 | 268.435.456 | 175.407.933 | 87.716.355 | 87.691.578 | 40.421.725 | 47.278.067 | 40.432.486 | 47.275.655 |
29 | 536.870.912 | 351.593.512 | 175.813.720 | 175.779.792 | 81.302.723 | 94.483.930 | 81.322.058 | 94.484.801 |
30 | 1.073.741.824 | 704.626.861 | 352.355.185 | 352.271.676 | 163.437.898 | 188.862.966 | 163.463.247 | 188.862.750 |
31 | 2.147.483.648 | 1.411.930.161 | 706.045.857 | 705.884.304 | 328.456.700 | 377.514.627 | 328.450.734 | 377.508.100 |
32 | 4.294.967.296 | 2.828.825.579 | 1.414.550.844 | 1.414.274.735 | 659.815.321 | 754.606.439 | 659.816.283 | 754.587.536 |
33 | 8.589.934.592 | 5.667.012.372 | 2.833.766.252 | 2.833.246.120 | 1.325.068.765 | 1.508.472.303 | 1.325.064.858 | 1.508.406.446 |
34 | 17.179.869.184 | 11.351.581.606 | 5.676.305.743 | 5.675.275.863 | 2.660.271.242 | 3.015.518.295 | 2.660.315.346 | 3.015.476.723 |