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-10x+2
f(0)=1
f(1)=7
f(2)=1
f(3)=19
f(4)=11
f(5)=23
f(6)=1
f(7)=1
f(8)=1
f(9)=1
f(10)=1
f(11)=13
f(12)=1
f(13)=41
f(14)=29
f(15)=1
f(16)=1
f(17)=1
f(18)=73
f(19)=173
f(20)=101
f(21)=233
f(22)=1
f(23)=43
f(24)=1
f(25)=1
f(26)=1
f(27)=461
f(28)=1
f(29)=79
f(30)=1
f(31)=653
f(32)=353
f(33)=761
f(34)=409
f(35)=877
f(36)=67
f(37)=1
f(38)=1
f(39)=103
f(40)=601
f(41)=1
f(42)=673
f(43)=1
f(44)=107
f(45)=83
f(46)=829
f(47)=1741
f(48)=1
f(49)=1913
f(50)=1
f(51)=1
f(52)=1093
f(53)=2281
f(54)=1
f(55)=2477
f(56)=1289
f(57)=383
f(58)=199
f(59)=263
f(60)=1
f(61)=283
f(62)=1613
f(63)=257
f(64)=1
f(65)=1
f(66)=1
f(67)=3821
f(68)=1973
f(69)=4073
f(70)=191
f(71)=619
f(72)=1
f(73)=1
f(74)=1
f(75)=4877
f(76)=193
f(77)=397
f(78)=379
f(79)=1
f(80)=2801
f(81)=523
f(82)=2953
f(83)=1
f(84)=3109
f(85)=911
f(86)=467
f(87)=6701
f(88)=3433
f(89)=541
f(90)=277
f(91)=1
f(92)=1
f(93)=1103
f(94)=359
f(95)=197
f(96)=4129
f(97)=367
f(98)=227
f(99)=1259
b) Substitution of the polynom
The polynom f(x)=x^2-10x+2 could be written as f(y)= y^2-23 with x=y+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-5
f'(x)>2x-11 with x > 5
A | B | C | D | E | F | G | H | I | J | K |
|
10^n | x | all Primes | P(x)=x^2-10x+2 | P(x) | x^2-10x+2 | C/B | D/B | E/B | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
|
1 | 10 | 5 | 4 | 1 | 0,500000 | 0,400000 | 0,100000 |
| |||
2 | 100 | 66 | 20 | 46 | 0,660000 | 0,200000 | 0,460000 | 13,200000 | 5,000000 | 46,000000 |
|
3 | 1.000 | 696 | 130 | 566 | 0,696000 | 0,130000 | 0,566000 | 10,545455 | 6,500000 | 12,304348 |
|
4 | 10.000 | 7.013 | 849 | 6.164 | 0,701300 | 0,084900 | 0,616400 | 10,076149 | 6,530769 | 10,890459 |
|
5 | 100.000 | 70.084 | 6.642 | 63.442 | 0,700840 | 0,066420 | 0,634420 | 9,993441 | 7,823322 | 10,292343 |
|
6 | 1.000.000 | 698.560 | 54.459 | 644.101 | 0,698560 | 0,054459 | 0,644101 | 9,967468 | 8,199187 | 10,152596 |
|
7 | 10.000.000 | 6.976.745 | 461.539 | 6.515.206 | 0,697675 | 0,046154 | 0,651521 | 9,987324 | 8,474981 | 10,115193 |
|
8 | 100.000.000 | 69.689.495 | 3.999.141 | 65.690.354 | 0,696895 | 0,039991 | 0,656904 | 9,988826 | 8,664795 | 10,082621 |
|
9 | 1.000.000.000 | 696.315.808 | 35.316.159 | 660.999.649 | 0,696316 | 0,035316 | 0,661000 | 9,991690 | 8,830936 | 10,062355 |
|
10 | 10.000.000.000 | 6.958.903.909 | 316.068.230 | 6.642.835.679 | 0,695890 | 0,031607 | 0,664284 | 9,993890 | 8,949677 | 10,049681 |
|
11 | 100.000.000.000 | 69.556.070.550 | 2.860.327.345 | 66.695.743.205 | 0,695561 | 0,028603 | 0,666957 | 9,995262 | 9,049715 | 10,040252 |
|
12 | 1.000.000.000.000 | 695.300.472.186 | 26.121.920.194 | 669.178.551.992 | 0,695300 | 0,026122 | 0,669179 | 9,996259 | 9,132493 | 10,033302 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A | B | C | D | E | F | G | H | I | J | K |
|
2^n | x | all Primes | P(x)=x^2-10x+2 | P(x) | x^2-10x+2 | C/B | D/B | E/B | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
|
1 | 2 | 2 | 2 | 0 | 1,000000 | 1,000000 | 0,000000 |
| |||
2 | 4 | 4 | 3 | 1 | 1,000000 | 0,750000 | 0,250000 | 2,000000 | 1,500000 |
| |
3 | 8 | 5 | 4 | 1 | 0,625000 | 0,500000 | 0,125000 | 1,250000 | 1,333333 | 1,000000 |
|
4 | 16 | 8 | 6 | 2 | 0,500000 | 0,375000 | 0,125000 | 1,600000 | 1,500000 | 2,000000 |
|
5 | 32 | 17 | 10 | 7 | 0,531250 | 0,312500 | 0,218750 | 2,125000 | 1,666667 | 3,500000 |
|
6 | 64 | 39 | 16 | 23 | 0,609375 | 0,250000 | 0,359375 | 2,294118 | 1,600000 | 3,285714 |
|
7 | 128 | 84 | 23 | 61 | 0,656250 | 0,179688 | 0,476563 | 2,153846 | 1,437500 | 2,652174 |
|
8 | 256 | 178 | 43 | 135 | 0,695313 | 0,167969 | 0,527344 | 2,119048 | 1,869565 | 2,213115 |
|
9 | 512 | 356 | 75 | 281 | 0,695313 | 0,146484 | 0,548828 | 2,000000 | 1,744186 | 2,081481 |
|
10 | 1.024 | 715 | 132 | 583 | 0,698242 | 0,128906 | 0,569336 | 2,008427 | 1,760000 | 2,074733 |
|
11 | 2.048 | 1.427 | 234 | 1.193 | 0,696777 | 0,114258 | 0,582520 | 1,995804 | 1,772727 | 2,046312 |
|
12 | 4.096 | 2.868 | 405 | 2.463 | 0,700195 | 0,098877 | 0,601318 | 2,009811 | 1,730769 | 2,064543 |
|
13 | 8.192 | 5.756 | 719 | 5.037 | 0,702637 | 0,087769 | 0,614868 | 2,006974 | 1,775309 | 2,045067 |
|
14 | 16.384 | 11.496 | 1.325 | 10.171 | 0,701660 | 0,080872 | 0,620789 | 1,997220 | 1,842837 | 2,019257 |
|
15 | 32.768 | 22.996 | 2.434 | 20.562 | 0,701782 | 0,074280 | 0,627502 | 2,000348 | 1,836981 | 2,021630 |
|
16 | 65.536 | 45.946 | 4.553 | 41.393 | 0,701080 | 0,069473 | 0,631607 | 1,998000 | 1,870583 | 2,013082 |
|
17 | 131.072 | 91.874 | 8.521 | 83.353 | 0,700943 | 0,065010 | 0,635933 | 1,999608 | 1,871513 | 2,013698 |
|
18 | 262.144 | 183.433 | 16.039 | 167.394 | 0,699741 | 0,061184 | 0,638557 | 1,996571 | 1,882291 | 2,008254 |
|
19 | 524.288 | 366.473 | 30.096 | 336.377 | 0,698992 | 0,057404 | 0,641588 | 1,997858 | 1,876426 | 2,009493 |
|
20 | 1.048.576 | 732.422 | 56.980 | 675.442 | 0,698492 | 0,054340 | 0,644152 | 1,998570 | 1,893275 | 2,007991 |
|
21 | 2.097.152 | 1.464.563 | 107.863 | 1.356.700 | 0,698358 | 0,051433 | 0,646925 | 1,999616 | 1,892998 | 2,008611 |
|
22 | 4.194.304 | 2.927.645 | 205.247 | 2.722.398 | 0,698005 | 0,048935 | 0,649070 | 1,998989 | 1,902849 | 2,006632 |
|
23 | 8.388.608 | 5.852.683 | 391.675 | 5.461.008 | 0,697694 | 0,046691 | 0,651003 | 1,999110 | 1,908310 | 2,005955 |
|
24 | 16.777.216 | 11.701.189 | 748.810 | 10.952.379 | 0,697445 | 0,044633 | 0,652813 | 1,999286 | 1,911815 | 2,005560 |
|
25 | 33.554.432 | 23.394.392 | 1.432.772 | 21.961.620 | 0,697207 | 0,042700 | 0,654507 | 1,999318 | 1,913399 | 2,005192 |
|
26 | 67.108.864 | 46.774.459 | 2.747.186 | 44.027.273 | 0,696994 | 0,040936 | 0,656057 | 1,999388 | 1,917392 | 2,004737 |
|
27 | 134.217.728 | 93.523.222 | 5.278.615 | 88.244.607 | 0,696802 | 0,039329 | 0,657474 | 1,999451 | 1,921463 | 2,004317 |
|
28 | 268.435.456 | 186.996.749 | 10.160.115 | 176.836.634 | 0,696617 | 0,037849 | 0,658768 | 1,999469 | 1,924769 | 2,003937 |
|
29 | 536.870.912 | 373.904.646 | 19.580.675 | 354.323.971 | 0,696452 | 0,036472 | 0,659980 | 1,999525 | 1,927210 | 2,003680 |
|
30 | 1.073.741.824 | 747.646.516 | 37.784.271 | 709.862.245 | 0,696300 | 0,035189 | 0,661111 | 1,999565 | 1,929672 | 2,003427 |
|
31 | 2.147.483.648 | 1.494.986.785 | 72.992.230 | 1.421.994.555 | 0,696157 | 0,033990 | 0,662168 | 1,999590 | 1,931815 | 2,003198 |
|
32 | 4.294.967.296 | 2.989.433.068 | 141.186.109 | 2.848.246.959 | 0,696032 | 0,032872 | 0,663159 | 1,999638 | 1,934262 | 2,002994 |
|
33 | 8.589.934.592 | 5.977.865.647 | 273.395.448 | 5.704.470.199 | 0,695915 | 0,031827 | 0,664088 | 1,999665 | 1,936419 | 2,002800 |
|
34 | 17.179.869.184 | 11.953.831.597 | 529.936.294 | 11.423.895.303 | 0,695805 | 0,030846 | 0,664958 | 1,999682 | 1,938351 | 2,002622 |
|
35 | 34.359.738.368 | 23.904.195.871 | 1.028.133.233 | 22.876.062.638 | 0,695704 | 0,029923 | 0,665781 | 1,999710 | 1,940107 | 2,002475 |
|
36 | 68.719.476.736 | 47.801.903.792 | 1.996.517.596 | 45.805.386.196 | 0,695609 | 0,029053 | 0,666556 | 1,999729 | 1,941886 | 2,002328 |
|
37 | 137.438.953.472 | 95.591.810.760 | 3.880.275.280 | 91.711.535.480 | 0,695522 | 0,028233 | 0,667289 | 1,999749 | 1,943522 | 2,002200 |
|
38 | 274.877.906.944 | 191.161.013.353 | 7.547.544.461 | 183.613.468.892 | 0,695440 | 0,027458 | 0,667982 | 1,999763 | 1,945105 | 2,002076 |
|
39 | 549.755.813.888 | 382.279.766.577 | 14.691.832.804 | 367.587.933.773 | 0,695363 | 0,026724 | 0,668639 | 1,999779 | 1,946571 | 2,001966 |
|
40 | 1.099.511.627.776 | 764.480.587.987 | 28.619.064.640 | 735.861.523.347 | 0,695291 | 0,026029 | 0,669262 | 1,999793 | 1,947957 | 2,001865 |
|
| |||||||||||
| |||||||||||