Coprimes bis zu N

51

Bei einer gegebenen Zahl n >= 2werden alle positiven ganzen Zahlen kleiner als nwhere ausgegeben gcd(n, k) == 1(wobei kes sich um eine der ausgegebenen Zahlen handelt). Zahlen dieser Art sind miteinander koprimiert .

Beispiel: 10gibt 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.

Rɪᴋᴇʀ
quelle
1\n3\nZählen einzelne Strings (zB ) als gültige Ausgabe?
DevRicher
@ devRicher das funktioniert, klar.
27.
Die Intuition darüber, dass es eine unendliche Anzahl von Zahlen über n gibt, die zu n koprim sind, fühlt sich für mich richtig an. Es gibt unendlich viele Primzahlen, und eine Primzahl würde mit jeder Zahl darunter koprime sein. Daher ist auch jede Primzahl größer als n (von denen es unendlich viele gibt) Teil der Coprime-Liste.
Brian J
@ BrianJ Nicht nur das. Wenn c und n Koprime sind, sind c + kn und n auch Koprime für alle ganzen Zahlen k .
Dennis
1
Lustige Tatsache: Diese werden Totative genannt .
Wojowu

Antworten:

17

Gelee , 3 Bytes

gÐṂ

Probieren Sie es online!

Wie funktioniert das?

gÐṂ - (Monadic) Volles Programm.

g - Größter gemeinsamer Teiler.
 ÐṂ - Behalte die Elemente mit dem minimalen Verknüpfungswert (dh die mit GCD == 1)
       Beachten Sie, dass dadurch automatisch der Bereich [1, Eingabe] (einschließlich) erstellt wird.

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):

  1. 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]1gcd(1,x)=1xZ1

  2. Zwei aufeinanderfolgende positive ganze Zahlen sind immer Koprime. Betrachte mit . Dann nehmen wir eine weitere positive ganze Zahl so dass und .x,yZy=x+1kkxky

    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(yx)k(x+1x)k111

Mr. Xcoder
quelle
2
Du hast Dennis nach 9 Monaten in seiner Muttersprache übertroffen!
Adám
@Adám Ich bin mir nicht sicher, ob ÐṂes das damals gab, trotzdem bin ich mit diesem recht zufrieden.
Mr. Xcoder
2
Für die Aufzeichnung DṂexistierte, aber es funktionierte nur für Monaden. Die Festschreibung implementiert Þ, ÐṂ, ÐṀfür Dyaden datiert 9. Mai 2017.
Dennis
@ Tennis Ich wusste, dass es einen guten Grund geben würde, warum Sie nicht die 3-Byte-Version hatten. Darüber haben wir uns auch im Chat Gedanken gemacht. Vielen Dank für die nützlichen Informationen!
Mr. Xcoder
56

Python 2 , 61 47 Bytes

lambda n:[k/n for k in range(n*n)if k/n*k%n==1]

Probieren 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)nZn={0,,n1}a n b = a ba+nb=(a+b)%n+ ,anb=ab%n+,, and %

Zwei Elemente und von heißen gegenseitige multiplikative Inversen modulo wenn . Beachten Sie, dass wenn .b Z n n a n b = 1abZnn1anb=1%nn > 11%n=1n>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>1anZnanx=anyxyZna ( x - y )ax%n=ay%nn 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(xy)%n=ax%nay%n=0na(xy)na(xy)nanxyn<xy<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=yan0,,an(n1)ZnZnn1 b a n b = 1Znanb=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>1aZnnppapnanbanb=1( a b - 1 )ab%n=1n | a b - 1 p | a p | a b p | n p | a b - 1 p | ( a b ) - ( a b - 1 ) = 1 p(ab1)%n=ab%n1=0nab1papab . Andererseits folgen wir seit auch diesem . Auf diese Weise ist , was der Annahme widerspricht, dass eine Primzahl ist.pnpab1p(ab)(ab1)=1p

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 = kabZnk:=an+babknka=k/n/ a n - 1 b n - 1 k Z n 2 k ( n - 1 ) n + ( n - 1 ) = n 2 - 1b=k%n/an1bn1kZn2k(n1)n+(n1)=n21

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 banbab%n=1kk/n=ak/nk%n=(k/n)(k%n)%n=1a

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 .ank/nk%n=1ka=k/na

Dies beweist, dass die Liste, die das Lambda zurückgibt, genau einmal alle Koprime von in .Z nnZn

Dennis
quelle
26
"GCD? Wo wir hingehen, brauchen wir keine GCD."
26.
1
Woah. Das war alles, was ich schreiben wollte, aber anscheinend brauchte ich 15 Zeichen. Trotzdem, woah. Gut gemacht.
Eric Lagergren
24

Gelee , 4 Bytes

gRỊT

Probieren Sie es online!

Wie es funktioniert

gRỊT  Main link. Argument: n

 R    Range; yield [1, ..., n].
g     Compute the GCD of n and each k in [1, ..., n].
  Ị   Insignificant; return 1 for GCDs less or equal to 1.
   T  Truth; yield the indices of all truthy elements.
Dennis
quelle
33
Das gRỊT
Codieren
1
Ich habe es geschafft, den "Minimum Link Value" quick ( ÐṂ) (ab) zu verwenden , um 3 Bytes zu erhalten .
Mr. Xcoder
14

Mathematica, 25 Bytes

Range@#~GCD~#~Position~1&

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:

Select[Range[x=#],#~GCD~x<2&]&
#&@@@Range@#~GCD~#~Position~1&

Mathematica hat tatsächlich, CoprimeQaber das ist viel zu lang.

Martin Ender
quelle
1
Was Qbedeutet in CoprimeQ?
Conor O'Brien
2
@ ConorO'Brien "Frage", denke ich. Alle Entscheidungsproblem Einbauten enden in Q wie EvenQ, PrimeQoder SubsetQ.
Martin Ender
10

2sable , 4 Bytes

Code:

ƒN¿–

Erläuterung:

ƒ       # For N in the range [0, input]..
 N¿     #   Compute the GCD of N and the input
   –    #   If 1, print N with a newline

Verwendet die CP-1252- Codierung. Probieren Sie es online!

Adnan
quelle
Gute Arbeit (fast) gegen Dennis. (ein paar Minuten zu spät).
Zacharý
10

Python, 93 82 74 Bytes

f=lambda a,b:f(b,a%b)if b else a<2
lambda c:[i for i in range(c)if f(i,c)]

fprüft rekursiv auf Koprime und das zweite Lambda generiert sie. Gibt eine Liste aus.

Rɪᴋᴇʀ
quelle
7

Eigentlich 8 Bytes

;╗R`╜┤`░

Probieren Sie es online!

Erläuterung:

;╗R`╜┤`░
  R`  `░  elements of range(1, n+1) where
;╗  ╜     n and the element
     ┤    are coprime
Mego
quelle
1
Ich glaube, Sie können nur tun, range(1, n)wenn das keine Bytes spart.
ETHproductions
1
@ETHproductions Das tut es nicht. Die beiden Optionen sind R( range(1, n+1)) und r( range(n)). Da sie gleichwertig sind, habe ich gewählt R(da ich beim Schreiben des Codes versehentlich die Feststelltaste gedrückt habe).
Mego
Ja, das habe ich mir gedacht. Ich habe keine Anweisung gesehen, die sich dem Inkrementieren zu widmen schien, aber ich dachte, es könnte sowieso eine gegeben haben
ETHproductions
6

JavaScript (ES6), 64 61 Bytes

3 Bytes gespart dank @ user81655

n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))

Testschnipsel

f=n=>[...Array(n).keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))

for(var i = 2; i < 50; i++) console.log(i + ":", `[${ f(i) }]`);

ETHproductions
quelle
Können Sie nicht tauschen a==mit a<2?
26.
@EasterlyIrk Nicht sicher, akönnte irgendwann 0 sein. Ich muss
nachsehen
Sie können die GCD-Funktion in verschieben filter, um zu b...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
vermeiden
@ user81655 Das ist großartig, danke! :-)
ETHproductions
6

Qualle , 19 18 Bytes

p
[#
`B
&~xr1
NnEi

Dies 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 iwird die Eingabe ausgewertet. für die Eingabe 10ist der Wert der i-Zelle 10.

r1
i

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 Eingabe 10gibt dies [9 8 7 6 5 4 3 2 1].

[#
`B
&~x
Nn

Dieser Teil ist eine große Funktion, die auf iund über den oben genannten Bereich ausgewertet wird.

~x
n

Schnittmenge ( n) von Primfaktoren ( x).

&~x
Nn

Ist es leer? ( N)

`
&~x
Nn

Fädle dich auf Level 0 ein und teste für jedes Element des Bereichs.

[#
`B
&~x
Nn

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, daher Bblockieren wir das Abrufen #von Argumenten mit a. Andernfalls würde der Wert der ~-Zelle als Argument der großen Funktion verwendet. Zum Schluss wird pdas Ergebnis gedruckt.

Zgarb
quelle
5

Gestapelt, nicht konkurrierend, 24 21 Bytes

3 Bytes gespeichert , inspiriert von Borsunhos Rubin . ( 1 eqzu 2<)

{!n:>1+:n gcd 2<keep}

Probieren Sie es hier aus!

Dies ist ein n-Lambda, das ein einzelnes Argument verwendet und das Array ergibt.

{!n:>1+:n gcd 2<keep}
{!                  }  n-lambda
  n                    push n
   :>                  range [0, n)
     1+                range [1, n]
       :               duplicate
        n gcd          element-wise gcd with n
              2<       element-wise equality with 1
                       this yields the range [1, n] and a boolean mask of coprime numbers
                keep   then, we simply apply the mask to the range and keep coprimes.
Conor O'Brien
quelle
Warum ist das nicht konkurrierend?
Zacharý
@ ZacharyT hauptsächlich keepfunktionierte nicht gut.
Conor O'Brien
5

CJam , 14 Bytes

{:X{Xmff%:*},}

Probieren Sie es online!

Erläuterung

Wir müssen nicht alle möglichen Teiler von überprüfen aund btesten, ob es sich um Coprime handelt. Es ist ausreichend zu prüfen, ob einer der Hauptfaktoren der bTeilung ist a.

:X     e# Store the input in X.
{      e# Filter the list [0 1 ... X-1] by the results of this block...
  Xmf  e#   Get the prime factors of X.
  f%   e#   Take the current value modulo each of those prime factors.
  :*   e#   Multiply the results. Iff any of them divide the current
       e#   value, there's a 0 in the list, and the result of the product
       e#   is also 0, dropping the value from the resulting list.
},
Martin Ender
quelle
5

Mathematica, 26 Bytes

Pick[r=Range@#,r~GCD~#,1]&
Alephalpha
quelle
1
Ohhhh, ich habe nach etwas wie Pick gesucht. Ich denke, jetzt bin ich froh, dass ich es nicht gefunden habe. ;) Aber es sollte für zukünftige Herausforderungen sehr nützlich sein.
Martin Ender
4

Brachylog , 16 bis 13 Bytes

>.$p'(e:A*?),

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

>.$p'(e:A*?),
>              The input is greater than
 .             the output, whose
  $p           prime factorisation does
    '(     )   not obey the following constraint:
      e        it has an element which
       :A*     can be multiplied by something to
          ?    produce the input.
            ,  (This comma turns off an unwanted implicit constraint.)

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.

Gemeinschaft
quelle
4

Dyalog APL, 10 Bytes .

0~⍨⍳×1=⊢∨⍳

Erklärung (Eingabe n):

0~⍨⍳×1=⊢∨⍳
         ⍳ - 1 ... n (Thus, ⎕IO is 1)
       ⊢∨  - Each GCD'd by n
     1=    - Test equality with 1 on each element
   ⍳×      - multiplied by its index
0~⍨        - without 0.
Zacharý
quelle
3
Ich mag die Art und Weise, wie APL-Code wie das Gesicht aussieht, das Sie beim Lesen machen.
DJMcMayhem
Ja, und es zerstört fast jede nicht Code-Golf-orientierte Sprache. :).
Zacharý
Warum nur "könnte" funktionieren?
26.
Ich gehe nur davon aus, dass es funktioniert.
Zacharý
@ ZacharyT warum kannst du es nicht testen? Wenn ich es in try-apl.org einfüge, tritt ein Fehler mit einem ungültigen Token auf.
26.
4

Japt -f , 9 8 5 2 Bytes

jN

Versuch es

  • 2 Bytes gespart dank Hinweis der ETH auf einen Brainfart, der zu einem weiteren gesparten Byte führte.
Zottelig
quelle
Sie könnteno f_jU
ETHproductions
Vielen Dank, @ETHproductions. Ich weiß nicht, was ich hier gedacht habe! Muss einer dieser (vielen) Momente gewesen sein, in denen ich vergessen habe, dass jman auch testen kann, ob zwei Zahlen Co-Primzahlen sind.
Shaggy
3

Mathematica, 33 Bytes

xSelect[Range@x,x~CoprimeQ~#&]

Enthält U + F4A1

JungHwan min
quelle
Was ist die nicht druckbare Aufgabe?
26.
3
@EasterlyIrk führt eine unbenannte Funktion mit einem benannten Argument ein. Es wird in Mma als Pfeil gerendert.
Martin Ender
@ MartinEnder oh, cool.
26.
U + F4A1 ist ein Zeichen für den privaten Gebrauch. Wie Martin sagte, wird es in Mathematica als Pfeil gerendert.
Zacharý
3

Meme , 11 Bytes nicht konkurrierend , veraltet

Nicht konkurrierend als Iteration von STDIN ist neu. Verwendet UTF-8-Codierung.

d`}}]i=1?ip

Erläuterung:

d     Set program to not output result
`}    Loop next input-times
}]i   GCD of input and loop index
=1?   Is it equal to 1? If yes,
ip    Print out loop index

}greift auf das nächste Eingabeelement zu, die letzte Eingabe wird jedoch durchgeschleift, sodass die Eingabe 6wie 6 6 6 6 6 ...bei STDIN erfolgt und das Lesen von zwei Ausgängen von einem ermöglicht wird.

devRicher
quelle
Hast du diese Sprache gerade erst erstellt? Wenn es vor der Herausforderung gemacht wird, muss es nicht konkurrierend sein.
Freitag,
@EasterlyIrk Es wurde vor 3 Tagen gemacht, ich arbeite nur ständig daran. Auch ich nehme an, du meinst danach ?
DevRicher
Ja, Tippfehler, danke. Und es ist in Ordnung, solange die in der Antwort verwendeten Funktionen älter als die Herausforderung sind.
26.
@EasterlyIrk Ich sehe, in diesem Fall muss ich meine Antwort bearbeiten.
DevRicher
Ja entschuldigung. : /
Rɪᴋᴇʀ
2

Ruby, 36 34

->n{n.times{|i|p i if i.gcd(n)<2}}

Zugegeben, das ist keine sehr inspirierte Antwort.

2 Bytes gespart dank Conor O'Brien.

Borsunho
quelle
Sie können zwei Bytes abschneiden, indem Sie die runden Klammern entfernen(n)
Conor O'Brien
2

Python 3 , 60 Bytes

Importiert gcd, anstatt ein neues Lambda dafür zu schreiben. Golfvorschläge sind willkommen. Probieren Sie es online!

import math
lambda c:[i for i in range(c)if math.gcd(c,i)<2]
Sherlock9
quelle
Ich glaube nicht, dass Sie mehr Golf spielen können. Wenn Sie gcd direkt oder math als m beide importieren, werden Bytes hinzugefügt.
26.
2

Julia, 30 Bytes

n->filter(x->(gcd(n,x)<2),1:n)

Anonyme Funktion. filterEntfernt 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 Bereich 1:n.

Rɪᴋᴇʀ
quelle
2

PARI / GP , 27 Bytes

n->[k|k<-[1..n],gcd(k,n)<2]

Hierbei wird die in Version 2.6.0 (2013) eingeführte Set-Notation verwendet. In früheren Versionen wurden vier weitere Bytes benötigt:

n->select(k->gcd(k,n)<2,[1..n])

würde gebraucht werden.

Charles
quelle
Wie funktioniert das?
28.
1
@EasterlyIrk Entspricht den meisten dieser Übermittlungen. Geben Sie einen Bereich von 1 bis n ( [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 <-).
Charles
2

05AB1E , 4 Bytes

GN¿–

Probieren Sie es online!

Wie es funktioniert

     # implicit input
G    # for N in range(1..input)
 N   # push N
  ¿  # gcd(input, N)
   – # if 1, print N
Neil A.
quelle
1

Pyth , 5 Bytes

x1iLQ

Probieren Sie es online!

Wie es funktioniert

Beachten Sie, dass Pyth die 0-Indizierung verwendet.

x1iLQ   Q = eval(input())

x1iLQQ  implicit Q at the end
  iLQQ  [gcd(Q,0), gcd(Q,1), ..., gcd(Q,Q-1)]
x1      all occurences of 1 in the above list (return their indices)
Undichte Nonne
quelle