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+6x-2
f(0)=1
f(1)=5
f(2)=7
f(3)=1
f(4)=19
f(5)=53
f(6)=1
f(7)=89
f(8)=11
f(9)=1
f(10)=79
f(11)=37
f(12)=107
f(13)=1
f(14)=139
f(15)=313
f(16)=1
f(17)=389
f(18)=43
f(19)=1
f(20)=1
f(21)=113
f(22)=307
f(23)=1
f(24)=359
f(25)=773
f(26)=83
f(27)=127
f(28)=1
f(29)=1013
f(30)=1
f(31)=229
f(32)=607
f(33)=257
f(34)=97
f(35)=1433
f(36)=151
f(37)=227
f(38)=167
f(39)=1753
f(40)=919
f(41)=1
f(42)=1
f(43)=421
f(44)=157
f(45)=2293
f(46)=239
f(47)=131
f(48)=1
f(49)=2693
f(50)=1399
f(51)=1
f(52)=137
f(53)=1
f(54)=1619
f(55)=479
f(56)=347
f(57)=1
f(58)=1
f(59)=3833
f(60)=1979
f(61)=1
f(62)=1
f(63)=1
f(64)=2239
f(65)=659
f(66)=1
f(67)=4889
f(68)=503
f(69)=739
f(70)=2659
f(71)=1093
f(72)=401
f(73)=1153
f(74)=269
f(75)=6073
f(76)=1
f(77)=6389
f(78)=1
f(79)=1
f(80)=181
f(81)=1409
f(82)=3607
f(83)=211
f(84)=3779
f(85)=1
f(86)=1
f(87)=8089
f(88)=827
f(89)=1
f(90)=617
f(91)=353
f(92)=4507
f(93)=263
f(94)=1
f(95)=1
f(96)=1
f(97)=1427
f(98)=1019
f(99)=547
b) Substitution of the polynom
The polynom f(x)=x^2+6x-2 could be written as f(y)= y^2-11 with x=y-3
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+3
f'(x)>2x+5
A | B | C | D | E | F | G | H | I | J | K |
|
10^n | x | all Primes | P(x)=x^2+6x-2 | P(x) | x^2+6x-2 | C/B | D/B | E/B | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
|
1 | 10 | 8 | 4 | 4 | 0,800000 | 0,400000 | 0,400000 |
| |||
2 | 100 | 71 | 17 | 54 | 0,710000 | 0,170000 | 0,540000 | 8,875000 | 4,250000 | 13,500000 |
|
3 | 1.000 | 696 | 104 | 592 | 0,696000 | 0,104000 | 0,592000 | 9,802817 | 6,117647 | 10,962963 |
|
4 | 10.000 | 7.001 | 724 | 6.277 | 0,700100 | 0,072400 | 0,627700 | 10,058908 | 6,961538 | 10,603041 |
|
5 | 100.000 | 69.944 | 5.523 | 64.421 | 0,699440 | 0,055230 | 0,644210 | 9,990573 | 7,628453 | 10,263024 |
|
6 | 1.000.000 | 697.842 | 45.100 | 652.742 | 0,697842 | 0,045100 | 0,652742 | 9,977153 | 8,165852 | 10,132441 |
|
7 | 10.000.000 | 6.968.656 | 381.917 | 6.586.739 | 0,696866 | 0,038192 | 0,658674 | 9,986008 | 8,468226 | 10,090877 |
|
8 | 100.000.000 | 69.617.899 | 3.308.104 | 66.309.795 | 0,696179 | 0,033081 | 0,663098 | 9,990147 | 8,661840 | 10,067166 |
|
9 | 1.000.000.000 | 695.678.933 | 29.187.747 | 666.491.186 | 0,695679 | 0,029188 | 0,666491 | 9,992817 | 8,823104 | 10,051172 |
|
10 | 10.000.000.000 | 6.953.068.193 | 261.206.564 | 6.691.861.629 | 0,695307 | 0,026121 | 0,669186 | 9,994651 | 8,949186 | 10,040435 |
|
11 | 100.000.000.000 | 69.502.420.813 | 2.363.706.298 | 67.138.714.515 | 0,695024 | 0,023637 | 0,671387 | 9,995935 | 9,049184 | 10,032890 |
|
12 | 1.000.000.000.000 | 694.800.894.771 | 21.586.726.901 | 673.214.167.870 | 0,694801 | 0,021587 | 0,673214 | 9,996787 | 9,132576 | 10,027213 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A | B | C | D | E | F | G | H | I | J | K |
|
2^n | x | all Primes | P(x)=x^2+6x-2 | P(x) | x^2+6x-2 | C/B | D/B | E/B | 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 |
| |||
2 | 4 | 4 | 2 | 2 | 1,000000 | 0,500000 | 0,500000 | 1,333333 | 1,000000 |
| |
3 | 8 | 7 | 4 | 3 | 0,875000 | 0,500000 | 0,375000 | 1,750000 | 2,000000 | 1,500000 |
|
4 | 16 | 12 | 5 | 7 | 0,750000 | 0,312500 | 0,437500 | 1,714286 | 1,250000 | 2,333333 |
|
5 | 32 | 23 | 8 | 15 | 0,718750 | 0,250000 | 0,468750 | 1,916667 | 1,600000 | 2,142857 |
|
6 | 64 | 45 | 13 | 32 | 0,703125 | 0,203125 | 0,500000 | 1,956522 | 1,625000 | 2,133333 |
|
7 | 128 | 90 | 20 | 70 | 0,703125 | 0,156250 | 0,546875 | 2,000000 | 1,538462 | 2,187500 |
|
8 | 256 | 182 | 35 | 147 | 0,710938 | 0,136719 | 0,574219 | 2,022222 | 1,750000 | 2,100000 |
|
9 | 512 | 357 | 67 | 290 | 0,697266 | 0,130859 | 0,566406 | 1,961538 | 1,914286 | 1,972789 |
|
10 | 1.024 | 715 | 105 | 610 | 0,698242 | 0,102539 | 0,595703 | 2,002801 | 1,567164 | 2,103448 |
|
11 | 2.048 | 1.448 | 181 | 1.267 | 0,707031 | 0,088379 | 0,618652 | 2,025175 | 1,723810 | 2,077049 |
|
12 | 4.096 | 2.879 | 337 | 2.542 | 0,702881 | 0,082275 | 0,620605 | 1,988260 | 1,861878 | 2,006314 |
|
13 | 8.192 | 5.729 | 607 | 5.122 | 0,699341 | 0,074097 | 0,625244 | 1,989927 | 1,801187 | 2,014949 |
|
14 | 16.384 | 11.469 | 1.093 | 10.376 | 0,700012 | 0,066711 | 0,633301 | 2,001920 | 1,800659 | 2,025771 |
|
15 | 32.768 | 22.918 | 2.048 | 20.870 | 0,699402 | 0,062500 | 0,636902 | 1,998256 | 1,873742 | 2,011372 |
|
16 | 65.536 | 45.898 | 3.728 | 42.170 | 0,700348 | 0,056885 | 0,643463 | 2,002705 | 1,820313 | 2,020604 |
|
17 | 131.072 | 91.691 | 7.055 | 84.636 | 0,699547 | 0,053825 | 0,645721 | 1,997712 | 1,892436 | 2,007019 |
|
18 | 262.144 | 183.165 | 13.226 | 169.939 | 0,698719 | 0,050453 | 0,648266 | 1,997633 | 1,874699 | 2,007881 |
|
19 | 524.288 | 365.873 | 25.000 | 340.873 | 0,697847 | 0,047684 | 0,650164 | 1,997505 | 1,890216 | 2,005855 |
|
20 | 1.048.576 | 731.845 | 47.133 | 684.712 | 0,697942 | 0,044950 | 0,652992 | 2,000271 | 1,885320 | 2,008701 |
|
21 | 2.097.152 | 1.462.745 | 89.571 | 1.373.174 | 0,697491 | 0,042711 | 0,654780 | 1,998709 | 1,900388 | 2,005477 |
|
22 | 4.194.304 | 2.924.091 | 169.872 | 2.754.219 | 0,697158 | 0,040501 | 0,656657 | 1,999044 | 1,896507 | 2,005732 |
|
23 | 8.388.608 | 5.846.110 | 324.452 | 5.521.658 | 0,696911 | 0,038678 | 0,658233 | 1,999291 | 1,909979 | 2,004800 |
|
24 | 16.777.216 | 11.688.531 | 618.970 | 11.069.561 | 0,696691 | 0,036893 | 0,659797 | 1,999369 | 1,907740 | 2,004753 |
|
25 | 33.554.432 | 23.370.006 | 1.185.366 | 22.184.640 | 0,696480 | 0,035327 | 0,661154 | 1,999396 | 1,915062 | 2,004112 |
|
26 | 67.108.864 | 46.726.723 | 2.273.082 | 44.453.641 | 0,696282 | 0,033872 | 0,662411 | 1,999431 | 1,917620 | 2,003803 |
|
27 | 134.217.728 | 93.428.229 | 4.365.930 | 89.062.299 | 0,696095 | 0,032529 | 0,663566 | 1,999460 | 1,920709 | 2,003487 |
|
28 | 268.435.456 | 186.816.810 | 8.398.616 | 178.418.194 | 0,695947 | 0,031287 | 0,664660 | 1,999576 | 1,923672 | 2,003297 |
|
29 | 536.870.912 | 373.555.468 | 16.183.498 | 357.371.970 | 0,695801 | 0,030144 | 0,665657 | 1,999582 | 1,926924 | 2,003002 |
|
30 | 1.073.741.824 | 746.968.831 | 31.225.725 | 715.743.106 | 0,695669 | 0,029081 | 0,666588 | 1,999620 | 1,929479 | 2,002796 |
|
31 | 2.147.483.648 | 1.493.673.241 | 60.332.875 | 1.433.340.366 | 0,695546 | 0,028095 | 0,667451 | 1,999646 | 1,932153 | 2,002591 |
|
32 | 4.294.967.296 | 2.986.854.625 | 116.691.003 | 2.870.163.622 | 0,695431 | 0,027169 | 0,668262 | 1,999671 | 1,934120 | 2,002430 |
|
33 | 8.589.934.592 | 5.972.830.633 | 225.937.943 | 5.746.892.690 | 0,695329 | 0,026303 | 0,669026 | 1,999706 | 1,936207 | 2,002287 |
|
34 | 17.179.869.184 | 11.944.036.512 | 437.939.940 | 11.506.096.572 | 0,695234 | 0,025491 | 0,669743 | 1,999728 | 1,938320 | 2,002142 |
|
35 | 34.359.738.368 | 23.885.076.589 | 849.639.960 | 23.035.436.629 | 0,695147 | 0,024728 | 0,670419 | 1,999749 | 1,940083 | 2,002020 |
|
36 | 68.719.476.736 | 47.764.566.376 | 1.649.863.576 | 46.114.702.800 | 0,695066 | 0,024009 | 0,671057 | 1,999766 | 1,941838 | 2,001903 |
|
37 | 137.438.953.472 | 95.518.682.613 | 3.206.591.923 | 92.312.090.690 | 0,694990 | 0,023331 | 0,671659 | 1,999781 | 1,943550 | 2,001793 |
|
38 | 274.877.906.944 | 191.018.013.504 | 6.237.159.361 | 184.780.854.143 | 0,694919 | 0,022691 | 0,672229 | 1,999797 | 1,945105 | 2,001697 |
|
39 | 549.755.813.888 | 381.999.933.299 | 12.141.088.699 | 369.858.844.600 | 0,694854 | 0,022085 | 0,672769 | 1,999811 | 1,946573 | 2,001608 |
|
40 | 1.099.511.627.776 | 763.932.794.221 | 23.650.285.030 | 740.282.509.191 | 0,694793 | 0,021510 | 0,673283 | 1,999824 | 1,947954 | 2,001527 |
|
| |||||||||||
| |||||||||||