Berechnen Sie bei einer positiven ganzen Zahl n die n- ^te Wilson-Zahl W (n), wobei

Wilson-Zahlenformel

und e = 1, wenn n ein primitives Wurzelmodulo n hat , andernfalls ist e = -1. Mit anderen Worten, n hat eine Primitivwurzel, wenn es keine ganze Zahl x gibt, wobei 1 < x < n-1 und x ² = 1 mod n .

Dies ist Code-Golf. Erstellen Sie also den kürzesten Code für eine Funktion oder ein Programm, die bzw. das die n- ^te Wilson-Zahl für eine Ganzzahl n > 0 berechnet .
Sie können entweder eine 1-basierte oder eine 0-basierte Indizierung verwenden. Sie können auch die ersten n Wilson-Zahlen ausgeben .
Dies ist die OEIS-Sequenz A157249 .

Testfälle

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

code-golf math sequence number-theory primes Meilen
quelle

Auch Oeis teilt durch n danach

H.PWiz

@EriktheOutgolfer Ich habe hinzugefügt, was unter einer primitiven Wurzel zu verstehen ist.

Meilen

1

Sollen wir durch n teilen?

Undichte Nonne

Soweit ich weiß, wenn k = 1und e = -1wäre das Ergebnis des Produkts 0. (Es tut mir leid, dass ich viele Fragen gestellt habe, aber ich brauche Klarstellungen für meine Antwort: p)

Erik the Outgolfer

2

Diese Zahlen werden Wilson-Quotienten genannt . Eine Wilson-Zahl ist eine Ganzzahl, die ihren Wilson-Quotienten gleichmäßig aufteilt. Beispielsweise ist 13 eine Wilson-Zahl seit 13 | 36846277 . Außerdem schließt W (n) normalerweise den Nenner aus.

Dennis

8

Gelee , 8 7 Bytes

1 Byte danke an Dennis.

gRỊTP‘:

Probieren Sie es online!

Sie müssen nicht wirklich rechnen, eda Sie sowieso teilen müssen.

Undichte Nonne
quelle

gRỊTSpeichert ein Byte.

Dennis

Dennis kommt zu den gRỊTDetails von Jelly ...

corsiKa

6

Schale , 11 Bytes

S÷ȯ→Π§foε⌋ḣ

Probieren Sie es online!

Erläuterung

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

H.PWiz
quelle

Bitte eine Erklärung hinzufügen? Ich denke, Sie haben eine

gute Idee

3

Mathematica, 91 Bytes

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

J42161217
quelle

@BillSteihn bitte nicht direkt die Antworten anderer bearbeiten ( relevante Metadiskussion ). Wenn Sie einen Golfvorschlag haben, hinterlassen Sie bitte einen Kommentar!

JungHwan Min

@JungHwanMin Ja, mir ist aufgefallen, dass bearbeiten!

Vielen

3

Pyth , 11 Bytes

/h*Ff>2iTQS

Probieren Sie es hier aus!

Wie?

/h*Ff>2iTQS - Volles Programm.
S- Inklusivbereich generieren [1, Eingabe]
f - Filter-Keep diejenigen:
- iTQ - Wessen GCD mit dem Eingang.
- >2- weniger als zwei (kann durch eine der folgenden Fassung: q1, !t)
*F- Multiplikation wiederholt anwenden. Mit anderen Worten, das Produkt der Liste.
h - Erhöhen Sie das Produkt um 1.
/ - Etageneinteilung mit der Eingabe.

TL; DR : Holen Sie sich alle Koprime zum Eingang in den Bereich [1, Eingang] , holen Sie sich ihr Produkt, erhöhen Sie es und dividieren Sie es durch den Eingang.

Mr. Xcoder
quelle

2

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

Probieren Sie es online!

Dennis
quelle

2

J, 33 Bytes

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

Dies ist mehr eine Bitte, eine Verbesserung zu sehen als alles andere. Ich habe zuerst eine stillschweigende Lösung ausprobiert, aber sie war länger.

Erläuterung

Dies ist eine ziemlich einfache Übersetzung von Mr. Xcoders Lösung in J.

Probieren Sie es online!

Jona
quelle

2

05AB1E , 8 Bytes

Lʒ¿}P>I÷

Probieren Sie es online!

Emigna
quelle

2

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)

Verwendet eine ganzzahlige Division, anstatt ewie viele Antworten hier herauszufinden , obwohl ich das herausgefunden habee=2*any((1:n)^2%%n==1%%n)-1 einschließlich des Randfalls, von n=1dem ich dachte, dass er ziemlich ordentlich war.

Verwendet die vektorisierte GCD-Funktion von rturnbull .

Probieren Sie es online!

Giuseppe
quelle

2

Pari / GP , 36 Bytes

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

Probieren Sie es online!

Alephalpha
quelle

2

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>

Erweitern Sie das Snippet

Die Ganzzahldivision schlägt erneut zu. Bearbeiten: 2 Bytes dank @Shaggy gespeichert. Sparte weitere 2 Bytes, indem es viel rekursiver gemacht wurde, so dass es möglicherweise bei kleineren Werten als früher fehlschlägt.

Neil
quelle

70 Bytes (obwohl ich noch keine Chance hatte, eine ganze Reihe von Tests durchzuführen):f=(n,i=n,p=1,g=(a,b)=>b?g(b,a%b):a)=>--i?f(n,i,g(n,i)-1?p:p*i):-~p/n|0

Shaggy

Ich bin zu der rekursiven Lösung zurückgekehrt, an der ich gearbeitet habe, bevor ich beschlossen habe, stattdessen ein Array zuzuordnen, und habe es auch auf 70 Byte reduziert. Es ist ein bisschen chaotisch, aber möglicherweise können Sie etwas daraus retten, um Ihre Lösung unter 70 zu bringen:(n,x=n)=>(g=s=>--x?g(s*(h=(y,z)=>z?h(z,y%z):--y?1:x)(n,x)):++s)(1)/n|0

Shaggy

@ Shaggy Nun, ich war inspiriert, es mir noch einmal anzuschauen, aber ich bin mir nicht sicher, was Sie erwartet haben ...

Neil

2

Haskell , 42 Bytes

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

Probieren Sie es online!

Verwendet den ganzzahligen Divisionstrick wie alle anderen Antworten.
Verwendet 1-basierte Indizes.

Erläuterung

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

SEJPM
quelle

1

Japt , 11 Bytes

õ fjU ×Ä zU

Versuch es

Erläuterung

Implizite Eingabe einer Ganzzahl U.

õ

Generieren Sie ein Array von Ganzzahlen von 1 bis U.

fjU

Filter ( f) Co-Primzahlen von U.

×

Reduzieren Sie durch Multiplikation.

Ä

Addiere 1.

zU

Teilen Sie Udas Ergebnis durch , begrenzen Sie es und geben Sie es implizit aus.

Zottelig
quelle

für n = 25 gibt es 1654529071288638400 zurück und es wäre falsch, weil es 1654529071288638505

RosLuP

@RosLuP: Wie der Herausforderungsautor bestätigt hat, müssen wir keine Zahlen von mehr als 32 Bit verarbeiten.

Shaggy

1

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)

Füge einen Typ hinzu, ungolf das und das Ergebnis

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

RosLuP
quelle

1

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

Mein erster Versuch war ein paar Bytes länger als Neils Lösung, weshalb ich ihn ursprünglich zugunsten der unten aufgeführten Array-Reduktionslösung verworfen habe. Ich habe seitdem Golf gespielt, um mit Neil zu binden.

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

Versuch es

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>

Erweitern Sie das Snippet

Nicht rekursiv, 76 Bytes

Ich wollte versuchen, einer nicht rekursiven Lösung zu zeigen, wie es ausgehen würde - nicht so schlimm, wie ich es erwartet hatte.

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

Versuch es

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>

Erweitern Sie das Snippet

Zottelig
quelle

Berechnen Sie die Wilson-Zahlen

Testfälle

Antworten:

Gelee , 8 7 Bytes

Schale , 11 Bytes

Erläuterung

Mathematica, 91 Bytes

Pyth , 11 Bytes

Wie?

Python 2 , 62 Bytes

J, 33 Bytes

Erläuterung

05AB1E , 8 Bytes

R 82 Bytes

Pari / GP , 36 Bytes

JavaScript (ES6), 72 70 68 Bytes

Haskell , 42 Bytes

Japt , 11 Bytes

Erläuterung

Axiom, 121 Bytes

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

Versuch es

Nicht rekursiv, 76 Bytes

Versuch es