El entero positivo más pequeño que es coprimo para los dos últimos predecesores y aún no ha aparecido; a (1) = 1, a (2) = 2

10

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 el a(n-1)y a(n-2)y aún no ha aparecido, para entero n >= 3.

Tarea

  • Dado entero positivo n, salida / impresión a(n).

Ejemplo

  • a(11) = 6porque 6es coprime con los dos últimos predecesores (a saber, 11y 13) y 6no 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), y 1es un número pequeño, su código debe ser lo más pequeño posible en términos de conteo de bytes.

Referencias

Monja permeable
fuente
44
Esas "razones" para el código corto ...
Luis Mendo
1
Me pregunto por qué esto fue rechazado. ¿Seguramente no por la horrible justificación?
Conor O'Brien
@Conor No soy yo. En realidad, yo voté. Espero que la gente vea tanto la razón como mi comentario como bromas
Luis Mendo
3
El problema con estas justificaciones "divertidas" para el golf de código es que necesito leer un chiste malo que abarca cuatro líneas solo para descubrir que este es el golf de código estándar. Simplemente está oscureciendo las reglas del desafío sin una buena razón.
Martin Ender
1
@ ConorO'Brien No todos los navegadores siempre muestran el título (y luego está la aplicación móvil), y generalmente describimos la puntuación en la publicación además de usar la etiqueta, porque la etiqueta por sí sola no significa nada para las personas que son nuevas al sitio. Aunque estoy familiarizado con nuestras etiquetas de tipo de desafío, nunca las leí para descubrir cómo se califica un desafío, pero trato de encontrarlo en el cuerpo del desafío. La etiqueta es para categorización, capacidad de búsqueda e información específica de tipo desafío en el wiki de la etiqueta.
Martin Ender

Respuestas:

5

Python 3.5, 160 141 126 124 121 109 bytes

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

import math;f=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+math.gcd(c,r[0]*r[1])<2and f(n-1,[c]+r)or f(n,r,c+1)

No golfista:

import math
def f(n, r=[2,1], c=3):
    if n<2:
        return r[1]
    elif (c in r) + math.gcd(c,r[0]*r[1]) < 2:
        return f(n-1, [c]+r)
    else:
        return f(n, r, c+1)
Sherlock9
fuente
Para Python 3.5 +, import mathentonces g=math.gcddebe ser más corta que la definición de su propia g. Porque antes de 3.5, que puede hacer from fractions import*para gcd.
Sp3000
Si inicializa c=3dentro del bucle, solo necesita hacerlo una vez. Según mi cuenta, ahorras 3 caracteres.
Peter Taylor
También hay un ahorro de 2 caracteres al construir la matriz al revés: debe usar en r=[c]+rlugar 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 necesario printporque ya no es un programa completo.
Peter Taylor
2

MATL , 28 27 bytes

2:i:"`@ym1MTF_)Zdqa+}@h]]G)

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

2:i:"`@ym1MTF_)Zdqa+}@h]]G:)XG

Véalo como arte ASCII o con salida gráfica en el compilador fuera de línea:

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Explicación

2:         % Push [1 2] to initiallize the sequence
i:         % Input n. Push [1 2 ... n]
"          % For loop: repeat n times
  `        %   Do while loop
    @      %     Push iteration index, starting at 1. This is the candidate number
           %     to extend the sequence
    y      %     Duplicate vector containing the sequence so far
    m      %     Is member? Gives true if the candidate is in the sequence
    1M     %     Push candidate and vector again
    TF_)   %     Get last two elements of the vector
    Zd     %     GCD between the candidate and those two elements. Produces a
           %     two-element vector
    qa     %     True if any of the two results exceeds 1, meaning
           %     the candidate is not coprime with the latest two sequence values
    +      %     Add. This corresponds to logical "or" of the two conditions, namely
           %     whether the candidate is member of the sequence so far, and
           %     whether it is not coprime with the latest two. In either case
           %     the do...while must continue with a next iteration, to try a new
           %     candidate. Else the loop is exited, and the current candidate
           %     is the new value of the sequence
  }        %   Finally (execute when the loop is exited)
    @h     %     Push current candidate and concatenate to the sequence vector
  ]        %   End do...while
]          % End for
G)         % Get n-th value of the sequence. Implicitly display
Luis Mendo
fuente
1

C, 185 bytes

G(a,b){return a%b?G(b,a%b):b;}
i,j,k;f(n){int a[n+2];for(i=0;i++<n;){a[i]=i<3?i:0;for(j=2;!a[i];++j){for(k=i;--k;){if(a[k]==j)++j,k=i;}a[G(a[i-1],j)*G(a[i-2],j)<2?i:0]=j;}}return a[n];}
orlp
fuente
1

En realidad , 38 37 35 33 31 30 bytes

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

2R#╗,;`1";2±╜tπg@╜í+Y"£╓╖`nD╜E

No golfista:

2R#╗    Push [1,2] and store it in register 0
,;      Take input and duplicate
`1      Start function, push 1
  "       Start string
  ;       Duplicate i
  2±╜t    Push (list in register 0)[-2:]
  πg      gcd(i, product of list[-2:])
  @╜í     Rotate the gcd and bring up i, check for i in list (0-based, -1 if not found)
  +Y      Add the gcd and the index, negate (1 if coprime and not found in list, else 0)
  "£      End string, turn into a function
╓       Push first (1) values where f(x) is truthy, starting with f(0)
╖`      Append result to the list in register 0, end function
n       Run function (input) times
D╜E     Return (final list)[n-1]
Sherlock9
fuente
1
La manipulación de la pila mucho
Leaky Nun
0

Haskell, 81 73 bytes

c l@(m:n:_)=m:c([x|x<-[1..],gcd(m*n)x<2,all(/=x)l]!!0:l)
((0:1:c[2,1])!!)

Ejemplo de uso: ((0:1:c[2,1])!!) 12-> 17.

Construya la lista de todos a(n), comenzando 0por arreglar el índice basado en 1 1y luego c[2,1]. ctoma el encabezado de su lista de argumentos lseguido de una llamada recursiva con el siguiente número que se ajusta (co-prime, no visto antes) agregado al frente l. Elija el nelemento th de esta lista.

nimi
fuente
0

R, 141 bytes

 f=Vectorize(function(n)ifelse(n>3,{c=3;a=f(n-1);b=f(n-2);d=f(4:n-3);while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)c=c+1;c},n))

sin golf

f=Vectorize( function(n)     #build a recursive function. Vectorize allows
    if(n>3) {                #the function to be called on vectors.
        c=3                  #Tests size. Builds some frequent variables.
        a=f(n-1)
        b=f(n-2)
        d=f(4:n-3)           #Should really golf this out, but its horribly slow.
        while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)
              c=c+1          #If we are coprime and not already seen. add.
        c
     } else n)               #First three are 1,2,3.
usuario5957401
fuente
0

Mathematica, 97 90 bytes

a@1=1;a@2=2;a@n_:=SelectFirst[Range[2n],GCD[a[n-1]a[n-2],#]<2&&!MemberQ[a/@Range[n-1],#]&]

Basado en mi conjetura que a(n) < 2n para todos n.

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)=1así gcd(ab,m) = gcd(a,m)*gcd(b,m))


fuente
No es una conjetura, ya que está escrito en la página OEIS que " ABS(a(n)-n) < n"
Leaky Nun
@LeakyNun Gracias. La página de OEIS estaba inactiva hasta hace unos momentos, y estaba preocupado por un posible contraejemplo en general n.
0

Pyth, 23 bytes

eu+Gf&-TGq1iT*F>2G1tQ]1

Banco de pruebas

Una implementación bastante sencilla, pero con algunos buenos trucos de golf.

eu+Gf&-TGq1iT*F>2G1tQ]1
 u                 tQ]1    Apply the following function input - 1 times,
                           where G is the current state (List of values so far)
  +G                       Add to G
    f             1        The first number, counting up from 1
      -TG                  That has not been seen so far
     &                     And where
               >2G         The most recent two numbers
             *F            Multiplied together
           iT              Gcd with the current number being checked
         q1                Equals 1
e                          Output the final element of the list.
isaacg
fuente