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

{{task}}

Generate the sequence of numbers '''a(k)''', where each '''k''' is the smallest positive integer such that '''k + 2<sup>m</sup>''' 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<sup>1</sup> (9) prime? False

Is 7 + 2<sup>2</sup> (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|OEIS:A033919 - Odd k for which k+2^m is composite for all m < k]]

=={{header|ALGOL 68}}==
{{Trans|Java|but basically the same brute-force algorithm used by most other samples}}
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.<br>
This will take some time...
{{libheader|ALGOL 68-primes}}
The source of primes.incl.a68 is on another page on Rosetta Code - see the above link.
<syntaxhighlight lang="algol68">
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</syntaxhighlight>
{{out}}
<pre>
773 2131 2491 4471 5101
</pre>

=={{header|FreeBASIC}}==
{{trans|Wren}}
{{libheader|GMP}}
<syntaxhighlight lang="vbnet">#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</syntaxhighlight>
{{out}}
<pre>773 2131 2491 4471 5101</pre>

=={{header|Go}}==
{{trans|Wren}}
{{libheader|GMP(Go wrapper)}}
Takes around 2.2 seconds though faster than using Go's native big.Int type which takes 6.2 seconds.
<syntaxhighlight 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()
}</syntaxhighlight>

{{out}}
<pre>
773 2131 2491 4471 5101 
</pre>

=={{header|Java}}==
<syntaxhighlight lang="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;
	}

}
</syntaxhighlight>
{{ out }}
<pre>
773 2131 2491 4471 5101 
</pre>

=={{header|Julia}}==
<syntaxhighlight 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)
</syntaxhighlight>

=={{header|Mathematica}}/{{header|Wolfram Language}}==
Since the code is reasonably performant I found the first 8 of this sequence:
<syntaxhighlight lang="mathematica">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</syntaxhighlight>
{{out}}
<pre>{773, 2131, 2491, 4471, 5101, 7013, 8543, 10711}</pre>

=={{header|Nim}}==
{{trans|Wren}}
{{libheader|Nim-Integers}}
<syntaxhighlight lang="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()
</syntaxhighlight>

{{out}}
<pre>773 2131 2491 4471 5101 
</pre>

=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight 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;
}</syntaxhighlight>
{{out}}
<pre>773 2131 2491 4471 5101</pre>

=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
 <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 <span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
 <span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
  
 <span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
 <span style="color: #008080;">function</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
         <span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
         <span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
 <span style="color: #008080;">while</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">5</span> <span style="color: #008080;">do</span>
     <span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
         <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
         <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
 <span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
Rather slow, even worse under pwa/p2js - about 90s...
<pre>
773 2131 2491 4471 5101
"22.7s"
</pre>

=={{header|Python}}==
<syntaxhighlight lang="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]
</syntaxhighlight>{{out}}
[773, 2131, 2491, 4471, 5101]


=={{header|Raku}}==

<syntaxhighlight lang="raku" line>put (1..∞).hyper(:250batch).map(* × 2 + 1).grep( -> $k { !(1 ..^ $k).first: ($k + 1 +< *).is-prime } )[^5]</syntaxhighlight>
{{out}}
<pre>773 2131 2491 4471 5101</pre>

=={{header|RPL}}==
Long integers cannot be greater than 10<sup>500</sup> in PRL.
{{works with|HP49-C}}
 « { } 3
   '''WHILE''' DUP 1658 < '''REPEAT'''               <span style="color:grey">''@ 2^1658 > 10^500''</span>
      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
 » '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { 773 }
</pre>

=={{header|Ruby}}==

<syntaxhighlight lang="ruby" line>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</syntaxhighlight>
{{out}}
<pre>[773, 2131, 2491, 4471, 5101]</pre>

=={{header|Wren}}==
{{libheader|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.
<syntaxhighlight lang="wren">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()</syntaxhighlight>

{{out}}
<pre>
773 2131 2491 4471 5101 
</pre>