I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Ultra useful primes

From Rosetta Code
Task
Ultra useful primes
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[edit]

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

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[edit]

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[edit]

Works with: Factor version 0.99 2021-06-02
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[edit]

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

Julia[edit]

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)

Perl[edit]

Library: ntheory
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[edit]

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[edit]

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

Wren[edit]

CLI[edit]

Library: Wren-big
Library: Wren-fmt

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[edit]

Library: 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 "./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