Fondo

La función totient de Eulerφ(n) se define como el número de números enteros menores o iguales a los nque son relativamente primos n, es decir, el número de valores posibles de xin 0 < x <= npara los cuales gcd(n, x) == 1. Hemos tenido un poco totient - relacionados retos antes, pero nunca uno que se acaba de calcularlo.

El mapeo de la función totient sobre los números enteros es OEIS A000010 .

Reto

Dado un número entero n > 0, calcular φ(n). Puede recibir información a través de argumentos de línea de comandos, entrada estándar, argumentos de función o cualquier otra cosa razonable. Puede dar salida a través de salida estándar, valores de retorno o cualquier otra cosa razonable. Las funciones anónimas son aceptables. Puede suponer que la entrada no desbordará su método natural de almacenamiento de enteros, por ejemplo, inten C, pero debe admitir entradas de hasta 255. Si su lenguaje tiene una función totient incorporada, no puede usarla.

Ejemplos

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

La respuesta más corta en bytes gana. Si su idioma usa una codificación que no sea UTF-8, mencione en su respuesta.

Mathematica, 27 22 bytes

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

Una función sin nombre que toma y devuelve un entero.

No hay mucho que explicar aquí, excepto que @es la notación de prefijo para las llamadas a funciones y ~...~la notación de infijo (asociativo a la izquierda), por lo que lo anterior es lo mismo que:

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

MATL, 7 bytes

t:Zd1=s

Puedes TryItOnline . La idea más simple es hacer un vector de 1 a N y tomar mcd de cada elemento con N ( Zdgcd). Luego, encuentra qué elementos son iguales a 1 y suma el vector para obtener la respuesta.

J, 9 bytes

(-~:)&.q:

Esto se basa en el ensayo de Jsoftware sobre funciones totient.

Dado n = p ₁ ^{e ₁} ∙ p ₂ ^{e ₂} ∙∙∙ p _k ^{e _k} donde p _k es un factor primo de n , la función 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} .

Uso

   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

Explicación

(-~:)&.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)

Jalea, 4 bytes

Rgċ1

Pruébalo en línea!

Explicación

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.

Con incorporado

ÆṪ

Pruébalo en línea!

Explicación

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.

Haskell, 28 bytes

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

Utiliza la coincidencia de patrones de constantes de Haskell . Los trucos aquí son bastante estándar para el golf, pero lo explicaré a una audiencia general.

La expresión se gcd n<$>[1..n]asigna gcd na [1..n]. En otras palabras, calcula el gcdcon nde cada número de 1a n:

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

A partir de aquí, la salida deseada es el número de 1entradas, pero Haskell carece de una countfunción. La forma idiomática filterde quedarse solo 1y tomar el resultado length, que es demasiado, es demasiado largo para jugar al golf.

En cambio, filterse simula mediante una comprensión de la lista [1|1<-l]con la lista resultante l. Por lo general, las comprensiones de listas enlazan valores en variables como en [x*x|x<-l], pero Haskell permite comparar un patrón, en este caso la constante 1.

Entonces, [1|1<-l]generando un 1en cada coincidencia de 1, extrayendo efectivamente solo los 1's de la lista original. Invocarlo sumda su longitud.

Python 2, 44 bytes

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

Menos golfizado:

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

Utiliza la fórmula que los clientes de Euler de los divisores ntienen una suma de n:

El valor de ϕ(n) se puede calcular recursivamente como nmenos la suma sobre divisores no triviales. Efectivamente, esto está haciendo una inversión de Möbius en la función de identidad. Utilicé el mismo método en un golf para calcular la función de Möbius .

Gracias a Dennis por guardar 1 byte con un mejor caso base, distribuyendo el valor inicial de +nen +1cada uno de los nbucles, hecho como-~ .

Pyke, 5 bytes

m.H1/

Pruébalo aquí!

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

J, 11 bytes

+/@(1=+.)i.

Uso

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

donde >>es STDIN y <<es STDOUT.

Explicación

+/ @ ( 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 bytes

Gracias a LeakyNun por jugar 12 bytes (!).

Gracias a Sp3000 por jugar golf en 6 bytes.

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

Me encanta lo legible que es Python. Esto tiene sentido, incluso a través del golf.

Regex (ECMAScript), 131 bytes

Al menos -12 bytes gracias a Deadcode (en el chat)

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

Pruébalo en línea!

La salida es la duración del partido.

Las expresiones regulares ECMAScript hacen que sea extremadamente difícil contar algo. Cualquier reflujo definido fuera de un bucle será constante durante el bucle, cualquier reflujo definido dentro de un bucle se restablecerá durante el bucle. Por lo tanto, la única forma de llevar el estado a través de iteraciones de bucle es usar la posición de coincidencia actual. Es un número entero único, y solo puede disminuir (bueno, la posición aumenta, pero la longitud de la cola disminuye, y eso es lo que podemos hacer con las matemáticas).

Dadas esas restricciones, simplemente contar los números coprimos parece imposible. En cambio, usamos la fórmula de Euler para calcular el totient.

Así es como se ve en pseudocódigo:

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

Hay dos cosas dudosas sobre esto.

Primero, no guardamos la entrada, solo el producto actual, entonces, ¿cómo podemos llegar a los factores primos de la entrada? El truco es que (N - (N / P)) tiene los mismos factores primos> P que N. Puede obtener nuevos factores primos <P, pero los ignoramos de todos modos. Tenga en cuenta que esto solo funciona porque iteramos sobre los factores primos de menor a mayor, de lo contrario fallaría.

En segundo lugar, tenemos que recordar dos números en las iteraciones de bucle (P y N, Z no cuenta ya que es constante), ¡y acabo de decir que era imposible! Afortunadamente, podemos mezclar esos dos números en uno solo. Tenga en cuenta que, al comienzo del ciclo, N siempre será un múltiplo de Z, mientras que P siempre será menor que Z. Por lo tanto, podemos recordar N + P y extraer P con un módulo.

Aquí está el pseudocódigo un poco más detallado:

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

Y aquí está la expresión regular comentada:

# \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

Y como un bono ...

Regex (ECMAScript 2018, número de coincidencias), 23 bytes

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

Pruébalo en línea!

La salida es el número de coincidencias. ECMAScript 2018 presenta una retrospectiva de longitud variable (evaluada de derecha a izquierda), que hace posible contar simplemente todos los números coprimos con la entrada.

Resulta que este es independientemente el mismo método utilizado por la solución Retina de Leaky Nun , y la expresión regular es incluso de la misma longitud ( e intercambiable ). Lo dejo aquí porque puede ser interesante que este método funcione en ECMAScript 2018 (y no solo .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

Perl 6 ,  26 24  22 bytes

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

Explicación:

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

Ejemplo:

#! /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 bytes

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

Es simple: la sumfunción le permite asignarle una función antes de sumar, básicamente el equivalente a ejecutar mapy luego sum. Esto cuenta directamente el número de números primos relativamente menores que n.

Python 2, 57 bytes

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

Pruébalo en Ideone .

Fondo

Por la fórmula del producto de Euler ,

donde φ denota la función totient de Euler y p varía solo sobre los números primos.

Para identificar números primos, usamos un corolario del teorema de Wilson :

Cómo funciona

En todo momento, la variable m será igual al cuadrado del factorial de k - 1 . De hecho, hemos llamado defecto argumentos para k = 1 y m = 0! ² = 1 .

Mientras k ≤ n , se n*(k>n)evalúa a 0 y orse ejecuta el siguiente código .

Recuerde que m%kproducirá 1 si m es primo y 0 si no. Esto significa que x%k<m%krendirá Verdadero si y solo si k es un número primo yx es divisible por k .

En este caso, (n%k<m%k)*n/kproduce n / k , y restarlo de n reemplaza su valor anterior con n (1 - 1 / k) , como en la fórmula del producto de Euler. De lo contrario, (n%k<m%k)*n/kproduce 0 y n se mantiene sin cambios.

Después de calcular lo anterior, incrementamos k y multiplicamos m por el valor "antiguo" de k ² , manteniendo así la relación deseada entre k y m , luego llamamos f recursivamente con los argumentos actualizados.

Una vez que k excede n , se n*(k>n)evalúa como n , que es devuelto por la función.

Ruby, 32 bytes

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

una lambda que toma un número entero n, y devuelve los recuentos de cuántos enteros en el rango (1..n) son coprimos con n.

Brachylog , 25 bytes

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

Explicación

Brachylog todavía no tiene un GCD incorporado, por lo que verificamos que los dos números no tengan factores primos en común.

• Predicado 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
  

• Predicado 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 bytes

smq1iQ

Pruébalo en línea!

/iLQQ1

Pruébalo en línea!

Explicación

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 bytes

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

PowerShell no tiene una función GCD disponible, así que tuve que rodar la mía.

Esto toma la entrada $n, luego varía de 1a $ny los canaliza en un bucle |%{...}. Cada iteración que establece dos variables auxiliares $ay $by luego ejecutar un GCD whilebucle. Cada iteración estamos comprobando que $baún es distinto de cero, y luego salvar $a%$ba $by el valor anterior de $bque $apara el próximo ciclo. Luego acumulamos si $aes igual a 1en nuestra variable de salida$o . Una vez que se realiza el bucle for, colocamos$o en la tubería y la salida es implícita.

Como un ejemplo de cómo funciona el whileciclo, considere $n=20y estamos en $_=8. La primera verificación tiene $b=20, así que entramos en el bucle. Primero calculamos $a%$bo 8%20 = 8, que se establece $ben al mismo tiempo que 20se establece en $a. Verifique 8=0, y entramos en la segunda iteración. Luego calculamos 20%8 = 4y establecemos eso en $b, luego establecemos $aen 8. Verifique 4=0, y entramos en la tercera iteración. Calculamos 8%4 = 0y establecemos eso en $b, luego establecemos $aen 4. Comprueba 0=0y salimos del bucle, por lo que el GCD (8,20) es $a = 4. Por !($a-1) = !(4-1) = !(3) = 0lo tanto, así $o += 0y no contamos ese.

Factor, 50 bytes

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

Hace un rango ( iota ) n , y curry n en una función que obtiene mcd xn para todos los valores de 0 <= x <= n , comprueba si el resultado es 1 . Filtrar el rango original para determinar si el resultado de gcd xn fue 1 , y tome su longitud .

Japt -mx, 7 5 bytes

yN ¥1

Ejecútalo en línea

-2 bytes gracias a Shaggy

Retina, 36 29 bytes

7 bytes gracias a Martin Ender.

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

Pruébalo en línea!

Explicación

Hay dos etapas (comandos).

Primera etapa

.+
$*

Es una simple sustitución de expresiones regulares, que convierte la entrada a esa cantidad.

Por ejemplo, 5se convertiría a11111 .

Segunda etapa

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

Esta expresión regular intenta hacer coincidir las posiciones que satisfacen la condición (primo con entrada) y luego devuelve el número de coincidencias.

Lisp común, 58 bytes

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

Este es un bucle simple que cuenta 1 hasta el n dado e incrementa la suma si gcd = 1. Uso el nombre de la función o ya que t es el verdadero valor booleano. No es el más corto, sino bastante simple.

MATLAB / Octave, 21 bytes

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

Crea una función anónima llamada ansque se puede llamar con el entero ncomo la única entrada:ans(n)

Demo en línea

Python 2 , 44 bytes

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

Esto utiliza el mismo método para identificar coprimes como mi respuesta a "Coprimes hasta N" .

Pruébalo en línea!

JavaScript (ES6), 53 bytes

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

Pruébalo en línea!

En realidad, 11 bytes

;╗R`╜g`M1@c

Pruébalo en línea!

Explicación

;╗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

Con incorporado

▒

Pruébalo en línea!

JavaScript (ES6), 67 bytes

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

05AB1E, 7 bytes

Lvy¹¿i¼

Explicado

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

Pruébalo en línea

APL, 7 bytes

+/1=⊢∨⍳

Este es un tren de funciones monádicas que toma un número entero a la derecha. El enfoque aquí es obvio: suma ( +/) el número de veces que el MCD de la entrada y los números del 1 a la entrada ( ⊢∨⍳) es igual a 1 ( 1=).

Pruébalo aquí

Haskell, 31 30 bytes

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

1 byte guardado, gracias a @Damien.

Selecciona valores con gcd = 1, asigna cada uno a 1, luego toma la suma.

Lotes, 151 145 144 bytes

@echo off
set t=
for /l %%i in (1,1,%1)do call:g %1 %%i
echo %t%
exit/b
:g
set/ag=%1%%%2
if not %g%==0 call:g %2 %g%
if %2%==1 set/at+=1

Editar: guardado 4 bytes eliminando espacios innecesarios. Guardado 1 byte mediante el uso +=. Se guardó 1 byte al borrar tcomo +=se interpretará como de 0todos modos. Guardado 1 byte gracias a @ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ.