Introducción (puede ser ignorado)

Poner todos los números positivos en su orden regular (1, 2, 3, ...) es un poco aburrido, ¿no? Así que aquí hay una serie de desafíos en torno a las permutaciones (reorganizaciones) de todos los números positivos. Este es el cuarto desafío de esta serie (enlaces al primer , segundo y tercer desafío).

En este desafío, exploraremos no solo una permutación de los números naturales, ¡sino un mundo entero de permutaciones!

En 2000, Clark Kimberling planteó un problema en la ^26ª edición de Crux Mathematicorum , una revista científica de matemáticas publicada por la Canadian Mathematical Society. El problema era:

$\text{Sequence }a = \begin{cases} a_1 = 1\\ a_n = \lfloor \frac{a_{n-1}}{2} \rfloor\text{ if }\lfloor \frac{a_{n-1}}{2} \rfloor \notin \{0, a_1, ... , a_{n-1}\}\\ a_n = 3 a_{n-1}\text{ otherwise} \end{cases}$

¿Cada número entero positivo ocurre exactamente una vez en esta secuencia?

En 2004, Mateusz Kwasnicki proporcionó pruebas positivas en la misma revista y en 2008, publicó una prueba más formal y (en comparación con la pregunta original) una prueba más general. Formuló la secuencia con los parámetros $p$ y $q$ :

$\begin{cases} a_1 = 1\\ a_n = \lfloor \frac{a_{n-1}}{q} \rfloor\text{ if }\lfloor \frac{a_{n-1}}{q} \rfloor \notin \{0, a_1, ... , a_{n-1}\}\\ a_n = p a_{n-1}\text{ otherwise} \end{cases}$

Él demostró que para cualquier $p, q>1$ tal que $log_p(q)$ sea ​​irracional, la secuencia es una permutación de los números naturales. Dado que hay un número infinito de valores $p$ y $q$ para los que esto es cierto, este es verdaderamente un mundo entero de permutaciones de los números naturales. Seguiremos con el original $(p, q)=(3, 2)$ , y para estos parámetros, la secuencia se puede encontrar como A050000en la OEIS. Sus primeros 20 elementos son:

1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7, 21, 10, 5, 15

Como se trata de un desafío de "secuencia pura", la tarea es generar $a(n)$ para un $n$ dado como entrada, donde $a(n)$ es A050000 .

Tarea

Dada una entrada entera $n$ , salida $a(n)$ en formato entero, donde:

$\begin{cases} a(1) = 1\\ a(n) = \lfloor \frac{a(n-1)}{2} \rfloor\text{ if }\lfloor \frac{a(n-1)}{2} \rfloor \notin \{0, a_1, ... , a(n-1)\}\\ a(n) = 3 a(n-1)\text{ otherwise} \end{cases}$

Nota: aquí se supone una indexación basada en 1; puede usar indexación basada en 0, entonces $a(0) = 1; a(1) = 3$ , etc. Mencione esto en su respuesta si elige usar esto.

Casos de prueba

Input | Output
---------------
1     |  1
5     |  2
20    |  15
50    |  165
78    |  207
123   |  94
1234  |  3537
3000  |  2245
9999  |  4065
29890 |  149853

Reglas

• La entrada y la salida son enteros (su programa al menos debe admitir entradas y salidas en el rango de 1 hasta 32767)
• La entrada no válida (0, flotantes, cadenas, valores negativos, etc.) puede generar salidas imprevistas, errores o un comportamiento (no) definido.
• Se aplican las reglas de E / S predeterminadas .
• Las lagunas predeterminadas están prohibidas.
• Este es el código de golf , por lo que las respuestas más cortas en bytes ganan

Japt , 15 14 bytes

1 indexado.

@[X*3Xz]kZ Ì}g

Intentalo

@[X*3Xz]kZ Ì}g     :Implicit input of integer U
             g     :Starting with the array [0,1] do the following U times, pushing the result to the array each time
@                  :  Pass the last element X in the array Z through the following function
 [                 :    Build an array containing
  X*3              :      X multiplied by 3
     Xz            :      X floor divided by 2
       ]           :    Close array
        kZ         :    Remove all elements contained in Z
           Ì       :    Get the last element
            }      :  End function
                   :Implicit output of the last element in the array

JavaScript (ES6),  55 51  50 bytes

Guardado 1 byte gracias a @EmbodimentofIgnorance
Guardado 1 byte gracias a @tsh

n=>eval("for(o=[p=2];n--;)o[p=o[q=p>>1]?3*p:q]=p")

Pruébalo en línea!

Jalea , 15 bytes

µ×3żHḞḢḟȯ1Ṫ;µ¡Ḣ

Un programa completo que acepta el número entero n(basado en 1) de STDIN que imprime el resultado.

Pruébalo en línea!

¿Cómo?

µ×3żHḞḢḟȯ1Ṫ;µ¡Ḣ - Main Link: no arguments (implicit left argument = 0)
µ           µ¡  - repeat this monadic chain STDIN times (starting with x=0)
                -                   e.g. x = ...  0      [1,0]            [9,3,1,0]
 ×3             -   multiply by 3                 0      [3,0]            [27,9,3,0]
    H           -   halve                         0      [1.5,0]          [4.5,1.5,0.5,0]
   ż            -   zip together                  [0,0]  [[3,1.5],[0,0]]  [[27,4.5],[9,1.5],[3,0.5],[0,0]]
     Ḟ          -   floor                         [0,0]  [[3,1],[0,0]]    [[27,4],[9,1],[3,0],[0,0]]
      Ḣ         -   head                          0      [3,1]            [27,4]
       ḟ        -   filter discard if in x        []     [3]              [27,4]
        ȯ1      -   logical OR with 1             1      [3]              [27,4]
          Ṫ     -   tail                          1      3                4
           ;    -   concatenate with x            [1,0]  [3,1,0]          [4,9,3,1,0]
              Ḣ - head                            1      3                4
                - implicit print

05AB1E , 16 15 bytes

Guardado 1 byte gracias a Kevin Cruijssen .
0 indexado.

¾ˆ$FDˆx3*‚;ï¯Kн

Pruébalo en línea!

Explicación

Usando n=1como ejemplo

¾ˆ                 # initialize global array as [0]
  $                # initialize stack with 1, input
   F               # input times do:
    Dˆ             # duplicate current item (initially 1) and add one copy to global array
                   # STACK: 1, GLOBAL_ARRAY: [0, 1]
      x            # push Top_of_stack*2
                   # STACK: 1, 2, GLOBAL_ARRAY: [0, 1]
       3*          # multiply by 3
                   # STACK: 1, 6, GLOBAL_ARRAY: [0, 1]
         ‚;ï       # pair and integer divide both by 2
                   # STACK: [0, 3], GLOBAL_ARRAY: [0, 1]
            ¯K     # remove any numbers already in the global array
                   # STACK: [3], GLOBAL_ARRAY: [0, 1]
              н    # and take the head
                   # STACK: 3

Perl 6 , 49 bytes

-2 bytes gracias a nwellnof

{(1,3,{(3*@_[*-1]Xdiv 6,1).max(*∉@_)}...*)[$_]}

Pruébalo en línea!

Devuelve el elemento indexado 0 en la secuencia. Puede cambiar esto a 1 indexado cambiando los elementos iniciales a en 0,1lugar de1,3

Explicación:

{                                             }  # Anonymous code block
 (                                   ...*)[$_]   # Index into the infinite sequence
  1,3                                            # That starts with 1,3
     ,{                             }            # And each element is
       (                 ).max(    )             # The first of
          @_[*-1]X                               # The previous element
        3*        div 6                          # Halved and floored
        3*        div  ,1                        # Or tripled
                               *∉@_             # That hasn't appeared in the sequence yet

J , 47 40 bytes

[:{:0 1(],<.@-:@{:@](e.{[,3*{:@])])^:[~]

Pruébalo en línea!

sin golf

[: {: 0 1 (] , <.@-:@{:@] (e. { [ , 3 * {:@]) ])^:[~ ]

Traducción directa de la definición a J. Se construye de abajo hacia arriba utilizando ^:para iterar desde el valor inicial el número requerido de veces.

Java 10, 120 99 bytes

n->{var L=" 1 0 ";int r=1,t;for(;n-->0;L+=r+" ")if(L.contains(" "+(r=(t=r)/2)+" "))r=t*3;return r;}

Pruébalo en línea.

Explicación:

n->{                              // Method with integer as both parameter and return-type
  var L=" 1 0 ";                  //  Create a String that acts as 'List', starting at [1,0]
  int r=1,                        //  Result-integer, starting at 1
      t;                          //  Temp-integer, uninitialized
  for(;n-->0;                     //  Loop the input amount of times:
      L+=r+" "))                  //    After every iteration: add the result to the 'List'
                          t=r     //   Create a copy of the result in `t`
                       r=(...)/2  //   Then integer-divide the result by 2
    if(L.contains(" "+(...)+" ")) //   If the 'List' contains this result//2:
      r=t*3;                      //    Set the result to `t` multiplied by 3 instead
  return r;}                      //  Return the result

Haskell , 67 65 bytes

(h[1,0]!!)
h l@(a:o)|elem(div a 2)o=a:h(3*a:l)|1>0=a:h(div a 2:l)

Pruébalo en línea!

Utiliza indexación basada en 0.

EDITAR: guardado 2 bytes usando en elemlugar de notElemy cambiando condiciones

Jalea , 21 bytes

Ø.;0ị×3$:2$:2eɗ?Ɗ$⁸¡Ṫ

Pruébalo en línea!

Un enlace monádico que toma un índice cero $n$ como argumento y vuelve $a(n)$.

Ruby , 54 52 48 bytes

->n{*s=0;j=2;n.times{s<<j=s==s-[j/2]?j/2:j*3};j}

Pruébalo en línea!

C ++ (gcc) , 189 180 bytes

-9 bytes a pequeños campos de golf

#import<vector>
#import<algorithm>
int a(int n){std::vector<int>s={1};for(int i=0;i<n;++i)s.push_back(i&&std::find(s.begin(),s.end(),s[i]/2)==s.end()?s[i]/2:3*s[i]);return s[n-1];}

Pruébalo en línea!

Calcula la secuencia hasta n, luego devuelve el elemento deseado. Lento para índices más grandes.

Python 2 , 66 bytes

l=lambda n,p=1,s=[0]:p*(n<len(s))or l(n,3*p*(p/2in s)or p/2,[p]+s)

Pruébalo en línea!

Utiliza indexación basada en cero. El lambda hace poco más que construir recursivamente la secuencia y regresar tan pronto como se alcanza el índice requerido.

Stax , 14 bytes

üÑα↕○Ü1∟¡f↑ô┬♥

Ejecutar y depurarlo

Indexado a cero.

Wolfram Language (Mathematica) , 63 bytes

(L=Last)@Nest[{##,If[FreeQ[#,x=⌊L@#/2⌋],x,3L@#]}&,{0,1},#]&

Pruébalo en línea!

Esto está indexado a 0
(en TIO agregué -1 en cada caso de prueba)

Python 2 , 62 bytes

a=lambda n:n<1or a(n-1)*6**(a(n-1)//2in[0]+map(a,range(n)))//2

Pruébalo en línea!

Devoluciones Truepara a(0). 0 indexado.

Python 3 , 105 103 100 95 83 bytes

-2 bytes gracias a agtoever
-12 bytes gracias a ArBo

def f(n):
 s=0,1
 while len(s)<=n:t=s[-1]//2;s+=(t in s)*3*s[-1]or t,
 return s[-1]

Pruébalo en línea!

Gaia , 22 20 bytes

2…@⟨:):3פḥ⌋,;D)+⟩ₓ)

Pruébalo en línea!

Índice basado en 0.

Gracias a Shaggy por el enfoque.

2…			| push [0 1]
  @⟨		 ⟩ₓ	| do the following n times:
    :):			| dup the list L, take the last element e, and dup that
       3פḥ⌋,		| push [3*e floor(e/2)]
	     ;D		| take the asymmetric set difference [3*e floor(e/2)] - L
	       )+	| take the last element of the difference and add it to the end of L (end of loop)
		   )	| finally, take the last element and output it

;D

Haskell , 55 bytes

(1%[0]!!)
a%o|b<-div a 2=a:last(b:[3*a|elem b o])%(a:o)

Pruébalo en línea!

Método de generación de listas ingeniosas del usuario de golf 1472751 .

Mismo largo:

(1%[0]!!)
a%o=a:[x|x<-[div a 2,a*3],all(/=x)o]!!0%(a:o)

Pruébalo en línea!

Lua , 78 bytes

x,y=1,3 u={}for _=2,...do
u[x]=0
x,y=y,y//2
if u[y]then y=3*x end
end
print(x)

Pruébalo en línea!