Biorąc pod uwagę dodatnią liczbę całkowitą n , oblicz n- ^tą liczbę Wilsona W (n) gdzie

oraz e = 1, jeśli n ma prymitywny moduł główny n , w przeciwnym razie e = -1. Innymi słowy, n ma pierwotny pierwiastek, jeśli nie istnieje liczba całkowita x, gdzie 1 < x < n-1 i x ² = 1 mod n .

• To jest kod-golf więc tworzyć najkrótszy kod funkcji lub programu, który oblicza n ^th liczby Wilson liczbę całkowitą wejściowego n > 0.
• Możesz użyć indeksowania 1 lub 0. Możesz także wybrać, aby wypisać pierwsze n liczb Wilsona.
• Jest to sekwencja OEIS A157249 .

Przypadki testowe

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

Galaretka , 8 7 bajtów

1 bajt dzięki Dennisowi.

gRỊTP‘:

Wypróbuj online!

Tak naprawdę nie musisz obliczać, eponieważ i tak musisz dzielić.

Łuska , 11 bajtów

S÷ȯ→Π§foε⌋ḣ

Wypróbuj online!

Wyjaśnienie

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

Mathematica, 91 bajtów

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

Pyth , 11 bajtów

/h*Ff>2iTQS

Wypróbuj tutaj!

W jaki sposób?

• /h*Ff>2iTQS - Pełny program.

• S- Wygeneruj obejmujący zakres [1, wejście]

• f - Filtruj:

  • iTQ - którego GCD z wejściem.

  • >2- jest mniejsza niż dwa (może być zastąpiony przez jedną z następujących czynności: q1, !t)

• *F- Zastosuj mnożenie wielokrotnie. Innymi słowy, produkt z listy.

• h - Zwiększ produkt o 1.

• / - Podział podłogi z wejściem.

TL; DR : Pobierz wszystkie koprimy do wejścia w zakresie [1, wejście] , pobierz ich produkt, zwiększ go i podziel przez wejście.

Python 2 , 62 bajty

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

Wypróbuj online!

J, 33 bajty

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

Ten jest raczej prośbą o poprawę niż cokolwiek innego. Najpierw wypróbowałem milczące rozwiązanie, ale było dłużej.

wyjaśnienie

Jest to dość proste tłumaczenie rozwiązania pana Xcodera na J.

Wypróbuj online!

05AB1E , 8 bajtów

Lʒ¿}P>I÷

Wypróbuj online!

R , 82 bajty

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

Używa podziału na liczby całkowite, a nie wymyśla, ejak wiele odpowiedzi tutaj, chociaż wymyśliłem to, w e=2*any((1:n)^2%%n==1%%n)-1tym przypadek skrajny, n=1który moim zdaniem był całkiem fajny.

Uses rturnbull's vectorized GCD function.

Try it online!

Pari/GP, 36 bytes

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

Try it online!

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.

Haskell , 42 bajty

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

Wypróbuj online!

Używa sztuczki dzielenia liczb całkowitych jak wszystkich innych odpowiedzi.
Wykorzystuje wskaźniki oparte na 1.

Wyjaśnienie

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

Japt , 11 bajtów

õ fjU ×Ä zU

Spróbuj

Wyjaśnienie

Domniemane wprowadzenie liczby całkowitej U.

õ

Wygeneruj tablicę liczb całkowitych od 1 do U.

fjU

Współczynniki filtru ( f) dla U.

×

Zmniejsz przez pomnożenie.

Ä

Dodaj 1.

zU

Podziel przez U, potwierdź wynik i domyślnie uzyskaj wynik.

Aksjomat, 121 bajtów

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)

dodaj jakiś typ, odłóż to i wynik

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

JavaScript (ES6), 83 81 80 78 76 68 bajtów

Mój pierwszy przebieg był o kilka bajtów dłuższy niż rozwiązanie Neila, dlatego pierwotnie porzuciłem to na rzecz rozwiązania redukcji macierzy poniżej. Od tego czasu grałem w golfa, żeby związać się z Neilem.

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

Spróbuj

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>

Brak rekurencji, 76 bajtów

Chciałem dać nierekurencyjne rozwiązanie, aby zobaczyć, jak to się potoczy - nie tak źle, jak się spodziewałem.

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

Spróbuj

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>