# Smallest number k such that k+2^m is composite for all m less than k

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.

Find and display, here on this page, the first 5 elements of this sequence.

## ALGOL 68

Translation of: Java – but basically the same brute-force algorithm used by most other samples
Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.
This will take some time...

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;
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```
Output:
```773 2131 2491 4471 5101
```

## FreeBASIC

Translation of: Wren
Library: GMP
```#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)
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

Translation of: Wren

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)
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++ ) {
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

Translation of: Wren
Library: Nim-Integers
```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

Library: ntheory
```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)
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.

Works with: HP49-C
```« { } 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
```
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

Library: Wren-gmp

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) {
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
```