tło

Eulera totient funkcja φ(n)jest definiowana jako ilość liczb całkowitych mniej niż lub równy n, które są względnie pierwsze do n, czyli liczba możliwych wartości xw 0 < x <= nodniesieniu do których gcd(n, x) == 1. Mieliśmy się kilka totient - powiązanych wyzwań przed, ale nie taki, który jest po prostu jej obliczenia.

Mapowanie funkcji totemu na liczby całkowite to OEIS A000010 .

Wyzwanie

Biorąc pod uwagę liczbę całkowitą n > 0, obliczyć φ(n). Możesz przyjmować dane wejściowe za pomocą argumentów wiersza poleceń, standardowych danych wejściowych, argumentów funkcyjnych lub cokolwiek innego uzasadnionego. Możesz podać dane wyjściowe poprzez standardowe dane wyjściowe, zwracane wartości lub cokolwiek innego rozsądnego. Funkcje anonimowe są dopuszczalne. Możesz założyć, że dane wejściowe nie przepełnią twojej naturalnej metody przechowywania liczb całkowitych, np. intW C, ale musisz obsługiwać dane wejściowe do 255. Jeśli twój język ma wbudowaną funkcję totient, nie możesz jej użyć.

Przykłady

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

Najkrótsza odpowiedź w bajtach wygrywa. Jeśli twój język używa kodowania innego niż UTF-8, podaj go w swojej odpowiedzi.

Mathematica, 27 22 bajtów

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

Nienazwana funkcja, która przyjmuje i zwraca liczbę całkowitą.

Nie ma tu wiele do wyjaśnienia, z wyjątkiem tego, że @jest to notacja prefiksu dla wywołań funkcji i ~...~jest notacja infiksowa (lewostronna), więc powyższe jest takie samo jak:

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

MATL, 7 bajtów

t:Zd1=s

Możesz TryItOnline . Najprostszy pomysł, wykonaj wektor od 1 do N i weź gcd każdego elementu za pomocą N ( Zdrobi gcd). Następnie znajdź elementy równe 1 i zsumuj wektor, aby uzyskać odpowiedź.

J, 9 bajtów

(-~:)&.q:

Jest to oparte na eseju Jsoftware na temat funkcji totient .

Biorąc pod uwagę n = p ₁ ^{e ₁} ∙ p ₂ ^{e ₂} ∙∙∙ p _k ^{e _k} gdzie p _k jest liczbą pierwszą n , funkcja totalna φ ( 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} .

Stosowanie

   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

Wyjaśnienie

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

Galaretka, 4 bajty

Rgċ1

Wypróbuj online!

Wyjaśnienie

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.

Z wbudowanym

ÆṪ

Wypróbuj online!

Wyjaśnienie

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.

Haskell, 28 bajtów

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

Wykorzystuje dopasowanie stałych według wzoru Haskella . Sztuczki tutaj są dość standardowe do gry w golfa, ale wyjaśnię to ogółowi odbiorców.

Wyrażenie gcd n<$>[1..n]odwzorowuje gcd nna [1..n]. Innymi słowy, wylicza gcdz nkażdej liczby od 1do n:

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

Stąd pożądanym wyjściem jest liczba 1wpisów, ale Haskell nie ma żadnej countfunkcji. Idiomatyczny sposób, aby filterzatrzymać tylko 1i wziąć wynikowy length, który jest o wiele za długi na grę w golfa.

Zamiast tego filterjest symulowane przez zrozumienie listy [1|1<-l]z wynikową listą l. Zwykle wyrażenia listowe wiążą wartości ze zmienną jak w [x*x|x<-l], ale Haskell pozwala na dopasowanie wzorca, w tym przypadku stałej 1.

Tak więc, [1|1<-l]generowanie 1przy każdym dopasowaniu 1, skutecznie wyodrębniając tylko 1z oryginalnej listy. Przywołanie sumgo określa jego długość.

Python 2, 44 bajty

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

Mniej golfa:

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

Wykorzystuje wzór, że sumy Eulera dzielników nmają sumę n:

Wartość ϕ(n)można następnie rekurencyjnie obliczyć jako nminus sumę ponad nietrywialnymi dzielnikami. Skutecznie robi to inwersję Möbiusa w funkcji tożsamości. Zastosowałem tę samą metodę w golfie, aby obliczyć funkcję Möbiusa .

Dzięki Dennisowi za zaoszczędzenie 1 bajtu z lepszą skrzynką podstawową, rozłożenie wartości początkowej +nna +1dla każdej z npętli, wykonane jak -~.

Pyke, 5 bajtów

m.H1/

Wypróbuj tutaj!

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

J, 11 bajtów

+/@(1=+.)i.

Stosowanie

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

gdzie >>jest STDIN i <<STDOUT.

Wyjaśnienie

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

Dzięki LeakyNun za grę w golfa z 12 (!) Bajtów.

Dzięki Sp3000 za grę w golfa z 6 bajtów.

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

Uwielbiam czytelność Pythona. Ma to sens, nawet poprzez grę w golfa.

Regex (ECMAScript), 131 bajtów

Co najmniej -12 bajtów dzięki Deadcode (na czacie)

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

Wypróbuj online!

Dane wyjściowe to długość dopasowania.

Wyrażenia regularne ECMAScript sprawiają, że niezwykle trudno jest policzyć cokolwiek. Wszelkie odnośniki zdefiniowane poza pętlą będą stałe podczas pętli, wszelkie odnośniki zdefiniowane w pętli zostaną zresetowane podczas zapętlania. Zatem jedynym sposobem przenoszenia stanu przez iteracje pętli jest użycie bieżącej pozycji dopasowania. To jedna liczba całkowita i może się tylko zmniejszać (no cóż, pozycja rośnie, ale długość ogona maleje i do tego możemy matematyki).

Biorąc pod uwagę te ograniczenia, zwykłe liczenie numerów coprime wydaje się niemożliwe. Zamiast tego używamy formuły Eulera do obliczania sumy.

Oto jak to wygląda w pseudokodzie:

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

Są w tym dwie wątpliwe rzeczy.

Po pierwsze, nie zapisujemy danych wejściowych, tylko bieżący produkt, więc w jaki sposób możemy dostać się do głównych czynników wejściowych? Sztuka polega na tym, że (N - (N / P)) ma takie same czynniki pierwsze> P jak N. Może zyskać nowe czynniki pierwsze <P, ale i tak je ignorujemy. Zauważ, że działa to tylko dlatego, że iterujemy czynniki pierwsze od najmniejszej do największej.

Po drugie, musimy pamiętać o dwóch liczbach w iteracjach pętli (P i N, Z nie liczy się, ponieważ jest stała), a ja właśnie powiedziałem, że to niemożliwe! Na szczęście możemy zamienić te dwie liczby w jednym. Zauważ, że na początku pętli N będzie zawsze wielokrotnością Z, podczas gdy P będzie zawsze mniejsze niż Z. Zatem możemy po prostu zapamiętać N + P i wyodrębnić P za pomocą modulo.

Oto nieco bardziej szczegółowy pseudo-kod:

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

A oto skomentowany regex:

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

A jako bonus…

Regex (ECMAScript 2018, liczba dopasowań), 23 bajty

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

Wypróbuj online!

Dane wyjściowe to liczba dopasowań. ECMAScript 2018 wprowadza zmienne spojrzenie wstecz (oceniane od prawej do lewej), co pozwala po prostu policzyć wszystkie liczby coprime z danymi wejściowymi.

Okazuje się, że jest to niezależnie ta sama metoda stosowana w rozwiązaniu Retina Leaky Nun , a regex jest nawet tej samej długości ( i zamiennie ). Zostawiam go tutaj, ponieważ może być interesujące, że ta metoda działa w ECMAScript 2018 (a nie tylko .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 bajtów

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

Wyjaśnienie:

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

Przykład:

#! /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 bajtów

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

To proste - sumfunkcja umożliwia nadanie jej funkcji do zastosowania przed zsumowaniem - w zasadzie odpowiednik uruchomienia, mapa następnie sum. To bezpośrednio zlicza liczbę względnie pierwszych liczb mniejszą niż n.

Python 2, 57 bajtów

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

Przetestuj na Ideone .

tło

Według formuły produktu Eulera ,

gdzie φ oznacza funkcję całkowitą Eulera, a p zmienia się tylko w liczbach pierwszych.

Aby zidentyfikować liczby pierwsze, używamy następstwa twierdzenia Wilsona :

Jak to działa

Przez cały czas zmienna m będzie równa kwadratowi silni k - 1 . W rzeczywistości nazwaliśmy argumenty domyślnie k = 1 i m = 0! ² = 1 .

Dopóki k ≤ n , przyjmuje n*(k>n)wartość 0 i następuje orwykonanie następującego kodu .

Przypomnijmy, że m%kda 1, jeśli m jest liczbą pierwszą, a 0, jeśli nie. Oznacza to, że x%k<m%kzwróci True , i tylko wtedy, gdy oba k jest liczbą pierwszą, a x jest podzielne przez k .

W tym przypadku (n%k<m%k)*n/kdaje n / k , a odjęcie go od n zastępuje jego poprzednią wartość n (1 - 1 / k) , jak we wzorze produktu Eulera. W przeciwnym razie (n%k<m%k)*n/kzwraca 0 i n pozostaje niezmienione.

Po obliczeniu powyższym, przyrost że k i namnażania m o „starej” wartość k ² , utrzymując w ten sposób żądany stosunek pomiędzy k i m , a następnie wywołać K rekurencyjnie aktualizowane z argumentów.

Gdy k przekroczy n , n*(k>n)zwraca wartość n , która jest zwracana przez funkcję.

Rubinowy, 32 bajty

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

lambda, która przyjmuje liczbę całkowitą n i zwraca liczbę całkowitych liczb z zakresu (1..n) stanowiących coprime dla n.

Brachylog , 25 bajtów

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

Wyjaśnienie

Brachylog nie ma jeszcze wbudowanego GCD, więc sprawdzamy, czy te dwie liczby nie mają wspólnych pierwiastków.

• Główny predykat:

  :{...}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
  

• Predykat 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 bajtów

smq1iQ

Wypróbuj online!

/iLQQ1

Wypróbuj online!

Wyjaśnienie

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 bajty

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

PowerShell nie ma dostępnej funkcji GCD, więc musiałem uruchomić własną.

To pobiera dane wejściowe $n, a następnie waha się od 1do $ni łączy je w pętlę |%{...}. Każda iteracja możemy ustawić dwie zmienne pomocnicze $ai $b, a następnie wykonać GCD whilepętlę. Każda iteracja, którą sprawdzamy, $bjest wciąż niezerowa, a następnie zapisujemy $a%$bdo $bpoprzedniej wartości $bi $adla następnej pętli. Następnie kumulujemy, czy $ajest równa 1naszej zmiennej wyjściowej $o. Po zakończeniu pętli for umieszczamy $ow potoku i wynik jest domyślny.

Jako przykład działania whilepętli zastanów się $n=20i włączamy $_=8. Pierwsze sprawdzenie ma $b=20, więc wchodzimy do pętli. Najpierw obliczamy $a%$blub 8%20 = 8, który jest ustawiany $bw tym samym czasie, który 20jest ustawiany na $a. Sprawdź 8=0, a my wprowadzamy drugą iterację. Następnie obliczamy 20%8 = 4i ustawiamy to na $b, a następnie ustawiamy $ana 8. Sprawdź 4=0, a my wprowadzamy trzecią iterację. Obliczamy 8%4 = 0i ustawiamy na $b, a następnie ustawiamy $ana 4. Sprawdź 0=0i wychodzimy z pętli, więc GCD (8,20) jest $a = 4. Tak !($a-1) = !(4-1) = !(3) = 0więc $o += 0i nie liczymy tego.

Współczynnik, 50 bajtów

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

Zmienia zakres ( iota ) n i curry n do funkcji, która otrzymuje gcd xn dla wszystkich wartości 0 <= x <= n , sprawdza, czy wynikiem jest 1 . Filtruj oryginalny zakres, sprawdzając, czy wynik gcd xn wynosił 1 , i bierz jego długość .

Japt -mx, 7 5 bajtów

yN ¥1

Uruchom to online

-2 bajty dzięki Shaggy

Retina, 36 29 bajtów

7 bajtów dzięki Martinowi Enderowi.

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

Wypróbuj online!

Wyjaśnienie

Istnieją dwa etapy (polecenia).

Pierwszy etap

.+
$*

Jest to proste podstawienie wyrażenia regularnego, które przekształca dane wejściowe na tak wiele.

Na przykład 5zostanie przekonwertowany na 11111.

Drugi etap

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

To wyrażenie regularne próbuje dopasować pozycje, które spełniają warunek (co-prime z wejściem), a następnie zwraca liczbę dopasowań.

Common Lisp, 58 bajtów

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

Jest to prosta pętla, która zlicza 1 do podanego n i zwiększa sumę, jeśli gcd = 1. Używam nazwy funkcji o, ponieważ t jest prawdziwą wartością logiczną. Nie prawie najkrótszy, ale dość prosty.

MATLAB / Octave, 21 bajtów

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

Tworzy anonimową funkcję o nazwie, ansktórą można wywołać za pomocą liczby całkowitej njako jedynego wejścia:ans(n)

Demo online

Python 2 , 44 bajty

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

Używa tej samej metody do identyfikacji coprimes, jak moja odpowiedź na „Coprimes do N” .

Wypróbuj online!

JavaScript (ES6), 53 bajty

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

Wypróbuj online!

Właściwie 11 bajtów

;╗R`╜g`M1@c

Wypróbuj online!

Wyjaśnienie

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

Z wbudowanym

▒

Wypróbuj online!

JavaScript (ES6), 67 bajtów

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

05AB1E, 7 bajtów

Lvy¹¿i¼

Wyjaśnił

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

Wypróbuj online

APL, 7 bajtów

+/1=⊢∨⍳

Jest to monadyczny ciąg funkcji, który przyjmuje liczbę całkowitą po prawej stronie. Podejście tutaj jest oczywiste: suma ( +/) liczba razy GCD wejścia i liczby od 1 do input ( ⊢∨⍳) jest równa 1 ( 1=).

Wypróbuj tutaj

Haskell, 31 30 bajtów

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

1 bajt zapisany dzięki @Damien.

Wybiera wartości z gcd = 1, mapuje każdą na 1, a następnie pobiera sumę.

Partia, 151 145 144 bajtów

@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

Edycja: Zapisano 4 bajty, usuwając niepotrzebne spacje. Zaoszczędzono 1 bajt +=. Zapisano 1 bajt, usuwając, tponieważ +=i tak to zinterpretuje 0. Zapisano 1 bajt dzięki @ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ.