De Polignac numbers: Difference between revisions

Content added Content deleted

Inline

@@ Line 753: / Line 753: @@
+</pre>
+Translation of: ALGOL W
+<syntaxhighlight lang "XPL0">define MAX_NUMBER = 500000;             \ maximum number we will consider     \
+define MAX_POWER  =     20;             \ maximum powerOf2 < MAX_NUMBER       \
+integer Prime      ( MAX_NUMBER+1 );
+integer PowersOf2  ( MAX_POWER+1  );
+integer DpCount;
+integer RootMaxNumber;
+integer I2, S, I;
+integer P2, P;
+integer Found;
+begin \ find some De Polignac numbers - positive odd numbers that can't be    \
+      \ written as p + 2^n for some prime p and integer n                     \
+    begin
+        \ Sieve the primes to MAX_NUMBER                                      \
+        begin
+            RootMaxNumber:= ( sqrt( MAX_NUMBER ) );
+            Prime( 0 ) := false;
+            Prime( 1 ) := false;
+            Prime( 2 ) := true;
+            for I := 3 to MAX_NUMBER do [Prime( I ) := true;   I:= I+1];
+            for I := 4 to MAX_NUMBER do [Prime( I ) := false;  I:= I+1];
+            for I := 3 to RootMaxNumber do begin
+                if Prime( I ) then begin
+                    I2 := I + I;
+                    for S := I * I to MAX_NUMBER do [Prime( S ) := false;  S:= S+I2-1]
+                end; \if_prime_i_and_i_lt_rootMaxNumber
+                I:= I+1
+            end \for_I
+        end;
+        \ Table of powers of 2 greater than 2^0 ( up to around 2 000 000 )    \
+        \       Increase the table size if MAX_NUMBER > 2 000 000             \
+        begin
+            P2 := 1;
+            for I := 1 to MAX_POWER do begin
+                P2             := P2 * 2;
+                PowersOf2( I ) := P2
+            end \for_I
+        end;
+        \ The numbers must be odd and not of the form p + 2^n                 \
+        \ Either p is odd and 2^n is even and hence n > 0 and p > 2           \
+        \     or 2^n is odd and p is even and hence n = 0 and p = 2           \
+        \ n = 0, p = 2 - the only possibility is 3                            \
+        DpCount := 0;
+        for I := 1 to 3 do begin
+            P := 2;
+            if P + 1 # I then begin
+                DpCount := DpCount + 1;
+                Format(5, 0);
+                RlOut(0, float(I))
+            end; \if_P_plus_1_ne_I
+            I:= I+1
+        end \for_I\ ;
+        \ n > 0, p > 2                                                        \
+        for I := 5 to MAX_NUMBER do begin
+            Found := false;
+            P := 1;
+            while P <= MAX_POWER and not Found and I > PowersOf2( P ) do begin
+                Found := Prime( I - PowersOf2( P ) );
+                P     := P + 1
+            end \while_not_found_and_have_a_suitable_power\ ;
+            if not Found then begin
+                DpCount := DpCount + 1;
+                if DpCount <= 50 then begin
+                    Format(5, 0);
+                    RlOut(0, float(I));
+                    if rem(DpCount / 10) = 0 then CrLf(0)
+                    end
+                else if DpCount = 1000 or DpCount = 10000 then begin
+                    Format(5, 0);
+                    Text(0, "The ");  RlOut(0, float(DpCount));
+                    Format(6, 0);
+                    Text(0, "th De Polignac number is ");  RlOut(0, float(I));
+                    CrLf(0)
+                end \if_various_DePolignac_numbers
+            end; \if_not_found
+        I:= I+1
+        end \for_I\ ;
+        Text(0, "Found ");  IntOut(0, DpCount);
+        Text(0, " De Polignac numbers up to ");  IntOut(0, MAX_NUMBER);  CrLf(0)
+    end
+end</syntaxhighlight>
+{{out}}
+<pre>
+127  149  251  331  337  373  509  599  701
+809  877  905  907  959  977  997 1019 1087
+1207 1211 1243 1259 1271 1477 1529 1541 1549
+1597 1619 1649 1657 1719 1759 1777 1783 1807
+1859 1867 1927 1969 1973 1985 2171 2203 2213
+The  1000th De Polignac number is  31941
+The 10000th De Polignac number is 273421
+Found 19075 De Polignac numbers up to 500000
 </pre>