# Ultra useful primes

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Ultra useful primes
You are encouraged to solve this task according to the task description, using any language you may know.

An ultra-useful prime is a member of the sequence where each a(n) is the smallest positive integer k such that 2(2n) - k is prime.

k must always be an odd number since 2 to any power is always even.

• 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.)

## 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.

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

ultraUseful: function [n][
k: 1
p: (2^2^n) - k
while ø [
if prime? p -> return k
p: p-2
k: k+2
]
]

print repeat "-" 10
loop 1..10 'x ->
print [(pad to :string x 3) "|" (pad.right to :string ultraUseful x 4)]
Output:
n | k
----------
1 | 1
2 | 3
3 | 5
4 | 15
5 | 5
6 | 59
7 | 159
8 | 189
9 | 569
10 | 105

## Factor

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

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:
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

## J

Implementation:

uup=: {{
ref=. 2x^2^y+1
k=. 1
while. -. 1 p: ref-k do. k=. k+2 end.
}}"0

I don't have the patience to get this little laptop to compute the first 10 such elements, so here I only show the first five:

uup i.5
1 3 5 15 5

## Julia

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)

## Mathematica/Wolfram Language

ClearAll[FindUltraUsefulPrimeK]
FindUltraUsefulPrimeK[n_] := Module[{num, tmp},
num = 2^(2^n);
Do[
If[PrimeQ[num - k],
tmp = k;
Break[];
]
,
{k, 1, \[Infinity], 2}
];
tmp
]
res = FindUltraUsefulPrimeK /@ Range[13];
Output:
1	1
2	3
3	5
4	15
5	5
6	59
7	159
8	189
9	569
10	105
11	1557

## Perl

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

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.

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

## Sidef

say(" n   k")
say("----------")

for n in (1..13) {
var t = 2**(2**n)
printf("%2d   %d\n", n, {|k| t - k -> is_prob_prime }.first)
}
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

(takes ~20 seconds)

## Wren

### CLI

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:
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.

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:
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