I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Ultra useful primes

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    ODEND`
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 [pad "n" 3 "|" pad.right "k" 4]print repeat "-" 10loop 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
```

## 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)
```

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

## Wren

### CLI

Library: Wren-big
Library: Wren-fmt

Manages to find the first ten but takes 84 seconds to do so.

`import "./big" for BigIntimport "./fmt" for Fmt var one = BigInt.onevar 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 Mpzimport "./fmt" for Fmt var one = Mpz.onevar 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
```