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

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

<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       #
                       # 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</lang>

Output:

 1 3 5 15 5 59 159 189 569 105

Arturo

<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)]</lang>

Output:

Factor

Works with: Factor version 0.99 2021-06-02

<lang 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</lang>

Output:

1 3 5 15 5 59 159 189 569 105

Go

Library: GMP(Go wrapper)

<lang 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))
   }

}</lang>

Output:

Julia

<lang julia>using Primes

nearpow2pow2prime(n) = findfirst(k -> isprime(2^(big"2"^n) - k), 1:10000)

@time println([nearpow2pow2prime(n) for n in 1:12])

</lang>

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

Library: ntheory

<lang 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;</lang>

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.

<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

CLI

Library: Wren-big

Library: Wren-fmt

Manages to find the first ten but takes 84 seconds to do so. <lang ecmascript>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))</lang>

Output:

Embedded

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. <lang ecmascript>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))</lang>

Output: