Hintergrund

Eulersche totient Funktion φ(n)wie die Anzahl der ganzen Zahlen definiert ist , weniger als oder gleich n, die teilerfremd zu n, das heißt, die Anzahl der möglichen Werte von xin , 0 < x <= nfür die gcd(n, x) == 1. Wir hatten ein paar totient - damit verbundene Herausforderungen vor, aber nie eine , die es einfach ist , zu berechnen.

Die Abbildung der Totientenfunktion auf die ganzen Zahlen ist OEIS A000010 .

Herausforderung

n > 0Berechnen Sie mit einer Ganzzahl φ(n). Sie können Eingaben über Befehlszeilenargumente, Standardeingaben, Funktionsargumente oder alles andere Vernünftige vornehmen. Sie können die Ausgabe über die Standardausgabe, Rückgabewerte oder einen anderen vernünftigen Wert vornehmen. Anonyme Funktionen sind zulässig. Sie können davon ausgehen, dass die Eingabe Ihre natürliche Methode zum Speichern von Ganzzahlen, z. B. intin C, nicht überläuft , Sie müssen jedoch Eingaben bis zu 255 unterstützen. Wenn Ihre Sprache eine integrierte Totientenfunktion hat, können Sie sie möglicherweise nicht verwenden.

Beispiele

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

Kürzeste Antwort in Bytes gewinnt. Wenn Ihre Sprache eine andere Codierung als UTF-8 verwendet, geben Sie dies in Ihrer Antwort an.

Mathematica, 27 22 Bytes

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

Eine unbenannte Funktion, die eine Ganzzahl annimmt und zurückgibt.

Es gibt hier nicht viel zu erklären, außer dass dies @eine Präfixnotation für Funktionsaufrufe und ~...~eine (linksassoziative) Infixnotation ist.

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

MATL, 7 Bytes

t:Zd1=s

Sie können TryItOnline . Am einfachsten ist es, einen Vektor 1 zu N zu machen und von jedem Element mit N Zdgcd zu nehmen ( tut gcd). Finden Sie dann, welche Elemente gleich 1 sind, und addieren Sie den Vektor, um die Antwort zu erhalten.

J 9 Bytes

(-~:)&.q:

Dies basiert auf dem Aufsatz der Jsoftware über Totient-Funktionen.

Gegeben n = p ₁ ^{e ₁} ∙ p ₂ ^{e ₂} ∙∙∙ p _k ^{e _k} wobei p _k ein Primfaktor ist n , die Totientenfunktion φ ( n ) = φ ( p ₁ ^{e ₁} ) ∙ φ ( p ₂ ^{e ₂} ) & PHgr; ( p _k ^{e _k} ) = ( p ₁ - 1) p ₁ ^{e ₁ - 1 &} PHgr; ( p ₂ - 1) p ₂^{e ₂ - 1} ( p _k - 1) p _k ^{e _k - 1} .

Verwendung

   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

Erläuterung

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

Gelee, 4 Bytes

Rgċ1

Probieren Sie es online!

Erläuterung

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.

Mit eingebautem

ÆṪ

Probieren Sie es online!

Erläuterung

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.

Haskell, 28 Bytes

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

Verwendet Haskells Mustervergleich von Konstanten . Die Tricks hier sind zum Golfen ziemlich üblich, aber ich erkläre es einem allgemeinen Publikum.

Der Ausdruck gcd n<$>[1..n]wird gcd nauf abgebildet [1..n]. Mit anderen Worten, es berechnet das gcdmit njeder Zahl von 1bis n:

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

Ab hier ist die gewünschte Ausgabe die Anzahl der 1Einträge, aber Haskell fehlt eine countFunktion. Die idiomatische Art filter, nur 1die zu behalten und die daraus resultierenden zu nehmen length, ist viel zu lang zum Golfen.

Stattdessen filterwird das durch ein Listenverständnis [1|1<-l]mit der daraus resultierenden Liste simuliert l. Normalerweise binden Listenverständnisse Werte an Variablen wie in [x*x|x<-l], aber mit Haskell kann ein Muster verglichen werden, in diesem Fall die Konstante 1.

Also, [1|1<-l]ein Erzeugen 1auf jedem Spiel von 1effektiv nur die Extraktion von 1‚s der ursprünglichen Liste. Das Aufrufen sumgibt seine Länge.

Pyke, 5 Bytes

m.H1/

Probieren Sie es hier aus!

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

Python> = 3,5, 76 64 58 Bytes

Danke an LeakyNun für das Golfen mit 12 (!) Bytes.

Dank an Sp3000 für das Golfen mit 6 Bytes.

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

Ich finde es toll, wie gut lesbar Python ist. Dies macht auch durch die Golffreundlichkeit Sinn.

Python 2, 44 Bytes

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

Weniger golfen:

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

Verwendet die Formel, dass die Euler-Summen der Teiler von neine Summe von haben n:

Der Wert von ϕ(n)kann dann rekursiv als nminus der Summe über nichttriviale Teiler berechnet werden . Tatsächlich führt dies eine Möbius-Inversion der Identitätsfunktion durch. Ich habe die gleiche Methode in einem Golf benutzt, um die Möbius-Funktion zu berechnen .

Vielen Dank an Dennis für das Speichern von 1 Byte mit einem besseren Basisfall, das Verteilen des Anfangswerts von +nin +1für jede der nSchleifen als -~.

Regex (ECMAScript), 131 Bytes

Mindestens -12 Bytes dank Deadcode (im Chat)

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

Probieren Sie es online!

Die Ausgabe ist die Länge der Übereinstimmung.

ECMAScript-reguläre Ausdrücke machen es extrem schwierig, etwas zu zählen. Jede Backref, die außerhalb einer Schleife definiert ist, bleibt während der Schleife konstant. Jede Backref, die innerhalb einer Schleife definiert ist, wird beim Schleifen zurückgesetzt. Die einzige Möglichkeit, den Status über Schleifeniterationen zu übertragen, ist die Verwendung der aktuellen Übereinstimmungsposition. Das ist eine einzelne Ganzzahl, und sie kann nur abnehmen (nun, die Position nimmt zu, aber die Länge des Schwanzes nimmt ab, und dafür können wir rechnen).

Angesichts dieser Einschränkungen scheint es unmöglich zu sein, Coprime-Zahlen zu zählen. Stattdessen verwenden wir die Euler-Formel , um den Totienten zu berechnen.

So sieht es im Pseudocode aus:

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

Es gibt zwei zweifelhafte Dinge.

Erstens speichern wir nicht die Eingabe, sondern nur das aktuelle Produkt. Wie können wir also zu den Hauptfaktoren der Eingabe gelangen? Der Trick ist, dass (N - (N / P)) die gleichen Primfaktoren> P wie N hat. Es kann neue Primfaktoren <P erhalten, aber wir ignorieren diese trotzdem. Beachten Sie, dass dies nur funktioniert, weil wir die Primfaktoren vom kleinsten zum größten iterieren. Andernfalls würde dies fehlschlagen.

Zweitens müssen wir uns zwei Zahlen über Schleifeniterationen merken (P und N, Z zählen nicht, da sie konstant sind), und ich sagte nur, dass das unmöglich war! Zum Glück können wir diese beiden Zahlen in einer einzigen verwandeln. Beachten Sie, dass zu Beginn der Schleife N immer ein Vielfaches von Z ist, während P immer kleiner als Z ist. Daher können wir uns nur an N + P erinnern und P mit einem Modulo extrahieren.

Hier ist der etwas detailliertere Pseudocode:

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

Und hier ist der kommentierte reguläre Ausdruck:

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

Und als Bonus ...

Regex (ECMAScript 2018, Anzahl der Übereinstimmungen), 23 Byte

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

Probieren Sie es online!

Ausgabe ist die Anzahl der Übereinstimmungen. Mit ECMAScript 2018 wird ein Look-Behind mit variabler Länge (von rechts nach links ausgewertet) eingeführt, mit dem einfach alle Zahlen gleichzeitig mit der Eingabe gezählt werden können.

Es stellt sich heraus, dass dies unabhängig von der Retina-Lösung von Leaky Nun die gleiche Methode ist , und der Regex hat sogar die gleiche Länge ( und ist austauschbar ). Ich lasse es hier, weil es von Interesse sein kann, dass diese Methode in ECMAScript 2018 (und nicht nur in .NET) funktioniert.

                        # 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$_)}

Erläuterung:

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

Beispiel:

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

J, 11 Bytes

+/@(1=+.)i.

Verwendung

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

wo >>ist STDIN und <<ist STDOUT.

Erläuterung

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

Julia, 25 Bytes

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

Es ist ganz einfach: Mit dieser sumFunktion können Sie der Funktion eine Funktion zuweisen, die vor der Summierung angewendet werden soll. Dies entspricht im Grunde dem Ausführen von mapund dann sum. Dies zählt direkt die Anzahl der relativ Primzahlen kleiner als 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)

Testen Sie es auf Ideone .

Hintergrund

Durch die Eulersche Produktformel ,

wobei φ die Euler'sche Totientenfunktion bezeichnet und p nur über Primzahlen variiert.

Um Primzahlen zu identifizieren, verwenden wir eine Folgerung aus Wilsons Theorem :

Wie es funktioniert

Die Variable m ist immer gleich dem Quadrat der Fakultät von k - 1 . Tatsächlich haben wir Argumente standardmäßig mit k = 1 und m = 0 benannt! ² = 1 .

Solange k ≤ n ist n*(k>n), wird 0 ausgewertet und der folgende Code orausgeführt.

Denken Sie daran, dass dies 1m%k ergibt, wenn m eine Primzahl ist, und 0, wenn nicht. Dies bedeutet, dass nur dann True ergibt, wenn sowohl k eine Primzahl ist als auch x durch k teilbar ist .x%k<m%k

In diesem Fall (n%k<m%k)*n/kergibt sich n / k , und durch Subtrahieren von n wird sein vorheriger Wert durch n (1 - 1 / k) ersetzt , wie in der Euler-Produktformel. Ansonsten (n%k<m%k)*n/kergibt sich 0 und n bleiben die unverändert.

Nach der Berechnung des Vorstehenden inkrementieren wir k und multiplizieren m mit dem "alten" Wert von k ² , wodurch die gewünschte Beziehung zwischen k und m aufrechterhalten wird , und rufen dann f rekursiv mit den aktualisierten Argumenten auf.

Sobald k überschreitet n , n*(k>n)auswertet bis n , die durch die Funktion zurückgebracht wird.

Brachylog , 25 Bytes

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

Erläuterung

In Brachylog ist noch kein GCD integriert, daher prüfen wir, ob die beiden Zahlen keine Primfaktoren gemeinsam haben.

• Hauptprädikat:

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

Probieren Sie es online!

/iLQQ1

Probieren Sie es online!

Erläuterung

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 Byte

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

PowerShell verfügt nicht über eine GCD-Funktion, daher musste ich meine eigene rollen.

Dies geschieht Eingang $n, dann reicht von 1zu $nund Rohren dieser in eine Schleife |%{...}. Jede Iteration setzen wir zwei Hilfsvariablen $aund $bdann eine GCD ausführen whileSchleife. Jede Iteration, die wir überprüfen, $bist immer noch ungleich Null und speichert $a%$bdann $bden vorherigen Wert von $bbis $afür die nächste Schleife. Wir sammeln sich dann , ob $aheißt auf gleich 1in unserer Ausgangsgröße$o . Sobald die for-Schleife abgeschlossen ist, platzieren wir sie $oin der Pipeline und die Ausgabe ist implizit.

whileBetrachten Sie als Beispiel, wie die Schleife funktioniert, $n=20und wir sind dabei $_=8. Der erste Check hat $b=20, also betreten wir die Schleife. Wir berechnen zuerst $a%$boder 8%20 = 8, was zur $bgleichen Zeit gesetzt wird, die 20gesetzt wird $a. Überprüfen Sie 8=0, und wir geben die zweite Iteration ein. Wir berechnen 20%8 = 4und setzen das auf $b, setzen dann $aauf 8. Überprüfen Sie 4=0, und wir geben die dritte Iteration ein. Wir berechnen 8%4 = 0und setzen das auf $b, dann setzen wir $aauf 4. Überprüfen Sie 0=0und wir verlassen die Schleife, so dass die GCD (8,20) ist $a = 4. So, !($a-1) = !(4-1) = !(3) = 0so $o += 0und wir zählen das nicht.

Ruby, 32 Bytes

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

Ein Lambda, das eine Ganzzahl n annimmt und die Anzahl der Ganzzahlen im Bereich (1..n) zurückgibt, die mit n zusammenfallen.

Japt -mx, 7 5 Bytes

yN ¥1

Führen Sie es online aus

-2 Bytes dank Shaggy

Retina, 36 29 Bytes

7 Bytes dank Martin Ender.

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

Probieren Sie es online!

Erläuterung

Es gibt zwei Stufen (Befehle).

Erste Stufe

.+
$*

Es ist eine einfache Regex-Ersetzung, die die Eingabe in so viele konvertiert.

Beispielsweise 5würde konvertiert werden zu 11111.

Zweite Etage

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

Dieser reguläre Ausdruck versucht, die Positionen zu finden, die die Bedingung erfüllen (mit der Eingabe übereinstimmen), und gibt dann die Anzahl der Übereinstimmungen zurück.

Common Lisp, 58 Bytes

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

Dies ist eine einfache Schleife, die 1 bis zum angegebenen n zählt und die Summe erhöht, wenn gcd = 1. Ich verwende den Funktionsnamen o, da t der wahre boolesche Wert ist. Nicht annähernd die kürzeste, aber ziemlich einfach.

MATLAB / Octave, 21 Bytes

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

Erstellt eine anonyme Funktion mit dem Namen, ansdie mit der Ganzzahl aufgerufen werden kannn Namen, die nur als Eingabe :ans(n)

Online Demo

Faktor 50 Bytes

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

Macht aus einem Bereich ( iota ) n und curries n eine Funktion, die gcd xn für alle Werte von 0 <= x <= n erhält und prüft, ob das Ergebnis 1 ist . Filtern sie den ursprünglichen Bereich , ob das Ergebnis der GCD xn war 1 , und das nimmt Länge .

Python 2 , 44 Bytes

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

Dies verwendet die gleiche Methode, um Koprime wie zu identifizieren meine Antwort auf "Koprime bis zu N" .

Probieren Sie es online!

JavaScript (ES6), 53 Byte

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

Probieren Sie es online!

Eigentlich 11 Bytes

;╗R`╜g`M1@c

Probieren Sie es online!

Erläuterung

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

Mit eingebautem

▒

Probieren Sie es online!

JavaScript (ES6), 67 Byte

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¼

Erklärt

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

Probieren Sie es online aus

APL, 7 Bytes

+/1=⊢∨⍳

Dies ist ein monadischer Funktionszug, der rechts eine ganze Zahl annimmt. Der Ansatz hier ist der offensichtliche: summieren Sie ( +/), wie oft die GCD der Eingabe und die Zahlen von 1 bis zur Eingabe ( ⊢∨⍳) gleich 1 ( 1=) sind.

Probieren Sie es hier aus

Haskell, 31-30 Bytes

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

Dank @Damien 1 Byte gespeichert.

Wählt Werte mit gcd = 1 aus, ordnet sie jeweils 1 zu und nimmt dann die Summe.

Batch, 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

Bearbeiten: 4 Bytes durch Entfernen unnötiger Leerzeichen gespeichert. 1 Byte mit gespeichert +=. 1 Byte gespart durch Löschen von tas +=wird das als 0ohnehin interpretiert . 1 Byte dank @ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ gespeichert.