Coprimes do N

51

Biorąc pod uwagę liczbę n >= 2, wypisz wszystkie dodatnie liczby całkowite mniejsze niż ngdzie gcd(n, k) == 1(przy kczym jest to jedna z liczb wyjściowych). Numery tego rodzaju są względnie pierwsze dla siebie.

Przykład: 10podaje dane wyjściowe [1, 3, 7, 9](w dowolnej formie, pod warunkiem, że liczby są jednoznacznie rozdzielone i znajdują się na liście). Lista nie może zawierać zduplikowanych wpisów i nie musi być sortowana.

Więcej przypadków testowych:

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]

Nie liczymy również powyższych liczb, nktóre są chronione prawem autorskim n, wyłącznie dlatego, że jestem pewien, że istnieją nieskończone rozwiązania.

Zauważ również: Liczby, które są dla siebie pierwszymi, są również uważane za względnie pierwsze lub wzajemnie pierwsze.

Rɪᴋᴇʀ
źródło
Czy oddzielne ciągi (np. 1\n3\n) Liczą się jako prawidłowe dane wyjściowe?
devRicher
@devRicher, który działa, na pewno.
Rɪᴋᴇʀ
Intuicja, że ​​istnieje nieskończona liczba liczb powyżej n, które są pierwszymi dla n, wydaje mi się słuszna. Istnieje nieskończenie wiele liczb pierwszych, a liczba pierwsza byłaby pierwszymi z każdej liczby poniżej. Dlatego każda liczba pierwsza większa niż n (której jest nieskończenie wiele) również znajduje się na liście coprime.
Brian J
@BrianJ Nie tylko to. Jeśli c i n są pierwszymi cyframi, c + kn i n są również pierwszymi cyframi, dla wszystkich liczb całkowitych k .
Dennis
1
Ciekawostka: są to tak zwane sumy .
Wojowu

Odpowiedzi:

17

Galaretka , 3 bajty

gÐṂ

Wypróbuj online!

Jak to działa?

gÐṂ - (Monadic) Pełny program.

g - Największy wspólny dzielnik.
 ÐṂ - Zachowaj elementy o minimalnej wartości linku (tj. Te z GCD == 1)
       Zauważ, że automatycznie tworzy to zakres [1, wejście] (włącznie).

Dowód ważności

Ponieważ chcemy wyodrębnić tylko koprime, minimalna wartość listy Greatest-Common-Divisors musi wynosić 1, aby lewka ÐṂdziałała. Udowodnijmy, że (dwiema metodami):

  1. Niejawnie wygenerowany zakres zawiera i . Największy wspólny dzielnik jest zawsze ściśle dodatnia, a więc jest gwarantowane miejsce i zawsze będzie wartością minimalną.1 gcd ( 1 , x ) = 1[1,Wejście]1 1gcd(1,x)=1xZ1

  2. Dwie kolejne dodatnie liczby całkowite są zawsze chronione prawem autorskim. Rozważ , gdzie . Następnie bierzemy kolejną dodatnią liczbę całkowitą taką jak i . y = x + 1 k k x k yx,yZy=x+1kkxky

    Oznacza to, że , więc , a więc . Jedyną dodatnią liczbą całkowitą do podzielenia jest sama , więc na pewno pojawi się na liście i zawsze będzie wartością minimalną.k ( x + 1 - x ) k 1 1 1k(y-x)k(x+1-x)k111

Pan Xcoder
źródło
2
Po 9 miesiącach obezwładniłeś Dennisa w jego własnym języku!
Adám
@ Adám Nie jestem pewien, czy ÐṂistniały wtedy, w każdym razie jestem z tego całkiem zadowolony.
Pan Xcoder,
2
Dla przypomnienia DṂistniało, ale działało tylko w przypadku monad. Commit wdrożone Þ, ÐṂ, ÐṀdla dyads jest datowany 9 maja 2017
Dennis
@Dennis Wiedziałem, że istnieje dobry powód, dla którego nie masz wersji 3-bajtowej. Zastanawialiśmy się nad tym również na czacie, więc dziękuję za przydatne informacje!
Pan Xcoder,
56

Python 2 , 61 47 bajtów

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

Wypróbuj online!

tło

Rozważmy pierścień . Chociaż ten pierścień jest zwykle definiowany za pomocą klas reszt modulo , można go również traktować jako zbiór , gdzie operatory dodawania i mnożenia są zdefiniowane przez oraz , gdzie oznacza zwykły dodatek, mnożenie i operatory modulo nad liczbami całkowitymi.n Z n = { 0 , , n - 1 } a + n b = ( a + b )(Zn,+n,n)nZn={0,,n-1}a n b = a bza+nb=(za+b)%n+ ,zanb=zab%n+,, i %

Dwa elementy i z nazywane są wzajemne multiplikatywne odwrotności modulo , jeśli . Zauważ, że za każdym razem, gdy .b Z n n a n b = 1zabZnn1zanb=1%nn > 11%n=1n>1

Ustalić i pozwolić być względnie pierwsze z w . Jeżeli dwa elementy i w mamy że . Oznacza to, że , a my podążamy za tym , tzn. dzieli równomiernie . Ponieważ nie dzieli pierwszych dzielników z , oznacza to, że . Wreszcie, ponieważa n Z n a n x = a n y x y Z n a xn>1zanZnzanx=zanyxyZna ( x - y )zax%n=zay%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 Zza(x-y)%n=zax%n-zay%n=0nza(x-y)nza(x-y)nzanx-y-n<x-y<n , wnioskujemy, że . To pokazuje, że produkty są różnymi elementami . Od ma dokładnie elementów, jedną (i) dokładnie jeden z tych produktów może być równa , to znaczy, jest unikalny w taki sposób, że .x=yzan0,,zan(n-1)ZnZnn1 b a n b = 1Znzanb=1

Z drugiej strony, ustalić i pozwolić być elementem , który nie względnie pierwsze do . W tym przypadku istnieje liczba pierwsza taka że a . Jeśli dopuszczone do Liczba odwrotna modulo (nazwijmy go ), musielibyśmy że , co oznacza, że , a więc , więc . Od podążamy za tyma Z n n p p a p n a n b a n b = 1 a bn>1zaZnnppzapnzanbzanb=1( a b - 1 )zab%n=1n a b - 1 p a p a b p n p a b - 1 p ( a b ) - ( a b - 1 ) = 1 p(zab-1)%n=zab%n-1=0nzab-1pzapzab . Z drugiej strony, ponieważ , podążamy również za tym . W ten sposób , co jest sprzeczne z założeniem, że jest liczbą pierwszą.pnpzab-1p(zab)-(zab-1)=1p

Dowodzi to, że następujące instrukcje są równoważne, gdy .n>1

  • nza i są chronione prawem autorskim.n

  • nzaprzyznaje zwielokrotniony odwrotny modulo .n

  • nzaprzyznaje się wyjątkową Liczba odwrotna modulo .n

Jak to działa

Dla każdej pary liczb całkowitych i w , liczba całkowita jest unikalny; W rzeczywistości, i są iloraz i pozostałą podzielone przez , to znaczy podane , można odzyskać , a , gdzie oznacza całkowitą podział. Na koniec, ponieważ i , jest elementem ; w rzeczywistości .b Z n k : = a n + b a b k n k a = k / n b = kzabZnk: =zan+bzabknkza=k/n/ a n - 1 b n - 1 k Z n 2 k ( n - 1 ) n + ( n - 1 ) = n 2 - 1b=k%n/zan-1bn-1kZn2)k(n-1)n+(n-1)=n2)-1

Jak wspomniano powyżej, jeśli i są koprime, będzie unikalny taki że , tzn. Będzie unikalny taki, że i , tak więc generowany lista zawiera dokładnie raz.n b a bzanbk k / n = a k / n kzab%n=1kk/n=zaak/nk%n=(k/n)(k%n)%n=1za

I odwrotnie, jeśli i nie są kopiami zapasowymi, warunek będzie fałszem dla wszystkich wartości takich, że , więc wygenerowana lista nie będzie zawierać .n k / n kzank a = k / n ak/nk%n=1kza=k/nza

Dowodzi to, że lista się lambda powraca będzie zawierać wszystkie coprimes „s w dokładnie raz.Z nnZn

Dennis
źródło
26
„GCD? Gdzie idziemy, nie potrzebujemy GCD”.
Rɪᴋᴇʀ
1
Łał To wszystko, co chciałem napisać, ale najwyraźniej potrzebowałem 15 znaków. Wciąż Dobra robota.
Eric Lagergren,
24

Galaretka , 4 bajty

gRỊT

Wypróbuj online!

Jak to działa

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
źródło
33
Kodowanie w tym języku zajmuje trochę czasugRỊT
ETHproductions
1
Udało mi się (ab) użyć opcji „Minimalna wartość łącza” ( ÐṂ), aby uzyskać 3 bajty .
Pan Xcoder,
14

Mathematica, 25 bajtów

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

Nieco dziwny format wyjściowy, w którym każdy wynik jest zawinięty na osobnej liście, np {{1}, {3}, {7}, {9}}. Jeśli to nie w porządku, mam dwa rozwiązania o wielkości 30 bajtów:

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

Mathematica faktycznie ma, CoprimeQale to zdecydowanie za długo.

Martin Ender
źródło
1
Co to Qoznacza w CoprimeQ?
Conor O'Brien
2
@ ConorO'Brien „pytanie”. Wszystkie problemu decyzyjnego Zabudowy kończą się jak Q EvenQ, PrimeQlub SubsetQ.
Martin Ender,
10

2sable , 4 bajty

Kod:

ƒN¿–

Wyjaśnienie:

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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

Adnan
źródło
Dobra robota (prawie) pokonanie Dennisa. (kilka minut później).
Zacharý
10

Python, 93 82 74 bajty

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

frekurencyjnie sprawdza, czy istnieją kopie zapasowe, a druga lambda je generuje. Wyświetla listę.

Rɪᴋᴇʀ
źródło
7

Właściwie 8 bajtów

;╗R`╜┤`░

Wypróbuj online!

Wyjaśnienie:

;╗R`╜┤`░
  R`  `░  elements of range(1, n+1) where
;╗  ╜     n and the element
     ┤    are coprime
Mego
źródło
1
Wierzę, że możesz to zrobić, range(1, n)jeśli pozwoli to zaoszczędzić jakieś bajty.
ETHproductions
1
@ETHproductions Nie ma. Dwie opcje to R( range(1, n+1)) i r( range(n)). Ponieważ są one równoważne, wybrałem R(ponieważ przypadkowo uderzyłem Caps Lock podczas pisania kodu).
Mego
Tak, właśnie to wymyśliłem. Nie widziałem instrukcji, która wydawałaby się poświęcona inkrementacji, ale pomyślałem, że i tak może być jedna
ETHproductions
6

JavaScript (ES6), 64 61 bajtów

Zaoszczędzono 3 bajty dzięki @ user81655

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

Testowy fragment kodu

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) }]`);

ETHprodukcje
źródło
Nie można zamieniać a==z a<2?
Rɪᴋᴇʀ
@EasterlyIrk Nie jestem pewien, aw pewnym momencie może być 0. Będę musiał sprawdzić
ETHproductions
Możesz przenieść funkcję GCD do, filteraby usunąć potrzebę otrzymania bparametru:...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
user81655
@ user81655 To świetnie, dziękuję! :-)
ETHproductions
6

Meduza , 19 18 bajtów

p
[#
`B
&~xr1
NnEi

Działa to poprzez obliczenie faktoryzacji pierwotnej każdej liczby w zakresie i sprawdzenie, czy przecina ona liczbę wejściową (Meduza nie ma jeszcze wbudowanej gcd). Ze względów golfowych dane wyjściowe są malejące. Wypróbuj online!

Wyjaśnienie

Po pierwsze, ioceniane jest wejście; dla danych wejściowych 10wartość i-cell wynosi 10.

r1
i

Tutaj r(zakres) jest stosowany do wejścia i 1. Ponieważ dane wejściowe są większe niż 1, zakres jest w kolejności malejącej; dla danych wejściowych 10daje to [9 8 7 6 5 4 3 2 1].

[#
`B
&~x
Nn

Ta część jest jedną dużą funkcją, która jest oceniana w ipowyższym zakresie.

~x
n

Przecięcie ( n) czynników pierwszych ( x).

&~x
Nn

Czy to jest puste ( N)

`
&~x
Nn

Wątek do poziomu 0, testowanie każdego elementu zakresu.

[#
`B
&~x
Nn

Filtruj ( #) zakres w odniesieniu do tej listy wartości logicznych. Funkcja stworzona przez [chce chce użyć argumentu #jako własnego argumentu, więc ustawiamy Bblokowanie #przed otrzymywaniem jakichkolwiek argumentów. W przeciwnym razie wartość ~-cell byłaby użyta jako argument dużej funkcji. Na koniec pdrukuje wynik.

Zgarb
źródło
5

Skumulowane, niekonkurencyjne, 24 21 bajtów

Zaoszczędzono 3 bajty, zainspirowane rubinem Borsunho . ( 1 eqdo 2<)

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

Wypróbuj tutaj!

Jest to n-lambda, która przyjmuje pojedynczy argument i zwraca tablicę.

{!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
źródło
Dlaczego to nie konkuruje?
Zacharý
@ZacharyT głównie keepnie działał ładnie.
Conor O'Brien,
5

CJam , 14 bajtów

{:X{Xmff%:*},}

Wypróbuj online!

Wyjaśnienie

Nie musimy sprawdzać wszystkich możliwych dzielników ai btestować, czy są chronione prawem autorskim. To wystarczy spojrzeć, czy którykolwiek z głównych czynników bpodziałami 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
źródło
5

Mathematica, 26 bajtów

Pick[r=Range@#,r~GCD~#,1]&
alephalpha
źródło
1
Ohhhh, szukałem czegoś takiego jak Pick. Teraz chyba się cieszę, że go nie znalazłem. ;) Ale powinno być bardzo przydatne w przypadku przyszłych wyzwań.
Martin Ender,
4

Brachylog , 16 13 bajtów

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

Jest to funkcja, która przyjmuje N jako dane wejściowe i generuje wszystkie liczby całkowite mniejsze niż i kopiuje do niej.

Wypróbuj online! Jak to często bywa w Brachylog, dodano do niego dodatkowy kod, aby uczynić tę funkcję pełnym programem; Interpreter Brachylog, jeśli otrzyma funkcję zamiast pełnego programu, uruchomi ją, ale nie wydrukuje wyniku, co oznacza, że ​​tak naprawdę nie można obserwować jego działania.

Wyjaśnienie:

Program Brachylog jest łańcuchem ograniczeń; zazwyczaj LHS jednego ograniczenia jest RHS następnego.

>.$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.)

Zanotowałem trzy znaki, zdając sobie sprawę, że nie ma powodu, aby sprawdzać, czy wspólny czynnik (który jest już znany jako czynnik wyjściowy) jest pierwszym czynnikiem wejściowym. Wiemy już, że jest to liczba pierwsza, więc możemy po prostu sprawdzić, czy to czynnik. Jestem mile zaskoczony, że :A*?nie wysyła interpretera do nieskończonej pętli i nie pozwala na wartość całkowitą dla A , ale ponieważ interpreter robi to, co chcę, wezmę to.

Społeczność
źródło
4

Dyalog APL, 10 bajtów .

0~⍨⍳×1=⊢∨⍳

Objaśnienie (wejście 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ý
źródło
3
Uwielbiam sposób, w jaki kod APL wygląda jak twarz, którą tworzysz podczas czytania.
DJMcMayhem
Tak, i niszczy prawie każdy język nie zorientowany na golfa. :).
Zacharý
Dlaczego tylko „może” działać?
Rɪᴋᴇʀ
Po prostu założę, że to działa.
Zacharý
@ZacharyT dlaczego nie możesz tego przetestować? Kiedy wklejam go do try-apl.org, pojawia się błąd z nieprawidłowym tokenem.
Rɪᴋᴇʀ
4

Japt -f , 9 8 5 2 bajty

jN

Spróbuj

  • 2 bajty zaoszczędzone dzięki ETH wskazując fart mózgowy, co doprowadziło do zapisania kolejnego bajtu.
Kudłaty
źródło
Mógłbyś zrobićo f_jU
ETHproductions
Dzięki, @ETHproductions. Nie wiem o czym tutaj myślałem! To musiał być jeden z tych (wielu) momentów, w których zapominam, że jmożna go również użyć do sprawdzenia, czy 2 liczby są pierwszymi.
Kudłaty,
3

Mathematica, 33 bajty

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

Zawiera U + F4A1

JungHwan Min
źródło
Co robią te niedrukowalne?
Rɪᴋᴇʀ
3
@EasterlyIrk wprowadza funkcję bez nazwy z nazwanym argumentem. jest renderowany jako strzałka w Mma.
Martin Ender
@MartinEnder och, spoko.
Rɪᴋᴇʀ
U + F4A1 jest postacią prywatnego użytku. Jak powiedział Martin, w Mathematica jest renderowany jako strzałka.
Zacharý
3

Haskell, 27 bajtów

f n=[k|k<-[1..n],gcd n k<2]

Wypróbuj online!

wada
źródło
3

memy , 11 bajtów niekonkurujących , nieaktualne

Niekonkurencyjne, ponieważ iteracja STDIN jest nowa. Wykorzystuje kodowanie UTF-8.

d`}}]i=1?ip

Wyjaśnienie:

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

}uzyskuje dostęp do następnego elementu wejściowego, ale ostatnie wejście jest zapętlone, gdy jest podane, więc wprowadzanie 6spowoduje jak 6 6 6 6 6 ...w STDIN, umożliwiając odczyt dwóch wyjść z jednego.

devRicher
źródło
Czy właśnie dzisiaj stworzyłeś ten język? Jeśli zostanie wykonany przed wyzwaniem, musi być niekonkurujący.
Rɪᴋᴇʀ
@EasterlyIrk Zostało wykonane 3 dni temu, po prostu ciągle nad nim pracuję. Ponadto zakładam, że masz na myśli po ?
devRicher,
Tak, literówka dzięki. I jest w porządku, o ile funkcje użyte w odpowiedzi są starsze niż wyzwanie.
Rɪᴋᴇʀ
@Elylylyrk Widzę, w takim przypadku będę musiał edytować swoją odpowiedź.
devRicher
Tak, przepraszam. : /
Rɪᴋᴇʀ
2

Ruby, 36 34

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

Trzeba przyznać, że nie jest to bardzo inspirująca odpowiedź.

2 bajty zapisane dzięki Conorowi O'Brienowi.

Borsunho
źródło
Możesz ogolić dwa bajty, usuwając nawiasy wokół(n)
Conor O'Brien
2

Python 3 , 60 bajtów

Importuje gcd zamiast pisać dla niego nową lambda. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

import math
lambda c:[i for i in range(c)if math.gcd(c,i)<2]
Sherlock9
źródło
Nie sądzę, że możesz więcej w golfa. Importowanie gcd bezpośrednio lub matematyki, gdy oba dodają bajty.
Rɪᴋᴇʀ
2

Julia, 30 bajtów

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

Funkcja anonimowa. filterusuwa elementy z listy, które nie są zgodne z prawdą według funkcji.

W tym przypadku funkcją jest x->(gcd(n,x)<2)(prawda, jeśli gcd wejścia i elementu listy jest mniejsza niż 2). Lista jest zakresem 1:n.

Rɪᴋᴇʀ
źródło
2

PARI / GP , 27 bajtów

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

Wykorzystuje to zestaw notacji wprowadzony w wersji 2.6.0 (2013). We wcześniejszych wersjach potrzebne były jeszcze cztery bajty:

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

byłoby potrzebne.

Charles
źródło
Jak to działa?
Rɪᴋᴇʀ
1
@EasterlyIrk Tak samo jak większość tych zgłoszeń - zmień zakres od 1 do n ( [1..n]), sprawdź, czy gcd ma wartość 1 ( gcd(n,k)<2), zwróć liczby z tą właściwością. Jest ->to notacja funkcji / zamknięcia, krótsza o 2 bajty niż normalna składnia funkcji i [...|...<-...,...]jest to notacja zestawu wyjaśniona w odpowiedzi (patrz rozdział 2.3.14 w Instrukcji użytkownika lub wyszukaj <-).
Charles
2

05AB1E , 4 bajty

GN¿–

Wypróbuj online!

Jak to działa

     # implicit input
G    # for N in range(1..input)
 N   # push N
  ¿  # gcd(input, N)
   – # if 1, print N
Neil A.
źródło
1

Pyth , 5 bajtów

x1iLQ

Wypróbuj online!

Jak to działa

Zauważ, że Pyth używa indeksowania 0.

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)
Leaky Nun
źródło