fundo

A sequência 1-2-3-Tribonacci

Imagine por um segundo que você poderia criar uma sequência de fibonacci substituindo a fórmula de iteração padrão pela seguinte:

Basicamente, em vez de somar os dois últimos para obter o próximo, você soma os três últimos. Esta é a base para a sequência 1-2-3-Tribonacci.

Critério de Brown

O critério de Brown declara que você pode representar qualquer valor inteiro como uma soma dos membros de uma sequência, desde que:

1. 

2. Para todos nmaiores que 1,

O que isso significa para o desafio

Você pode descrever qualquer número inteiro positivo como uma soma dos membros da sequência 1-2-3-Tribonacci formada pelas seguintes condições iniciais:

Isso é conhecido como, para todos os valores nessa sequência, a proporção entre os termos nunca é maior que 2 (a média fica em torno de 1,839).

Como escrever neste sistema de representação numérica

Digamos que você use uma representação little-endian. Alinhe os membros da sequência da seguinte maneira:

1  2  3  6 11 20 37 68

Então, você pega seu número para ser representado (para nossos testes, digamos que seja 63) e encontra os valores dos 1-2-3-Tribonacci fornecidos, que somam 63 (usando os maiores valores primeiro!) . Se o número fizer parte da soma, coloque 1 abaixo, 0 se não.

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

Você pode fazer isso para qualquer número inteiro - basta verificar se você usa primeiro os maiores valores abaixo de sua entrada!

Definição (finalmente)

Escreva um programa ou função que faça o seguinte, com alguma entrada inteira positiva n(escrita em qualquer base padrão) entre 1 e o valor máximo do seu idioma:

1. Converta o valor na representação numérica do 1-2-3-Tribonacci definida.
2. Usando essa representação binária, e leia-a como se fosse binária. Isso significa que os dígitos permanecem os mesmos, mas o que eles significam muda.
3. Pegue esse número binário e converta-o na base do número original.
4. Envie ou retorne esse novo número.

No entanto, enquanto a saída for válida, você não precisará seguir estas etapas. Se você encontrar magicamente uma fórmula mais curta (e matematicamente equivalente), fique à vontade para usá-la.

Exemplos

Deixe a função fser a função descrita pela definição e []represente as etapas executadas (como little-endian, embora não deva importar) (você não precisa seguir esse processo, este é apenas o processo 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 117 111 bytes

Obrigado a @theonlygusti por ajudar no golfe com 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}

Como funciona

Primeiro, a função gera todos os números de tribonacci até encontrar um maior que a entrada

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

Em seguida, ele pesquisa inversamente a lista de números. Se um número for menor que a entrada, ele adiciona 2 ^ (índice desse número) ao valor de retorno e reduz a entrada por esse número.

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

Finalmente, ele retorna o resultado.

Experimente Online

Python 2 , 110 102 bytes

-3 bytes graças a Rod (truque interessante para converter booleano ipara um int com, +ipara que o 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)

Experimente online!

JavaScript (ES6), 97 93 bytes

Aqui, estamos usando reduce()uma função recursiva. Assumimos que a saída seja de 31 bits (que é a maior quantidade não assinada com a qual JS pode trabalhar facilmente para operações bit a bit).

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)

Em termos de desempenho, isso claramente não é muito eficiente.

Para os curiosos:

• A proporção entre o número de chamadas para iterações F()N + 1 reduce()e N iterações converge rapidamente para a Constante de Tribonacci (≈ 1.83929). Portanto, cada bit adicional na saída custa aproximadamente o dobro do tempo que o anterior.
• Com 31 bits, a F()função é chamada bons 124 milhões de vezes.

Teste

Nota: pode demorar 1 ou 2 segundos para concluir.

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},#]gera uma lista, de comprimento igual à entrada, dos números 1-2-3 tribonacci. (O {1,1,1}representa a soma dos três termos anteriores, enquanto {1,2,3}os valores iniciais.) Em seguida, #~NumberDecompose~encontra a maneira mais ambiciosa de escrever a entrada como uma soma dos elementos da lista (esta é a mesma função que decomporia um valor monetário em múltiplos de as moedas disponíveis, por exemplo). Por fim, Fold[#+##&,...]converte a lista binária resultante em um número inteiro (base 10).

Submissão anterior:

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

Como costuma ser o caso (embora não acima), essa versão golfista é super lenta em entradas maiores que 20 ou mais, porque gera (com recursão não otimizada) uma lista de tribos cujo comprimento é a entrada; a substituição da final #por um limite mais razoável Round[2Log@#+1]resulta em desempenho muito melhor.

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

Exemplo de uso: f 63-> 104. Experimente online! .

Como funciona: !cria a sequência 1-2-3-Tribonacci. Dado 1, 2e 3como parâmetros de início, pegamos os primeiros nelementos da sequência. Em seguida, dobre a partir da função direita #que subtrai o próximo elemento ede ne define o bit no valor de retorno rse eé necessário ou permite que o unset bit. Definir o bit está dobrando re adicionando 1, deixando-o desabilitado está apenas dobrando.

Gelatina , 31 bytes

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

Experimente online!

Estou quase certo de que há uma maneira MUITO mais curta de conseguir isso em Jelly.

Quão?

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 graças a b2gills

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

Como funciona

• Primeiro, ele gera a sequência 1-2-3-Tribonacci até o primeiro elemento maior que a entrada:

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

• Com base nisso, ele encontra o subconjunto da sequência que se soma à entrada:

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

• Com base nisso, constrói uma lista de booleanos especificando se cada elemento da sequência faz parte da soma:

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

• E, finalmente, interpreta essa lista de valores True = 1, False = 0 como base 2 e a retorna como um 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 os números 1-2-3-Tribonacci até atingir o número original e, à medida que a recursão se desenrola, tenta subtrair cada um por sua vez, duplicando o resultado à medida que avança.

Editar: salvou 1 byte graças 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

Porta da minha resposta JavaScript. Editar: salvei 3 bytes passando meus argumentos de sub-rotina em ordem inversa e outros 3 bytes usando @s individuais em cada linha em vez de @echo off.

Geléia , 19 18 17 bytes

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

Experimente online!

fundo

Em vez de tentar converter um número inteiro em 1,2,3-Tribonacci base, depois de binário em número inteiro, faremos o oposto: converter números inteiros em binário, depois de 1,2,3-Trionacci base em número inteiro e retornar o mais alto que corresponde à entrada. Isso é facilmente realizado.

Vamos exemplificar o processo para a entrada 63 , em particular a etapa em que 104 é testado. Em binário, do dígito mais significativo ao menos significativo, 104 é igual a

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

onde a segunda linha representa os valores posicionais desses dígitos.

Podemos estender a sequência 1,2,3-Tribonacci para a direita, observando que os dígitos adicionados cumprem a mesma fórmula recursiva. Por três dígitos, isso dá

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

Agora, para calcular o valor do número 1,2,3-Tribonacci base, podemos usar a fórmula recursiva. Como cada número é a soma dos três números à direita (na tabela acima), podemos remover o primeiro dígito e adicioná-lo aos três primeiros dígitos da matriz restante. Após 7 etapas, que é igual ao número de dígitos binários de 104 , é raro ficar com apenas três 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

Agora, como o primeiro e o último dígito restante possuem valor posicional 0 , o resultado é o dígito do meio, ou seja, 63 .

Como 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 ( garfo ), 17 16 bytes

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

Economizei 1 byte graças a @Dennis, que jogou golfe sem nem mesmo executá-lo.

Isso se baseia em um garfo de geléia, onde ainda estou trabalhando decepcionantemente na implementação de um eficiente átomo de resolução Frobenius. Para aqueles que estão interessados, gostaria de igualar a velocidade do Mathematica FrobeniusSolvee, felizmente, há uma explicação de suas método no artigo "Fazendo mudanças e encontrando repetições: equilibrando uma mochila", de Daniel Lichtblau.

Explicação

ḣ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

Bem, parece que grandes mentes que pensam da mesma forma. Aparentemente, o algoritmo que criei para contornar as limitações dedc inventei é coincidentemente o mesmo usado na resposta do @LliwTelrac. Interessante.

Experimente online!

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

Esta é uma porta da minha resposta Jelly .

Experimente online!

utilitários bash + BSD (OS X, etc.), 53 bytes

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

utilitários bash + GNU (funciona também com BSD), 59 bytes

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

Entrada e saída em ambos os itens acima estão em binário.

Experimente a versão GNU no TIO. (O exemplo vinculado a demonstra a entrada de 111111, que é 63 em binário, e a saída de 1101000, que é 104 em binário.)

Não acho que o TIO ofereça uma opção BSD, mas se você tiver um Mac disponível, poderá experimentá-los por aí. (O programa de 59 bytes é muito mais rápido que o programa de 53 bytes.)

Infelizmente, seqnão pode simplesmente ser descartado na solução BSD no lugar dejot , pois o formato de saída para seqé diferente para saídas acima de 999999. (Isso começa a ser um problema para entradas em torno de 32, desde 32 ^ 4> 1000000.)

Você pode substituir jotacima por seq -f%.fpara que isso funcione com os utilitários GNU, mas pelos mesmos 59 bytes, você pode usar a solução GNU acima, que é muito mais rápida.