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

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 

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:

 n   k
----------
 1   1
 2   3
 3   5
 4   15
 5   5
 6   59
 7   159
 8   189
 9   569
10   105

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:

 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