Berechnen Sie die Euler'sche Summenfunktion

27

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.

bkul
quelle
4
Nun , es war dies der andere Tag. Ich denke nicht, dass die wiederholte Anwendung einen ausreichenden Unterschied macht, aber wenn irgendetwas, würde ich die andere schließen, weil ich auch nicht denke, dass die wiederholte Anwendung irgendetwas hinzufügt. Der größere Unterschied besteht jedoch darin, dass diese Version integrierte Funktionen zulässt und diese nicht.
Martin Ender
Das Verbieten von eingebauten Funktionen hat anscheinend keinen Einfluss auf die Antworten.
Julie Pelletier
2
@ JuliePelletier Warum ist das so? Meine Mathematica-Antwort wäre sonst 19 Bytes kürzer gewesen:EulerPhi
Martin Ender
@ JuliePelletier GCD ist zulässig, da die Berechnung von GCD nicht das beabsichtigte Problem ist, das gelöst werden soll. Sicher, es könnte die Anzahl der Bytes bei diesen Antworten erhöhen, aber es macht die Herausforderung nicht besser. Ich werde bearbeiten, um zu klären.
bkul

Antworten:

13

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] &
Martin Ender
quelle
11

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.

David
quelle
Das eingebaute ist _Zpfür diejenigen, die sich fragen.
David
9

J 9 Bytes

(-~:)&.q:

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

Gegeben n = p 1 e 1p 2 e 2 ∙∙∙ p k e k wobei p k ein Primfaktor ist n , die Totientenfunktion φ ( n ) = φ ( p 1 e 1 ) ∙ φ ( p 2 e 2 ) & PHgr; ( p k e k ) = ( p 1 - 1) p 1 e 1 - 1 & PHgr; ( p 2 - 1) p 2e 2 - 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)
Meilen
quelle
Verwenden Sie die Tatsache, dass Totient multiplikativ ist, um eine andere Lösung in J mit Rekursion zu machen :)
Leaky Nun
@LeakyNun Ich glaube nicht, dass es eine einfache Möglichkeit gibt, das Factoring zu testen, da selbst bei der Verwendung der iterativen Form [:*/@({.(^-(^<:)){:)2&p:24 Byte erforderlich sind. Oder vielleicht gibt es einen kürzeren Weg und ich sehe es nicht.
Meilen
8

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.
Undichte Nonne
quelle
7

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.

xnor
quelle
Ich denke, dies ist die erste Antwort von Haskell, die ich tatsächlich verstehe. Es ist so eine coole Sprache, aber es ist so anders als die meisten anderen.
bkul
Wow, ich habe erwartet, dass der Mustervergleich in den Verstehenslisten vollständig sein muss. Danke für den Trick.
Damien
6

Pyke, 5 Bytes

m.H1/

Probieren Sie es hier aus!

count(map(gcd, range(input)), 1)
Blau
quelle
1
So viele Python-Derivate. Ich mag dieses allerdings. Interessante Voraussetzung.
bkul
5

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.

bkul
quelle
1
lambda n:sum(gcd(n,x)<2for x in range(n))
Undichte Nonne
Oh, endlich hat Python gcddas Mathe-Modul erweitert! Ich wusste es nicht.
Rubik
5

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:

Bildbeschreibung hier eingeben

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 -~.

xnor
quelle
5

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
Grimmig
quelle
4

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
Brad Gilbert b2gills
quelle
20 Bytes
Jo King
4

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
Undichte Nonne
quelle
Wie haben Sie die vertikale Baumdarstellung erhalten? Ich dachte, dass es nur horizontal produziert.
Meilen
@miles Ich habe es selbst geschrieben.
Undichte Nonne
4

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.

Glen O
quelle
4

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 ,

Eulers Produktformel

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

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

Folgerung aus Wilsons Satz

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! 2 = 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 2 , 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.

Dennis
quelle
3

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
    
Tödlich
quelle
3

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
Undichte Nonne
quelle
3

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.

AdmBorkBork
quelle
3

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.

Redouane Red
quelle
Hallo und willkommen bei PPCG! Dies ist ein großartiger erster Beitrag.
NoOneIsHere
Willkommen bei Programming Puzzles und Code Golf! Dies ist eine großartige erste Lösung, weiter so!
bkul
Danke, nicht wirklich so kurz, ich frage mich, ob es möglich ist, es zu verbessern.
Redouane Red
3

Japt -mx, 7 5 Bytes

yN ¥1

Führen Sie es online aus

-2 Bytes dank Shaggy

Oliver
quelle
5 Bytes mit -mx.
Shaggy
@ Shaggy Ah, schön. Ich habe versucht, eine -mLösung zu finden, aber vergessen -x. Vielen Dank!
Oliver
2

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.

Undichte Nonne
quelle
Lookbehind macht keinen Backtrack, außer in einem Lookahead?
Undichte Nonne
Lookarounds ziehen sich im Allgemeinen nicht zurück.
Martin Ender
Wie kommt es dann, dass der Regex jeden Teiler getestet hat?
Undichte Nonne
1
Nun, sie ziehen sich zurück, solange Sie sie nicht verlassen. Solange sich die Engine im Lookaround befindet, wird alles versucht, um diesen Lookaround zu erzielen (oder bei einem negativen Lookaround fehlschlagen). Sobald der Lookaround bestanden ist, wird die Engine nicht mehr zurückverfolgen, wenn irgendetwas danach fehlschlägt (es sei denn, sie beginnt auch, Dinge vor dem Lookaround zurückzuverfolgen und muss sowieso alles neu bewerten).
Martin Ender
2

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.

WarWeasle
quelle
Hat CL keine anonyme Funktion?
Katze
2

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

Suever
quelle
2

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 .

Katze
quelle
[ dup iota swap '[ _ gcd nip 1 = ] map sum ]spart 6 Bytes (glaube ich - nicht sehr erfahren mit Faktor).
bkul
@bkul Danke für den Vorschlag! : D Leider gibt es keinerlei Kompatibilität zwischen Zahlen und t/f(Symbolen) in Factor. Die einzige Möglichkeit, dies zu implementieren, besteht darin, genau [ dup iota swap '[ _ gcd nip 1 = 1 0 ? ] map sum ]dieselbe Länge wie die aktuelle Lösung zu verwenden.
Katze
Ah, verdammt. Das starke Tippen schlägt wieder zu.
bkul
@bkul Nun, ich bin dankbar für das starke Tippen und TYPED:in echtem Faktorcode : P
cat
1

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!

Undichte Nonne
quelle
Sie können alternativ ;╗R`╜g1=`MΣfür die gleiche Byteanzahl verwenden
Mego
1

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)
Neil
quelle
1

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

Emigna
quelle
1

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

Alex A.
quelle
1

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.

sudee
quelle
Sie können ==1durch<2
Damien
1

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.

Neil
quelle