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

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

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

Library: Wren-gmp

An embedded version as Wren-CLI (with BigInt) will be very slow for this task.

The following takes about 17.5 seconds to get to n = 13 but 7 minutes 15 seconds to reach n = 14. I didn't bother after that. <lang ecmascript>import "./gmp" for Mpz import "./fmt" for Fmt

var a = Fn.new { |n|

   var p = Mpz.one.lsh(1 << n)
   var k = 1
   while (true) {
       var q = p - k
       if (q.probPrime(15) > 0) return k
       k = k + 2
   }

}

System.print(" n k") System.print("----------") for (n in 1..14) Fmt.print("$2d $d", n, a.call(n))</lang>

Output: