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(2n) - k is prime.
You are encouraged to solve this task according to the task description, using any language you may know.
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
ALGOL 68
Uses Algol 68G's LONG LONG INT which has programmer-specifiable precision. Uses Miller Rabin primality testing.
<lang algol68>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</lang>
- Output:
1 3 5 15 5 59 159 189 569 105
Factor
<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
Go
<lang 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)) }
}</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
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
<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
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
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