I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# 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.

## 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 otherwisefunc 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
```

## Julia

`using Lazyusing 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) `

## 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"
```

## Raku

`put (1..∞).hyper(:250batch).map(* × 2 + 1).grep( -> \$k { !(1 ..^ \$k).first: (\$k + 1 +< *).is-prime } )[^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 otherwisevar 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 = 0var k = 1while (count < 5) {    if (a.call(k)) {        System.write("%(k) ")        count = count + 1    }    k = k + 2}System.print()`
Output:
```773 2131 2491 4471 5101
```