De Polignac numbers: Difference between revisions

Content added Content deleted

Inline

@@ Line 27: / Line 27: @@
 ;* [[oeis:A006285|OEIS:A006285 - Odd numbers not of form p + 2^k (de Polignac numbers)]]
+=={{header|Action!}}==
+{{Trans|PL/M}}
+{{libheader|Action! Sieve of Eratosthenes}}
+<syntaxhighlight lang="action!">
+;;; Find some De Polignac numbers: positive odd numbers that can't be
+;;;      written as p + 2**n for some prime p and integer n
+INCLUDE "H6:SIEVE.ACT"
+PROC showDePolignac( CARD dpNumber )
+  Put(' )
+  IF dpNumber <   10 THEN Put(' ) FI
+  IF dpNumber <  100 THEN Put(' ) FI
+  IF dpNumber < 1000 THEN Put(' ) FI
+  PrintC( dpNumber )
+RETURN
+PROC Main()
+  DEFINE MAX_DP = "4000", MAX_POWER_OF_2 = "11"
+  BYTE ARRAY primes(MAX_DP+1)
+  CARD ARRAY powersOf2(MAX_POWER_OF_2+1) =
+                 [1 2 4 8 16 32 64 128 256 512 1024 2048]
+  CARD i, p, count
+  BYTE found
+  Sieve(primes,MAX_DP+1)
+  ; 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
+  FOR i = 1 TO 3 STEP 2 DO
+    p = 2
+    IF p + 1 <> i THEN
+      count ==+ 1
+      showDePolignac( i )
+    FI
+  OD
+  ; n > 0, p > 2
+  i = 3
+  WHILE i < MAX_DP AND count < 50 DO
+    i ==+ 2
+    found = 0
+    p = 1
+    WHILE found = 0 AND p <= MAX_POWER_OF_2 AND i > powersOf2( p ) DO
+       found = primes( i - powersOf2( p ) )
+       p ==+ 1
+    OD
+    IF found = 0 THEN
+      count ==+ 1
+      showDePolignac( i )
+      IF count MOD 10 = 0 THEN PutE() FI
+    FI
+  OD
+RETURN
+</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
+</pre>
 =={{header|J}}==