Contexte

D'Euler indicatrice de fonction φ(n)est définie comme étant le nombre de nombres entiers inférieurs ou égaux à nqui sont relativement premier n, qui est, le nombre de valeurs possibles xdans 0 < x <= npour lesquels gcd(n, x) == 1. Nous avons eu un peu totient - connexes défis , mais jamais celui qui est juste le calculer.

Le mappage de la fonction de totient sur les nombres entiers est OEIS A000010 .

Défi

Étant donné un entier n > 0, calculez φ(n). Vous pouvez prendre des entrées via des arguments de ligne de commande, des entrées standard, des arguments de fonction ou toute autre chose raisonnable. Vous pouvez donner une sortie via une sortie standard, des valeurs de retour ou toute autre chose raisonnable. Les fonctions anonymes sont acceptables. Vous pouvez supposer que l'entrée ne dépassera pas votre méthode naturelle de stockage des entiers, par exemple inten C, mais vous devez prendre en charge les entrées jusqu'à 255. Si votre langage a une fonction de totient intégrée, vous ne pouvez pas l'utiliser.

Exemples

φ(1) => 1
φ(2) => 1
φ(3) => 2
φ(8) => 4
φ(9) => 6
φ(26) => 12
φ(44) => 20
φ(105) => 48

La réponse la plus courte en octets gagne. Si votre langue utilise un encodage autre que UTF-8, mentionnez-le dans votre réponse.

Mathematica, 27 22 octets

Range@#~GCD~#~Count~1&

Une fonction sans nom qui prend et retourne un entier.

Pas grand-chose à expliquer ici, sauf qu'il @s'agit de la notation de préfixe pour les appels de fonction et de ~...~la notation d'infixe (associative à gauche), donc ce qui précède est le même que:

Count[GCD[Range[#], #], 1] &

MATL, 7 octets

t:Zd1=s

Vous pouvez TryItOnline . Idée la plus simple, faire un vecteur 1 à N, et prendre en gcd de chaque élément avec N ( Zdfait gcd). Ensuite, trouvez quels éléments sont égaux à 1 et additionnez le vecteur pour obtenir la réponse.

J, 9 octets

(-~:)&.q:

Ceci est basé sur l' essai de Jsoftware sur les fonctions totientes.

Étant donné n = p ₁ ^{e ₁} ∙ p ₂ ^{e ₂} ∙∙∙ p _k ^{e _k} où p _k est un facteur premier de n , la fonction de totient φ ( n ) = φ ( p ₁ ^{e ₁} ) ∙ φ ( p ₂ ^{e ₂} ) ∙∙∙ φ ( p _k ^{e _k} ) = ( p ₁ - 1) p ₁ ^{e ₁ - 1} ∙ ( p ₂ - 1) p ₂^{e ₂ - 1} ∙∙∙ ( p _k - 1) p _k ^{e _k - 1} .

Usage

   f =: (-~:)&.q:
   (,.f"0) 1 2 3 8 9 26 44 105
  1  1
  2  1
  3  2
  8  4
  9  6
 26 12
 44 20
105 48
   f 12345
6576

Explication

(-~:)&.q:  Input: integer n
       q:  Prime decomposition. Get the prime factors whose product is n
(   )&     Operate on them
  ~:         Nub-sieve. Create a mask where 1 is the first occurrence
             of a unique value and 0 elsewhere
 -           Subtract elementwise between the prime factors and the mask
     &.q:  Perform the inverse of prime decomposition (Product of the values)

Gelée, 4 octets

Rgċ1

Essayez-le en ligne!

Explication

Rgċ1   Main monadic chain. Argument: z

R      Yield [1 2 3 .. z].
 g     gcd (of each) (with z).
  ċ1   Count the number of occurrences of 1.

Avec intégré

ÆṪ

Essayez-le en ligne!

Explication

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.

Haskell, 28 octets

f n=sum[1|1<-gcd n<$>[1..n]]

Utilise la mise en correspondance de constantes de Haskell . Les astuces ici sont assez standard pour le golf, mais je vais expliquer à un public général.

L'expression gcd n<$>[1..n]correspond gcd nà [1..n]. En d'autres termes, il calcule le gcdavec nde chaque nombre de 1à n:

[gcd n i|i<-[1..n]]

À partir d'ici, la sortie souhaitée est le nombre d' 1entrées, mais Haskell n'a pas de countfonction. La façon idiomatique de filterne garder que 1des, et de prendre le résultat length, ce qui est beaucoup trop long pour le golf.

Au lieu de cela, le filterest simulé par une compréhension [1|1<-l]de la liste avec la liste résultante l. Habituellement, les compréhensions de liste lient des valeurs à des variables comme dans [x*x|x<-l], mais Haskell permet de comparer un modèle, dans ce cas la constante 1.

Donc, en [1|1<-l]générant un 1sur chaque correspondance de 1, en extrayant efficacement les seuls 1de la liste d'origine. Faire appel sumà lui donne sa longueur.

Python 2, 44 octets

f=lambda n,d=1:d/n or-f(d)*(n%d<1)-~f(n,d+1)

Moins golfé:

f=lambda n:n-sum(f(d)for d in range(1,n)if n%d<1)

Utilise la formule dont les totaux d'Euler des diviseurs nont une somme de n:

La valeur de ϕ(n)peut alors être récursivement calculée comme nmoins la somme sur les diviseurs non triviaux. Effectivement, cela fait une inversion de Möbius sur la fonction d'identité. J'ai utilisé la même méthode dans un golf pour calculer la fonction Möbius .

Merci à Dennis d'avoir sauvé 1 octet avec un meilleur cas de base, en répartissant la valeur initiale de +ndans +1pour chacune des nboucles, faites comme -~.

Pyke, 5 octets

m.H1/

Essayez-le ici!

count(map(gcd, range(input)), 1)

Regex (ECMAScript), 131 octets

Au moins -12 octets grâce à Deadcode (dans le chat)

(?=((xx+)(?=\2+$)|x+)+)(?=((x*?)(?=\1*$)(?=(\4xx+?)(\5*(?!(xx+)\7+$)\5)?$)(?=((x*)(?=\5\9*$)x)(\8*)$)x*(?=(?=\5$)\1|\5\10)x)+)\10|x

Essayez-le en ligne!

La sortie est la longueur de la correspondance.

Les expressions régulières ECMAScript rendent extrêmement difficile de compter quoi que ce soit. Toute backref définie à l'extérieur d'une boucle sera constante pendant la boucle, toute backref définie à l'intérieur d'une boucle sera réinitialisée lors de la boucle. Ainsi, la seule façon de transporter l'état sur des itérations de boucle est d'utiliser la position de correspondance actuelle. C'est un entier unique, et il ne peut que diminuer (enfin, la position augmente, mais la longueur de la queue diminue, et c'est à cela que nous pouvons faire des calculs).

Compte tenu de ces restrictions, le simple comptage des nombres premiers semble impossible. Au lieu de cela, nous utilisons la formule d' Euler pour calculer le total.

Voici à quoi cela ressemble en pseudocode:

N = input
Z = largest prime factor of N
P = 0

do:
   P = smallest number > P that’s a prime factor of N
   N = N - (N / P)
while P != Z

return N

Il y a deux choses douteuses à ce sujet.

Tout d'abord, nous ne sauvegardons pas l'entrée, uniquement le produit actuel, alors comment pouvons-nous accéder aux facteurs premiers de l'entrée? L'astuce est que (N - (N / P)) a les mêmes facteurs premiers> P que N. Il peut gagner de nouveaux facteurs premiers <P, mais nous les ignorons quand même. Notez que cela ne fonctionne que parce que nous itérons sur les facteurs premiers du plus petit au plus grand, aller dans l'autre sens échouerait.

Deuxièmement, nous devons nous souvenir de deux nombres sur les itérations de boucle (P et N, Z ne compte pas car il est constant), et je viens de dire que c'était impossible! Heureusement, nous pouvons regrouper ces deux chiffres en un seul. Notez qu'au début de la boucle, N sera toujours un multiple de Z, tandis que P sera toujours inférieur à Z. Ainsi, nous pouvons simplement nous souvenir de N + P et extraire P avec un modulo.

Voici le pseudo-code légèrement plus détaillé:

N = input
Z = largest prime factor of N

do:
   P = N % Z
   N = N - P
   P = smallest number > P that’s a prime factor of N
   N = N - (N / P) + P
while P != Z

return N - Z

Et voici l'expression régulière commentée:

# \1 = largest prime factor of N
# Computed by repeatedly dividing N by its smallest factor
(?= ( (xx+) (?=\2+$) | x+ )+ )

(?=
        # Main loop!
        (
                # \4 = N % \1, N -= \4
                (x*?) (?=\1*$)

                # \5 = next prime factor of N
                (?= (\4xx+?) (\5* (?!(xx+)\7+$) \5)? $ )

                # \8 = N / \5, \9 = \8 - 1, \10 = N - \8
                (?= ((x*) (?=\5\9*$) x) (\8*) $ )

                x*
                (?=
                        # if \5 = \1, break.
                        (?=\5$) \1
                |
                        # else, N = (\5 - 1) + (N - B)
                        \5\10
                )
                x
        )+
) \10

Et en bonus…

Regex (ECMAScript 2018, nombre de correspondances), 23 octets

x(?<!^\1*(?=\1*$)(x+x))

Essayez-le en ligne!

La sortie est le nombre de correspondances. ECMAScript 2018 introduit une analyse de longueur variable (évaluée de droite à gauche), qui permet de compter simplement tous les nombres en coprime avec l'entrée.

Il s'avère que c'est indépendamment la même méthode utilisée par la solution de rétine de Leaky Nun , et que l'expression régulière est même de la même longueur ( et interchangeable ). Je le laisse ici car il peut être intéressant que cette méthode fonctionne dans ECMAScript 2018 (et pas seulement .NET).

                        # Implicitly iterate from the input to 0
x                       # Don’t match 0
 (?<!                 ) # Match iff there is no...
                 (x+x)  # integer >= 2...
         (?=\1*$)       # that divides the current number...
     ^\1*               # and also divides the input

J, 11 octets

+/@(1=+.)i.

Usage

>> f =: +/@(1=+.)i.
>> f 44
<< 20

où >>est STDIN et <<STDOUT.

Explication

+/ @ ( 1 = +. ) i.
               │
   ┌───────────┴┐
 +/@(1=+.)      i.
   │
 ┌─┼──┐
+/ @ 1=+.
    ┌─┼─┐
    1 = +.

>> (i.) 44            NB. generate range
<< 0 1 2 3 4 ... 43
>> (+.i.) 44          NB. calculate gcd of each with input
<< 44 1 2 1 4 ... 1
>> ((1=+.)i.) 44      NB. then test if each is one (1 if yes, 0 if no)
<< 0 1 0 1 0 ... 1
>> (+/@(1=+.)i.) 44   NB. sum of all the tests
<< 20

Python> = 3,5, 76 64 58 octets

Merci à LeakyNun d'avoir joué au golf sur 12 (!) Octets.

Merci à Sp3000 pour avoir joué au golf sur 6 octets.

import math
lambda n:sum(math.gcd(n,x)<2for x in range(n))

J'adore la lisibilité de Python. Cela a du sens, même à travers le golf.

Perl 6 ,  26 24  22 octets

{[+] (^$^n Xgcd $n) X== 1}
{+grep 2>*,(^$_ Xgcd$_)}
{[+] 2 X>(^$_ Xgcd$_)}

Explication:

{
  [+] # reduce using &infix:<+>
    2
    X[>] # crossed compared using &infix:«>»
    (
      ^$_    # up to the input ( excludes input )
      X[gcd] # crossed using &infix:<gcd>
      $_     # the input
    )
}

Exemple:

#! /usr/bin/env perl6
use v6.c;

my &φ = {[+] 2 X>(^$_ Xgcd$_)};

say φ(1) # 1
say φ(2) # 1
say φ(3) # 2
say φ(8) # 4
say φ(9) # 6
say φ(26) # 12
say φ(44) # 20
say φ(105) # 48

say φ 12345 # 6576

Julia, 25 octets

!n=sum(i->gcd(i,n)<2,1:n)

C'est simple - la sumfonction vous permet de lui donner une fonction à appliquer avant de sommer - essentiellement l'équivalent de l'exécution mapet ensuite sum. Cela compte directement le nombre de nombres premiers relativement inférieurs à n.

Python 2, 57 octets

f=lambda n,k=1,m=1:n*(k>n)or f(n-(n%k<m%k)*n/k,k+1,m*k*k)

Testez-le sur Ideone .

Contexte

Par la formule du produit d'Euler ,

où φ désigne la fonction de totient d'Euler et p ne varie que sur les nombres premiers.

Pour identifier les nombres premiers, nous utilisons un corollaire du théorème de Wilson :

Comment ça marche

À tout moment, la variable m sera égale au carré de la factorielle de k - 1 . En fait, nous avons nommé les arguments par défaut à k = 1 et m = 0! ² = 1 .

Tant que k ≤ n , est n*(k>n)évalué à 0 et le code suivant orest exécuté.

Rappelez-vous que m%kcela donnera 1 si m est premier et 0 sinon. Cela signifie que x%k<m%kcela donnera True si et seulement si k est un nombre premier et x est divisible par k .

Dans ce cas, le (n%k<m%k)*n/krendement n / k , et en le soustrayant de n remplace sa valeur précédente par n (1 - 1 / k) , comme dans la formule du produit d'Euler. Sinon, les (n%k<m%k)*n/krendements 0 et n restent inchangés.

Après avoir calculé ce qui précède, nous incrémentons k et multiplions m par la «vieille» valeur de k ² , maintenant ainsi la relation souhaitée entre k et m , puis appelons f récursivement avec les arguments mis à jour.

Une fois que k dépasse n , est n*(k>n)évalué à n , qui est renvoyé par la fonction.

Rubis, 32 octets

->n{(1..n).count{|i|i.gcd(n)<2}}

un lambda qui prend un entier n et retourne le nombre de nombres entiers dans la plage (1..n) en coprime avec n.

Brachylog , 25 octets

:{:1e.$pdL,?$pd:LcCdC}fl.

Explication

Brachylog n'a pas encore de GCD intégré, nous vérifions donc que les deux nombres n'ont pas de facteurs premiers en commun.

• Prédicat principal:

  :{...}fl.             Find all variables which satisfy predicate 1 when given to it as
                        output and with Input as input.
                        Unify the Output with the length of the resulting list
  

• Prédicat 1:

  :1e.                  Unify Output with a number between Input and 1
      $pdL              L is the list of prime factors of Output with no duplicates
          ,
           ?$pd:LcC     C is the concatenation of the list of prime factors of Input with
                        no duplicates and of L
                   dC   C with duplicates removed is still C
  

Pyth, 6 octets

smq1iQ

Essayez-le en ligne!

/iLQQ1

Essayez-le en ligne!

Explication

smq1iQ     input as Q
smq1iQdQ   implicitly fill variables

 m     Q   for d in [0 1 2 3 .. Q-1]:
    iQd        gcd of Q and d
  q1           equals 1? (1 if yes, 0 if no)
s          sum of the results


/iLQQ1     input as Q

 iLQQ      gcd of each in [0 1 2 3 .. Q-1] with Q
/    1     count the number of occurrences of 1

PowerShell v2 +, 72 octets

param($n)1..$n|%{$a=$_;$b=$n;while($b){$a,$b=$b,($a%$b)};$o+=!($a-1)};$o

PowerShell ne dispose pas d'une fonction GCD, j'ai donc dû rouler la mienne.

Cela prend l'entrée $n, puis s'étend de 1à $net dirige ceux-ci dans une boucle |%{...}. Chaque itération nous avons mis deux variables d'aide $aet $bpuis exécuter une GCD whileboucle. Chaque itération que nous vérifions $best toujours non nulle, puis enregistrons $a%$bvers $bet la valeur précédente de $bvers $apour la boucle suivante. Nous accumulons ensuite si $aest égal à 1dans notre variable de sortie $o. Une fois la boucle for terminée, nous la plaçons $osur le pipeline et la sortie est implicite.

Comme exemple de la façon dont la whileboucle fonctionne, réfléchissez $n=20et c'est parti $_=8. La première vérification a $b=20, nous entrons donc dans la boucle. Nous calculons d'abord $a%$bou 8%20 = 8, qui est réglé sur $ben même temps que 20sur $a. Vérifiez 8=0, et nous entrons dans la deuxième itération. Nous calculons 20%8 = 4et réglons ensuite cela sur $b, puis $asur 8. Vérifiez 4=0, et nous entrons dans la troisième itération. Nous calculons 8%4 = 0et réglons cela sur $b, puis réglons $asur 4. Vérifiez 0=0et nous quittons la boucle, donc le GCD (8,20) est $a = 4. Ainsi, !($a-1) = !(4-1) = !(3) = 0donc $o += 0et nous ne comptons pas celui-là.

Facteur, 50 octets

[ dup iota swap '[ _ gcd nip 1 = ] filter length ]

Fait un intervalle ( iota ) n , et curry n dans une fonction qui obtient gcd xn pour toutes les valeurs de 0 <= x <= n , teste si le résultat est 1 . Filtrez la plage d'origine pour savoir si le résultat de gcd xn était 1 et prenez sa longueur .

Japt -mx, 7 5 octets

yN ¥1

Exécutez-le en ligne

-2 octets grâce à Shaggy

Rétine, 36 29 octets

7 octets grâce à Martin Ender.

.+
$*
(?!(11+)\1*$(?<=^\1+)).

Essayez-le en ligne!

Explication

Il y a deux étapes (commandes).

Première étape

.+
$*

Il s'agit d'une simple substitution d'expression régulière, convertissant l'entrée en autant.

Par exemple, 5serait converti en 11111.

Deuxième étape

(?!(11+)\1*$(?<=^\1+)).

Cette expression régulière tente de faire correspondre les positions qui satisfont à la condition (co-amorçage avec entrée), puis renvoie le nombre de correspondances.

05AB1E, 7 octets

Lvy¹¿i¼

Expliqué

Lv        # for each x in range(1,n)
  y¹¿     # GCD(x,n)
     i¼   # if true (1), increase counter
          # implicitly display counter

Essayez-le en ligne

Lisp commun, 58 octets

(defun o(x)(loop for i from 1 to x if (=(gcd x i)1)sum 1))

Il s'agit d'une simple boucle qui compte jusqu'à 1 jusqu'au n donné et incrémente la somme si gcd = 1. J'utilise le nom de fonction o puisque t est la vraie valeur booléenne. Pas le plus court mais assez simple.

MATLAB / Octave, 21 octets

@(n)sum(gcd(n,1:n)<2)

Crée une fonction anonyme nommée ansqui peut être appelée avec l'entier ncomme seule entrée:ans(n)

Démo en ligne

Python 2 , 44 octets

lambda n:sum(k/n*k%n>n-2for k in range(n*n))

Cela utilise la même méthode pour identifier les coprimes comme ma réponse à "Coprimes jusqu'à N" .

Essayez-le en ligne!

JavaScript (ES6), 53 octets

f=(n,k=n)=>k--&&(C=(a,b)=>b?C(b,a%b):a<2)(n,k)+f(n,k)

Essayez-le en ligne!

C (gcc) , 67 65 octets

f(x,a,b,y,z){for(z=y=x;a=y--;z-=b>1)for(b=x;a^=b^=a^=b%=a;);x=z;}

Essayez-le en ligne!

Edit: Suppression de la variable temp.

Edit2: -1 grâce à @HowChen

Un peu moins golfé

f(x,a,b,y,z){
  // counts y NOT coprime with x and subtract
  for(z=y=x;a=y--;z-=b>1)
    // compute GCD
    for(b=x;a^=b^=a^=b%=a;);
  x=z;
}

En fait, 11 octets

;╗R`╜g`M1@c

Essayez-le en ligne!

Explication

;╗R`╜g`M1@c   register stack             remarks

                       44
;                      44 44
 ╗            44       44
  R           44       [1 2 3 .. 44]
       M      44       10                for example
    ╜         44       10 44
     g        44       2
              44       [1 2 1 .. 44]     gcd of each with register
        1     44       [1 2 1 .. 44] 1
         @    44       1 [1 2 1 .. 44]
          c   44       20                count

Avec intégré

▒

Essayez-le en ligne!

JavaScript (ES6), 67 octets

f=n=>[...Array(n)].reduce(r=>r+=g(n,++i)<2,i=0,g=(a,b)=>b?g(b,a%b):a)

APL, 7 octets

+/1=⊢∨⍳

Il s'agit d'un train de fonctions monadique qui prend un entier à droite. L'approche ici est la plus évidente: somme ( +/) le nombre de fois que le GCD de l'entrée et les nombres de 1 à l'entrée ( ⊢∨⍳) est égal à 1 ( 1=).

Essayez-le ici

Haskell, 31 30 octets

\n->sum[1|x<-[1..n],gcd n x<2]

1 octet enregistré grâce à @Damien.

Sélectionne les valeurs avec gcd = 1, mappe chacune à 1, puis prend la somme.