Dado un número n >= 2, genera todos los enteros positivos menos que ndonde gcd(n, k) == 1(con kcualquiera de los números de salida). Los números de este tipo son coprimos entre sí.

Ejemplo: 10da la salida [1, 3, 7, 9](en cualquier forma que desee, siempre y cuando los números estén separados inequívocamente y en algún tipo de lista). La lista no puede tener entradas duplicadas y no tiene que ser ordenada.

Más casos de prueba:

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]

Tampoco estamos contando los números anteriores nque son primos n, solo porque estoy bastante seguro de que hay soluciones infinitas.

También tenga en cuenta: los números que son primos entre sí también se dice que son relativamente primos o mutuamente primos entre sí.

Jalea , 3 bytes

gÐṂ

Pruébalo en línea!

¿Como funciona esto?

gÐṂ - (Monadic) Programa completo.

g - Máximo divisor común.
 ÐṂ - Mantenga los elementos con un valor de enlace mínimo (es decir, aquellos con GCD == 1)
       Tenga en cuenta que esto crea automáticamente el rango [1, entrada] (inclusive).

Prueba de validez

Dado que queremos extraer sólo los coprimes, el valor mínimo de la lista grande-Common-divisores tiene que ser 1 para el ÐṂtruco para el trabajo. Probemos eso (en dos métodos diferentes):

1. $[1, \text{input}]$$1$$\gcd(1, x) = 1\:\:\forall\:\:x \in \mathbb{Z}^{*}$$1$

2. Dos enteros positivos consecutivos son siempre coprimos. Considere , con . Luego tomamos otro entero positivo tal que y . y = x + 1 k k ∣ x k ∣ $x, y \in \mathbb{Z}^{*}$$y = x + 1$$k$$k \mid x$$k \mid y$

   Esto implica que , entonces , por lo tanto . El único entero positivo para dividir es sí mismo, por lo que se garantiza que aparecerá en la lista y siempre será el valor mínimo.k ∣ ( x + 1 - x ) k ∣ 1 1 $k \mid (y - x)$$k \mid (x + 1 - x)$$k \mid 1$$1$$1$

Python 2 , 61 47 bytes

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

Pruébalo en línea!

Antecedentes

Considere el anillo . Si bien este anillo generalmente se define usando las clases de residuos módulo , también se puede considerar como el conjunto , donde los operadores de suma y multiplicación se definen por y , donde , significan la adición habitual, multiplicación y operadores de módulo sobre los enteros.n Z n = { 0 , … , n - 1 } a + n b = ( a + b $(Z_n, +_n, \cdot_n)$$n$$Z_n = \{0, \dots, n - 1\}$a ⋅ n b = a ⋅ $a +_n b = (a + b)\:\%\: n$+ $a \cdot_n b = a \cdot b\:\%\: n$$+,\:\cdot\text{, and } \%$

Dos elementos y de se llaman inversos multiplicativos mutuos módulo si . Tenga en cuenta que siempre que .b Z n n a ⋅ n b = $a$$b$$Z_n$$n$$a \cdot_n b = 1\:\%\:n$n > $1\:\%\:n = 1$$n > 1$

Arregle y deje que sea ​​un coprimo de en . Si para dos elementos e de , tenemos que . Esto implica que , y seguimos que , es decir, divide manera uniforme. Como no comparte divisores primos con , esto significa que . Finalmente porquea n Z n a ⋅ n x = a ⋅ n y x y Z n a ⋅ $n > 1$$a$$n$$Z_n$$a \cdot_n x = a \cdot_n y$$x$$y$$Z_n$a ⋅ ( x - y $a \cdot x\:\%\:n = a \cdot 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 $a \cdot (x - y)\:\%\:n = a \cdot x\:\%\:n - a \cdot y\:\%\:n = 0$$n \mid a \cdot (x - y)$$n$$a \cdot (x - y)$$n$$a$$n \mid x - y$$-n < x - y < n$ , concluimos que . Esto muestra que los productos son todos elementos diferentes de . Como tiene exactamente elementos, uno (y exactamente uno) de esos productos debe ser igual a , es decir, hay una única en tal que .$x = y$$a \cdot_n 0, \dots, a \cdot_n (n - 1)$$Z_n$$Z_n$$n$$1$ $b$ a ⋅ n b = $Z_n$$a \cdot_n b = 1$

Por el contrario, arregle y deje que sea ​​un elemento de que no sea coprimo para . En este caso, hay un primer tal que y . Si admitidos un módulo inverso multiplicativo (llamémoslo ), tendríamos que , lo que significa que y, por lo tanto, , entonces . Desde , seguimos quea Z n n p p ∣ a p ∣ n a n b a ⋅ n b = 1 a ⋅ $n > 1$$a$$Z_n$$n$$p$$p \mid a$$p \mid n$$a$$n$$b$$a \cdot_n b = 1$( a ⋅ b - 1 $a \cdot 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 $(a \cdot b - 1)\:\%\:n = a \cdot b\:\%\:n - 1 = 0$$n \mid a \cdot b - 1$$p \mid a$$p \mid a \cdot b$ . Por otro lado, desde , también seguimos que . De esta manera, , lo que contradice la suposición de que es un número primo.$p \mid n$$p \mid a \cdot b - 1$$p \mid (a \cdot b) - (a \cdot b - 1) = 1$$p$

Esto demuestra que las siguientes afirmaciones son equivalentes cuando .$n > 1$

• $a$ y son primos entre sí.$n$

• $a$ admite un módulo inverso multiplicativo .$n$

• $a$ admite un módulo inverso multiplicativo único .$n$

Cómo funciona

Para cada par de enteros y en , el entero es único; de hecho, y son cociente y el resto de dividido por , es decir, dado , podemos recuperar y , donde denota enteros división. Finalmente, dado que y , es un elemento de ; de hecho, .b Z n k : = a ⋅ n + b a b k n k a = k / n b = $a$$b$$Z_n$$k := a \cdot 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 - $b = k\:\%\: n$$/$$a ≤ n - 1$$b ≤ n - 1$$k$$Z_{n^2}$$k ≤ (n - 1) \cdot n + (n - 1) = n^2 - 1$

Como se ha señalado anteriormente, si y son primos entre sí, no habrá un único de tal manera que , es decir, habrá un único tal que y , por lo que la lista generada contendrá exactamente una vez.n b a ⋅ $a$$n$$b$$a \cdot b\:\%\:n = 1$$k$$k / n = a$$k / n \cdot k\:\%\:n = (k / n) \cdot (k\:\%\:n)\:\%\:n = 1$$a$

A la inversa, si y son no primos entre sí, la condición será falsa para todos los valores de tal que , por lo que la lista generada será no contener .$a$$n$$k / n \cdot k\:\%\:n = 1$$k$$a = k / n$$a$

Esto prueba que la lista que devuelve el lambda contendrá todos los coprimes de en exactamente una vez.Z $n$$Z_n$

Jalea , 4 bytes

gRỊT

Pruébalo en línea!

Cómo funciona

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.

Mathematica, 25 bytes

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

Formato de salida ligeramente extraño, donde cada resultado se envuelve en una lista separada, por ejemplo {{1}, {3}, {7}, {9}}. Si eso no está bien, tengo dos soluciones en 30 bytes:

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

Mathematica realmente tiene CoprimeQpero eso es demasiado tiempo.

2sable , 4 bytes

Código:

ƒN¿–

Explicación:

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

Utiliza la codificación CP-1252 . Pruébalo en línea!

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

fverifica recursivamente los coprimos y la segunda lambda los genera. Emite una lista.

En realidad , 8 bytes

;╗R`╜┤`░

Pruébalo en línea!

Explicación:

;╗R`╜┤`░
  R`  `░  elements of range(1, n+1) where
;╗  ╜     n and the element
     ┤    are coprime

MATL , 7 bytes

:GZd1=f

Pruébalo en línea!

MATLAB / Octave, 22 bytes

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

Pruébalo en línea!

JavaScript (ES6), 64 61 bytes

Guardado 3 bytes gracias a @ user81655

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

Fragmento de prueba

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

Medusa , 19 18 bytes

p
[#
`B
&~xr1
NnEi

Esto funciona calculando la factorización prima de cada número en el rango y verificando si se cruza con la entrada (Jellyfish aún no tiene un mcd incorporado). Por razones de golf, la salida es en orden descendente. Pruébalo en línea!

Explicación

En primer lugar, ise evalúa la entrada; para entrada 10, el valor de la icelda es 10.

r1
i

Aquí r(rango) se aplica a la entrada y 1. Como la entrada es mayor que 1, el rango está en orden descendente; para entrada 10, esto da [9 8 7 6 5 4 3 2 1].

[#
`B
&~x
Nn

Esta parte es una gran función, que se evalúa iy el rango anterior.

~x
n

Intersección ( n) de factores primos ( x).

&~x
Nn

Esta vacio? ( N)

`
&~x
Nn

Subproceso al nivel 0, probando para cada elemento del rango.

[#
`B
&~x
Nn

Filtre ( #) el rango con respecto a esta lista de booleanos. La función producida por [quiere usar el argumento #como su propio argumento, por lo que ponemos un Bbloque para que #no obtenga ningún argumento. De lo contrario, el valor de la ~celda se utilizaría como argumento de la gran función. Finalmente, pimprime el resultado.

Apilado, no competitivo, 24 21 bytes

Guardado 3 bytes, inspirado en el rubí de Borsunho . ( 1 eqa 2<)

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

Pruébalo aquí!

Esta es una n-lambda que toma un solo argumento y produce la matriz.

{!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.

CJam , 14 bytes

{:X{Xmff%:*},}

Pruébalo en línea!

Explicación

No necesitamos verificar todos los divisores posibles ay bprobar si son coprimos. Es suficiente mirar si alguno de los factores primos de la bdivisión 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.
},

Mathematica, 26 bytes

Pick[r=Range@#,r~GCD~#,1]&

Perl 6 , 20 bytes

{grep 2>* gcd$_,^$_}

Brachylog , 16 13 bytes

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

Esta es una función que toma N como entrada y genera todos los enteros menos que y coprimos.

Pruébalo en línea! Como suele ser el caso en Brachylog, se ha agregado un código adicional para convertir la función en un programa completo; El intérprete de Brachylog, si se le da una función en lugar de un programa completo, lo ejecutará pero no imprimirá la salida, lo que significa que realmente no puede observar su funcionamiento.

Explicación:

Un programa Brachylog es una cadena de restricciones; típicamente, el LHS de una restricción es el RHS de la siguiente.

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

Disminuyó tres caracteres al darse cuenta de que no hay razón para verificar si el factor común (que ya se sabe que es un factor primo de la salida) es un factor primo de la entrada. Ya sabemos que es primo, por lo que podemos verificar si es un factor. Estoy gratamente sorprendido aquí que :A*?no envía al intérprete a un bucle infinito y no permite un valor no entero para A , pero como el intérprete hace lo que quiero, lo tomaré.

Dyalog APL, 10 bytes .

0~⍨⍳×1=⊢∨⍳

Explicación (entrada 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.

Japt -f , 9 8 5 2 bytes

jN

Intentalo

• 2 bytes guardados gracias a que ETH señaló un pedo cerebral, lo que llevó a otro byte guardado.

Mathematica, 33 bytes

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

Contiene U + F4A1

Haskell, 27 bytes

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

Pruébalo en línea!

Julia 0.5 , 23 bytes

!n=1÷gcd.(1:n,n)|>find

Pruébalo en línea!

memes , 11 bytes no competitivos , obsoletos

No competitiva ya que la iteración de STDIN es nueva. Utiliza codificación UTF-8.

d`}}]i=1?ip

Explicación:

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

}accede al siguiente elemento de entrada, pero la última entrada se enlaza cuando se proporciona, por lo que la entrada 6dará como resultado 6 6 6 6 6 ...STDIN, lo que hace posible leer dos salidas de una.

05AB1E , 3 bytes

Lʒ¿

Pruébalo en línea!

Tiene nuevas funciones.

Rubí, 36 34

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

Es cierto que esta no es una respuesta muy inspirada .

2 bytes guardados gracias a Conor O'Brien.

Python 3 , 60 bytes

Importa gcd en lugar de escribir una nueva lambda para él. Sugerencias de golf bienvenidas. Pruébalo en línea!

import math
lambda c:[i for i in range(c)if math.gcd(c,i)<2]

Julia, 30 bytes

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

Función anónima. filterelimina elementos de una lista que no son verdaderos según una función.

En este caso, la función es x->(gcd(n,x)<2)(verdadera si el mcd de la entrada y el elemento de la lista es menor que 2). La lista es el rango 1:n.

PARI / GP , 27 bytes

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

Utiliza la notación de conjunto presentada en la versión 2.6.0 (2013). En versiones anteriores, se necesitaban cuatro bytes más:

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

sería necesario.

05AB1E , 4 bytes

GN¿–

Pruébalo en línea!

Cómo funciona

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

C (gcc) , 54 bytes

k;f(n){for(k=0;++k/n<n;k/n*k%n-1||printf("%u ",k/n));}

Este es un puerto de mi respuesta de Python .

Pruébalo en línea!

Pyth , 5 bytes

x1iLQ

Pruébalo en línea!

Cómo funciona

Tenga en cuenta que Pyth usa indexación 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)