Ultra useful primes: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
Thundergnat (talk | contribs) m (Promote. multiple implementations, no questions) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (22 intermediate revisions by 14 users not shown) | |||
Line 25:
Uses Algol 68G's LONG LONG INT which has programmer-specifiable precision. Uses Miller Rabin primality testing.
{{libheader|ALGOL 68-primes}}
<
PR precision 650 PR # set number of digits for LONG LOMG INT #
# 2^(2^10) has 308 digits but we need more for #
Line 42:
DO SKIP OD
OD
END</
{{out}}
<pre>
1 3 5 15 5 59 159 189 569 105
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">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)]</syntaxhighlight>
{{out}}
<pre> n | k
----------
1 | 1
2 | 3
3 | 5
4 | 15
5 | 5
6 | 59
7 | 159
8 | 189
9 | 569
10 | 105</pre>
=={{header|C}}==
{{trans|Wren}}
{{libheader|GMP}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <gmp.h>
int a(unsigned int n) {
int k;
mpz_t p;
mpz_init_set_ui(p, 1);
mpz_mul_2exp(p, p, 1 << n);
mpz_sub_ui(p, p, 1);
for (k = 1; ; k += 2) {
if (mpz_probab_prime_p(p, 15) > 0) return k;
mpz_sub_ui(p, p, 2);
}
}
int main() {
unsigned int n;
printf(" n k\n");
printf("----------\n");
for (n = 1; n < 15; ++n) printf("%2d %d\n", n, a(n));
return 0;
}</syntaxhighlight>
{{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>
=={{header|Craft Basic}}==
<syntaxhighlight lang="basic">for n = 1 to 10
let k = -1
do
let k = k + 2
wait
loop prime(2 ^ (2 ^ n) - k) = 0
print "n = ", n, " k = ", k
next n</syntaxhighlight>
=={{header|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<
: useful ( -- list )
Line 56 ⟶ 150:
[ 2^ 2^ 1 lfrom [ - prime? ] with lfilter car ] lmap-lazy ;
10 useful ltake [ pprint bl ] leach nl</
{{out}}
<pre>
1 3 5 15 5 59 159 189 569 105
</pre>
=={{header|FreeBASIC}}==
{{trans|Ring}}
<syntaxhighlight lang="vb">#include "isprime.bas"
Dim As Longint n, k, limit = 10
Dim As ulongint num
For n = 1 To limit
k = -1
Do
k += 2
num = (2 ^ (2 ^ n)) - k
If isPrime(num) Then
Print "n = "; n; " k = "; k
Exit Do
End If
Loop
Next
Sleep</syntaxhighlight>
=={{header|Go}}==
{{libheader|GMP(Go wrapper)}}
<
import (
Line 91 ⟶ 205:
fmt.Printf("%2d %d\n", n, a(n))
}
}</
{{out}}
Line 110 ⟶ 224:
12 2549
13 2439
</pre>
=={{header|J}}==
Implementation:
<syntaxhighlight lang="j">uup=: {{
ref=. 2^2x^y+1
k=. 1
while. -. 1 p: ref-k do. k=. k+2 end.
}}"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:
<syntaxhighlight lang="j"> uup i.10
1 3 5 15 5 59 159 189 569 105</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
public final class UltraUsefulPrimes {
public static void main(String[] args) {
for ( int n = 1; n <= 10; n++ ) {
showUltraUsefulPrime(n);
}
}
private static void showUltraUsefulPrime(int n) {
BigInteger prime = BigInteger.ONE.shiftLeft(1 << n);
BigInteger k = BigInteger.ONE;
while ( ! prime.subtract(k).isProbablePrime(20) ) {
k = k.add(BigInteger.TWO);
}
System.out.print(k + " ");
}
}
</syntaxhighlight>
{{ out }}
<pre>
1 3 5 15 5 59 159 189 569 105
</pre>
=={{header|Julia}}==
<
nearpow2pow2prime(n) = findfirst(k -> isprime(2^(big"2"^n) - k), 1:10000)
@time println([nearpow2pow2prime(n) for n in 1:12])
</
<pre>
[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)
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">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]</syntaxhighlight>
{{out}}
<pre>1 1
2 3
3 5
4 15
5 5
6 59
7 159
8 189
9 569
10 105
11 1557</pre>
=={{header|Nim}}==
{{libheader|Nim-Integers}}
<syntaxhighlight lang="Nim">import std/strformat
import integers
let One = newInteger(1)
echo " n k"
var count = 1
var n = 1
while count <= 13:
var k = 1
var p = One shl (1 shl n) - k
while not p.isPrime:
p -= 2
k += 2
echo &"{n:2} {k}"
inc n
inc count
</syntaxhighlight>
{{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
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<
use warnings;
use feature 'say';
Line 144 ⟶ 371:
}
say join ' ', useful 1..13;</
{{out}}
<pre>1 3 5 15 5 59 159 189 569 105 1557 2549 2439</pre>
=={{header|Phix}}==
<!--<
<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>
Line 176 ⟶ 403:
<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>
<!--</
{{out}}
<pre>
Line 186 ⟶ 413:
The first 10 take less than a quarter second. 11 through 13, a little under 30 seconds. Drops off a cliff after that.
<syntaxhighlight lang="raku"
(|$n).map: {
my $p = 1 +< ( 1 +< $_ );
Line 195 ⟶ 422:
put useful 1..10;
put useful 11..13;</
{{out}}
<pre>1 3 5 15 5 59 159 189 569 105
1557 2549 2439</pre>
=={{header|Python}}==
<syntaxhighlight lang="python>
# useful.py by xing216
from gmpy2 import is_prime
def useful(n):
k = 1
is_useful = False
while is_useful == False:
if is_prime(2**(2**n) - k):
is_useful = True
break
k += 2
return k
if __name__ == "__main__":
print("n | k")
for i in range(1,14):
print(f"{i:<4}{useful(i)}")
</syntaxhighlight>
{{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
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
see "works..." + nl
limit = 10
for n = 1 to limit
k = -1
while true
k = k + 2
num = pow(2,pow(2,n)) - k
if isPrime(num)
? "n = " + n + " k = " + k
exit
ok
end
next
see "done.." + nl
func isPrime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
</syntaxhighlight>
{{out}}
<pre>
works...
n = 1 k = 1
n = 2 k = 3
n = 3 k = 5
n = 4 k = 15
n = 5 k = 5
n = 6 k = 59
n = 7 k = 159
n = 8 k = 189
n = 9 k = 569
n = 10 k = 105
done...
</pre>
=={{header|Ruby}}==
The 'prime?' method in Ruby's OpenSSL (standard) lib is much faster than the 'prime' lib. 0.05 sec. for this, about a minute for the next three.
<syntaxhighlight lang="ruby">require 'openssl'
(1..10).each do |n|
pow = 2 ** (2 ** n)
print "#{n}:\t"
puts (1..).step(2).detect{|k| OpenSSL::BN.new(pow-k).prime?}
end</syntaxhighlight>
{{out}}
<pre>1: 1
2: 3
3: 5
4: 15
5: 5
6: 59
7: 159
8: 189
9: 569
10: 105
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">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)
}</syntaxhighlight>
{{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
</pre>
(takes ~20 seconds)
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Zig">
import math
fn main() {
limit := 10 // depending on computer, higher numbers = longer times
mut num, mut k := i64(0), i64(0)
println("n k\n-------")
for n in 1..limit {
k = -1
for n < limit {
k = k + 2
num = math.powi(2, math.powi(2 , n)) - k
if is_prime(num) == true {
println("${n} ${k}")
break
}
}
}
}
fn is_prime(num i64) bool {
if num <= 1 {return false}
if num % 2 == 0 && num != 2 {return false}
for idx := 3; idx <= math.floor(num / 2) - 1; idx += 2 {
if num % idx == 0 {return false}
}
return true
}
</syntaxhighlight>
{{out}}
<pre>
n k
-------
1 1
2 3
3 5
4 15
5 5
6 59
7 159
8 189
9 569
10 105
</pre>
=={{header|Wren}}==
Line 205 ⟶ 605:
{{libheader|Wren-fmt}}
Manages to find the first ten but takes 84 seconds to do so.
<
import "./fmt" for Fmt
Line 223 ⟶ 623:
System.print(" n k")
System.print("----------")
for (n in 1..10) Fmt.print("$2d $d", n, a.call(n))</
{{out}}
Line 243 ⟶ 643:
{{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.
<
import "./fmt" for Fmt
Line 261 ⟶ 661:
System.print(" n k")
System.print("----------")
for (n in 1..14) Fmt.print("$2d $d", n, a.call(n))</
{{out}}
| |||