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

From Rosetta Code
Revision as of 22:57, 31 March 2024 by Tigerofdarkness (talk | contribs) (Added Algol 68)
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

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

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
» 'TASK' STO
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) {
        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