Compute the Wilson numbers

Question

Given a positive integer n, compute the n^th Wilson number W(n) where

and e = 1 if n has a primitive root modulo n, otherwise e = -1. In other words, n has a primitive root if there does not exist an integer x where 1 < x < n-1 and x² = 1 mod n.

• This is code-golf so create the shortest code for a function or program that computes the n^th Wilson number for an input integer n > 0.
• You may use either 1-based or 0-based indexing. You may also choose to output the first n Wilson numbers.
• This is the OEIS sequence A157249.

Test Cases

n  W(n)
1  2
2  1
3  1
4  1
5  5
6  1
7  103
8  13
9  249
10 19
11 329891
12 32
13 36846277
14 1379
15 59793
16 126689
17 1230752346353
18 4727
19 336967037143579
20 436486
21 2252263619
22 56815333
23 48869596859895986087
24 1549256
25 1654529071288638505

Answer 1

Jelly, 8 7 bytes

1 byte thanks to Dennis.

gRỊTP‘:

Try it online!

You don't really have to compute e since you need to divide anyway.

Answer 2

Husk, 11 bytes

S÷ȯ→Π§foε⌋ḣ

Try it online!

Explanation

          ḣ   Range from 1 to input
     §foε⌋    Keep only those whose gcd with the input is 1
    Π         Product
  ȯ→          Plus 1
S÷            Integer division with input

Answer 3

Mathematica, 91 bytes

If[(k=#)==1,2,(Times@@Select[Range@k,CoprimeQ[k,#]&]+If[IntegerQ@PrimitiveRoot@#,1,-1])/#]&

Answer 4

Pyth, 11 bytes

/h*Ff>2iTQS

Try it here!

---

How?

• /h*Ff>2iTQS - Full program.

• S - Generate the inclusive range [1, input]

• f - Filter-keep those:

  • iTQ - whose GCD with the input.

  • >2 - Is less than two (can be replaced by either of the following: q1, !t)

• *F - Apply multiplication repeatedly. In other words, the product of the list.

• h - Increment the product by 1.

• / - Floor division with the input.

TL;DR: Get all the coprimes to the input in the range [1, input], get their product, increment it and divide it by the input.

Answer 5

Python 2, 62 bytes

n=input();k=r=1
exec'r*=k/n*k%n!=1or k/n;k+=1;'*n*n
print-~r/n

Try it online!

Answer 6

J, 33 bytes

3 :'<.%&y>:*/(#~1&=@(+.&y))1+i.y'

This one is more of a request to see an improvement than anything else. I tried a tacit solution first, but it was longer than this.

explanation

This is fairly straightforward translation of Mr. Xcoder's solution into J.

Try it online!

Answer 7

05AB1E, 8 bytes

Lʒ¿}P>I÷

Try it online!

Answer 8

R, 82 bytes

function(n)(prod((1:n)[g(n,1:n)<2])+1)%/%n
g=function(a,b)ifelse(o<-a%%b,g(b,o),b)

Uses integer division rather than figuring out e like many answers here, although I did work out that e=2*any((1:n)^2%%n==1%%n)-1 including the edge case of n=1 which I thought was pretty neat.

Uses rturnbull's vectorized GCD function.

Try it online!

Answer 9

Pari/GP, 36 bytes

n->(prod(i=1,n,i^(gcd(i,n)==1))+1)\n

Try it online!

Answer 10

JavaScript (ES6), 72 70 68 bytes

f=(n,p=1,i=n,a=n,b=i)=>i?f(n,b|a-1?p:p*i,i-=!b,b||n,b?a%b:i):-~p/n|0

<input type=number min=1 oninput=o.textContent=f(+this.value)><pre id=o>

Integer division strikes again. Edit: Saved 2 bytes thanks to @Shaggy. Saved a further 2 bytes by making it much more recursive, so it may fail for smaller values than it used to.

Answer 11

Haskell, 42 bytes

f n=div(product[x|x<-[1..n],gcd x n<2]+1)n

Try it online!

Uses the integer division trick as all the other answers.
Uses 1-based indices.

Explanation

f n=                                       -- function
    div                                  n -- integer division of next arg by n
       (product                            -- multiply all entries in the following list
               [x|                         -- return all x with ...
                  x<-[1..n],               -- ... 1 <= x <= n and ...
                            gcd x n<2]     -- ... gcd(x,n)==1
                                      +1)  -- fix e=1

Answer 12

Japt, 11 bytes

õ fjU ×Ä zU

Try it

---

Explanation

Implicit input of integer U.

õ

Generate an array of integers from 1 to U.

fjU

Filter (f) co-primes of U.

×

Reduce by multiplication.

Ä

Add 1.

zU

Divide by U, floor the result and implicitly output.

Answer 13

Axiom, 121 bytes

f(n)==(e:=p:=1;for i in 1..n repeat(if gcd(i,n)=1 then p:=p*i;e=1 and i>1 and i<n-1 and(i*i)rem n=1=>(e:=-1));(p+e)quo n)

add some type, ungolf that and result

w(n:PI):PI==
   e:INT:=p:=1
   for i in 1..n repeat
       if gcd(i,n)=1 then p:=p*i
       e=1 and i>1 and i<n-1 and (i*i)rem n=1=>(e:=-1)
   (p+e)quo n

(5) -> [[i,f(i)] for i in 1..25]
   (5)
   [[1,2], [2,1], [3,1], [4,1], [5,5], [6,1], [7,103], [8,13], [9,249],
    [10,19], [11,329891], [12,32], [13,36846277], [14,1379], [15,59793],
    [16,126689], [17,1230752346353], [18,4727], [19,336967037143579],
    [20,436486], [21,2252263619], [22,56815333], [23,48869596859895986087],
    [24,1549256], [25,1654529071288638505]]
                                                  Type: List List Integer

(8) -> f 101
   (8)
  9240219350885559671455370183788782226803561214295210046395342959922534652795_
   041149400144948134308741213237417903685520618929228803649900990099009900990_
   09901
                                                    Type: PositiveInteger

Answer 14

JavaScript (ES6), 83 81 80 78 76 68 bytes

My first pass at this was a few bytes longer than Neil's solution, which is why I originally ditched it in favour of the array reduction solution below. I've since golfed it down to tie with Neil.

n=>(g=s=>--x?g(s*(h=(y,z)=>z?h(z,y%z):--y?1:x)(n,x)):++s)(1,x=n)/n|0

---

Try it

o.innerText=(f=
n=>(g=s=>--x?g(s*(h=(y,z)=>z?h(z,y%z):--y?1:x)(n,x)):++s)(1,x=n)/n|0
)(i.value=8);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

---

Non-recursive, 76 bytes

I wanted to give a non-recursive solution a try to see how it would turn out - not as bad as I expected.

n=>-~[...Array(x=n)].reduce(s=>s*(g=(y,z)=>z?g(z,y%z):y<2?x:1)(--x,n),1)/n|0

---

Try it

o.innerText=(f=
n=>-~[...Array(x=n)].reduce(s=>s*(g=(y,z)=>z?g(z,y%z):y<2?x:1)(--x,n),1)/n|0
)(i.value=8);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>