Smallest number k such that k+2^m is composite for all m less than k
You are encouraged to solve this task according to the task description, using any language you may know.
Generate the sequence of numbers a(k), where each k is the smallest positive integer such that k + 2m is composite for every positive integer m less than k.
- For example
Suppose k == 7; test m == 1 through m == 6. If any are prime, the test fails.
Is 7 + 21 (9) prime? False
Is 7 + 22 (11) prime? True
So 7 is not an element of this sequence.
It is only necessary to test odd natural numbers k. An even number, plus any positive integer power of 2 is always composite.
- Task
Find and display, here on this page, the first 5 elements of this sequence.
- See also
OEIS:A033919 - Odd k for which k+2^m is composite for all m < k
ALGOL 68
Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.
This will take some time...
ALGOL 68 Genie version 3 issues a warning: 5004 digits precision impacts performance.
The source of primes.incl.a68 is on another page on Rosetta Code - see the above link.
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;
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
- Output:
773 2131 2491 4471 5101
FreeBASIC
#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
- Output:
773 2131 2491 4471 5101
Go
Takes around 2.2 seconds though faster than using Go's native big.Int type which takes 6.2 seconds.
package main
import (
"fmt"
big "github.com/ncw/gmp"
)
// returns true if k is a sequence member, false otherwise
func a(k int64) bool {
if k == 1 {
return false
}
bk := big.NewInt(k)
for m := uint(1); m < uint(k); m++ {
n := big.NewInt(1)
n.Lsh(n, m)
n.Add(n, bk)
if n.ProbablyPrime(15) {
return false
}
}
return true
}
func main() {
count := 0
k := int64(1)
for count < 5 {
if a(k) {
fmt.Printf("%d ", k)
count++
}
k += 2
}
fmt.Println()
}
- Output:
773 2131 2491 4471 5101
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;
}
}
- Output:
773 2131 2491 4471 5101
Julia
using Lazy
using Primes
a(k) = all(m -> !isprime(k + big"2"^m), 1:k-1)
A033939 = @>> Lazy.range(2) filter(isodd) filter(a)
println(take(5, A033939)) # List: (773 2131 2491 4471 5101)
Mathematica /Wolfram Language
Since the code is reasonably performant I found the first 8 of this sequence:
ClearAll[ValidK]
ValidK[1] := False
ValidK[k_] := If[EvenQ[k],
False,
AllTrue[Range[k - 1], CompositeQ[k + 2^#] &]
]
list = {};
Do[
If[ValidK[k],
AppendTo[list, k];
If[Length[list] >= 8, Break[]]
]
,
{k, 1, \[Infinity]}
]
list
- Output:
{773, 2131, 2491, 4471, 5101, 7013, 8543, 10711}
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()
- Output:
773 2131 2491 4471 5101
Perl
use strict;
use warnings;
use bigint;
use ntheory 'is_prime';
my $cnt;
LOOP: for my $k (2..1e10) {
next unless 1 == $k % 2;
for my $m (1..$k-1) {
next LOOP if is_prime $k + (1<<$m)
}
print "$k ";
last if ++$cnt == 5;
}
- Output:
773 2131 2491 4471 5101
Phix
with javascript_semantics atom t0 = time() include mpfr.e mpz z = mpz_init() function a(integer k) if k=1 then return false end if for m=1 to k-1 do mpz_ui_pow_ui(z,2,m) mpz_add_si(z,z,k) if mpz_prime(z) then return false end if end for return true end function integer k = 1, count = 0 while count<5 do if a(k) then printf(1,"%d ",k) count += 1 end if k += 2 end while printf(1,"\n") ?elapsed(time()-t0)
- Output:
Rather slow, even worse under pwa/p2js - about 90s...
773 2131 2491 4471 5101 "22.7s"
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]
- Output:
[773, 2131, 2491, 4471, 5101]
Raku
put (1..∞).hyper(:250batch).map(* × 2 + 1).grep( -> $k { !(1 ..^ $k).first: ($k + 1 +< *).is-prime } )[^5]
- Output:
773 2131 2491 4471 5101
RPL
Long integers cannot be greater than 10500 in PRL.
« { } 3 WHILE DUP 1658 < REPEAT @ 2^1658 > 10^500 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 » 'TASK' STO
- Output:
1: { 773 }
Ruby
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
- Output:
[773, 2131, 2491, 4471, 5101]
Wren
An embedded version as, judging by the size of numbers involved, Wren-CLI (using BigInt) will be too slow for this.
Brute force approach - takes a smidge under 2 seconds.
import "./gmp" for Mpz
// returns true if k is a sequence member, false otherwise
var a = Fn.new { |k|
if (k == 1) return false
for (m in 1...k) {
var n = Mpz.one.lsh(m).add(k)
if (n.probPrime(15) > 0) return false
}
return true
}
var count = 0
var k = 1
while (count < 5) {
if (a.call(k)) {
System.write("%(k) ")
count = count + 1
}
k = k + 2
}
System.print()
- Output:
773 2131 2491 4471 5101