Definición
- Dos números enteros son coprimos si no comparten divisores comunes positivos que no sean
1
. a(1) = 1
a(2) = 2
a(n)
es el entero positivo más pequeño que es coprimo para ela(n-1)
ya(n-2)
y aún no ha aparecido, para enteron >= 3
.
Tarea
- Dado entero positivo
n
, salida / impresióna(n)
.
Ejemplo
a(11) = 6
porque6
es coprime con los dos últimos predecesores (a saber,11
y13
) y6
no ha aparecido antes.
Notas
- Tenga en cuenta que la secuencia no es ascendente, lo que significa que un elemento puede ser más pequeño que su predecesor.
Especificaciones
- Usted debe utilizar 1-indexada.
Casos de prueba
n a(n)
1 1
2 2
3 3
4 5
5 4
6 7
7 9
8 8
9 11
10 13
11 6
12 17
13 19
14 10
15 21
16 23
17 16
18 15
19 29
20 14
100 139
1000 1355
10000 13387
100000 133361
Puntuación
- Dado que coprime significa que los dos números comparten solo un divisor (
1
), y1
es un número pequeño, su código debe ser lo más pequeño posible en términos de conteo de bytes.
Referencias
- OEIS A084937
code-golf
sequence
number-theory
Monja permeable
fuente
fuente
Respuestas:
Python 3.5,
160141126124121109 bytesEsta es una implementación simple de la definición de la secuencia. Sugerencias de golf bienvenidas.
Editar: -17 bytes gracias a Leaky Nun. -9 bytes gracias a Peter Taylor. -6 bytes gracias a Sp3000 y cambiando a Python 3.5.
No golfista:
fuente
import math
entoncesg=math.gcd
debe ser más corta que la definición de su propiag
. Porque antes de 3.5, que puede hacerfrom fractions import*
paragcd
.c=3
dentro del bucle, solo necesita hacerlo una vez. Según mi cuenta, ahorras 3 caracteres.r=[c]+r
lugar de+=
, pero tres índices negativos se vuelven positivos. Y luego hay un ahorro adicional de 2 caracteres por la reescritura como lambda, aunque eso es un cambio bastante drástico:from fractions import*;F=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+gcd(r[0]*r[1],c)<2and F(n-1,[c]+r)or F(n,r,c+1)
y no es necesarioprint
porque ya no es un programa completo.MATL ,
2827 bytesEl código es lento, pero da el resultado correcto.
Pruébalo en línea! O verificar los primeros diez casos .
Una pequeña modificación del código produce un gráfico de la secuencia:
Véalo como arte ASCII o con salida gráfica en el compilador fuera de línea:
Explicación
fuente
C, 185 bytes
fuente
En realidad ,
383735333130 bytesEsta es una implementación simple de la definición de la función. Sugerencias de golf bienvenidas. Pruébalo en línea!
Editar: -3 bytes gracias a Leaky Nun.
No golfista:
fuente
Haskell,
8173 bytesEjemplo de uso:
((0:1:c[2,1])!!) 12
->17
.Construya la lista de todos
a(n)
, comenzando0
por arreglar el índice basado en 11
y luegoc[2,1]
.c
toma el encabezado de su lista de argumentosl
seguido de una llamada recursiva con el siguiente número que se ajusta (co-prime, no visto antes) agregado al frentel
. Elija eln
elemento th de esta lista.fuente
R, 141 bytes
sin golf
fuente
Mathematica,
9790 bytesBasado en
mi conjetura quea(n) < 2n
para todosn
.Para obtener una ejecución más rápida, agregue
a@n=
después del original:=
para que la función no necesite volver a calcular los valores anteriores .Guardado 7 bytes gracias a Sherlock9 (si es
gcd(a,b)=1
asígcd(ab,m) = gcd(a,m)*gcd(b,m)
)fuente
ABS(a(n)-n) < n
"n
.Pyth, 23 bytes
Banco de pruebas
Una implementación bastante sencilla, pero con algunos buenos trucos de golf.
fuente