Smallest number k such that k+2^m is composite for all m less than k: Difference between revisions
Smallest number k such that k+2^m is composite for all m less than k (view source)
Revision as of 22:57, 31 March 2024
, 2 months agoAdded Algol 68
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added Algol 68) |
||
| (9 intermediate revisions by 8 users not shown) | |||
Line 24:
;See also
[[oeis:A033919|OEIS:
=={{header|ALGOL 68}}==
{{Trans|Java|but basically the same brute-force algorithm used by most other samples}}
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.<br>
This will take some time...
{{libheader|ALGOL 68-primes}}
The source of primes.incl.a68 is on another page on Rosetta Code - see the above link.
<syntaxhighlight lang="algol68">
BEGIN # find the smallest k such that k+2^m is composite for all 0 < m < k #
# this is sequence A033919 on the OEIS #
PR precision 5000 PR # set the precision of LONG LONG INT #
PR read "primes.incl.a68" PR # include prime utilities #
PROC is a033919 = ( INT ak )BOOL:
BEGIN
LONG LONG INT big k = ak;
LONG LONG INT p2 := 2;
BOOL result := FALSE;
FOR m TO ak - 1 WHILE result := NOT is probably prime( big k + p2 ) DO p2 *:= 2 OD;
result
END # is a033919 # ;
INT count := 0;
FOR k FROM 3 BY 2 WHILE count < 5 DO
IF is a033919( k ) THEN
print( ( whole( k, 0 ), " " ) );
count +:= 1
FI
OD;
print( ( newline ) )
END</syntaxhighlight>
{{out}}
<pre>
773 2131 2491 4471 5101
</pre>
=={{header|FreeBASIC}}==
{{trans|Wren}}
{{libheader|GMP}}
<syntaxhighlight lang="vbnet">#include once "gmp.bi"
Dim Shared As mpz_ptr z
mpz_init(z)
Function a(k As Integer) As Boolean
If k = 1 Then Return False
For m As Integer = 1 To k - 1
mpz_ui_pow_ui(z, 2, m)
mpz_add_ui(z, z, k)
If mpz_probab_prime_p(z, 5) <> 0 Then Return False
Next m
Return True
End Function
Dim As Integer k = 1, count = 0
While count < 5
If a(k) Then
Print k; " ";
count += 1
End If
k += 2
Wend
Print
Sleep</syntaxhighlight>
{{out}}
<pre>773 2131 2491 4471 5101</pre>
=={{header|Go}}==
Line 69 ⟶ 137:
{{out}}
<pre>
773 2131 2491 4471 5101
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
public final class SmallestNumberK {
public static void main(String[] aArgs) {
int count = 0;
int k = 3;
while ( count < 5 ) {
if ( isA033919(k) ) {
System.out.print(k + " ");
count += 1;
}
k += 2;
}
System.out.println();
}
private static boolean isA033919(int aK) {
final BigInteger bigK = BigInteger.valueOf(aK);
for ( int m = 1; m < aK; m++ ) {
if ( bigK.add(BigInteger.ONE.shiftLeft(m)).isProbablePrime(20) ) {
return false;
}
}
return true;
}
}
</syntaxhighlight>
{{ out }}
<pre>
773 2131 2491 4471 5101
Line 104 ⟶ 209:
{{out}}
<pre>{773, 2131, 2491, 4471, 5101, 7013, 8543, 10711}</pre>
=={{header|Nim}}==
{{trans|Wren}}
{{libheader|Nim-Integers}}
<syntaxhighlight lang="Nim">import integers
let One = newInteger(1)
proc a(k: Positive): bool =
## Return true if "k" is a sequence member, false otherwise.
if k == 1: return false
for m in 1..<k:
if isPrime(One shl m + k):
return false
result = true
var count = 0
var k = 1
while count < 5:
if a(k):
stdout.write k, ' '
inc count
inc k, 2
echo()
</syntaxhighlight>
{{out}}
<pre>773 2131 2491 4471 5101
</pre>
=={{header|Perl}}==
Line 158 ⟶ 292:
"22.7s"
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">""" wiki/Smallest_number_k_such_that_k%2B2%5Em_is_composite_for_all_m_less_than_k """
from sympy import isprime
def a(k):
""" returns true if k is a sequence member, false otherwise """
if k == 1:
return False
for m in range(1, k):
n = 2**m + k
if isprime(n):
return False
return True
if __name__ == '__main__':
print([i for i in range(1, 5500, 2) if a(i)]) # [773, 2131, 2491, 4471, 5101]
</syntaxhighlight>{{out}}
[773, 2131, 2491, 4471, 5101]
=={{header|Raku}}==
Line 164 ⟶ 324:
{{out}}
<pre>773 2131 2491 4471 5101</pre>
=={{header|RPL}}==
Long integers cannot be greater than 10<sup>500</sup> in PRL.
{{works with|HP49-C}}
« { } 3
'''WHILE''' DUP 1658 < '''REPEAT''' <span style="color:grey">''@ 2^1658 > 10^500''</span>
1 SF 1 OVER 1 -
'''FOR''' m
'''IF''' DUP 2 m ^ + ISPRIME? '''THEN''' 1 CF DUP 'm' STO '''END'''
'''NEXT'''
'''IF''' 1 FS? '''THEN''' SWAP OVER + SWAP '''END'''
2 +
'''END''' DROP
» '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { 773 }
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby" line>require 'openssl'
a = (1..).step(2).lazy.select do |k|
next if k == 1
(1..(k-1)).none? {|m| OpenSSL::BN.new(k+(2**m)).prime?}
end
p a.first 5</syntaxhighlight>
{{out}}
<pre>[773, 2131, 2491, 4471, 5101]</pre>
=={{header|Wren}}==
Line 170 ⟶ 360:
Brute force approach - takes a smidge under 2 seconds.
<syntaxhighlight lang="
// returns true if k is a sequence member, false otherwise
| |||