Smallest number k such that k+2^m is composite for all m less than k: Difference between revisions
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 31: | Line 31: | ||
{{libheader|GMP(Go wrapper)}} |
{{libheader|GMP(Go wrapper)}} |
||
Takes around 2.2 seconds though faster than using Go's native big.Int type which takes 6.2 seconds. |
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 ( |
import ( |
||
Line 66: | Line 66: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 74: | Line 74: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Lazy |
||
using Primes |
using Primes |
||
Line 82: | Line 82: | ||
println(take(5, A033939)) # List: (773 2131 2491 4471 5101) |
println(take(5, A033939)) # List: (773 2131 2491 4471 5101) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
Since the code is reasonably performant I found the first 8 of this sequence: |
Since the code is reasonably performant I found the first 8 of this sequence: |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[ValidK] |
||
ValidK[1] := False |
ValidK[1] := False |
||
ValidK[k_] := If[EvenQ[k], |
ValidK[k_] := If[EvenQ[k], |
||
Line 101: | Line 101: | ||
{k, 1, \[Infinity]} |
{k, 1, \[Infinity]} |
||
] |
] |
||
list</ |
list</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{773, 2131, 2491, 4471, 5101, 7013, 8543, 10711}</pre> |
<pre>{773, 2131, 2491, 4471, 5101, 7013, 8543, 10711}</pre> |
||
Line 107: | Line 107: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use bigint; |
use bigint; |
||
Line 120: | Line 120: | ||
print "$k "; |
print "$k "; |
||
last if ++$cnt == 5; |
last if ++$cnt == 5; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>773 2131 2491 4471 5101</pre> |
<pre>773 2131 2491 4471 5101</pre> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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: #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> |
||
Line 151: | Line 151: | ||
<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: #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> |
<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}} |
{{out}} |
||
Rather slow, even worse under pwa/p2js - about 90s... |
Rather slow, even worse under pwa/p2js - about 90s... |
||
Line 161: | Line 161: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>put (1..∞).hyper(:250batch).map(* × 2 + 1).grep( -> $k { !(1 ..^ $k).first: ($k + 1 +< *).is-prime } )[^5]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>773 2131 2491 4471 5101</pre> |
<pre>773 2131 2491 4471 5101</pre> |
||
Line 170: | Line 170: | ||
Brute force approach - takes a smidge under 2 seconds. |
Brute force approach - takes a smidge under 2 seconds. |
||
< |
<syntaxhighlight lang="ecmascript">import "./gmp" for Mpz |
||
// returns true if k is a sequence member, false otherwise |
// returns true if k is a sequence member, false otherwise |
||
Line 191: | Line 191: | ||
k = k + 2 |
k = k + 2 |
||
} |
} |
||
System.print()</ |
System.print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 15:18, 28 August 2022
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
Go
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
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}
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;
}
- 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
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.
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