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 + 2^m 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 + 2¹ (9) prime? False

Is 7 + 2² (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:A033939 - Odd k for which k+2^m is composite for all m < k

Go

Translation of: Wren

Library: GMP(Go wrapper)

Takes around 2.2 seconds though faster than using Go's native big.Int type which takes 6.2 seconds. <lang go>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()

}</lang>

Output:

773 2131 2491 4471 5101 

Julia

<lang 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) </lang>

Perl

Library: ntheory

<lang 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;

}</lang>

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"

Raku

<lang perl6>put (1..∞).hyper(:250batch).map(* × 2 + 1).grep( -> $k { !(1 ..^ $k).first: ($k + 1 +< *).is-prime } )[^5]</lang>

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. <lang ecmascript>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()</lang>

Output:

773 2131 2491 4471 5101