Wieferich primes

This page uses content from Wikipedia. The original article was at Weiferich prime. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In number theory, a Wieferich prime is a prime number p such that p² evenly divides 2^{(p − 1)} − 1 .

It is conjectured that there are infinitely many Wieferich primes, but as of March 2021,only two have been identified.

Task

Write a routine (function procedure, whatever) to find Wieferich primes.

Use that routine to identify and display all of the Wieferich primes less than 5000.

See also

OEIS A001220 - Wieferich primes

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: io kernel math math.functions math.primes prettyprint sequences ;

"Weiferich primes less than 5000:" print 5000 primes-upto [ [ 1 - 2^ 1 - ] [ sq divisor? ] bi ] filter .</lang>

Output:

Weiferich primes less than 5000:
V{ 1093 3511 }

Julia

<lang julia>using Primes

is_weiferich(p) = (big"2"^(p - 1) - 1) % p^2 == 0

function weiferich_to(N)

   n = 0
   while (n = nextprime(n + 1)) < N
       is_weiferich(n) && print(n, "   ")
   end

end

weiferich_to(5000) # prints 1093 3511 </lang>

Phix

include mpfr.e
function weiferich(integer p)
    mpz p2pm1m1 = mpz_init()
    mpz_ui_pow_ui(p2pm1m1,2,p-1)
    mpz_sub_ui(p2pm1m1,p2pm1m1,1)
    return mpz_fdiv_q_ui(p2pm1m1,p2pm1m1,p*p)=0
end function
printf(1,"Weiferich primes less than 5000: %V\n",{filter(get_primes_le(5000),weiferich)})

Output:

Weiferich primes less than 5000: {1093,3511}

Raku

<lang perl6>put "Weiferich primes less than 5000: ", join ', ', ^5000 .grep: { .is-prime and not ( exp($_-1, 2) - 1 ) % .² };</lang>

Output:

Weiferich primes less than 5000: 1093, 3511

Wren

Library: Wren-math

Library: Wren-big

<lang ecmascript>import "/math" for Int import "/big" for BigInt

var primes = Int.primeSieve(5000) System.print("Weiferich primes < 5000:") for (p in primes) {

   var num = (BigInt.one << (p - 1)) - 1
   var den = p * p
   if (num % den == 0) System.print(p)

}</lang>

Output:

Weiferich primes < 5000:
1093
3511