Jump to content

De Polignac numbers

From Rosetta Code
Task
De Polignac numbers
You are encouraged to solve this task according to the task description, using any language you may know.

Alphonse de Polignac, a French mathematician in the 1800s, conjectured that every positive odd integer could be formed from the sum of a power of 2 and a prime number.

He was subsequently proved incorrect.

The numbers that fail this condition are now known as de Polignac numbers.

Technically 1 is a de Polignac number, as there is no prime and power of 2 that sum to 1. De Polignac was aware but thought that 1 was a special case. However.

127 is also fails that condition, as there is no prime and power of 2 that sum to 127.

As it turns out, de Polignac numbers are not uncommon, in fact, there are an infinite number of them.


Task
  • Find and display the first fifty de Polignac numbers.


Stretch
  • Find and display the one thousandth de Polignac number.
  • Find and display the ten thousandth de Polignac number.


See also


11l

Translation of: C++
F is_prime(p)
   I p < 2 | p % 2 == 0
      R p == 2
   L(i) (3 .. Int(sqrt(p))).step(2)
      I p % i == 0
         R 0B
   R 1B

F is_depolignac_number(n)
   V p = 1
   L p < n
      I is_prime(n - p)
         R 0B
      p <<= 1
   R 1B

print(‘First 50 de Polignac numbers:’)
V count = 0
L(n) (1..).step(2)
   I is_depolignac_number(n)
      count++
      I count <= 50
         print(f:‘{commatize(n):5}’, end' I count % 10 == 0 {"\n"} E ‘ ’)
      E I count == 1000
         print("\nOne thousandth: "commatize(n))
      E I count == 10000
         print("\nTen thousandth: "commatize(n))
         L.break
Output:
First 50 de Polignac numbers:
    1   127   149   251   331   337   373   509   599   701
  757   809   877   905   907   959   977   997 1,019 1,087
1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549
1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807
1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213

One thousandth: 31,941

Ten thousandth: 273,421

Action!

Translation of: PL/M

which is based on the ALGOL 68 sample.

;;; 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
Output:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

ALGOL 68

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                     #
    INT max number = 500 000; # maximum number we will consider               #
    # sieve the primes to max number                                          #
    [ 0 : max number ]BOOL prime;
    prime[ 0 ] := prime[ 1 ] := FALSE;
    prime[ 2 ] := TRUE;
    FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE  OD;
    FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
    FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
        IF prime[ i ] THEN
            FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
        FI
    OD;
    # 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                 #
    [ 1 : 20 ]INT powers of 2;
    BEGIN
        INT p2 := 1;
        FOR i TO UPB powers of 2 DO
            powers of 2[ i ] := ( p2 *:= 2 )
        OD
    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               #
    INT dp count := 0;
    # n = 0, p = 2 - the only possibility is 3                                #
    FOR i BY 2 TO 3 DO
        INT p = 2;
        IF p + 1 /= i THEN
            print( ( whole( i, -5 ) ) );
            dp count +:= 1
        FI
    OD;
    # n > 0, p > 2                                                            #
    FOR i FROM 5 BY 2 TO max number DO
        BOOL found := FALSE;
        FOR p TO UPB powers of 2 WHILE NOT found AND i > powers of 2[ p ] DO
            found := prime[ i - powers of 2[ p ] ]
        OD;
        IF NOT found THEN
            IF ( dp count +:= 1 ) <= 50 THEN
                print( ( whole( i, -5 ) ) );
                IF dp count MOD 10 = 0 THEN print( ( newline ) ) FI
            ELIF dp count = 1 000 OR dp count = 10 000 THEN
                print( ( "The ", whole( dp count, -5 )
                       , "th De Polignac number is ", whole( i, -7 )
                       , newline
                       )
                     )
            FI
        FI
    OD;
    print( ( "Found ", whole( dp count, 0 )
           , " De Polignac numbers up to ", whole( max number, 0 )
           , newline
           )
         )
END
Output:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 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

ALGOL W

Translation of: ALGOL 68
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                     %
    integer MAX_NUMBER;                     % maximum number we will consider %
    integer MAX_POWER;                      % maximum powerOf2 < MAX_NUMBER   %
    MAX_NUMBER := 500000;
    MAX_POWER  :=     20;
    begin
        logical array prime      ( 0 :: MAX_NUMBER );
        integer array powersOf2  ( 1 :: MAX_POWER  );
        integer dpCount;
        % sieve the primes to MAX_NUMBER                                      %
        begin
            integer rootMaxNumber;
            rootMaxNumber:= entier( sqrt( MAX_NUMBER ) );
            prime( 0 ) := prime( 1 ) := false;
            prime( 2 ) := true;
            for i := 3 step 2 until MAX_NUMBER do prime( i ) := true;
            for i := 4 step 2 until MAX_NUMBER do prime( i ) := false;
            for i := 3 step 2 until rootMaxNumber do begin
                if prime( i ) then begin
                    integer i2;
                    i2 := i + i;
                    for s := i * i step i2 until MAX_NUMBER do prime( s ) := false
                end if_prime_i_and_i_lt_rootMaxNumber
            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
            integer p2;
            p2 := 1;
            for i := 1 until 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 step 2 until 3 do begin
            integer p;
            p := 2;
            if p + 1 not = i then begin
                dpCount := dpCount + 1;
                writeon( i_w := 5, i )
            end if_p_plus_1_ne_i
        end for_i ;
        % n > 0, p > 2                                                        %
        for i := 5 step 2 until MAX_NUMBER do begin
            logical found;
            integer p;
            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
                    writeon( i_w := 5, i );
                    if dpCount rem 10 = 0 then write()
                    end
                else if dpCount = 1000 or dpCount = 10000 then begin
                    write( i_w := 5, s_w := 0, "The ", dpCount
                         , "th De Polignac number is ", i
                         )
                end if_various_DePolignac_numbers
            end if_not_found
        end for_i;
        write( i_w := 1, s_w := 0
             , "Found ", dpCount, " De Polignac numbers up to ", MAX_NUMBER
             )
    end
end.
Output:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 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

BASIC

BASIC256

Translation of: FreeBASIC
arraybase 0
maxNumber = 500000   # maximum number we will consider
maxPower  =     20   # maximum powerOf2 < maxNumber

dim powersOf2(maxPower)  # sieve the primes to maxNumber
dim prime(maxNumber)
prime[0] = false
prime[1] = false
prime[2] = true
for i = 3 to maxNumber step 2
	prime[i] = true
next i
for i = 4 to maxNumber-1 step 2
	prime[i] = false
next i

rootMaxNumber = sqr(maxNumber)
for i = 3 to rootMaxNumber step 2
	if prime[i] then
		i2 = i + i
		for s = i * i to maxNumber step i2
			prime[s] = false
		next s
	end if
next i

# table of powers of 2 greater than 2^0 (up to around 2 000 000)
#       increase the table size if maxNumber > 2 000 000
p2 = 1
for i = 1 to maxPower-1
	p2 *= 2
	powersOf2[i] = p2
next i

# 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
print "First 50 de Polignac numbers:"
dpCount = 0
for i = 1 to 3 step 2
	p = 2
	if p + 1 <> i then
		dpCount += 1
		print rjust(i,5);
	end if
next i
# n > 0, p > 2
for i = 5 to maxNumber step 2
	found = false
	p = 1
	while p <= maxPower and not found and i > powersOf2[p]
		found = prime[i - powersOf2[p]]
		p += 1
	end while
	if not found then
		dpCount += 1
		if dpCount <= 50 then
			print rjust(i,5);
			if dpCount mod 10 = 0 then print
		else
			if dpCount = 1000 or dpCount = 10000 then print "The "; rjust(dpCount,5); "th De Polignac number is "; i
		end if
	end if
next
print "Found "; dpCount; " De Polignac numbers up to "; maxNumber
Output:
Similar to FreeBASIC entry.

Chipmunk Basic

Works with: Chipmunk Basic version 3.6.4
Translation of: FreeBASIC
100 maxnumber = 500000 ' maximum number we will consider
110 maxpower = 20 ' maximum powerOf2 < maxNumber
120 dim powersof2(maxpower)' sieve the primes to maxNumber
130 dim prime(maxnumber)
140 prime(0) = false
150 prime(1) = false
160 prime(2) = true
170 for i = 3 to maxnumber step 2
180   prime(i) = true
190 next i
200 for i = 4 to maxnumber step 2
210   prime(i) = false
220 next i
230 rootmaxnumber = sqr(maxnumber)
240 for i = 3 to rootmaxnumber step 2
250   if prime(i) then
260     i2 = i+i
270     for s = i*i to maxnumber step i2
280       prime(s) = false
290     next s
300   endif
310 next i
320 ' table of powers of 2 greater than 2^0 (up to around 2 000 000)
330 '     increase the table size if maxNumber > 2 000 000
340 p2 = 1
350 for i = 1 to maxpower
360   p2 = p2*2
370   powersof2(i) = p2
380 next i
390 ' the numbers must be odd and not of the form p + 2^n
400 ' either p is odd and 2^n is even and hence n > 0 and p > 2
410 '   or 2^n is odd and p is even and hence n = 0 and p = 2
420 ' n = 0, p = 2 - the only possibility is 3
430 print "First 50 de Polignac numbers:"
440 dpcount = 0
450 for i = 1 to 3 step 2
460   p = 2
470   if p+1 <> i then
480     dpcount = dpcount+1
490     print using "#####";i;
500   endif
510 next i
520 ' n > 0, p > 2
530 for i = 5 to maxnumber step 2
540   found = false
550   p = 1
560   while p <= maxpower and  not found and i > powersof2(p)
570     found = prime(i-powersof2(p))
580     p = p+1
590   wend
600   if not found then
610     dpcount = dpcount+1
620     if dpcount <= 50 then print using "#####";i;
660     if dpcount = 1000 or dpcount = 10000 then
670       print : print "The ";
680       print using "#####";dpcount;
690       print "th De Polignac number is ";i;
700     endif
720   endif
730 next
740 print : print chr$(10);"Found ";dpcount;"De Polignac numbers up to ";maxnumber
750 end
Output:
Similar to FreeBASIC entry.

C

Translation of: Wren
#include <stdio.h>
#include <stdbool.h>
#include <locale.h>

bool isPrime(int n) {
    if (n < 2) return false;
    if (n%2 == 0) return n == 2;
    if (n%3 == 0) return n == 3;
    int d = 5;
    while (d*d <= n) {
        if (n%d == 0) return false;
        d += 2;
        if (n%d == 0) return false;
        d += 4;
    }
    return true;
}

int main() {
    int i, j, n, pows2[20], dp[50], dpc = 1, dp1000, dp10000, count, pow;
    bool found;
    for (i = 0; i < 20; ++i) pows2[i] = 1 << i;
    dp[0] = 1;
    for (n = 3, count = 1; count < 10000; n += 2) {
        found = false;
        for (j = 0; j < 20; ++j) {
            pow = pows2[j];
            if (pow > n) break;
            if (isPrime(n-pow)) {
                found = true;
                break;
            }
        }
        if (!found) {
            ++count;
            if (count <= 50) {
                dp[dpc++] = n;
            } else if (count == 1000) {
                dp1000 = n;
            } else if (count == 10000) {
                dp10000 = n;
            }
        }
    }
    setlocale(LC_NUMERIC, "");
    printf("First 50 De Polignac numbers:\n");
    for (i = 0; i < dpc; ++i) {
        printf("%'5d ", dp[i]);
        if (!((i+1)%10)) printf("\n");
    }
    printf("\nOne thousandth: %'d\n", dp1000);
    printf("\nTen thousandth: %'d\n", dp10000);
    return 0;
}
Output:
Same as Wren example.

C++

#include <iomanip>
#include <iostream>

bool is_prime(int n) {
    if (n < 2)
        return false;
    if (n % 2 == 0)
        return n == 2;
    if (n % 3 == 0)
        return n == 3;
    for (int p = 5; p * p <= n; p += 4) {
        if (n % p == 0)
            return false;
        p += 2;
        if (n % p == 0)
            return false;
    }
    return true;
}

bool is_depolignac_number(int n) {
    for (int p = 1; p < n; p <<= 1) {
        if (is_prime(n - p))
            return false;
    }
    return true;
}

int main() {
    std::cout.imbue(std::locale(""));
    std::cout << "First 50 de Polignac numbers:\n";
    for (int n = 1, count = 0; count < 10000; n += 2) {
        if (is_depolignac_number(n)) {
            ++count;
            if (count <= 50)
                std::cout << std::setw(5) << n
                          << (count % 10 == 0 ? '\n' : ' ');
            else if (count == 1000)
                std::cout << "\nOne thousandth: " << n << '\n';
            else if (count == 10000)
                std::cout << "\nTen thousandth: " << n << '\n';
        }
    }
}
Output:
First 50 de Polignac numbers:
    1   127   149   251   331   337   373   509   599   701
  757   809   877   905   907   959   977   997 1,019 1,087
1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549
1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807
1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213

One thousandth: 31,941

Ten thousandth: 273,421

Delphi

Works with: Delphi version 6.0

Uses a little algebra to simplify the code. {We are looking for 2^I + Prime = N therefore this 2^I - N should be prime if N is not a De Polignac number. Run Time: 111 ms on a Rizen 7 processor.

function IsPrime(N: integer): boolean;
{Fast, optimised prime test}
var I,Stop: integer;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
     begin
     I:=5;
     Stop:=Trunc(sqrt(N));
     Result:=False;
     while I<=Stop do
           begin
           if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
           Inc(I,6);
           end;
     Result:=True;
     end;
end;


function IsPolignac(N: integer): boolean;
{We are looking for 2^I + Prime = N
Therefore this 2^I - N should be prime}
var Pw2: integer;
begin
Result:=False;
Pw2:=1;
{Test all powers of less than N}
while Pw2<N do
	begin
	{If the difference is prime, it is not Polignac}
	if IsPrime(N-Pw2) then exit;
	Pw2:=Pw2 shl 1;
	end;
Result:=True;
end;


procedure ShowPolignacNumbers(Memo: TMemo);
{Show the first 50, 1000th and 10,000th Polignac numbers}
var I,Cnt: integer;
var S: string;
begin
Memo.Lines.Add('First 50 Polignac numbers:');
I:=1; Cnt:=0; S:='';
{Iterate through all odd numbers}
while true do
	begin
	if IsPolignac(I) then
		begin
		S:=S+Format('%10.0n',[I*1.0]);
		Inc(Cnt);
		if (Cnt mod 10)=0 then
			begin
			Memo.Lines.Add(S);
			S:='';
			end;

		end;
	Inc(I,2);
	if Cnt>=50 then break;
	end;
if S<>'' then Memo.Lines.Add(IntToStr(I));
while true do
	begin
	if IsPolignac(I) then
		begin
		Inc(Cnt);
		if Cnt=1000 then Memo.Lines.Add('1,000th = '+Format('%10.0n',[I*1.0]));
		if Cnt=10000 then
			begin
			Memo.Lines.Add('10,000th = '+Format('%10.0n',[I*1.0]));
			break;
			end;
		end;
	Inc(I,2);
	end;
end;
Output:
First 50 Polignac numbers:
         1       127       149       251       331       337       373       509       599       701
       757       809       877       905       907       959       977       997     1,019     1,087
     1,199     1,207     1,211     1,243     1,259     1,271     1,477     1,529     1,541     1,549
     1,589     1,597     1,619     1,649     1,657     1,719     1,759     1,777     1,783     1,807
     1,829     1,859     1,867     1,927     1,969     1,973     1,985     2,171     2,203     2,213
1,000th =     31,941
10,000th =    273,421

EasyLang

Translation of: C
func isprim num .
   i = 2
   while i <= sqrt num
      if num mod i = 0
         return 0
      .
      i += 1
   .
   return 1
.
p = 2
for i to 20
   pow2[] &= p
   p *= 2
.
n = 1
while count < 50
   j = 1
   repeat
      p = pow2[j]
      until p > n or isprim (n - p) = 1
      j += 1
   .
   if p > n
      count += 1
      print n
   .
   n += 2
.

Euler

Basic task only.
Based on the Algol W sample, but as 3 is clearly not a de Polignac number, only considers odd primes.

begin new isOddPrime; 
    isOddPrime
        <- ` formal n;
             if n mod 2 = 0
             then false
             else begin
                 new prime; new f; new f2; new toNext; label primeLoop;
                 prime  <- true;
                 f      <-    3;
                 f2     <-    9;
                 toNext <-   16;
primeLoop:       if f2 <= n and prime then begin
                     prime  <- n mod f <> 0;
                     f      <- f + 2;
                     f2     <- toNext;
                     toNext <- toNext + 8;
                 goto primeLoop end else 0;
                 prime
             end
           ';
    begin new n; new count; label forI;
        count    <- 0;
        n        <- -1;
forI:   if begin n <- n + 2; count < 50 end then begin
            new found; new p; new powerOf2; label p2Loop;
            found    <- false;
            powerOf2 <- 1;
p2Loop:     if not found and n > powerOf2 then begin
                found    <- isOddPrime( n - powerOf2 );
                powerOf2 <- powerOf2 * 2;
            goto p2Loop end else 0;
            if not found then begin
                count <- count + 1;
                out n
            end else 0;
        goto forI end else 0
    end

end $
Output:
    NUMBER                   1
    NUMBER                 127
    NUMBER                 149
    ...
    NUMBER                2171
    NUMBER                2203
    NUMBER                2213

FreeBASIC

Translation of: ALGOL W
' find some De Polignac numbers - positive odd numbers that can't be
' written as p + 2^n for some prime p and integer n
Const maxNumber = 500000    ' maximum number we will consider
Const maxPower  =     20    ' maximum powerOf2 < maxNumber

Dim As Uinteger powersOf2(1 To maxPower)    ' sieve the primes to maxNumber
Dim As Boolean prime(0 To maxNumber)

Dim As Integer rootMaxNumber = Sqr(maxNumber)
Dim As Integer i, s

prime(0) = false
prime(1) = false
prime(2) = true
For i = 3 To maxNumber Step 2
    prime(i) = true
Next i
For i = 4 To maxNumber Step 2
    prime(i) = false
Next i
For i = 3 To rootMaxNumber Step 2
    If prime(i) Then
        Dim As Integer i2 = i + i
        For s = i * i To maxNumber  Step i2
            prime(s) = false
        Next s
    End If
Next i

' table of powers of 2 greater than 2^0 (up to around 2 000 000)
'       increase the table size if maxNumber > 2 000 000
Dim As Integer p2 = 1
For i = 1 To maxPower
    p2 *= 2
    powersOf2(i) = p2
Next i

' 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
Dim As Uinteger dpCount = 0
For i = 1 To 3 Step 2
    Dim As Integer p = 2
    If p + 1 <> i Then 
        dpCount += 1
        Print Using "#####"; i;
    End If
Next i
' n > 0, p > 2
For i = 5 To maxNumber Step 2
    Dim As Boolean found = false
    Dim As Integer p = 1
    While p <= maxPower And Not found And i > powersOf2(p)
        found = prime(i - powersOf2(p))
        p += 1
    Wend
    If Not found Then
        dpCount += 1
        If dpCount <= 50 Then
            Print Using "#####"; i;
            If dpCount Mod 10 = 0 Then Print
        Elseif dpCount = 1000 Or dpCount = 10000 Then
            Print Using "The #####th De Polignac number is ######"; dpCount; i
        End If
    End If
Next
Print "Found "; dpCount; " De Polignac numbers up to "; maxNumber
Sleep
Output:
Same as ALGOL W entry.

Go

Translation of: Wren
Library: Go-rcu
package main

import (
    "fmt"
    "rcu"
)

func main() {
    pows2 := make([]int, 20)
    for i := 0; i < 20; i++ {
        pows2[i] = 1 << i
    }
    dp := []int{1}
    dp1000, dp10000 := 0, 0
    for n, count := 3, 1; count < 10000; n += 2 {
        found := false
        for _, pow := range pows2 {
            if pow > n {
                break
            }
            if rcu.IsPrime(n - pow) {
                found = true
                break
            }
        }
        if !found {
            count++
            if count <= 50 {
                dp = append(dp, n)
            } else if count == 1000 {
                dp1000 = n
            } else if count == 10000 {
                dp10000 = n
            }
        }
    }
    fmt.Println("First 50 De Polignac numbers:")
    rcu.PrintTable(dp, 10, 5, true)
    fmt.Printf("\nOne thousandth: %s\n", rcu.Commatize(dp1000))
    fmt.Printf("\nTen thousandth: %s\n", rcu.Commatize(dp10000))
}
Output:
Same as Wren example.

J

Implementation:

depolignac=: (1+i.@>.&.-:) (-.,) i.@>.&.(2&^.) +/ i.&.(p:inv)

Task example:

   5 10$depolignac 3000
   1  127  149  251  331  337  373  509  599  701
 757  809  877  905  907  959  977  997 1019 1087
1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

Stretch:

   T=: depolignac 3e5
   999 { T
31941
   9999 { T
273421

(We use 999 here for the 1000th number because 0 is the first J index.)

Java

public final class DePolignacNumbers {

	public static void main(String[] args) {
	    System.out.println("The first 50 de Polignac numbers:");
	    for ( int n = 1, count = 0; count < 10_000; n += 2 ) {
	        if ( isDePolignacNumber(n) ) {
	            count += 1;
	            if ( count <= 50 ) {
	                System.out.print(String.format("%5d%s", n, ( count % 10 == 0 ? "\n" : " ") ));
	            } else if ( count == 1_000 ) {
	            	System.out.println();
	                System.out.println("The 1,000th de Polignac number: " + n);
	            } else if ( count == 10_000 ) {
	            	System.out.println();
	                System.out.println("The 10,000th de Polignac number: " + n);
	            }
	        }
	    }
	}
	
	private static boolean isDePolignacNumber(int number) {
	    for ( int p = 1; p < number; p <<= 1 ) {
	        if ( isPrime(number - p) ) {
	            return false;
	        }
	    }
	    return true;
	}
	
	private static boolean isPrime(int number) {
		if ( number < 2 ) {
			return false;
		}
		if ( number % 2 == 0 ) {
			return number == 2;
		}
		if ( number % 3 == 0 ) {
			return number == 3;
		}
		
		int delta = 2;
		int k = 5;
		while ( k * k <= number ) {
		    if ( number % k == 0 ) {
		    	return false;
		    }
		    k += delta;
		    delta = 6 - delta;
		}
		return true;
	}
	
}
Output:
The first 50 de Polignac numbers:
    1   127   149   251   331   337   373   509   599   701
  757   809   877   905   907   959   977   997  1019  1087
 1199  1207  1211  1243  1259  1271  1477  1529  1541  1549
 1589  1597  1619  1649  1657  1719  1759  1777  1783  1807
 1829  1859  1867  1927  1969  1973  1985  2171  2203  2213

The 1,000th de Polignac number: 31941

The 10,000th de Polignac number: 273421

jq

Works with: jq
# Input should be an integer
def isPrime:
  . as $n
  | if    ($n < 2)      then false
    elif ($n % 2 == 0)  then $n == 2
    elif ($n % 3 == 0)  then $n == 3
    else 5
    | until( . <= 0;
        if .*. > $n then -1
	elif ($n % . == 0) then 0
        else . + 2
        |  if ($n % . == 0) then 0
           else . + 4
           end
        end)
     | . == -1
     end;

# Generate the stream of de Polignac integers:
def dePolignacs:
  1,
  ( range(3; infinite; 2) as $n
    | first(
        foreach range(0; infinite) as $i (null;
        if . == null then 1 else .*2 end;
        if . > $n then $n
        elif ($n - .) | isPrime
        then -1
        else empty
        end) )
    | select(.>0) ) ;

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

def task($n):
  (label $out
   | foreach dePolignacs as $i ({};
       .count += 1
       | if .count <= 50
         then .dp += [$i]
         elif .count == 1000
         then .dp1000 = $i
         elif .count == 10000
         then .dp10000 = $i
         else .
         end;
	   if .count == 10000 then ., break $out else empty end))
   | "The first \($n) de Polignac numbers:",
     (.dp | _nwise(10) | map(lpad(4)) | join(" ")),
     "\nThe  1,000th: \(.dp1000)",
     "\nThe 10,000th: \(.dp10000)";

task(50)

Invocation: jq -nrc -f de-polignac.jq

Output:
The first 50 de Polignac numbers:
   1  127  149  251  331  337  373  509  599  701
 757  809  877  905  907  959  977  997 1019 1087
1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

The  1,000th: 31941

The 10,000th: 273421

Julia

  • Needs Primes.jl
using Primes
using Printf

function isdepolignac(n::Integer)
    iseven(n) && return false

    twopows = Iterators.map(x -> 2^x, 0:floor(Int, log2(n)))

    return !any(twopows) do twopow
        isprime(n - twopow)
    end
end

function depolignacs()
    naturals = Iterators.countfrom()
    return Iterators.filter(isdepolignac, naturals)
end


for (i, dep) in Iterators.enumerate(depolignacs())
    if i == 1
        println("The first 50 de Polignac numbers:")
    end

    if i <= 50
        @printf "%4d" dep
        i % 10 == 0 ? println() : print(" ")
    end

    if i == 50
        println()
    end

    if i == 1000
        println("The 1000th de Polignac number is $dep")
        println()
    end

    if i == 10000
        println("The 10000th de Polignac number is $dep")
        break
    end
end
The first 50 de Polignac numbers:
   1  127  149  251  331  337  373  509  599  701
 757  809  877  905  907  959  977  997 1019 1087
1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

The 1000th de Polignac number is 31941

The 10000th de Polignac number is 273421

Mathematica /Wolfram Language

Translation of: Julia
IsDePolignac[n_Integer] := Module[{twoPows},
    If[EvenQ[n], Return[False]];
    twoPows = 2^Range[0, Floor[Log2[n]]];
    Not[Or @@ (PrimeQ[n - #] & /@ twoPows)]
]

DePolignacs[] := Module[{naturals = 1},
    Select[Table[naturals++, {i, 1, 280000}], IsDePolignac]
]

dePolignacNumbers = DePolignacs[];

Print["The first 50 de Polignac numbers:", Take[dePolignacNumbers, 50]];

Print["The 1000th de Polignac number is ", dePolignacNumbers[[1000]]];

Print["The 10000th de Polignac number is ", dePolignacNumbers[[10000]]];
Output:
The first 50 de Polignac numbers:{1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, 1529, 1541, 1549, 1589, 1597, 1619, 1649, 1657, 1719, 1759, 1777, 1783, 1807, 1829, 1859, 1867, 1927, 1969, 1973, 1985, 2171, 2203, 2213}
The 1000th de Polignac number is 31941
The 10000th de Polignac number is 273421

Nim

import std/[algorithm, math, strformat]

const N = 500_000

func initPrimes(lim: Natural): seq[int] =
  ## Build list of primes using a sieve of Erathostenes.
  var composite = newSeq[bool]((lim + 1) shr 1)
  composite[0] = true
  for n in countup(3, int(sqrt(lim.toFloat)), 2):
    if not composite[n shr 1]:
      for k in countup(n * n, lim, 2 * n):
        composite[k shr 1] = true
  result.add 2
  for n in countup(3, lim, 2):
    if not composite[n shr 1]:
      result.add n

func initPowers(lim: Natural): seq[int] =
  ## Build list of powers of 2.
  var n = 1
  for i in 0..log2(N.toFloat).int:
    result.add n
    n = n shl 1

func initDePolignac(primes, powers: seq[int]): seq[int] =
  ## Build list of de Polignac numbers using a sieve
  ## for odd numbers.
  var sieve: array[0..(N div 2), bool]
  sieve.fill(true)
  for p1 in primes:
    for p2 in powers:
      if p1 + p2 <= N:
        sieve[(p1 + p2) shr 1] = false
  for i, isDePolignac in sieve:
    if isDePolignac:
      result.add i shl 1 + 1

let primes = initPrimes(N)
let powers = initPowers(N)
let dePolignac = initDePolignac(primes, powers)

echo "First 50 de Polignac numbers:"
for i in 0..49:
  stdout.write &"{dePolignac[i]:>4}"
  stdout.write if i mod 10 == 9: '\n' else: ' '
echo()

for i in [1000, 10000]:
  echo &"The {i:>5}th de Polignac number is {dePolignac[i-1]:>6}"
Output:
First 50 de Polignac numbers:
   1  127  149  251  331  337  373  509  599  701
 757  809  877  905  907  959  977  997 1019 1087
1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

The  1000th de Polignac number is  31941
The 10000th de Polignac number is 273421

Pascal

Free Pascal

Translation of: Delphi

slightly modified for console

program DePolignacNum;
{$IFDEF FPC}{$MODE DELPHI}{$Optimization ON,ALL} {$ENDIF}
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
uses
  sysutils;

function IsPrime(n: Uint32): boolean;
{Fast, optimised prime test}
const
  DeltaMOD235: array[0..7] of Uint32 =(4,2,4,2,4,6,2,6);
var
  pr,idx : NativeUint;
begin
  if n < 32 then
    Exit(n in [2,3,5,7,11,13,17,19,23,29,31]);
  IF n AND 1 = 0 then EXIT(false);
  IF n mod 3 = 0 then EXIT(false);
  IF n mod 5 = 0 then EXIT(false);
  pr := 7;
  idx := 0;
  repeat
    if sqr(pr) >n then
      EXIT(true);
    if n mod pr = 0 then
      EXIT(false);
    pr += DeltaMOD235[idx];
    idx := (idx+1) AND 7;
  until false;
end;

function IsPolignac(N: Uint32): boolean;
{We are looking for 2^I + Prime = N
Therefore this 2^I - N should be prime}
var
  Pw2: Uint32;
begin
  Pw2:=1;
  {Test all powers of less than N}
  while Pw2<N do
  begin
    {If the difference is prime, it is not Polignac}
    if IsPrime(N-Pw2) then
      EXIT(false);
    //Pw2:=Pw2 shl 1;
    Pw2 +=Pw2;
  end;
  Result:=True;
end;

procedure ShowPolignacNumbers;
{Show the first 50, 1000th and 10,000th Polignac numbers}
var
  I,Cnt,lmt: Uint32;
  S: string;
begin
  writeln('First 50 Polignac numbers:');
  I:=1; Cnt:=0; S:='';
  {Iterate through all odd numbers}
  lmt := 10;
  while true do
  begin
    if IsPolignac(I) then
    begin
      S:=S+Format('%6.0n',[I*1.0]);
      Inc(Cnt);
      if Cnt = lmt then
      begin
        writeln(S);
        S:='';
        inc(lmt,10);
      end;
    end;
    Inc(I,2);
    if Cnt>=50 then break;
  end;
  writeln;

  lmt := 100;
  repeat
    if IsPolignac(I) then
    begin
      Inc(Cnt);
      if Cnt=lmt then
      begin
        writeln(Format('%10.0nth %10.0n',[cnt*1.0,I*1.0]));
        lmt *= 10;
        if lmt > 10000 then
          BREAK;
      end;
    end;
    Inc(I,2);
  until false;
end;

var
  T : Int64;
BEGIN
  //wait for change in GetTickCount64
  T := GetTickCount64+1;repeat until T <= GetTickCount64;
  ShowPolignacNumbers;
  Writeln(GetTickCount64-T,' ms');
end.
@TIO.RUN:
First 50 Polignac numbers:
     1   127   149   251   331   337   373   509   599   701
   757   809   877   905   907   959   977   997 1,019 1,087
 1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549
 1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807
 1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213

       100th      4,153
     1,000th     31,941
    10,000th    273,421
162 ms // 32 ms @home Ryzen 5600G on Linux 64-bit

Perl

Library: ntheory
use v5.36;
use ntheory <is_prime vecmax vecany logint>;

sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub table ($c, @V) { my $t = $c * (my $w = 2 + vecmax map { length } @V); ( sprintf( ('%'.$w.'s')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }

my ($n, @D) = (3, 1);
while ($n++) {
    next unless $n % 2;
    next if vecany { is_prime($n - (1 << $_)) } reverse(1 .. logint($n, 2));
    push @D, comma $n;
    last if 10_000 == @D;
}

say "First fifty de Polignac numbers:\n" . table 10, @D[0..49];
say 'One thousandth: ' . $D[ 999];
say 'Ten thousandth: ' . $D[9999];
Output:
First fifty de Polignac numbers:
      1    127    149    251    331    337    373    509    599    701
    757    809    877    905    907    959    977    997  1,019  1,087
  1,199  1,207  1,211  1,243  1,259  1,271  1,477  1,529  1,541  1,549
  1,589  1,597  1,619  1,649  1,657  1,719  1,759  1,777  1,783  1,807
  1,829  1,859  1,867  1,927  1,969  1,973  1,985  2,171  2,203  2,213

One thousandth: 31,941
Ten thousandth: 273,421

Phix

Translation of: Python
with javascript_semantics
constant MAX_VALUE = 1_000_000,
        all_primes = get_primes_le(MAX_VALUE),
       powers_of_2 = sq_power(2,tagset(floor(log2(MAX_VALUE)),0))
sequence allvalues = repeat(true,MAX_VALUE),
        dePolignac = {}

for i in all_primes do
    for j in powers_of_2 do
        if i + j < MAX_VALUE then
            allvalues[i + j] = false
        end if
    end for
end for
for n=1 to MAX_VALUE by 2 do
    if allvalues[n] then dePolignac &= n end if
end for

printf(1,"First fifty de Polignac numbers:\n%s\n",{join_by(dePolignac[1..50],1,10,"",fmt:="%5d")})
printf(1,"One thousandth: %,d\n",dePolignac[1000])
printf(1,"Ten thousandth: %,d\n",dePolignac[10000])
Output:
First fifty de Polignac numbers:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

One thousandth: 31,941
Ten thousandth: 273,421

alternative

No magic constant or arbitrary limit, but about seven times slower. Based on Wren/Raku, same output as above.

with javascript_semantics
sequence depolignac = {1}
function dePolignac(integer n)
    -- return the nth depolignac number
    integer t = depolignac[$]+2
    while length(depolignac)<n do
        integer p2 = 1
        bool found = false
        while p2<t do
            if is_prime(t-p2) then
                found = true
                exit
            end if
            p2 *= 2
        end while
        if not found then
            depolignac &= t
        end if
        t += 2
    end while
    return depolignac[n]
end function

printf(1,"First fifty de Polignac numbers:\n%s\n",{join_by(apply(tagset(50),dePolignac),1,10,"",fmt:="%5d")})
printf(1,"One thousandth: %,d\n",dePolignac(1000))
printf(1,"Ten thousandth: %,d\n",dePolignac(10000))

PL/M

Based on the ALGOL 68 sample.

Works with: 8080 PL/M Compiler

... under CP/M (or an emulator)

100H: /* FIND SOME DE POLIGNAC NUMBERS - POSITIVE ODD NUMBERS THAT CAN'T BE  */
      /* WRITTEN AS P + 2**N FOR SOME PRIME P AND INTEGER N                  */

   DECLARE FALSE LITERALLY '0', TRUE LITERALLY '0FFH';

   /* CP/M SYSTEM CALL AND I/O ROUTINES                                      */
   BDOS:      PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
   PR$CHAR:   PROCEDURE( C ); DECLARE C BYTE;    CALL BDOS( 2, C );  END;
   PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S );  END;
   PR$NL:     PROCEDURE;   CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
   PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH  */
      DECLARE N ADDRESS;
      DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
      V = N;
      W = LAST( N$STR );
      N$STR( W ) = '$';
      N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      DO WHILE( ( V := V / 10 ) > 0 );
         N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      END;
      CALL PR$STRING( .N$STR( W ) );
   END PR$NUMBER;
   /* END SYSTEM CALL AND I/O ROUTINES                                       */

   DECLARE MAX$DP        LITERALLY '4000', /* MAXIMUM NUMBER TO CONSIDER     */
           MAX$DP$PLUS$1 LITERALLY '4001'; /* MAX$DP + 1 FOR ARRAY BOUNDS    */

   /* SIEVE THE PRIMES TO MAX$DP                                             */
   DECLARE PRIME ( MAX$DP$PLUS$1 )BYTE;
   DO;
      DECLARE ( I, S ) ADDRESS;
      PRIME( 0 ),  PRIME( 1 ) = FALSE;
      PRIME( 2 ) = TRUE;
      DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE;  END;
      DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;
      DO I = 3 TO LAST( PRIME ) / 2 BY 2;
         IF PRIME( I ) THEN DO;
            DO S = I + I TO LAST( PRIME ) BY I; PRIME( S ) = FALSE; END;
         END;
      END;
   END;

   /* TABLE OF POWERS OF 2 UP TO MAX$DP                                      */
   DECLARE POWERS$OF$2 ( 12 )ADDRESS
           INITIAL( 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 );

   /* DISPLAYS A DE POLIGNAC NUMBER, IF NECESSARY                            */
   SHOW$DE$POLIGNAC: PROCEDURE( DP$NUMBER );
      DECLARE ( DP$NUMBER ) ADDRESS;
      CALL PR$CHAR( ' ' );
      IF DP$NUMBER <   10 THEN CALL PR$CHAR( ' ' );
      IF DP$NUMBER <  100 THEN CALL PR$CHAR( ' ' );
      IF DP$NUMBER < 1000 THEN CALL PR$CHAR( ' ' );
      CALL PR$NUMBER( DP$NUMBER );
   END SHOW$DE$POLIGNAC;

   DECLARE ( I, P, COUNT ) ADDRESS;
   DECLARE FOUND BYTE;

   /* 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                            */
   DO I = 1 TO 3 BY 2;
      P = 2;
      IF P + 1 <> I THEN DO;
         COUNT = COUNT + 1;
         CALL SHOW$DE$POLIGNAC( I );
      END;
   END;
   /* N > 0, P > 2                                                        */
   I = 3;
   DO WHILE I < MAX$DP AND COUNT < 50;
      I = I + 2;
      FOUND = FALSE;
      P = 1;
      DO WHILE NOT FOUND
           AND P <= LAST( POWERS$OF$2 )
           AND I > POWERS$OF$2( P );
         FOUND = PRIME( I - POWERS$OF$2( P ) );
         P     = P + 1;
      END;
      IF NOT FOUND THEN DO;
         CALL SHOW$DE$POLIGNAC( I );
         IF ( COUNT := COUNT + 1 ) MOD 10 = 0 THEN CALL PR$NL;
      END;
   END;

EOF
Output:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

Python

''' Rosetta code rosettacode.org/wiki/De_Polignac_numbers '''

from sympy import isprime
from math import log
from numpy import ndarray

max_value = 1_000_000

all_primes = [i for i in range(max_value + 1) if isprime(i)]
powers_of_2 = [2**i for i in range(int(log(max_value, 2)))]

allvalues = ndarray(max_value, dtype=bool)
allvalues[:] = True

for i in all_primes:
    for j in powers_of_2:
        if i + j < max_value:
            allvalues[i + j] = False
        
dePolignac = [n for n in range(1, max_value) if n & 1 == 1 and allvalues[n]]

print('First fifty de Polignac numbers:')
for i, n in enumerate(dePolignac[:50]):
    print(f'{n:5}', end='\n' if (i + 1) % 10 == 0 else '')
    
print(f'\nOne thousandth: {dePolignac[999]:,}')
print(f'\nTen thousandth: {dePolignac[9999]:,}')
Output:
First fifty de Polignac numbers:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

One thousandth: 31,941

Ten thousandth: 273,421

Quackery

from, index, end, and incr are defined at Loops/Increment loop index within loop body#Quackery.

isprime is defined at Primality by trial division#Quackery.

  [ true swap
    1 from
      [ index over > iff
          end done
        dup index -
        isprime if
          [ dip not end ]
        index incr ]
    drop ]                is depolignac ( n --> b )

  [] 1 from
    [ index depolignac if
        [ index join ]
      dup size 50 = if 
        end
      2 incr ]
  echo
Output:
[ 1 127 149 251 331 337 373 509 599 701 757 809 877 905 907 959 977 997 1019 1087 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213 ]

Raku

use List::Divvy;
use Lingua::EN::Numbers;
constant @po2 = (1..∞).map: 2 ** *;
my @dePolignac = lazy 1, |(2..∞).hyper.map(* × 2 + 1).grep: -> $n { all @po2.&upto($n).map: { !is-prime $n - $_ } };

say "First fifty de Polignac numbers:\n" ~ @dePolignac[^50]».&comma».fmt("%5s").batch(10).join: "\n";
say "\nOne thousandth: " ~ comma @dePolignac[999];
say "\nTen thousandth: " ~ comma @dePolignac[9999];
Output:
First fifty de Polignac numbers:
    1   127   149   251   331   337   373   509   599   701
  757   809   877   905   907   959   977   997 1,019 1,087
1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549
1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807
1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213

One thousandth: 31,941

Ten thousandth: 273,421

RPL

Polignac really made a fool of himself for all time by writing to the French Academy of Science that he had verified his "theorem" up to 3,000,000. To make the search faster, RPL flag management features (CF, SF and FC? instructions) are used to exit loops when the remainder of (n - 2^k) is not prime.

Works with: Halcyon Calc version 4.2.7
IF DUP 5 ≤ THEN 
     { 2 3 5 } SWAP POS SIGN 
  ELSE
     IF DUP 2 MOD NOT THEN 2
     ELSE
        DUP √ CEIL → lim 
        ≪ 3 
           WHILE DUP2 MOD OVER lim ≤ AND REPEAT 2 + ENDEND
     MOD SIGN
  END
≫ 'PRIM?' STO 

≪ → n 
  ≪ { 1 } 3 
     DO 
       1 CF 
       DUP LN 2 LN / FLOOR 
       WHILE DUP 0 ≥ 1 FC? AND REPEAT 
           2 OVER ^ 3 PICK SWAP - 
           IF PRIM? THEN 1 SF END
           1 - 
       END DROP
       IF 1 FC? THEN DUP ROT SWAP + SWAP END
       2 + 
     UNTIL OVER SIZE n == END 
     DROP
 ≫ ≫ 'DPFAIL' STO
50 DPFAIL
Output:
1: { 1 127 149 251 331 337 373 509 599 701 757 809 877 905 907 959 977 997 1019 1087 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807 1829 1859 1867 1927 1969 1973 1985 2171 2203 }

Ruby

Using Thundergnats observation that it is enough to subtract powers of 2 and verify that none of the results is prime.

require 'prime'

def pow2floor(n)
  n.bit_length-1
end

def polignac?(n)
  (0..pow2floor(n)).none? {|exp| (n-(1 << exp)).prime? }
end

polignacs =  (1..).step(2).lazy.select{|n| polignac?(n)}.first(10000)

puts "first #{n = 50} de Polignac numbers:"
polignacs[0...n].each_slice(10){|s| puts "%5d"*s.size % s}
[1000, 10000].each{|n| puts "\n#{n}: #{polignacs[n-1]}"}
Output:
first 50 de Polignac numbers:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

1000: 31941

10000: 273421

Scala

Translation of: Java
object DePolignacNumbers extends App {

  println("The first 50 de Polignac numbers:")
  Stream.from(1, 2).filter(isDePolignacNumber).take(10000).zipWithIndex.foreach {
    case (number, index) =>
      val count = index + 1
      if (count <= 50) {
        print(f"$number%5d" + (if (count % 10 == 0) "\n" else " "))
      } else if (count == 1000) {
        println()
        println(s"The 1,000th de Polignac number: $number")
      } else if (count == 10000) {
        println()
        println(s"The 10,000th de Polignac number: $number")
      }
  }

  def isDePolignacNumber(number: Int): Boolean = {
    Iterator.iterate(1)(_ << 1).takeWhile(_ < number).forall(p => !isPrime(number - p))
  }

  def isPrime(number: Int): Boolean = number match {
    case n if n < 2 => false
    case 2 | 3 => true
    case n if n % 2 == 0 || n % 3 == 0 => false
    case _ =>
      Stream.from(5, 2).takeWhile(k => k * k <= number)
        .filter(k => number % k == 0 || number % (k + 2) == 0)
        .isEmpty
  }

}
Output:
The first 50 de Polignac numbers:
    1   127   149   251   331   337   373   509   599   701
  757   809   877   905   907   959   977   997  1019  1087
 1199  1207  1211  1243  1259  1271  1477  1529  1541  1549
 1589  1597  1619  1649  1657  1719  1759  1777  1783  1807
 1829  1859  1867  1927  1969  1973  1985  2171  2203  2213

The 1,000th de Polignac number: 31941

The 10,000th de Polignac number: 273421


Sidef

Translation of: Ruby
var polignacs = (1..Inf -> by(2).lazy.grep {|n|
    RangeNum(n.ilog2, 0, -1).none {|k| n - (1<<k) -> is_prime }
})

with (50) {|n|
    say ("first #{n} de Polignac numbers:")
    polignacs.first(n).slices(10).each{|s| say("%5d"*s.len % s...) }
}

say ''; [1000, 10000].each{|n|
    say "#{n}th de Polignac number: #{polignacs.nth(n)}"
}
Output:
first 50 de Polignac numbers:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213

1000th de Polignac number: 31941
10000th de Polignac number: 273421

Wren

Library: Wren-math
Library: Wren-fmt
import "./math" for Int
import "./fmt" for Fmt

var pows2 = (0..19).map { |i| 1 << i }.toList
var dp = [1]
var dp1000
var dp10000
var count = 1
var n = 3
while (true) {
    var found = false
    for (pow in pows2) {
        if (pow > n) break
        if (Int.isPrime(n-pow)) {
            found = true
            break
        }
    }
    if (!found) {
        count = count + 1
        if (count <= 50) {
            dp.add(n)
        } else if (count == 1000) {
            dp1000 = n
        } else if (count == 10000) {
            dp10000 = n
            break
        }
    }
    n = n + 2
}
System.print("First 50 De Polignac numbers:")
Fmt.tprint("$,5d", dp, 10)
Fmt.print("\nOne thousandth: $,d", dp1000)
Fmt.print("\nTen thousandth: $,d", dp10000)
Output:
First 50 De Polignac numbers:
    1   127   149   251   331   337   373   509   599   701 
  757   809   877   905   907   959   977   997 1,019 1,087 
1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549 
1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807 
1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213 

One thousandth: 31,941

Ten thousandth: 273,421

XPL0

Slow. Takes 225 seconds on Pi4.

func IsPrime(N);        \Return 'true' if N is prime
int  N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
    [if rem(N/I) = 0 then return false;
    I:= I+1;
    ];
return true;
];

func IsDePolignac(N);   \Return 'true' if N is a de Polignac number
int  N, P, T;
[for P:= N-1 downto 2 do
    if IsPrime(P) then
        [T:= 1;
        repeat  if T+P = N then return false;
                T:= T<<1;
        until   T+P > N;
        ];
return true;
];

int N, C;
[Format(5, 0);
N:= 1;  C:= 0;
loop    [if IsDePolignac(N) then
            [C:= C+1;
            if C<=50 or C=1000 or C=10000 then
                [RlOut(0, float(N));
                if rem(C/10) = 0 then CrLf(0);
                if C = 10000 then quit;
                ];
            ];
        N:= N+2;
        ];
]
Output:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 1859 1867 1927 1969 1973 1985 2171 2203 2213
31941
273421

Translation of: ALGOL W

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
Output:
    1  127  149  251  331  337  373  509  599  701
  757  809  877  905  907  959  977  997 1019 1087
 1199 1207 1211 1243 1259 1271 1477 1529 1541 1549
 1589 1597 1619 1649 1657 1719 1759 1777 1783 1807
 1829 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
Cookies help us deliver our services. By using our services, you agree to our use of cookies.