Ultra useful primes

Ultra useful primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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