De Polignac numbers: Difference between revisions
Add Mathematica/Wolfram Language implementation
(Added XPL0 example.) |
(Add Mathematica/Wolfram Language implementation) |
||
| (37 intermediate revisions by 21 users not shown) | |||
Line 1:
{{
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.
Line 27:
;* [[oeis:A006285|OEIS:A006285 - Odd numbers not of form p + 2^k (de Polignac numbers)]]
=={{header|11l}}==
{{trans|C++}}
<syntaxhighlight lang="11l">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Action!}}==
{{Trans|PL/M}}
which is based on the ALGOL 68 sample.
{{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>
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
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">
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.
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vb">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</syntaxhighlight>
{{out}}
<pre>Similar to FreeBASIC entry.</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|FreeBASIC}}
<syntaxhighlight lang="qbasic">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</syntaxhighlight>
{{out}}
<pre>Similar to FreeBASIC entry.</pre>
=={{header|C}}==
{{trans|Wren}}
<syntaxhighlight lang="c">#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;
}</syntaxhighlight>
{{out}}
<pre>
Same as Wren example.
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#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';
}
}
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
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.
<syntaxhighlight lang="Delphi">
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;
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight lang=easylang>
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
.
</syntaxhighlight>
=={{header|Euler}}==
Basic task only.<br/>
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''' $
{{out}}
<pre>
NUMBER 1
NUMBER 127
NUMBER 149
...
NUMBER 2171
NUMBER 2203
NUMBER 2213
</pre>
=={{header|FreeBASIC}}==
{{trans|ALGOL W}}
<syntaxhighlight lang="freebasic">' 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</syntaxhighlight>
{{out}}
<pre>Same as ALGOL W entry.</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<syntaxhighlight lang="go">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))
}</syntaxhighlight>
{{out}}
<pre>
Same as Wren example.
</pre>
=={{header|J}}==
Line 45 ⟶ 904:
273421</syntaxhighlight>
(We use 999 here for the 1000th number because 0 is the first J index.)
=={{header|Java}}==
<syntaxhighlight lang="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;
}
}
</syntaxhighlight>
{{ out }}
<pre>
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
</pre>
=={{header|jq}}==
{{works with|jq}}
<syntaxhighlight lang=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)
</syntaxhighlight>
Invocation: jq -nrc -f de-polignac.jq
{{output}}
<pre>
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
</pre>
=={{header|Julia}}==
* Needs Primes.jl
<syntaxhighlight lang="julia">
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
</syntaxhighlight>
<pre>
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
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Julia}}
<syntaxhighlight lang="Mathematica">
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]]];
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Nim}}==
<syntaxhighlight lang="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}"
</syntaxhighlight>
{{out}}
<pre>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
</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
{{trans|Delphi}}
slightly modified for console
<syntaxhighlight lang="pascal">
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.</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
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
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>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];</syntaxhighlight>
{{out}}
<pre style="height:20ex">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</pre>
=={{header|Phix}}==
Line 82 ⟶ 1,394:
One thousandth: 31,941
Ten thousandth: 273,421
</pre>
===alternative===
No magic constant or arbitrary limit, but about seven times slower. Based on Wren/Raku, same output as above.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">depolignac</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">dePolignac</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return the nth depolignac number</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">depolignac</span><span style="color: #0000FF;">[$]+</span><span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">depolignac</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;"><</span><span style="color: #000000;">t</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">depolignac</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">depolignac</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First fifty de Polignac numbers:\n%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">50</span><span style="color: #0000FF;">),</span><span style="color: #000000;">dePolignac</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%5d"</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"One thousandth: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dePolignac</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Ten thousandth: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dePolignac</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
=={{header|PL/M}}==
Based on the ALGOL 68 sample.
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
<syntaxhighlight lang="plm">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
Line 125 ⟶ 1,571:
Ten thousandth: 273,421
</pre>
=={{header|Quackery}}==
<code>from</code>, <code>index</code>, <code>end</code>, and <code>incr</code> are defined at [[Loops/Increment loop index within loop body#Quackery]].
<code>isprime</code> is defined at [[Primality by trial division#Quackery]].
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>[ 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 ]</pre>
=={{header|Raku}}==
Line 146 ⟶ 1,621:
Ten thousandth: 273,421</pre>
=={{header|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 (<code>CF</code>, <code>SF</code> and <code>FC?</code> instructions) are used to exit loops when the remainder of (n - 2^k) is not prime.
{{works with|Halcyon Calc|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 + '''END'''
≫
'''END'''
MOD SIGN
'''END'''
≫ '<span style="color;blue">PRIM?</span>' 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''' <span style="color;blue">PRIM?</span> '''THEN''' 1 SF '''END'''
1 -
'''END''' DROP
'''IF''' 1 FC? '''THEN''' DUP ROT SWAP + SWAP '''END'''
2 +
'''UNTIL''' OVER SIZE n == '''END'''
DROP
≫ ≫ '<span style="color;blue">DPFAIL</span>' STO
50 <span style="color;blue">DPFAIL</span>
{{out}}
<pre>
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 }
</pre>
=={{header|Ruby}}==
Using Thundergnats observation that it is enough to subtract powers of 2 and verify that none of the results is prime.
<syntaxhighlight lang="ruby">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]}"}
</syntaxhighlight>
{{out}}
<pre>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
</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
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
}
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Sidef}}==
{{trans|Ruby}}
<syntaxhighlight lang="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)}"
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
Line 248 ⟶ 1,871:
31941
273421
</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>
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
</pre>
| |||