Calculez les nombres de Wilson

14

Etant donné un nombre entier positif n , le calcul de la n ième Wilson nombre W (n) , où

Formule du nombre de Wilson

et e = 1 si n a un module racine primitif n , sinon e = -1. En d'autres termes, n a une racine primitive s'il n'existe pas un entier x où 1 < x < n-1 et x 2 = 1 mod n .

  • Il s'agit de code-golf, alors créez le code le plus court pour une fonction ou un programme qui calcule le n ème nombre Wilson pour un nombre entier d' entrée n > 0.
  • Vous pouvez utiliser une indexation basée sur 1 ou basée sur 0. Vous pouvez également choisir de sortir le premier n nombres Wilson.
  • Il s'agit de la séquence OEIS A157249 .

Cas de test

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 miles
la source
De plus, Oeis divise par n par la suite
H.PWiz
@EriktheOutgolfer J'ai ajouté ce que l'on entend par avoir une racine primitive.
miles
1
Sommes-nous censés diviser par n?
Leaky Nun
Autant que je sache, si k = 1et e = -1, le résultat du produit serait 0. (désolé de poser beaucoup de questions mais j'ai besoin de clarifications pour ma réponse: p)
Erik the Outgolfer
2
Ces nombres sont appelés quotients de Wilson . Un nombre de Wilson est un entier qui divise son quotient de Wilson de manière égale. Par exemple, 13 est un nombre de Wilson depuis 13 | 36846277 . De plus, W (n) exclut généralement le dénominateur.
Dennis

Réponses:

8

Gelée , 8 7 octets

1 octet merci à Dennis.

gRỊTP‘:

Essayez-le en ligne!

Vous n'avez pas vraiment besoin de calculer ecar vous devez quand même diviser.

Leaky Nun
la source
gRỊTenregistre un octet.
Dennis
Dennis gRỊT
revient
6

Husk , 11 octets

S÷ȯ→Π§foε⌋ḣ

Essayez-le en ligne!

Explication

          ḣ   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
la source
Veuillez ajouter une explication? Je pense que vous avez un algo astucieux là-bas ...
Erik the Outgolfer
3

Mathematica, 91 octets

If[(k=#)==1,2,(Times@@Select[Range@k,CoprimeQ[k,#]&]+If[IntegerQ@PrimitiveRoot@#,1,-1])/#]&
J42161217
la source
@BillSteihn, veuillez ne pas modifier directement les réponses des autres ( méta-discussion pertinente ). Si vous avez une suggestion de golf, veuillez laisser un commentaire à la place!
JungHwan Min
@JungHwanMin Oui, j'ai remarqué cette modification! merci d'avoir aidé les nouveaux utilisateurs avec les règles
J42161217
3

Pyth , 11 octets

/h*Ff>2iTQS

Essayez-le ici!

Comment?

  • /h*Ff>2iTQS - Programme complet.

  • S- Générer la plage inclusive [1, entrée]

  • f - Filtrez-les:

    • iTQ - dont GCD avec l'entrée.

    • >2- est inférieure à deux (peut être remplacé par une ou l' autre des éléments suivants: q1, !t)

  • *F- Appliquer la multiplication à plusieurs reprises. En d'autres termes, le produit de la liste.

  • h - Augmentez le produit de 1.

  • / - Division du plancher avec l'entrée.

TL; DR : Obtenez tous les coprimes à l'entrée dans la plage [1, entrée] , obtenez leur produit, incrémentez-le et divisez-le par l'entrée.

M. Xcoder
la source
2

J, 33 octets

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

Celui-ci est plus une demande de voir une amélioration que toute autre chose. J'ai d'abord essayé une solution tacite, mais c'était plus long que cela.

explication

Il s'agit d'une traduction assez simple de la solution de M. Xcoder en J.

Essayez-le en ligne!

Jonas
la source
2

R , 82 octets

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

Utilise la division entière plutôt que de trouver ecomme beaucoup de réponses ici, bien que j'aie e=2*any((1:n)^2%%n==1%%n)-1compris que le cas de bord den=1 que je pensais était assez soigné.

Utilise la fonction GCD vectorisée de rturnbull .

Essayez-le en ligne!

Giuseppe
la source
2

JavaScript (ES6), 72 70 68 octets

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>
Développer l'extrait

La division entière frappe à nouveau. Edit: sauvé 2 octets grâce à @Shaggy. Enregistré 2 octets supplémentaires en le rendant beaucoup plus récursif, il peut donc échouer pour des valeurs plus petites qu'auparavant.

Neil
la source
70 octets (même si je n'ai pas encore eu la chance de lancer un ensemble complet de tests):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
Je suis retourné à la solution récursive sur laquelle je travaillais avant de décider d'essayer de mapper un tableau à la place et de le réduire à 70 octets également. C'est un peu le bordel, mais vous pourriez peut-être en récupérer quelque chose pour aider à faire descendre votre solution en dessous de 70:(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 Eh bien, j'ai été inspiré pour y jeter un œil, mais je ne suis pas sûr que ce soit ce que vous attendiez ...
Neil
2

Haskell , 42 octets

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

Essayez-le en ligne!

Utilise l'astuce de division entière comme toutes les autres réponses.
Utilise des indices basés sur 1.

Explication

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
la source
1

Japt , 11 octets

õ fjU ×Ä zU

Essayez-le

Explication

Saisie implicite d'entier U.

õ

Générez un tableau d'entiers de 1 à U.

fjU

Filter ( f) co-nombres premiers de U.

×

Réduisez par multiplication.

Ä

Ajoutez 1.

zU

Divisez par U, plancher le résultat et implicitement sortie.

Hirsute
la source
pour n = 25, il renvoie 1654529071288638400 et ce serait faux car ce serait 1654529071288638505
RosLuP
@RosLuP: Comme l'a confirmé l'auteur du défi, nous n'avons pas besoin de gérer des nombres supérieurs à 32 bits.
Shaggy
1

Axiome, 121 octets

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)

ajouter un type, débloquer cela et le résultat

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
la source
1

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

Mon premier passage à ceci était quelques octets plus long que la solution de Neil, c'est pourquoi je l'ai abandonné à l'origine en faveur de la solution de réduction de tableau ci-dessous. Je l'ai depuis joué au golf pour nouer avec 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

Essayez-le

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>
Développer l'extrait

Non récursif, 76 octets

Je voulais essayer une solution non récursive pour voir comment cela se passerait - pas aussi mauvais que ce à quoi je m'attendais.

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

Essayez-le

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>
Développer l'extrait

Hirsute
la source