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) = 2x^2+1
f(0)=1
f(1)=3
f(2)=1
f(3)=19
f(4)=11
f(5)=17
f(6)=73
f(7)=1
f(8)=43
f(9)=163
f(10)=67
f(11)=1
f(12)=1
f(13)=113
f(14)=131
f(15)=41
f(16)=1
f(17)=193
f(18)=59
f(19)=241
f(20)=89
f(21)=883
f(22)=1
f(23)=353
f(24)=1153
f(25)=139
f(26)=1
f(27)=1459
f(28)=523
f(29)=1
f(30)=1801
f(31)=641
f(32)=683
f(33)=2179
f(34)=257
f(35)=1
f(36)=2593
f(37)=83
f(38)=107
f(39)=179
f(40)=97
f(41)=1
f(42)=3529
f(43)=137
f(44)=1291
f(45)=4051
f(46)=1
f(47)=491
f(48)=419
f(49)=1601
f(50)=1667
f(51)=1
f(52)=601
f(53)=1873
f(54)=307
f(55)=2017
f(56)=1
f(57)=1
f(58)=2243
f(59)=211
f(60)=379
f(61)=827
f(62)=233
f(63)=467
f(64)=2731
f(65)=313
f(66)=8713
f(67)=1
f(68)=3083
f(69)=1
f(70)=1
f(71)=3361
f(72)=10369
f(73)=1
f(74)=1217
f(75)=11251
f(76)=3851
f(77)=1
f(78)=283
f(79)=1
f(80)=251
f(81)=1193
f(82)=4483
f(83)=1531
f(84)=1283
f(85)=4817
f(86)=4931
f(87)=15139
f(88)=1721
f(89)=5281
f(90)=953
f(91)=5521
f(92)=1
f(93)=17299
f(94)=1
f(95)=547
f(96)=18433
f(97)=1
f(98)=337
f(99)=19603
b) Substitution of the polynom
The polynom f(x)=2x^2+1 could be written as f(y)= 2y^2+1 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 > 1
A | B | C | D | E | F | G | H | I | J | K |
|
10^n | x | all Primes | P(x)=2x^2+1 | P(x) | 2x^2+1 | 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 | 76 | 19 | 57 | 0,760000 | 0,190000 | 0,570000 | 9,500000 | 4,750000 | 14,250000 |
|
3 | 1.000 | 760 | 117 | 643 | 0,760000 | 0,117000 | 0,643000 | 10,000000 | 6,157895 | 11,280702 |
|
4 | 10.000 | 7.445 | 841 | 6.604 | 0,744500 | 0,084100 | 0,660400 | 9,796053 | 7,188034 | 10,270607 |
|
5 | 100.000 | 73.477 | 6.606 | 66.871 | 0,734770 | 0,066060 | 0,668710 | 9,869308 | 7,854935 | 10,125833 |
|
6 | 1.000.000 | 726.948 | 54.629 | 672.319 | 0,726948 | 0,054629 | 0,672319 | 9,893545 | 8,269603 | 10,053970 |
|
7 | 10.000.000 | 7.218.256 | 462.547 | 6.755.709 | 0,721826 | 0,046255 | 0,675571 | 9,929536 | 8,467060 | 10,048368 |
|
8 | 100.000.000 | 71.801.859 | 4.027.074 | 67.774.785 | 0,718019 | 0,040271 | 0,677748 | 9,947259 | 8,706302 | 10,032224 |
|
9 | 1.000.000.000 | 715.087.632 | 35.630.373 | 679.457.259 | 0,715088 | 0,035630 | 0,679457 | 9,959180 | 8,847708 | 10,025222 |
|
10 | 10.000.000.000 | 7.127.665.635 | 319.422.804 | 6.808.242.831 | 0,712767 | 0,031942 | 0,680824 | 9,967541 | 8,964902 | 10,020119 |
|
11 | 100.000.000.000 | 71.089.166.879 | 2.895.004.512 | 68.194.162.367 | 0,710892 | 0,028950 | 0,681942 | 9,973696 | 9,063237 | 10,016412 |
|
12 | 1.000.000.000.000 | 709.344.259.821 | 26.471.105.994 | 682.873.153.827 | 0,709344 | 0,026471 | 0,682873 | 9,978233 | 9,143718 | 10,013660 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A | B | C | D | E | F | G | H | I | J | K |
|
2^n | x | all Primes | P(x)=2x^2+1 | P(x) | 2x^2+1 | C/B | D/B | E/B | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
|
1 | 2 | 1 | 1 | 0 | 0,500000 | 0,500000 | 0,000000 |
| |||
2 | 4 | 3 | 2 | 1 | 0,750000 | 0,500000 | 0,250000 | 3,000000 | 2,000000 |
| |
3 | 8 | 6 | 3 | 3 | 0,750000 | 0,375000 | 0,375000 | 2,000000 | 1,500000 | 3,000000 |
|
4 | 16 | 11 | 4 | 7 | 0,687500 | 0,250000 | 0,437500 | 1,833333 | 1,333333 | 2,333333 |
|
5 | 32 | 24 | 8 | 16 | 0,750000 | 0,250000 | 0,500000 | 2,181818 | 2,000000 | 2,285714 |
|
6 | 64 | 50 | 12 | 38 | 0,781250 | 0,187500 | 0,593750 | 2,083333 | 1,500000 | 2,375000 |
|
7 | 128 | 99 | 22 | 77 | 0,773438 | 0,171875 | 0,601563 | 1,980000 | 1,833333 | 2,026316 |
|
8 | 256 | 194 | 37 | 157 | 0,757813 | 0,144531 | 0,613281 | 1,959596 | 1,681818 | 2,038961 |
|
9 | 512 | 388 | 70 | 318 | 0,757813 | 0,136719 | 0,621094 | 2,000000 | 1,891892 | 2,025478 |
|
10 | 1.024 | 776 | 120 | 656 | 0,757813 | 0,117188 | 0,640625 | 2,000000 | 1,714286 | 2,062893 |
|
11 | 2.048 | 1.540 | 223 | 1.317 | 0,751953 | 0,108887 | 0,643066 | 1,984536 | 1,858333 | 2,007622 |
|
12 | 4.096 | 3.073 | 392 | 2.681 | 0,750244 | 0,095703 | 0,654541 | 1,995455 | 1,757848 | 2,035687 |
|
13 | 8.192 | 6.099 | 714 | 5.385 | 0,744507 | 0,087158 | 0,657349 | 1,984705 | 1,821429 | 2,008579 |
|
14 | 16.384 | 12.160 | 1.293 | 10.867 | 0,742188 | 0,078918 | 0,663269 | 1,993769 | 1,810924 | 2,018013 |
|
15 | 32.768 | 24.225 | 2.372 | 21.853 | 0,739288 | 0,072388 | 0,666901 | 1,992188 | 1,834493 | 2,010951 |
|
16 | 65.536 | 48.262 | 4.484 | 43.778 | 0,736420 | 0,068420 | 0,667999 | 1,992239 | 1,890388 | 2,003295 |
|
17 | 131.072 | 96.117 | 8.450 | 87.667 | 0,733315 | 0,064468 | 0,668846 | 1,991567 | 1,884478 | 2,002536 |
|
18 | 262.144 | 191.661 | 15.902 | 175.759 | 0,731129 | 0,060661 | 0,670467 | 1,994039 | 1,881893 | 2,004848 |
|
19 | 524.288 | 382.127 | 29.956 | 352.171 | 0,728849 | 0,057137 | 0,671713 | 1,993765 | 1,883788 | 2,003715 |
|
20 | 1.048.576 | 762.133 | 57.002 | 705.131 | 0,726827 | 0,054361 | 0,672465 | 1,994449 | 1,902858 | 2,002240 |
|
21 | 2.097.152 | 1.520.931 | 108.191 | 1.412.740 | 0,725236 | 0,051589 | 0,673647 | 1,995624 | 1,898021 | 2,003514 |
|
22 | 4.194.304 | 3.035.027 | 205.398 | 2.829.629 | 0,723607 | 0,048971 | 0,674636 | 1,995506 | 1,898476 | 2,002937 |
|
23 | 8.388.608 | 6.058.303 | 392.498 | 5.665.805 | 0,722206 | 0,046789 | 0,675417 | 1,996128 | 1,910914 | 2,002314 |
|
24 | 16.777.216 | 12.094.615 | 751.210 | 11.343.405 | 0,720895 | 0,044776 | 0,676120 | 1,996370 | 1,913921 | 2,002082 |
|
25 | 33.554.432 | 24.149.710 | 1.439.421 | 22.710.289 | 0,719717 | 0,042898 | 0,676819 | 1,996732 | 1,916137 | 2,002070 |
|
26 | 67.108.864 | 48.226.395 | 2.764.920 | 45.461.475 | 0,718629 | 0,041201 | 0,677429 | 1,996976 | 1,920856 | 2,001801 |
|
27 | 134.217.728 | 96.316.171 | 5.316.867 | 90.999.304 | 0,717611 | 0,039614 | 0,677998 | 1,997167 | 1,922973 | 2,001680 |
|
28 | 268.435.456 | 192.381.714 | 10.237.140 | 182.144.574 | 0,716678 | 0,038136 | 0,678541 | 1,997398 | 1,925408 | 2,001604 |
|
29 | 536.870.912 | 384.295.122 | 19.746.417 | 364.548.705 | 0,715805 | 0,036781 | 0,679025 | 1,997566 | 1,928900 | 2,001425 |
|
30 | 1.073.741.824 | 767.729.885 | 38.119.892 | 729.609.993 | 0,715004 | 0,035502 | 0,679502 | 1,997761 | 1,930471 | 2,001406 |
|
31 | 2.147.483.648 | 1.533.851.929 | 73.682.997 | 1.460.168.932 | 0,714255 | 0,034311 | 0,679944 | 1,997906 | 1,932928 | 2,001301 |
|
32 | 4.294.967.296 | 3.064.705.816 | 142.607.233 | 2.922.098.583 | 0,713557 | 0,033203 | 0,680354 | 1,998045 | 1,935416 | 2,001206 |
|
33 | 8.589.934.592 | 6.123.796.529 | 276.272.479 | 5.847.524.050 | 0,712904 | 0,032162 | 0,680741 | 1,998168 | 1,937296 | 2,001139 |
|
34 | 17.179.869.184 | 12.237.071.081 | 535.760.398 | 11.701.310.683 | 0,712291 | 0,031185 | 0,681106 | 1,998282 | 1,939246 | 2,001071 |
|
35 | 34.359.738.368 | 24.454.319.674 | 1.039.909.544 | 23.414.410.130 | 0,711714 | 0,030265 | 0,681449 | 1,998380 | 1,940997 | 2,001007 |
|
36 | 68.719.476.736 | 48.871.362.246 | 2.020.283.544 | 46.851.078.702 | 0,711172 | 0,029399 | 0,681773 | 1,998476 | 1,942749 | 2,000951 |
|
37 | 137.438.953.472 | 97.672.370.547 | 3.928.018.222 | 93.744.352.325 | 0,710660 | 0,028580 | 0,682080 | 1,998560 | 1,944291 | 2,000901 |
|
38 | 274.877.906.944 | 195.211.920.067 | 7.643.397.852 | 187.568.522.215 | 0,710177 | 0,027807 | 0,682370 | 1,998640 | 1,945866 | 2,000851 |
|
39 | 549.755.813.888 | 390.172.411.497 | 14.883.784.616 | 375.288.626.881 | 0,709719 | 0,027073 | 0,682646 | 1,998712 | 1,947273 | 2,000808 |
|
40 | 1.099.511.627.776 | 779.868.595.785 | 29.003.055.988 | 750.865.539.797 | 0,709286 | 0,026378 | 0,682908 | 1,998779 | 1,948634 | 2,000768 |
|
| |||||||||||
| |||||||||||