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

From Rosetta Code
Task
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


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

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

put (1..∞).hyper(:250batch).map(* × 2 + 1).grep( -> $k { !(1 ..^ $k).first: ($k + 1 +< *).is-prime } )[^5]
Output:
773 2131 2491 4471 5101

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