Coprimes hasta N

51

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

Rɪᴋᴇʀ
fuente
¿Las cadenas separadas (p 1\n3\n. Ej. ) Cuentan como salida válida?
devRicher
@devRicher que funciona, claro.
Rɪᴋᴇʀ
La intuición acerca de que hay un número infinito de números por encima de n que son coprimos para n me parece correcta. Hay infinitos números primos, y un número primo sería coprimo con cada número debajo de él. Por lo tanto, cada primo mayor que n (de los cuales hay infinitos) también forman parte de la lista de números coprimos.
Brian J
@BrianJ No solo eso. Si c y n son coprimos, c + kn y n también son coprimos, para todos los enteros k .
Dennis
1
Dato curioso : estos se llaman totativos .
Wojowu

Respuestas:

17

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

  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 yx,yZy=x+1kkxky

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

Sr. Xcoder
fuente
2
¡Superaste a Dennis en su propio idioma después de 9 meses!
Adám
@ Adám No estoy seguro de si ÐṂexistía en ese entonces, de todos modos estoy bastante satisfecho con este.
Sr. Xcoder
2
Para el registro, DṂexistía, pero solo funcionó para las mónadas. La confirmación implementado Þ, ÐṂ, ÐṀpara diadas con fecha 9 de mayo de 2017.
Dennis
@ Dennis Sabía que habría una buena razón por la que no tenías la versión de 3 bytes. También nos preguntamos sobre eso en el chat, así que gracias por la información útil.
Sr. Xcoder
56

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 )(Zn,+n,n)nZn={0,,n1}a n b = a ba+nb=(a+b)%n+ ,anb=ab%n+,, 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 = 1abZnn1anb=1%nn > 11%n=1n>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 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 , 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=yan0,,an(n1)ZnZnn1 b a n b = 1Znanb=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 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 . Por otro lado, desde , también seguimos que . De esta manera, , lo que contradice la suposición de que es un número primo.pnpab1p(ab)(ab1)=1p

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

  • na y son primos entre sí.n

  • na admite un módulo inverso multiplicativo .n

  • na 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 = 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

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

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

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

Dennis
fuente
26
"¿GCD? A dónde vamos, no necesitamos GCD".
Rɪᴋᴇʀ
1
Woah Eso es todo lo que quería escribir, pero aparentemente necesitaba 15 caracteres. Aún así, woah. Gran trabajo.
Eric Lagergren
24

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.
Dennis
fuente
33
La codificación en este idioma requiere algo de tiempogRỊT
ETHproductions
1
Logré (ab) usar el "Valor mínimo de enlace" quick ( ÐṂ) para obtener 3 bytes .
Sr. Xcoder
14

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.

Martin Ender
fuente
1
¿Qué Qsignifica en CoprimeQ?
Conor O'Brien
2
@ ConorO'Brien "pregunta", supongo. Todos los problemas de decisión incorporados terminan en Q como EvenQ, PrimeQo SubsetQ.
Martin Ender
10

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!

Adnan
fuente
Buen trabajo (casi) superando a Dennis. (aunque unos minutos tarde).
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)]

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

Rɪᴋᴇʀ
fuente
7

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
Mego
fuente
1
Creo que puedes hacerlo range(1, n)si eso ahorra bytes.
ETHproductions
1
@ETHproductions No lo hace. Las dos opciones son R( range(1, n+1)) y r( range(n)). Como son equivalentes, elegí R(ya que accidentalmente presioné el bloqueo de mayúsculas mientras escribía el código).
Mego
Sí, eso es lo que pensé. No vi una instrucción que pareciera dedicada a aumentar, pero pensé que podría haber una de todos modos
ETHproductions,
6

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

ETHproducciones
fuente
¿No puedes intercambiar a==con a<2?
Rɪᴋᴇʀ
@EasterlyIrk No estoy seguro, apodría ser 0 en algún momento. Tendré que verificar
ETHproductions
Puede mover la función GCD filterpara eliminar la necesidad de recibir un bparámetro:...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
user81655
@ user81655 Eso es genial, ¡gracias! :-)
ETHproductions
6

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.

Zgarb
fuente
5

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.
Conor O'Brien
fuente
¿Por qué esto no es competitivo?
Zacharý
@ZacharyT principalmente, keepno estaba funcionando bien.
Conor O'Brien
5

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.
},
Martin Ender
fuente
5

Mathematica, 26 bytes

Pick[r=Range@#,r~GCD~#,1]&
alephalpha
fuente
1
Ohhhh, he estado buscando algo como Pick. Supongo que ahora me alegro de no haberlo encontrado. ;) Pero debería ser muy útil para futuros desafíos.
Martin Ender
4

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

Comunidad
fuente
4

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.
Zacharý
fuente
3
Me encanta la forma en que el código APL se parece a la cara que haces cuando lo lees.
DJMcMayhem
Sí, y demuele casi todos los lenguajes no orientados al código golf. :).
Zacharý
¿Por qué solo funciona el "poder"?
Rɪᴋᴇʀ
Solo voy a asumir que funciona.
Zacharý
@ZacharyT ¿por qué no puedes probarlo? Cuando lo pego en try-apl.org, se produce un error con un token no válido.
Rɪᴋᴇʀ
4

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.
Lanudo
fuente
Podrías hacerloo f_jU
ETHproductions
Gracias, @ETHproductions. ¡No sé lo que estaba pensando aquí! Debe haber sido uno de esos (muchos) momentos en los que olvido jque también se puede usar para probar si 2 números son primos.
Shaggy
3

Mathematica, 33 bytes

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

Contiene U + F4A1

JungHwan Min
fuente
¿Qué hace el no imprimible?
Rɪᴋᴇʀ
3
@EasterlyIrk presenta una función sin nombre con un argumento con nombre. se representa como una flecha en Mma.
Martin Ender
@ MartinEnder oh, genial.
Rɪᴋᴇʀ
U + F4A1 es un personaje de uso privado. Como dijo Martin, se representa como una flecha en Mathematica.
Zacharý
3

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.

devRicher
fuente
¿Acabas de crear este lang hoy? Si se hace antes del desafío, tiene que ser no competitivo.
Rɪᴋᴇʀ
@EasterlyIrk Se hizo hace 3 días, estoy constantemente trabajando en ello. Además, supongo que te refieres después ?
devRicher
Sí, error tipográfico gracias. Y está bien, siempre y cuando las características utilizadas en la respuesta y anteriores al desafío.
Rɪᴋᴇʀ
@EasterlyIrk Ya veo, en ese caso tendré que editar mi respuesta.
devRicher
Si lo siento : /
Rɪᴋᴇʀ
2

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.

Borsunho
fuente
Puede recortar dos bytes eliminando paréntesis(n)
Conor O'Brien
2

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]
Sherlock9
fuente
No creo que puedas jugar más al golf. Importar gcd directamente o matemáticas como m agrega bytes.
Rɪᴋᴇʀ
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.

Rɪᴋᴇʀ
fuente
2

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.

Charles
fuente
¿Como funciona esto?
Rɪᴋᴇʀ
1
@EasterlyIrk Lo mismo que la mayoría de estas presentaciones: haga un rango de 1 a n ( [1..n]), verifique si gcd es 1 ( gcd(n,k)<2), devuelva los números con esta propiedad. Esta ->es la notación de función / cierre, más corta en 2 bytes que la sintaxis de función normal y [...|...<-...,...]es la notación establecida explicada en la respuesta (consulte la sección 2.3.14 en el Manual del usuario, o busque <-).
Charles
2

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
Neil A.
fuente
1

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)
Monja permeable
fuente