Antecedentes

La secuencia 1-2-3-Tribonacci

Imagine por un segundo que podría hacer una secuencia de Fibonacci reemplazando la fórmula de iteración estándar con lo siguiente:

Básicamente, en lugar de sumar los dos últimos para obtener el siguiente, sumas los últimos tres. Esta es la base de la secuencia 1-2-3-Tribonacci.

Criterio de Brown

El Criterio de Brown establece que puede representar cualquier valor entero como una suma de miembros de una secuencia siempre que:

1. 

2. Para todos los nmayores de 1,

¿Qué significa esto para el desafío?

Puede describir cualquier número entero positivo como una suma de miembros de la secuencia 1-2-3-Tribonacci formada por las siguientes condiciones iniciales:

Esto se conoce como, para cada valor en esta secuencia, la proporción entre términos nunca es mayor que 2 (la proporción promedia aproximadamente 1.839).

Cómo escribir en este sistema de representación numérica

Digamos que usa una representación little-endian. Alinee a los miembros de la secuencia de la siguiente manera:

1  2  3  6 11 20 37 68

Luego, toma su número para representarlo (para nuestras pruebas, digamos que es 63) y encuentra los valores de los 1-2-3-Tribonacci dados que suman 63 (¡usando primero los valores más grandes!) . Si el número es parte de la suma, ponga un 1 debajo, 0 si no.

1  2  3  6 11 20 37 68
0  0  0  1  0  1  1  0

Puede hacer esto para cualquier número entero dado, ¡primero verifique que use los valores más grandes debajo de su entrada dada!

Definición (finalmente)

Escriba un programa o función que haga lo siguiente, dada una entrada entera positiva n(escrita en cualquier base estándar) entre 1 y el valor máximo de su idioma:

1. Convierta el valor en la representación numérica definida de 1-2-3-Tribonacci.
2. Usando esta representación de tipo binario, y léelo como si fuera binario. Esto significa que los dígitos permanecen iguales, pero lo que significan cambia.
3. Tome este número binario y conviértalo en la base del número original.
4. Envía o devuelve este nuevo número.

Sin embargo, mientras la salida sea válida, no necesita seguir estos pasos. Si mágicamente encuentra alguna fórmula que es más corta (y matemáticamente equivalente), siéntase libre de usarla.

Ejemplos

Deje que la función fsea ​​la función descrita por la definición y []represente los pasos tomados (como little-endian, aunque no debería importar) (no es necesario que siga este proceso, este es solo el proceso descrito):

>>> f(1)
[1]
[1]
[1]
1

>>> f(5)
[5]
[0, 1, 1]
[6]
6

>>> f(63)
[63]
[0, 0, 0, 1, 0, 1, 1]
[104]
104

Javascript 117111 bytes

Gracias a @theonlygusti por ayudar al golf con 5 bytes

x=>{r=0;a=[1,2,3];i=1;while(a[++i]<x)a[i+1]=a[i]+a[i-1]+a[i-2];for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}return r}

Cómo funciona

Primero, la función genera todos los números de tribonacci hasta que encuentra uno mayor que la entrada

a=[1,2,3];i=1;for(;a[++i]<x;)a[i+1]=a[i]+a[i-1]+a[i-2];

A continuación, realiza búsquedas inversas en la lista de números. Si un número es menor que la entrada, agrega 2 ^ (índice de ese número) al valor de retorno y reduce la entrada en ese número.

for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}

Finalmente devuelve el resultado.

Pruébalo en línea

Python 2 , 110 102 bytes

-3 bytes gracias a Rod (buen truco para lanzar boolean ia un int +ipara que la repr `+i`funcione)

n=input()
x=[3,2,1]
r=''
while x[0]<n:x=[sum(x[:3])]+x
for v in x:i=n>=v;n-=v*i;r+=`+i`
print int(r,2)

Pruébalo en línea!

JavaScript (ES6), 97 93 bytes

Aquí, estamos usando reduce()una función recursiva. Suponemos que la salida es de 31 bits (que es la mayor cantidad sin signo con la que JS puede trabajar fácilmente para operaciones bit a bit de todos modos).

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

En cuanto al rendimiento, esto claramente no es muy eficiente.

Para los curiosos:

• La relación entre el número de llamadas a F()N + 1reduce() iteraciones vs N iteraciones converge rápidamente hacia la constante de Tribonacci (≈ 1.83929). Por lo tanto, cada bit adicional en la salida cuesta aproximadamente el doble de tiempo que el anterior.
• Con 31 bits, la F()función se llama un buen 124 millones de veces.

Prueba

Nota: Esto puede tardar 1 o 2 segundos en completarse.

let f =

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

console.log(f(63))

Mathematica, 78 74 bytes

Fold[#+##&,#~NumberDecompose~Reverse@LinearRecurrence[{1,1,1},{1,2,3},#]]&

LinearRecurrence[{1,1,1},{1,2,3},#]genera una lista, de longitud igual a la entrada, de los números tribonacci 1-2-3. (El {1,1,1}representa la suma de los tres términos anteriores, mientras que {1,2,3}son los valores iniciales.) Luego #~NumberDecompose~encuentra la forma más codiciosa de escribir la entrada como una suma de elementos de la lista (esta es la misma función que descompondría una cantidad monetaria en múltiplos de las monedas disponibles, por ejemplo). Finalmente, Fold[#+##&,...]convierte la lista binaria resultante en un entero (base-10).

Presentación previa:

Fold[#+##&,#~NumberDecompose~Reverse@Array[If[#<4,#,Tr[#0/@(#-Range@3)]]&,#]]&

Como suele ser el caso (aunque no arriba), esta versión de golf es súper lenta en entradas mayores de 20 o más, porque genera (con recursión no optimizada) una lista de tribus cuya longitud es la entrada; reemplazar la final #por un límite más razonable como Round[2Log@#+1]resultados en un rendimiento mucho mejor.

Haskell, 95 bytes

(a!b)c=a:(b!c)(a+b+c)
e#(r,c)|c-e<0=(2*r,c)|1<2=(2*r+1,c-e)
f n=fst$foldr(#)(0,n)$take n$(1!2)3

Ejemplo de uso: f 63 -> 104. Pruébalo en línea! .

Cómo funciona: !construye la secuencia 1-2-3-Tribonacci. Dado 1, 2y 3como los parámetros de inicio, tomamos los primeros nelementos de la secuencia. Luego veces a partir de la función de la derecha #, que resta el siguiente elemento ede ny establece el bit en el valor de retorno rsi ese necesita o deja que el desarmado bits. Establecer el bit es duplicar ry agregar 1, dejar que se desactive es simplemente duplicar.

Jalea , 31 bytes

S=³
3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ

Pruébalo en línea!

Estoy casi seguro de que hay una manera MUCHO más corta de lograr esto en Jelly.

¿Cómo?

S=³ - Link 1, compare sum to input: list
S   - sum
  ³ - 3rd command line argument which is 1st program argument.
 =  - equal?

3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ - Main link: n
3RU                         - range(3) upended -> [3,2,1]
   µ    µ   µ¿              - while
         <³                 - less than input (vectorises)
           Ạ                - all?
    ḣ3S;                    -     head(3), sum, and concatenate
                                  [3,2,1] -> [6,3,2,1] -> [11,6,3,2,1] -> ...
              µ             - monadic chain separation, call the result x
               ŒP           - power set of x - e.g. for [6,3,2,1] -> [[],[6],[3],[2],[1],[6,3],[6,2],[6,1],[3,2],[3,1],[2,1],[6,3,2],[6,3,1],[6,2,1],[3,2,1],[6,3,2,1]]
                  Ðf        - filter keep
                 Ç          -     last link (1) as a monad (those that sum to the input)
                    Ṁ       - maximum (e.g. an input of 63 would yield [[37,20,6],[37,20,3,2,1]], the maximum of which is [37,20,6], the one with the largest numbers used)
                         µ  - monadic chain separation (to have x as the right argument below)
                     e@Ѐ   - exists in with reversed arguments mapped over x (e.g. [37,20,6] with x = [68,37,20,11,6,3,2,1] yields [0,1,1,0,1,0,0,0])
                          Ḅ - convert from binary to integer.        

Perl 6 , 93 91 bytes

-2 bytes gracias a b2gills

{my@f=1,2,3,*+*+*...*>$^n;sum @f».&{$_~~any first *.sum==$n,@f.combinations}Z*(2 X**^∞)}

Cómo funciona

• Primero, genera la secuencia 1-2-3-Tribonacci hasta el primer elemento más grande que la entrada:

  my @f = 1, 2, 3, *+*+* ... * > $^n;

• En base a eso, encuentra el subconjunto de la secuencia que se suma a la entrada:

  first *.sum==$n, @f.combinations

• Basado en eso, construye una lista de booleanos que especifica si cada elemento de la secuencia es parte de la suma:

  @f».&{$_~~any ...}

• Y finalmente interpreta esa lista de valores True = 1, False = 0 como base 2 y la devuelve como un número (base 10):

  sum ... Z* (2 X** ^∞)

JavaScript (ES6), 61 60 bytes

n=>(g=(x,y,z)=>(n>x&&g(y,z,x+y+z)*2)+!(n<x||![n-=x]))(1,2,3)

Calcula los números 1-2-3-Tribonacci hasta que alcanza el número original, luego, a medida que la recursión se desenrolla, trata de restar cada uno por turno, duplicando el resultado a medida que avanza.

Editar: guardado 1 byte gracias a @Arnauld.

Lote, 151 148 145 bytes

@set/ar=0,n=%1
@call:c 3 2 1
@echo %r%
@exit/b
:c
@set/as=%1+%2+%3
@if %n% gtr %3 call:c %s% %*
@set/ar*=2
@if %n% geq %3 set/an-=%3,r+=1

Puerto de mi respuesta de JavaScript. Editar: guardé 3 bytes al pasar mis argumentos de subrutina en orden inverso y otros 3 bytes al usar @s individuales en cada línea en lugar de @echo off.

Jalea , 19 18 17 bytes

Ḣx3+
BÇL¡2ị
²Ç€»ċ

Pruébalo en línea!

Antecedentes

En lugar de intentar convertir un número entero a 1,2,3-Tribonacci base, luego de binario a entero, haremos lo contrario: convertir enteros a binario, luego de 1,2,3-Trionacci base a entero, y regresar el más alto que coincide con la entrada. Esto se logra fácilmente.

Ejemplificaremos el proceso para la entrada 63 , en particular el paso donde se prueba 104 . En binario, del dígito más significativo al menos significativo, 104 es igual a

 1  1  0  1  0  0  0
37 20 11  6  3  2  1

donde la segunda fila representa los valores posicionales de esos dígitos.

Podemos extender la secuencia 1,2,3-Tribonacci a la derecha, observando que los dígitos agregados cumplen con la misma fórmula recursiva. Para tres dígitos más, esto da

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

Ahora, para calcular el valor del número base 1,2,3-Tribonacci, podemos hacer uso de la fórmula recursiva. Dado que cada número es la suma de los tres números a su derecha (en la tabla anterior), podemos eliminar el primer dígito y agregarlo a los primeros tres dígitos de la matriz restante. Después de 7 pasos, que es igual al número de dígitos binarios de 104 , rara vez nos quedamos con solo tres dígitos.

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

    2  1  2  0  0  0  0  0  0
   20 11  6  3  2  1  0  1  0

       3  4  2  0  0  0  0  0
      11  6  3  2  1  0  1  0

          7  5  3  0  0  0  0
          6  3  2  1  0  1  0

            12 10  7  0  0  0
             3  2  1  0  1  0

               22 19 12  0  0
                2  1  0  1  0

                  41 34 22  0
                   1  0  1  0

                     75 63 41
                      0  1  0

Ahora, dado que el primer y el último dígito restante tienen valor posicional 0 , el resultado es el dígito del medio, es decir, 63 .

Cómo funciona

²Ç€»ċ   Main link. Argument: n

²       Yield n². Since 1.839² = 3.381921 > 2, the range [1, ..., n²] will contain
        the answer. Better bounds, at the cost of additional bytes are possible.
 Ç€     Map the the second helper link over [1, ..., n²].
   »    Take the maximum of n and each result.
    ċ   Count the occurrences of n.


BÇL¡2ị  Second helper link. Left argument: k. Right argument: n

B       Convert k to binary. Let's call the result A.
  L     Length; count the number of binary digits. Let's call the result l.
 Ç ¡    Apply the first helper link l times to A.
    2ị  Retrieve the second element.


Ḣ×3+    First helper link. Argument: A (array)

Ḣ       Head; pop and yield the first element of A.
 x3     Repeat it thrice.
   +    Add the result, component by component, to the beheaded A.

Gelatina ( tenedor ), 17 16 bytes

ḣ3S;µ¡
3RṚdzæFṪḄ

Ahorré 1 byte gracias a @Dennis que lo jugó sin siquiera ejecutarlo.

Esto se basa en una bifurcación de Jelly donde estoy decepcionantemente trabajando en la implementación de un átomo de solución de Frobenius eficiente. Para aquellos que estén interesados, me gustaría hacer coincidir la velocidad de Mathematica FrobeniusSolvey afortunadamente hay una explicación de su método en el documento "Haciendo el cambio y encontrando repfigits: equilibrando una mochila" de Daniel Lichtblau.

Explicación

ḣ3S;µ¡  Helper link. Input: a list
    µ   Create monadic chain
ḣ3        Take the first 3 items
  S       Sum
   ;      Prepend to the list
     ¡  Repeat it n (initial argument from main) times

3RṚdzæFṪḄ  Main link. Input: integer n
3          The constant 3
 R         Range. Makes [1, 2, 3]
  Ṛ        Reverse. Makes [3, 2, 1]
   Ç       Call the helper link on that list.
           Generates the first (n+3) 123-Tribonacci values in reverse
    ³      Get n
     æF    Frobenius solve for n using the first n 123-Tribonacci values in reverse
       Ṫ   Tail. Take the last value. The results of Frobenius solve are ordered
           where the last result uses the least
        Ḅ  Unbinary. Convert digits from base 2 to base 10

dc , 110 102 bytes

?se1sa2sb3sc_1sf[laddSdlbdsalcdsb++sclf1+sfle>y]dsyx0sk[lk2lf^+skler-se]sr[Lddle!<rlf1-dsf0!>z]dszxlkp

Pues bien, parece que las grandes mentes no piensan igual. Aparentemente, el algoritmo que se me ocurrió para sortear las limitaciones dces el mismo que se usó en la respuesta de @ LliwTelrac. Interesante.

Pruébalo en línea!

Python 2 , 93 bytes

n=input();y=k=n*n
while y>n:
 x=y=z=0;k-=1
 for t in bin(k):x+=t=='1';x,y,z=y+x,z+x,x
print k

Este es un puerto de mi respuesta Jelly .

Pruébalo en línea!

bash + utilidades BSD (OS X, etc.), 53 bytes

jot $[2#$1**4]|egrep -v '[2-9]|11(1|$)'|sed $[2#$1]!d

bash + utilidades GNU (también funciona bajo BSD), 59 bytes

seq -f2o%.fp $[2#$1**2]|dc|egrep -v '11(1|$)'|sed $[2#$1]!d

La entrada y la salida en los dos anteriores están en binario.

Pruebe la versión de GNU en TIO. (El ejemplo vinculado a muestra la entrada de 111111, que es 63 en binario, y la salida de 1101000, que es 104 en binario).

No creo que TIO ofrezca una opción de BSD, pero si tiene una Mac disponible, puede probar ambas. (El programa de 59 bytes es mucho más rápido que el programa de 53 bytes).

Desafortunadamente, seqno se puede colocar simplemente en la solución BSD en lugar de jot, ya que el formato de salidaseq es diferente para salidas superiores a 999999. (Esto comienza a ser un problema para las entradas alrededor de 32, ya que 32 ^ 4> 1000000).

Puede reemplazar el jotanterior con seq -f%.fpara que esto funcione con las utilidades GNU, pero para los mismos 59 bytes, puede usar la solución GNU anterior, que es mucho más rápida.