Ultra useful primes: Difference between revisions
SqrtNegInf (talk | contribs) (Added Perl) |
(Added Wren) |
||
Line 61: | Line 61: | ||
<pre>1 3 5 15 5 59 159 189 569 105 |
<pre>1 3 5 15 5 59 159 189 569 105 |
||
1557 2549 2439</pre> |
1557 2549 2439</pre> |
||
=={{header|Wren}}== |
|||
{{libheader|Wren-gmp}} |
|||
An embedded version as Wren-CLI (with BigInt) will be very slow for this task. |
|||
The following takes about 17.5 seconds to get to n = 13 but 7 minutes 15 seconds to reach n = 14. I didn't bother after that. |
|||
<lang ecmascript>import "./gmp" for Mpz |
|||
import "./fmt" for Fmt |
|||
var a = Fn.new { |n| |
|||
var p = Mpz.one.lsh(1 << n) |
|||
var k = 1 |
|||
while (true) { |
|||
var q = p - k |
|||
if (q.probPrime(15) > 0) return k |
|||
k = k + 2 |
|||
} |
|||
} |
|||
System.print(" n k") |
|||
System.print("----------") |
|||
for (n in 1..14) Fmt.print("$2d $d", n, a.call(n))</lang> |
|||
{{out}} |
|||
<pre> |
|||
n k |
|||
---------- |
|||
1 1 |
|||
2 3 |
|||
3 5 |
|||
4 15 |
|||
5 5 |
|||
6 59 |
|||
7 159 |
|||
8 189 |
|||
9 569 |
|||
10 105 |
|||
11 1557 |
|||
12 2549 |
|||
13 2439 |
|||
14 13797 |
|||
</pre> |
Revision as of 22:20, 13 January 2022
An ultra-useful prime is a member of the sequence where each a(n) is the smallest positive integer k such that 2(2n) - k is prime.
k must always be an odd number since 2 to any power is always even.
- Task
- Find and show here, on this page, the first 10 elements of the sequence.
- Stretch
- Find and show the next several elements. (The numbers get really big really fast. Only nineteen elements have been identified as of this writing.)
- See also
Perl
<lang perl>use strict; use warnings; use bigint; use ntheory 'is_prime';
sub useful {
my @n = @_; my @u; for my $n (@n) { my $p = 2**(2**$n); LOOP: for (my $k = 1; $k < $p; $k += 2) { is_prime($p-$k) and push @u, $k and last LOOP; } } @u
}
say join ' ', useful 1..13;</lang>
- Output:
1 3 5 15 5 59 159 189 569 105 1557 2549 2439
Raku
The first 10 take less than a quarter second. 11 through 13, a little under 30 seconds. Drops off a cliff after that.
<lang perl6>sub useful ($n) {
(|$n).map: { my $p = 1 +< ( 1 +< $_ ); ^$p .first: ($p - *).is-prime }
}
put useful 1..10;
put useful 11..13;</lang>
- Output:
1 3 5 15 5 59 159 189 569 105 1557 2549 2439
Wren
An embedded version as Wren-CLI (with BigInt) will be very slow for this task.
The following takes about 17.5 seconds to get to n = 13 but 7 minutes 15 seconds to reach n = 14. I didn't bother after that. <lang ecmascript>import "./gmp" for Mpz import "./fmt" for Fmt
var a = Fn.new { |n|
var p = Mpz.one.lsh(1 << n) var k = 1 while (true) { var q = p - k if (q.probPrime(15) > 0) return k k = k + 2 }
}
System.print(" n k") System.print("----------") for (n in 1..14) Fmt.print("$2d $d", n, a.call(n))</lang>
- Output:
n k ---------- 1 1 2 3 3 5 4 15 5 5 6 59 7 159 8 189 9 569 10 105 11 1557 12 2549 13 2439 14 13797