Ultra useful primes

An ultra-useful prime is a member of the sequence where each a(n) is the smallest positive integer k such that 2^(2ⁿ) - 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

OEIS:A058220 - Ultra-useful primes: smallest k such that 2^(2^n) - k is prime

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.

Library: ALGOL 68-primes

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:

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]

Library: GMP(Go wrapper)

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:

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:

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: