Smallest number k such that k+2^m is composite for all m less than k: Difference between revisions
Thundergnat (talk | contribs) (New draft task and Raku example) |
(Added Wren) |
||
Line 33: | Line 33: | ||
{{out}} |
{{out}} |
||
<pre>773 2131 2491 4471 5101</pre> |
<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 over 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 << m) + 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> |
|||
{{out}} |
|||
<pre> |
|||
773 2131 2491 4471 5101 |
|||
</pre> |
Revision as of 11:25, 12 January 2022
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
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 over 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 << m) + 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