Wagstaff primes

A Wagstaff prime is a prime number of the form (2^p + 1)/3 where the exponent p is an odd prime.

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

Definition

Example

(2^5 + 1)/3 = 11 is a Wagstaff prime because both 5 and 11 are primes.

Task

Find and show here the first 10 Wagstaff primes and their corresponding exponents p.

Stretch (requires arbitrary precision integers)

Find and show here the exponents p corresponding to the next 14 Wagstaff primes (not the primes themselves) and any more that you have the patience for.

When testing for primality, you may use a method which determines that a large number is probably prime with reasonable certainty.

References

• Wikipedia - Wagstaff prime
• OEIS:A000979 - Wagstaff numbers

Wren

Library: Wren-math

Library: Wren-gmp

Library: Wren-fmt

An embedded solution so we can use GMP to test for probable primeness in a reasonable time.

Even so, as far as the stretch goal is concerned, takes around 25 seconds to find the next 14 Wagstaff primes but almost 10 minutes to find the next 19 on my machine (Core i7). I gave up after that.

import "./math" for Int
import "./gmp" for Mpz
import "./fmt" for Fmt

var isWagstaff = Fn.new { |p|
    var w = (2.pow(p) + 1) / 3
    if (!w.isInteger || !Int.isPrime(w)) return [false, null]
    return [true, [p, w]]
}

var isBigWagstaff = Fn.new { |p|
    var w = Mpz.one.lsh(p).add(1)
    if (!w.isDivisibleUi(3)) return [false, null]
    w.div(3)
    if (w.probPrime(15) == 0) return [false, null]
    return [true, p]
}

var start = System.clock
var p = 1
var wagstaff = []
while (wagstaff.count < 10) {
    while (true) {
        p = p + 2
        if (Int.isPrime(p)) break
    }
    var res = isWagstaff.call(p)
    if (res[0]) wagstaff.add(res[1])
}
System.print("First 10 Wagstaff primes for the values of 'p' shown:")
for (i in 0..9) Fmt.print("$2d: $d", wagstaff[i][0], wagstaff[i][1])
System.print("\nTook %(System.clock - start) seconds")

var limit = 19
var count = 0
System.print("\nValues of 'p' for the next %(limit) Wagstaff primes and")
System.print("overall time taken to reach them to higher second:")
while (count < limit) {
    while (true) {
        p = p + 2
        if (Int.isPrime(p)) break
    }
    var res = isBigWagstaff.call(p)
    if (res[0]) {
        Fmt.print("$5d ($3d secs)", res[1], (System.clock - start).ceil)
        count = count + 1
    }
}

Output:

First 10 Wagstaff primes for the values of 'p' shown:
 3: 3
 5: 11
 7: 43
11: 683
13: 2731
17: 43691
19: 174763
23: 2796203
31: 715827883
43: 2932031007403

Took 0.056335 seconds

Values of 'p' for the next 19 Wagstaff primes and
overall time taken to reach them to higher second:
   61 (  1 secs)
   79 (  1 secs)
  101 (  1 secs)
  127 (  1 secs)
  167 (  1 secs)
  191 (  1 secs)
  199 (  1 secs)
  313 (  1 secs)
  347 (  1 secs)
  701 (  1 secs)
 1709 (  1 secs)
 2617 (  2 secs)
 3539 (  5 secs)
 5807 ( 25 secs)
10501 (198 secs)
10691 (210 secs)
11279 (251 secs)
12391 (348 secs)
14479 (599 secs)