Ultra useful primes: Difference between revisions
m (J) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 25: | Line 25: | ||
Uses Algol 68G's LONG LONG INT which has programmer-specifiable precision. Uses Miller Rabin primality testing. |
Uses Algol 68G's LONG LONG INT which has programmer-specifiable precision. Uses Miller Rabin primality testing. |
||
{{libheader|ALGOL 68-primes}} |
{{libheader|ALGOL 68-primes}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find members of the sequence a(n) = smallest k such that 2^(2^n) - k is prime # |
||
PR precision 650 PR # set number of digits for LONG LOMG INT # |
PR precision 650 PR # set number of digits for LONG LOMG INT # |
||
# 2^(2^10) has 308 digits but we need more for # |
# 2^(2^10) has 308 digits but we need more for # |
||
Line 42: | Line 42: | ||
DO SKIP OD |
DO SKIP OD |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 50: | Line 50: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">ultraUseful: function [n][ |
||
k: 1 |
k: 1 |
||
p: (2^2^n) - k |
p: (2^2^n) - k |
||
Line 63: | Line 63: | ||
print repeat "-" 10 |
print repeat "-" 10 |
||
loop 1..10 'x -> |
loop 1..10 'x -> |
||
print [(pad to :string x 3) "|" (pad.right to :string ultraUseful x 4)]</ |
print [(pad to :string x 3) "|" (pad.right to :string ultraUseful x 4)]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 82: | Line 82: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-06-02}} |
{{works with|Factor|0.99 2021-06-02}} |
||
< |
<syntaxhighlight lang="factor">USING: io kernel lists lists.lazy math math.primes prettyprint ; |
||
: useful ( -- list ) |
: useful ( -- list ) |
||
Line 88: | Line 88: | ||
[ 2^ 2^ 1 lfrom [ - prime? ] with lfilter car ] lmap-lazy ; |
[ 2^ 2^ 1 lfrom [ - prime? ] with lfilter car ] lmap-lazy ; |
||
10 useful ltake [ pprint bl ] leach nl</ |
10 useful ltake [ pprint bl ] leach nl</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 96: | Line 96: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{libheader|GMP(Go wrapper)}} |
{{libheader|GMP(Go wrapper)}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 123: | Line 123: | ||
fmt.Printf("%2d %d\n", n, a(n)) |
fmt.Printf("%2d %d\n", n, a(n)) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 148: | Line 148: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang="j">uup=: {{ |
||
ref=. 2x^2^y+1 |
ref=. 2x^2^y+1 |
||
k=. 1 |
k=. 1 |
||
while. -. 1 p: ref-k do. k=. k+2 end. |
while. -. 1 p: ref-k do. k=. k+2 end. |
||
}}"0</ |
}}"0</syntaxhighlight> |
||
I don't have the patience to get this little laptop to compute the first 10 such elements, so here I only show the first five: |
I don't have the patience to get this little laptop to compute the first 10 such elements, so here I only show the first five: |
||
< |
<syntaxhighlight lang="j"> uup i.5 |
||
1 3 5 15 5</ |
1 3 5 15 5</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
nearpow2pow2prime(n) = findfirst(k -> isprime(2^(big"2"^n) - k), 1:10000) |
nearpow2pow2prime(n) = findfirst(k -> isprime(2^(big"2"^n) - k), 1:10000) |
||
@time println([nearpow2pow2prime(n) for n in 1:12]) |
@time println([nearpow2pow2prime(n) for n in 1:12]) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
[1, 3, 5, 15, 5, 59, 159, 189, 569, 105, 1557, 2549] |
[1, 3, 5, 15, 5, 59, 159, 189, 569, 105, 1557, 2549] |
||
Line 172: | Line 172: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[FindUltraUsefulPrimeK] |
||
FindUltraUsefulPrimeK[n_] := Module[{num, tmp}, |
FindUltraUsefulPrimeK[n_] := Module[{num, tmp}, |
||
num = 2^(2^n); |
num = 2^(2^n); |
||
Line 186: | Line 186: | ||
] |
] |
||
res = FindUltraUsefulPrimeK /@ Range[13]; |
res = FindUltraUsefulPrimeK /@ Range[13]; |
||
TableForm[res, TableHeadings -> Automatic]</ |
TableForm[res, TableHeadings -> Automatic]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 1 |
<pre>1 1 |
||
Line 202: | Line 202: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 220: | Line 220: | ||
} |
} |
||
say join ' ', useful 1..13;</ |
say join ' ', useful 1..13;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 3 5 15 5 59 159 189 569 105 1557 2549 2439</pre> |
<pre>1 3 5 15 5 59 159 189 569 105 1557 2549 2439</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 252: | Line 252: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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}} |
||
<pre> |
<pre> |
||
Line 262: | Line 262: | ||
The first 10 take less than a quarter second. 11 through 13, a little under 30 seconds. Drops off a cliff after that. |
The first 10 take less than a quarter second. 11 through 13, a little under 30 seconds. Drops off a cliff after that. |
||
<lang |
<syntaxhighlight lang="raku" line>sub useful ($n) { |
||
(|$n).map: { |
(|$n).map: { |
||
my $p = 1 +< ( 1 +< $_ ); |
my $p = 1 +< ( 1 +< $_ ); |
||
Line 271: | Line 271: | ||
put useful 1..10; |
put useful 1..10; |
||
put useful 11..13;</ |
put useful 11..13;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 3 5 15 5 59 159 189 569 105 |
<pre>1 3 5 15 5 59 159 189 569 105 |
||
Line 277: | Line 277: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">say(" n k") |
||
say("----------") |
say("----------") |
||
Line 283: | Line 283: | ||
var t = 2**(2**n) |
var t = 2**(2**n) |
||
printf("%2d %d\n", n, {|k| t - k -> is_prob_prime }.first) |
printf("%2d %d\n", n, {|k| t - k -> is_prob_prime }.first) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 309: | Line 309: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Manages to find the first ten but takes 84 seconds to do so. |
Manages to find the first ten but takes 84 seconds to do so. |
||
< |
<syntaxhighlight lang="ecmascript">import "./big" for BigInt |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 327: | Line 327: | ||
System.print(" n k") |
System.print(" n k") |
||
System.print("----------") |
System.print("----------") |
||
for (n in 1..10) Fmt.print("$2d $d", n, a.call(n))</ |
for (n in 1..10) Fmt.print("$2d $d", n, a.call(n))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 347: | Line 347: | ||
{{libheader|Wren-gmp}} |
{{libheader|Wren-gmp}} |
||
The following takes about 17 seconds to get to n = 13 but 7 minutes 10 seconds to reach n = 14. I didn't bother after that. |
The following takes about 17 seconds to get to n = 13 but 7 minutes 10 seconds to reach n = 14. I didn't bother after that. |
||
< |
<syntaxhighlight lang="ecmascript">import "./gmp" for Mpz |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 365: | Line 365: | ||
System.print(" n k") |
System.print(" n k") |
||
System.print("----------") |
System.print("----------") |
||
for (n in 1..14) Fmt.print("$2d $d", n, a.call(n))</ |
for (n in 1..14) Fmt.print("$2d $d", n, a.call(n))</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 19:28, 28 August 2022
You are encouraged to solve this task according to the task description, using any language you may know.
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
ALGOL 68
Uses Algol 68G's LONG LONG INT which has programmer-specifiable precision. Uses Miller Rabin primality testing.
BEGIN # find members of the sequence a(n) = smallest k such that 2^(2^n) - k is prime #
PR precision 650 PR # set number of digits for LONG LOMG INT #
# 2^(2^10) has 308 digits but we need more for #
# Miller Rabin primality testing #
PR read "primes.incl.a68" PR # include the prime related utilities #
FOR n TO 10 DO
LONG LONG INT two up 2 up n = LONG LONG INT( 2 ) ^ ( 2 ^ n );
FOR i BY 2
WHILE IF is probably prime( two up 2 up n - i ) THEN
# found a sequence member #
print( ( " ", whole( i, 0 ) ) );
FALSE # stop looking #
ELSE
TRUE # haven't found a sequence member yet #
FI
DO SKIP OD
OD
END
- Output:
1 3 5 15 5 59 159 189 569 105
Arturo
ultraUseful: function [n][
k: 1
p: (2^2^n) - k
while ø [
if prime? p -> return k
p: p-2
k: k+2
]
]
print [pad "n" 3 "|" pad.right "k" 4]
print repeat "-" 10
loop 1..10 'x ->
print [(pad to :string x 3) "|" (pad.right to :string ultraUseful x 4)]
- Output:
n | k ---------- 1 | 1 2 | 3 3 | 5 4 | 15 5 | 5 6 | 59 7 | 159 8 | 189 9 | 569 10 | 105
Factor
USING: io kernel lists lists.lazy math math.primes prettyprint ;
: useful ( -- list )
1 lfrom
[ 2^ 2^ 1 lfrom [ - prime? ] with lfilter car ] lmap-lazy ;
10 useful ltake [ pprint bl ] leach nl
- Output:
1 3 5 15 5 59 159 189 569 105
Go
package main
import (
"fmt"
big "github.com/ncw/gmp"
)
var two = big.NewInt(2)
func a(n uint) int {
one := big.NewInt(1)
p := new(big.Int).Lsh(one, 1 << n)
p.Sub(p, one)
for k := 1; ; k += 2 {
if p.ProbablyPrime(15) {
return k
}
p.Sub(p, two)
}
}
func main() {
fmt.Println(" n k")
fmt.Println("----------")
for n := uint(1); n < 14; n++ {
fmt.Printf("%2d %d\n", n, a(n))
}
}
- 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
J
Implementation:
uup=: {{
ref=. 2x^2^y+1
k=. 1
while. -. 1 p: ref-k do. k=. k+2 end.
}}"0
I don't have the patience to get this little laptop to compute the first 10 such elements, so here I only show the first five:
uup i.5
1 3 5 15 5
Julia
using Primes
nearpow2pow2prime(n) = findfirst(k -> isprime(2^(big"2"^n) - k), 1:10000)
@time println([nearpow2pow2prime(n) for n in 1:12])
- Output:
[1, 3, 5, 15, 5, 59, 159, 189, 569, 105, 1557, 2549] 3.896011 seconds (266.08 k allocations: 19.988 MiB, 1.87% compilation time)
Mathematica/Wolfram Language
ClearAll[FindUltraUsefulPrimeK]
FindUltraUsefulPrimeK[n_] := Module[{num, tmp},
num = 2^(2^n);
Do[
If[PrimeQ[num - k],
tmp = k;
Break[];
]
,
{k, 1, \[Infinity], 2}
];
tmp
]
res = FindUltraUsefulPrimeK /@ Range[13];
TableForm[res, TableHeadings -> Automatic]
- Output:
1 1 2 3 3 5 4 15 5 5 6 59 7 159 8 189 9 569 10 105 11 1557
Perl
use strict;
use warnings;
use feature 'say';
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;
- Output:
1 3 5 15 5 59 159 189 569 105 1557 2549 2439
Phix
with javascript_semantics atom t0 = time() include mpfr.e mpz p = mpz_init() function a(integer n) mpz_ui_pow_ui(p,2,power(2,n)) mpz_sub_si(p,p,1) integer k = 1 while not mpz_prime(p) do k += 2 mpz_sub_si(p,p,2) end while return k end function for i=1 to 10 do printf(1,"%d ",a(i)) end for if machine_bits()=64 then ?elapsed(time()-t0) for i=11 to 13 do printf(1,"%d ",a(i)) end for end if ?elapsed(time()-t0)
- Output:
1 3 5 15 5 59 159 189 569 105 "0.0s" 1557 2549 2439 "1 minute and 1s"
Raku
The first 10 take less than a quarter second. 11 through 13, a little under 30 seconds. Drops off a cliff after that.
sub useful ($n) {
(|$n).map: {
my $p = 1 +< ( 1 +< $_ );
^$p .first: ($p - *).is-prime
}
}
put useful 1..10;
put useful 11..13;
- Output:
1 3 5 15 5 59 159 189 569 105 1557 2549 2439
Sidef
say(" n k")
say("----------")
for n in (1..13) {
var t = 2**(2**n)
printf("%2d %d\n", n, {|k| t - k -> is_prob_prime }.first)
}
- 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
(takes ~20 seconds)
Wren
CLI
Manages to find the first ten but takes 84 seconds to do so.
import "./big" for BigInt
import "./fmt" for Fmt
var one = BigInt.one
var two = BigInt.two
var a = Fn.new { |n|
var p = (BigInt.one << (1 << n)) - one
var k = 1
while (true) {
if (p.isProbablePrime(5)) return k
p = p - two
k = k + 2
}
}
System.print(" n k")
System.print("----------")
for (n in 1..10) Fmt.print("$2d $d", n, a.call(n))
- Output:
n k ---------- 1 1 2 3 3 5 4 15 5 5 6 59 7 159 8 189 9 569 10 105
Embedded
The following takes about 17 seconds to get to n = 13 but 7 minutes 10 seconds to reach n = 14. I didn't bother after that.
import "./gmp" for Mpz
import "./fmt" for Fmt
var one = Mpz.one
var two = Mpz.two
var a = Fn.new { |n|
var p = Mpz.one.lsh(1 << n).sub(one)
var k = 1
while (true) {
if (p.probPrime(15) > 0) return k
p.sub(two)
k = k + 2
}
}
System.print(" n k")
System.print("----------")
for (n in 1..14) Fmt.print("$2d $d", n, a.call(n))
- 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