La secuencia de rebote

19

Definamos una secuencia. Diremos que es el número más pequeño, , que tiene las siguientes propiedades:un(norte)X

  • Xn y son co-primos (no comparten factor)norte

  • X no aparece antes en la secuencia

  • El |norte-XEl |>1

A diferencia de la mayoría de las secuencias, el dominio y el rango de nuestra secuencia son los enteros mayores que 1.


Calculemos el primer par de términos.

un(2)a ( 2 ) , debe ser al menos 4 , pero 4 y 2 comparten un factor de 2, por lo que debe ser 5 .a(2)

a(3)a ( 2 ) , debe ser al menos 5 pero 5 es tomado por , por lo que es al menos 6 , pero 6 comparte un factor con 3, por lo que debe ser al menos 7 , 7 cumple los tres requisitos, por lo tanto .a(2)a(3)=7

a(4)

  • 2 comparte un factor
  • 3 demasiado cerca
  • 4 demasiado cerca
  • 5 demasiado cerca
  • 6 comparte un factor
  • 7 Tomado por un (3)
  • 8 comparte un factor
  • 9 es bueno

un(5 5)

  • 2 es bueno

Tarea

En este desafío, debe escribir un programa que tome un número mayor que 1 y devuelva un(norte) .

Esta es una pregunta de , por lo que las respuestas se puntuarán en bytes, con menos bytes mejor.

Casos de prueba

Aquí están los primeros dos términos de la secuencia (Por supuesto, están indexados 2):

5,7,9,2,11,3,13,4,17,6,19,8,23,22,21,10,25,12,27,16,15,14

Dato curioso adicional

Como lo demostró Robert Israel en Math.se ( enlace ), esta secuencia es su propia inversa, lo que significa que un(un(norte))=norte para todo n.

OEIS

Después de hacer esta pregunta, envié esta secuencia al OEIS y, después de unos días, se agregó.

OEIS A290151

Asistente de trigo
fuente
¿Cuántos valores calculaste? (Hablando de la bonificación)
Socratic Phoenix
@SocraticPhoenix Lo he estado haciendo a mano, así que solo los que se muestran en los casos de prueba. Actualmente estoy depurando un programa para verificar valores más grandes.
Wheat Wizard
1
Como yo ... no está funcionando en este momento, sin embargo, mi indexación está desactivada (editar :) y ahora está funcionando ... los primeros 1000 están seguros xD
Socratic Phoenix
¿Conoces un límite superior para una (x)? Por ejemplo, a (x) <u * x para algunos u. Por cierto, los primeros millones de valores son seguros.
nimi
@nimi No sé de un límite superior.
Wheat Wizard

Respuestas:

8

Haskell , 61 bytes

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0

Pruébalo en línea!

Soy bastante nuevo en Haskell, por lo que cualquier consejo de golf es conveniente.

Gracias a Wheat Wizard por 2 bytes y nimi por 4 bytes

Explicación:

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0
f n=                                                          -- define a function f :: Int -> Int
    [i|i<-[2..],                                              -- out of positive integers greater than two
                gcd i n<2,                                    -- gcd of i and n is 1
                          all((/=i).f)[2..n-1],               -- i isn't already in the sequence
                                               abs(n-i)>1]    -- and |n-i| > 1
                                                          !!0 -- take the first element
Mego
fuente
2

Alice , 42 bytes

/oi
\1@/2-&whq&[]w].q-H.t*n$K.qG?*h$KW.!kq

Pruébalo en línea!

Explicación

/oi
\1@/.........

Esta es una plantilla estándar para programas que toman un número como entrada y emiten un número, modificado para colocar un 1 en la pila debajo del número de entrada.

La parte principal del programa coloca cada número ken la ranura a(k)de la cinta. El ciclo interno calcula a (k), y el ciclo externo itera sobre k hasta que se calcula a (n).

1       push 1
i       take input
2-&w    repeat n-1 times (push return address n-2 times)
h       increment current value of k
q&[     return tape to position 0
]       move right to position 1
w       push return address to start inner loop
]       move to next tape position
.q-     subtract tape position from k
H       absolute value
.t*     multiply by this amount minus 1
n$K     if zero (i.e., |k-x| = 0 or 1), return to start of inner loop
.qG     GCD(k, x)
?       current value of tape at position: -1 if x is available, or something positive otherwise
*       multiply
h$K     if not -1, return to start of inner loop
W       pop return address without jumping (end inner loop)
.!      store k at position a(k)
k       end outer loop
q       get tape position, which is a(n)
o       output
@       terminate
Nitrodon
fuente
1

VB.NET (.NET 4.5), 222 bytes

Function A(n)
Dim s=New List(Of Long)
For i=2To n
Dim c=2
While Math.Abs(i-c)<2Or g(c,i)>1Or s.Contains(c)
c+=1
End While
s.Add(c)
Next
Return s.Last
End Function
Function g(a, b)
Return If(b=0,a,g(b,a Mod b))
End Function

Tuve que rodar tu propio GCD. Tampoco pude descubrir cómo hacer que no sea una función completa.

GCD es siempre> = 1, por lo que solo debe ignorar 1

Tomó cortocircuito en el golf porque es más corto

Sin golf

Function Answer(n As Integer) As Integer
    Dim seqeunce As New List(Of Integer)
    For i As Integer = 2 To n
        Dim counter As Integer = 2
        ' took out short-circuiting in the golf because it's shorter
        ' GCD is always >= 1, so only need to ignore 1
        While Math.Abs(i - counter) < 2 OrElse GCD(counter, i) > 1 OrElse seqeunce.Contains(counter)
            counter += 1
        End While
        seqeunce.Add(counter)
    Next
    Return seqeunce.Last
End Function

' roll your own GCD
Function GCD(a, b)
    Return If(b = 0, a, GCD(b, a Mod b))
End Function
Brian J
fuente
Me sorprende que .NET no tenga un GCD integrado fuera de la clase BigInteger.
Mego
1

Mathematica, 111 bytes

(s={};Table[m=2;While[m<3#,If[CoprimeQ[i,m]&&FreeQ[s,m]&&Abs[i-m]>1,s~AppendTo~m;m=3#];m++],{i,2,#}];s[[#-1]])&


Pruébalo en línea! 2..23 (modo rango)

Pruébalo en línea! o 150 (valores distintos)

J42161217
fuente
0

05AB1E , 26 bytes

2IŸεDU°2Ÿ¯KʒX¿}ʒXα1›}θDˆ}θ

norte°T*10norte10norte

Explicación:

2IŸ               # Create a list in the range [2, input]
   ε              # Map each value `y` to:
    DU            #  Store a copy of `y` in variable `X`
    °2Ÿ           #  Create a list in the range [10**`y`,2]
       ¯K         #  Remove all values already in the global_array
       ʒX¿}       #  Only keep values with a greatest common divider of 1 with `X`
       ʒXα1›}     #  Only keep values with an absolute difference larger than 1 with `X`
             θ    #  After these filters: keep the last (the smallest) element
              Dˆ  #  And add a copy of it to the global_array
                # After the map: only leave the last value
                  # (and output the result implicitly)
Kevin Cruijssen
fuente