De Polignac numbers: Difference between revisions
Add Mathematica/Wolfram Language implementation
(→{{header|Ruby}}: Better way to find pow2) |
(Add Mathematica/Wolfram Language implementation) |
||
| (15 intermediate revisions by 11 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 312:
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}}==
Line 533 ⟶ 673:
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>
Line 542 ⟶ 770:
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
Line 604 ⟶ 832:
End If
Next
Print "Found "; dpCount; " De Polignac numbers up to "; maxNumber
Sleep</syntaxhighlight>
{{out}}
Line 676 ⟶ 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}}==
Line 814 ⟶ 1,112:
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>
Line 1,004 ⟶ 1,331:
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use v5.36;
use ntheory <is_prime vecmax vecany logint>;
Line 1,013 ⟶ 1,339:
while ($n++) {
next unless $n % 2;
next if vecany { is_prime($n -
push @D, comma $n;
last if 10_000 == @D;
Line 1,245 ⟶ 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 1,268 ⟶ 1,623:
=={{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
{{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
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>
Line 1,312 ⟶ 1,662:
=={{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'
Line 1,339 ⟶ 1,690:
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>
Line 1,344 ⟶ 1,773:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||