Bei einer gegebenen Zahl n >= 2
werden alle positiven ganzen Zahlen kleiner als n
where ausgegeben gcd(n, k) == 1
(wobei k
es sich um eine der ausgegebenen Zahlen handelt). Zahlen dieser Art sind miteinander koprimiert .
Beispiel: 10
gibt die Ausgabe aus [1, 3, 7, 9]
(in beliebiger Form, solange die Zahlen eindeutig getrennt sind und in einer Liste stehen). Die Liste darf keine doppelten Einträge enthalten und muss nicht sortiert werden.
Weitere Testfälle:
2 -> [1]
3 -> [1, 2]
6 -> [1, 5]
10 -> [1, 3, 7, 9]
20 -> [1, 3, 7, 9, 11, 13, 17, 19]
25 -> [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24]
30 -> [1, 7, 11, 13, 17, 19, 23, 29]
Wir zählen auch keine Zahlen darüber n
, für die Coprime gilt n
, nur weil ich ziemlich sicher bin, dass es unendlich viele Lösungen gibt.
Beachten Sie auch: Zahlen, die miteinander in Zusammenhang stehen, gelten ebenfalls als relativ prim oder für sich gegenseitig prim.
code-golf
math
number-theory
primes
Rɪᴋᴇʀ
quelle
quelle
1\n3\n
Zählen einzelne Strings (zB ) als gültige Ausgabe?Antworten:
Gelee , 3 Bytes
Probieren Sie es online!
Wie funktioniert das?
Gültigkeitsnachweis
Da wir die coprimes nur extrahieren möchten, der Minimalwert der Greatest-Common Divisoren Liste hat seine 1 für den
ÐṂ
Trick an der Arbeit. Beweisen wir das (auf zwei verschiedene Arten):Der implizit generierte Bereich enthält und . Der größte gemeinsame Teiler ist immer eine streng positive ganze Zahl, daher ist das Auftreten von garantiert und der Mindestwert.[1,input] 1 gcd(1,x)=1∀x∈Z∗ 1
Zwei aufeinanderfolgende positive ganze Zahlen sind immer Koprime. Betrachte mit . Dann nehmen wir eine weitere positive ganze Zahl so dass und .x,y∈Z∗ y=x+1 k k∣x k∣y
Dies impliziert, dass , also , also . Die einzige positive Ganzzahl zum Teilen von ist selbst, daher wird sie garantiert in der Liste angezeigt und ist immer der Mindestwert.k∣(y−x) k∣(x+1−x) k∣1 1 1
quelle
ÐṂ
es das damals gab, trotzdem bin ich mit diesem recht zufrieden.DṂ
existierte, aber es funktionierte nur für Monaden. Die Festschreibung implementiertÞ
,ÐṂ
,ÐṀ
für Dyaden datiert 9. Mai 2017.Python 2 ,
6147 BytesProbieren Sie es online!
Hintergrund
Betrachten Sie den Ring . Während dieser Ring normalerweise unter Verwendung der Restklassen modulo , kann er auch als die Menge , wobei die Additions- und Multiplikationsoperatoren durch und , wobei die übliche Addition bezeichnen, Multiplikation und Modulo-Operatoren über die ganzen Zahlen.n Z n = { 0 , … , n - 1 } a + n b = ( a + b )(Zn,+n,⋅n) n Zn={0,…,n−1} a ⋅ n b = a ⋅ ba+nb=(a+b)%n + ,a⋅nb=a⋅b%n +,⋅, and %
Zwei Elemente und von heißen gegenseitige multiplikative Inversen modulo wenn . Beachten Sie, dass wenn .b Z n n a ≤ n b = 1a b Zn n 1a⋅nb=1%n n > 11%n=1 n>1
Fixiere und sei ein Koprime von in . Wenn für zwei Elemente und von , haben wir das . Dies impliziert, dass , und wir folgen diesem , dh teilt gleichmäßig auf. Da keine Primteiler mit teilt , bedeutet dies, dass . Endlich, weila n Z n a ≤ n x = a ≤ n y x y Z n a ≤ xn>1 a n Zn a⋅nx=a⋅ny x y Zn a ⋅ ( x - y )a⋅x%n=a⋅y%n n ∣ a ⋅ ( x - y ) n a ⋅ ( x - y ) n a n ∣ x - y - n < x - y < n x = y a ⋅ n 0 , ... , a ⋅ n ( n - 1 ) Z n Z n n 1 b Za⋅(x−y)%n=a⋅x%n−a⋅y%n=0 n∣a⋅(x−y) n a⋅(x−y) n a n∣x−y −n<x−y<n , wir schließen daraus, dass . Dies zeigt, dass die Produkte alle verschiedene Elemente von . Da genau Elemente hat, muss eines (und genau eines) dieser Produkte gleich , dh es gibt ein eindeutiges in so dass .x=y a⋅n0,…,a⋅n(n−1) Zn Zn n 1 b a ≤ n b = 1Zn a⋅nb=1
umgekehrt und lasse ein Element von , das nicht zu ist . In diesem Fall gibt es eine Primzahl , so daß und . Wenn eine multiplikative Inverse Modulo zugelassen (nennen wir es ), wir haben würde , was bedeutet , dass und daher , also . Seit folgen wir dema Z n n p p | a p | n a n b eine ⋅ n b = 1 eine ⋅ bn>1 a Zn n p p∣a p∣n a n b a⋅nb=1 ( a ⋅ b - 1 )a⋅b%n=1 n | a ⋅ b - 1 p | a p | a ⋅ b p | n p | a ⋅ b - 1 p | ( a ⋅ b ) - ( a ⋅ b - 1 ) = 1 p(a⋅b−1)%n=a⋅b%n−1=0 n∣a⋅b−1 p∣a p∣a⋅b . Andererseits folgen wir seit auch diesem . Auf diese Weise ist , was der Annahme widerspricht, dass eine Primzahl ist.p∣n p∣a⋅b−1 p∣(a⋅b)−(a⋅b−1)=1 p
Dies beweist, dass die folgenden Aussagen äquivalent sind, wenn .n>1
na und sind Koprime.n
na ein multiplikatives inverses Modulo .n
na gibt eine eindeutige multiplikative Inverse modulo .n
Wie es funktioniert
Für jedes Paar von ganzen Zahlen und in ist die ganze Zahl eindeutig; Tatsächlich sind und Quotient und der Rest von geteilt durch , dh wenn , können wir und , wobei eine ganzzahlige Division bedeutet. Schließlich ist , da und , ein Element von ; in der Tat ist .b Z n k : = a ⋅ n + b a b k n k ein = k / n b = ka b Zn k:=a⋅n+b a b k n k a=k/n / a ≤ n - 1 b ≤ n - 1 k Z n 2 k ≤ ( n - 1 ) ⋅ n + ( n - 1 ) = n 2 - 1b=k%n / a≤n−1 b≤n−1 k Zn2 k≤(n−1)⋅n+(n−1)=n2−1
Wie oben erwähnt, gibt es , wenn und Koprime sind, ein eindeutiges so dass , dh es gibt ein eindeutiges so dass und , so wird die erzeugte Liste enthält genau einmal.n b a ⋅ ba n b a⋅b%n=1 k k/n=a k/n⋅k%n=(k/n)⋅(k%n)%n=1 a
Umgekehrt, wenn und sind nicht coprime, die Bedingung für alle Werte von falsch sein derart , daß , so dass die erzeugte Liste wird nicht enthalten .a n k/n⋅k%n=1 k a=k/n a
Dies beweist, dass die Liste, die das Lambda zurückgibt, genau einmal alle Koprime von in .Z nn Zn
quelle
Gelee , 4 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
gRỊT
ÐṂ
) (ab) zu verwenden , um 3 Bytes zu erhalten .Mathematica, 25 Bytes
Etwas seltsames Ausgabeformat, bei dem jedes Ergebnis in eine separate Liste eingeschlossen wird, z
{{1}, {3}, {7}, {9}}
. Wenn das nicht in Ordnung ist, habe ich zwei Lösungen mit 30 Bytes:Mathematica hat tatsächlich,
CoprimeQ
aber das ist viel zu lang.quelle
Q
bedeutet inCoprimeQ
?EvenQ
,PrimeQ
oderSubsetQ
.2sable , 4 Bytes
Code:
Erläuterung:
Verwendet die CP-1252- Codierung. Probieren Sie es online!
quelle
Python,
938274 Bytesf
prüft rekursiv auf Koprime und das zweite Lambda generiert sie. Gibt eine Liste aus.quelle
Eigentlich 8 Bytes
Probieren Sie es online!
Erläuterung:
quelle
range(1, n)
wenn das keine Bytes spart.R
(range(1, n+1)
) undr
(range(n)
). Da sie gleichwertig sind, habe ich gewähltR
(da ich beim Schreiben des Codes versehentlich die Feststelltaste gedrückt habe).MATL , 7 Bytes
Probieren Sie es online!
quelle
MATLAB / Octave, 22 Bytes
Probieren Sie es online!
quelle
JavaScript (ES6),
6461 Bytes3 Bytes gespart dank @ user81655
Testschnipsel
quelle
a==
mita<2
?a
könnte irgendwann 0 sein. Ich mussfilter
, um zub
...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
Qualle ,
1918 BytesDies funktioniert, indem die Primfaktorisierung jeder Zahl im Bereich berechnet und überprüft wird, ob sie die der Eingabe schneidet (Jellyfish hat noch keinen integrierten GCD). Aus Golfgründen erfolgt die Ausgabe in absteigender Reihenfolge. Probieren Sie es online!
Erläuterung
Zunächst
i
wird die Eingabe ausgewertet. für die Eingabe10
ist der Wert deri
-Zelle10
.Hier wird
r
(range) auf den Eingang und 1 angewendet. Da der Eingang größer als 1 ist, ist der Bereich in absteigender Reihenfolge. für die Eingabe10
gibt dies[9 8 7 6 5 4 3 2 1]
.Dieser Teil ist eine große Funktion, die auf
i
und über den oben genannten Bereich ausgewertet wird.Schnittmenge (
n
) von Primfaktoren (x
).Ist es leer? (
N
)Fädle dich auf Level 0 ein und teste für jedes Element des Bereichs.
Filtern Sie (
#
) den Bereich in Bezug auf diese Liste von Booleschen Werten. Die von erzeugte Funktion[
möchte das Argument to#
als eigenes Argument verwenden, daherB
blockieren wir das Abrufen#
von Argumenten mit a. Andernfalls würde der Wert der~
-Zelle als Argument der großen Funktion verwendet. Zum Schluss wirdp
das Ergebnis gedruckt.quelle
Gestapelt, nicht konkurrierend,
2421 Bytes3 Bytes gespeichert , inspiriert von Borsunhos Rubin . (
1 eq
zu2<
)Probieren Sie es hier aus!
Dies ist ein n-Lambda, das ein einzelnes Argument verwendet und das Array ergibt.
quelle
keep
funktionierte nicht gut.CJam , 14 Bytes
Probieren Sie es online!
Erläuterung
Wir müssen nicht alle möglichen Teiler von überprüfen
a
undb
testen, ob es sich um Coprime handelt. Es ist ausreichend zu prüfen, ob einer der Hauptfaktoren derb
Teilung ista
.quelle
Mathematica, 26 Bytes
quelle
Perl 6 , 20 Bytes
quelle
Brachylog ,
16 bis13 BytesDies ist eine Funktion, die N als Eingabe verwendet und alle Ganzzahlen generiert, die kleiner sind als und gleichzeitig dazu gehören.
Probieren Sie es online! Wie so oft in Brachylog wurde ein zusätzlicher Code hinzugefügt, um die Funktion in ein vollständiges Programm zu verwandeln. Wenn der Brachylog-Interpreter eine Funktion anstelle eines vollständigen Programms ausführt, wird die Ausgabe jedoch nicht gedruckt, was bedeutet, dass Sie die Funktionsweise nicht wirklich beobachten können.
Erläuterung:
Ein Brachylog-Programm ist eine Kette von Einschränkungen. Typischerweise ist die LHS einer Einschränkung die RHS der nächsten.
Es gibt keinen Grund zu prüfen, ob der gemeinsame Faktor (von dem bereits bekannt ist, dass er ein Primfaktor der Ausgabe ist) ein Primfaktor der Eingabe ist. Wir wissen bereits, dass es eine Primzahl ist, also können wir einfach prüfen, ob es sich um einen Faktor handelt. Ich bin hier angenehm überrascht, dass
:A*?
der Interpreter nicht in eine Endlosschleife geschickt wird und keinen nicht ganzzahligen Wert für A zulässt , aber da der Interpreter tut, was ich will, nehme ich ihn.quelle
Dyalog APL, 10 Bytes .
Erklärung (Eingabe
n
):quelle
⍨
Japt
-f
,9852 BytesVersuch es
quelle
o f_jU
j
man auch testen kann, ob zwei Zahlen Co-Primzahlen sind.Mathematica, 33 Bytes
Enthält U + F4A1
quelle
Haskell, 27 Bytes
Probieren Sie es online!
quelle
Julia 0,5 , 23 Bytes
Probieren Sie es online!
quelle
Meme , 11 Bytes nicht konkurrierend , veraltet
Nicht konkurrierend als Iteration von STDIN ist neu. Verwendet UTF-8-Codierung.
Erläuterung:
}
greift auf das nächste Eingabeelement zu, die letzte Eingabe wird jedoch durchgeschleift, sodass die Eingabe6
wie6 6 6 6 6 ...
bei STDIN erfolgt und das Lesen von zwei Ausgängen von einem ermöglicht wird.quelle
05AB1E , 3 Bytes
Probieren Sie es online!
Hat neue Funktionen.
quelle
Ruby,
3634Zugegeben, das ist keine sehr inspirierte Antwort.
2 Bytes gespart dank Conor O'Brien.
quelle
(n)
Python 3 , 60 Bytes
Importiert gcd, anstatt ein neues Lambda dafür zu schreiben. Golfvorschläge sind willkommen. Probieren Sie es online!
quelle
Julia, 30 Bytes
Anonyme Funktion.
filter
Entfernt Elemente aus einer Liste, die gemäß einer Funktion nicht wahr sind.In diesem Fall lautet die Funktion
x->(gcd(n,x)<2)
(true, wenn der gcd des Eingangs und des Listenelements kleiner als 2 ist). Die Liste ist der Bereich1:n
.quelle
PARI / GP , 27 Bytes
Hierbei wird die in Version 2.6.0 (2013) eingeführte Set-Notation verwendet. In früheren Versionen wurden vier weitere Bytes benötigt:
würde gebraucht werden.
quelle
[1..n]
) ein, überprüfen Sie, ob gcd 1 (gcd(n,k)<2
) ist, und geben Sie die Zahlen mit dieser Eigenschaft zurück. Die->
ist die Funktions- / Schließungsnotation, die um 2 Byte kürzer als die normale Funktionssyntax ist, und[...|...<-...,...]
die in der Antwort erläuterte Satznotation (siehe Abschnitt 2.3.14 im Benutzerhandbuch oder suchen nach<-
).05AB1E , 4 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
C (gcc) , 54 Bytes
Dies ist ein Port meiner Python-Antwort .
Probieren Sie es online!
quelle
Pyth , 5 Bytes
Probieren Sie es online!
Wie es funktioniert
Beachten Sie, dass Pyth die 0-Indizierung verwendet.
quelle