fundo

A função totiente de Eulerφ(n) é definida como o número de números inteiros menor ou igual a nque são relativamente primos para n, ou seja, o número de valores possíveis de xem 0 < x <= npara o qual gcd(n, x) == 1. Nós tivemos um pouco totient - relacionados desafios antes, mas nunca um que é apenas cálculo.

O mapeamento da função totiente para os números inteiros é OEIS A000010 .

Desafio

Dado um número inteiro n > 0, calcule φ(n). Você pode receber informações por meio de argumentos de linha de comando, entrada padrão, argumentos de função ou qualquer outra coisa razoável. Você pode fornecer a saída por meio da saída padrão, valores de retorno ou qualquer outra coisa razoável. Funções anônimas são aceitáveis. Você pode presumir que a entrada não excederá o seu método natural de armazenar números inteiros, por exemplo, intem C, mas você deve suportar entradas de até 255. Se o seu idioma tiver uma função de orientação interna, você não poderá usá-lo.

Exemplos

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

A resposta mais curta em bytes vence. Se o seu idioma usa uma codificação diferente de UTF-8, mencione-a na sua resposta.

Mathematica, 27 22 bytes

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

Uma função sem nome que pega e retorna um número inteiro.

Não há muito a explicar aqui, exceto que @é a notação de prefixo para chamadas de função e ~...~é a notação de infixo (associativa à esquerda); portanto, o acima é o mesmo que:

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

MATL, 7 bytes

t:Zd1=s

Você pode TryItOnline . Idéia mais simples, faça um vetor de 1 a N e tire o MDC de cada elemento com N ( Zdgcd). Em seguida, encontre quais elementos são iguais a 1 e some o vetor para obter a resposta.

J, 9 bytes

(-~:)&.q:

Isso é baseado no ensaio do Jsoftware sobre funções totientes.

Dado n = p ₁ ^{e ₁} ∙ p ₂ ^{e _dois} ∙∙∙ p _k ^{e _k} onde p _k é um factor primo de N , o φ função totiente ( n ) = φ ( p ₁ ^{e ₁} ) ∙ φ ( p ₂ ^{e ₂} ) φ p ( 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

Explicação

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

Gelatina, 4 bytes

Rgċ1

Experimente online!

Explicação

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.

Com built-in

ÆṪ

Experimente online!

Explicação

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.

Haskell, 28 bytes

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

Usa a correspondência de constantes de Haskell . Os truques aqui são bastante padrão para o golfe, mas vou explicar para o público em geral.

A expressão é gcd n<$>[1..n]mapeada gcd npara [1..n]. Em outras palavras, ele calcula o gcdcom nde cada número a partir 1de n:

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

A partir daqui, a saída desejada é o número de 1entradas, mas Haskell não possui uma countfunção. A maneira idiomática filterde manter apenas 1's' e pegar o resultado length, que é muito longo para o golfe.

Em vez disso, o filteré simulado por uma compreensão da lista [1|1<-l]com a lista resultante l. Geralmente, as compreensões de lista vinculam valores a variáveis ​​como em [x*x|x<-l], mas Haskell permite comparar um padrão, neste caso a constante 1.

Assim, [1|1<-l]gerando um 1em cada correspondência de 1, efetivamente extraindo apenas os 1da lista original. Invocá sum-lo dá o seu comprimento.

Python 2, 44 bytes

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

Menos golfe:

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

Usa a fórmula que o Euler totients dos divisores de ntem uma soma de n:

O valor de ϕ(n)pode então ser recursivamente calculado como nmenos a soma dos divisores não triviais. Efetivamente, isso está fazendo a inversão de Möbius na função de identidade. Eu usei o mesmo método em um golfe para calcular a função Möbius .

Graças a Dennis para guardar um byte com um caso base melhor, espalhando-se o valor inicial de +nem +1para cada uma das nansas, feito como -~.

Pyke, 5 bytes

m.H1/

Experimente aqui!

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

J, 11 bytes

+/@(1=+.)i.

Uso

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

onde >>é STDIN e <<STDOUT.

Explicação

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

Agradecimentos a LeakyNun por jogar fora 12 (!) Bytes.

Agradecimentos ao Sp3000 por jogar fora 6 bytes.

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

Eu amo o quão legível é o Python. Isso faz sentido, mesmo através do golfe.

Regex (ECMAScript), 131 bytes

Pelo menos -12 bytes graças ao código morto (no chat)

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

Experimente online!

Saída é o comprimento da partida.

As expressões regulares ECMAScript tornam extremamente difícil contar qualquer coisa. Qualquer backref definido fora de um loop será constante durante o loop, qualquer backref definido dentro de um loop será redefinido durante o loop. Portanto, a única maneira de transportar o estado pelas iterações do loop é usando a posição de correspondência atual. Esse é um número inteiro único e só pode diminuir (bem, a posição aumenta, mas o comprimento da cauda diminui, e é para isso que podemos fazer contas).

Dadas essas restrições, simplesmente contar números de coprime parece impossível. Em vez disso, usamos a fórmula de Euler para calcular o totiente.

Veja como fica no 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

Há duas coisas duvidosas sobre isso.

Primeiro, não salvamos a entrada, apenas o produto atual; então, como podemos obter os principais fatores da entrada? O truque é que (N - (N / P)) tem os mesmos fatores primos> P que N. Ele pode ganhar novos fatores primos <P, mas nós os ignoramos de qualquer maneira. Observe que isso só funciona porque iteramos os fatores primos do menor para o maior, seguindo o caminho inverso.

Segundo, precisamos lembrar dois números nas iterações de loop (P e N, Z não conta, pois é constante), e eu apenas disse que era impossível! Felizmente, podemos misturar esses dois números em um único. Observe que, no início do loop, N sempre será um múltiplo de Z, enquanto P sempre será menor que Z. Assim, podemos apenas lembrar de N + P e extrair P com um módulo.

Aqui está o pseudo-código um pouco mais detalhado:

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

E aqui está o regex comentado:

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

E como um bônus ...

Regex (ECMAScript 2018, número de correspondências), 23 bytes

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

Experimente online!

Saída é o número de correspondências. O ECMAScript 2018 apresenta look-behind de comprimento variável (avaliado da direita para a esquerda), o que torna possível contar simplesmente todos os números de coprime com a entrada.

Acontece que esse é independentemente o mesmo método usado pela solução Retina da Leaky Nun , e o regex tem até o mesmo comprimento ( e é intercambiável ). Estou deixando aqui porque pode ser interessante que esse método funcione no ECMAScript 2018 (e não apenas no .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$_)}

Explicação:

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

Exemplo:

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

É simples - a sumfunção permite atribuir uma função a ser aplicada antes da soma - basicamente o equivalente a executar mape depois sum. Isso conta diretamente o número de números relativamente primos menor 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)

Teste em Ideone .

fundo

Pela fórmula do produto de Euler ,

onde φ denota a função totiente de Euler ep varia apenas sobre os números primos.

Para identificar números primos, usamos um corolário do teorema de Wilson :

Como funciona

Em todos os momentos, a variável m será igual ao quadrado do fatorial de k - 1 . Na verdade, nós chamado argumentos padrão para k = 1 e m = 0! ² = 1 .

Desde que k ≤ n , n*(k>n)avalie como 0 e o código a seguiror é executado.

Lembre-se de que m%kproduzirá 1 se m for primo e 0 se não. Isso significa que x%k<m%kproduzirá True se e somente se k for um número primo e x for divisível por k .

Nesse caso, (n%k<m%k)*n/kgera n / k e subtrai-lo de n substitui seu valor anterior por n (1 - 1 / k) , como na fórmula do produto de Euler. Caso contrário, (n%k<m%k)*n/kproduz 0 e n permanece inalterado.

Após calcular o acima, incrementamos k e multiplicamos m pelo valor "antigo" de k ² , mantendo assim a relação desejada entre k e m , em seguida, chamamos f recursivamente com os argumentos atualizados.

Quando k excede n , n*(k>n)avalia como n , que é retornado pela função.

Ruby, 32 bytes

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

um lambda que pega um número inteiro n e retorna a contagem de quantos números inteiros no intervalo (1..n) são coprime com n.

Braquilog , 25 bytes

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

Explicação

O Brachylog ainda não possui um GCD, portanto, verificamos que os dois números não têm fatores primos em comum.

• 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
  

Pitão, 6 bytes

smq1iQ

Experimente online!

/iLQQ1

Experimente online!

Explicação

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

O PowerShell não tem uma função GCD disponível, então tive que usar minha própria.

Isso leva a entrada e $n, em seguida, varia de 1a $ne canaliza essas para um loop |%{...}. Cada iteração definimos duas variáveis auxiliares $ae $bem seguida, executar um GCD whileloop. Cada iteração estamos verificando que $bainda não é zero, e depois salvar $a%$ba $be o valor anterior $bpara $apara o próximo ciclo. Em seguida, acumulamos se $aé igual a 1nossa variável de saída $o. Depois que o loop for concluído, colocamos$o no pipeline e a saída é implícita.

Como um exemplo de como o whileloop funciona, considere $n=20e continuamos $_=8. A primeira verificação tem $b=20, então entramos no loop. Primeiro calculamos $a%$bou 8%20 = 8, que é definido ao $bmesmo tempo em que 20é definido $a. Verifique 8=0e entramos na segunda iteração. Em seguida, calculamos 20%8 = 4e configuramos isso como $b, em seguida, definimos $acomo 8. Verifique 4=0e entramos na terceira iteração. Calculamos 8%4 = 0e configuramos isso para $b, depois definimos $acomo 4. Verifique 0=0e saímos do loop, então o GCD (8,20) é $a = 4. Assim, !($a-1) = !(4-1) = !(3) = 0assim $o += 0e não contamos essa.

Fator, 50 bytes

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

Faz um intervalo ( iota ) n , e altera n para uma função que obtém gcd xn para todos os valores de 0 <= x <= n , testa se o resultado é 1 . Filtre o intervalo original se o resultado de gcd xn foi 1 e calcule o comprimento .

Japonês -mx, 7 5 bytes

yN ¥1

Execute-o online

-2 bytes graças a Shaggy

Retina, 36 29 bytes

7 bytes graças a Martin Ender.

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

Experimente online!

Explicação

Existem dois estágios (comandos).

Primeira etapa

.+
$*

É uma substituição simples de regex, convertendo a entrada para muitas.

Por exemplo, 5 seria convertido para 11111.

Segundo estágio

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

Essa regex tenta corresponder as posições que satisfazem a condição (co-prime com entrada) e, em seguida, retorna o número de correspondências.

Lisp comum, 58 bytes

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

Este é um loop simples que conta 1 até o dado n e incrementa a soma se gcd = 1. Uso o nome da função o, pois t é o verdadeiro valor booleano. Não é o mais curto, mas é bastante simples.

MATLAB / oitava, 21 bytes

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

Cria uma função anônima chamada ansque pode ser chamada com o número inteiro ncomo a única entrada:ans(n)

Demo Online

Python 2 , 44 bytes

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

Ele usa o mesmo método para identificar coprimes que a minha resposta para "Coprimes até N" .

Experimente online!

JavaScript (ES6), 53 bytes

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

Experimente online!

Na verdade, 11 bytes

;╗R`╜g`M1@c

Experimente online!

Explicação

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

Com built-in

▒

Experimente online!

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

Experimente online

APL, 7 bytes

+/1=⊢∨⍳

Este é um trem de função monádica que leva um número inteiro à direita. A abordagem aqui é óbvia: soma ( +/) o número de vezes que o GCD da entrada e os números de 1 à entrada (⊢∨⍳ ) são iguais a 1 ( 1=).

Experimente aqui

Haskell, 31 30 bytes

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

1 byte salvo, graças a @Damien.

Seleciona valores com gcd = 1, mapeia cada um para 1 e assume a soma.

Lote, 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: salvou 4 bytes removendo espaços desnecessários. 1 byte salvo usando +=. Economizou 1 byte limpando, tpois +=o interpretará como de 0qualquer maneira. Guardou 1 byte graças a @ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ.