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