O teorema de Zeckendorf mostra que todo número inteiro positivo pode ser representado exclusivamente como uma soma de números de Fibonacci não adjacentes. Neste desafio, você deve calcular a soma de dois números na representação de Zeckendorf.

Seja F _n o n- ésimo número de Fibonacci onde

F ₁ = 1,
F ₂ = 2 e
para todos k > 2, F _k = F _{k - 1} + F _{k - 2} .

A representação Zeckendorf Z ( n ) de um número inteiro não negativo n é um conjunto de números inteiros positivos, de modo que

n = Σ _{i ∈ Z ( n )} F _i   e
∀ _{i ∈ Z ( n )} i + 1 ∉ Z ( n ).

(em prosa: a representação de Zeckendorf de um número n é um conjunto de números inteiros positivos, de modo que os números de Fibonacci para esses índices somam n e nenhum número inteiro adjacente faça parte desse conjunto)

Notavelmente, a representação de Zeckendorf é única. Aqui estão alguns exemplos para representações de Zeckendorf:

Z (0) = ∅ (o conjunto vazio)
Z (1) = {1}
Z (2) = {2}
Z (3) = {3} ({1, 2} não é a representação de Zeckendorf de 3)
Z (10) = {5, 2}
Z (100) = {3, 5, 10}

Nesse desafio, as representações de Zeckendorf são codificadas como conjuntos de bits, onde o bit menos significativo representa se 1faz parte do conjunto, etc. Você pode assumir que as representações de entrada e saída de Zeckendorf se encaixam em 31 bits.

Sua tarefa é calcular Z ( n + m ) dados Z ( n ) e Z ( m ). A solução com o menor comprimento em octetos vence.

Você pode encontrar uma implementação de referência escrita em ANSI C aqui . Também pode ser usado para gerar representações do Zeckendorf ou calcular um número a partir da representação do Zeckendorf.

Aqui estão alguns pares de amostra de entrada e saída, em que as duas primeiras colunas contêm a entrada e a terceira coluna contém a saída:

73865           9077257         9478805
139808          287648018       287965250
34              279004309       279004425
139940          68437025        69241105
272794768       1051152         273846948
16405           78284865        83888256
9576577         4718601         19013770
269128740       591914          270574722
8410276         2768969         11184785
16384           340             16724

K (ngn / k) , 45 43 42 41 bytes

{2/<':(+/F@&+/'|2\x){y!x}\|F:64(+':1,)/0}

Experimente online!

@ Algoritmo de Bubbler

{ } função com argumento x

64( )/0 faça 64 vezes, usando 0 como valor inicial:

• 1, anexar 1

• +': adicione cada anterior (deixe o primeiro elemento intacto)

F:atribuir a F"sequência de fibonacci"

| marcha ré

(.. ){y!x}\.. começando com o valor à esquerda, calcule os restos cumulativos (da esquerda para a direita) para a lista à direita. o valor à esquerda é a soma simples das entradas sem representação zeckendorf:

• 2\xbinário codifica as entradas. esta será uma matriz de nbits por 2

• | marcha ré

• +/' somar cada

• &onde estão os 1s? - lista de índices. se houver 2s, o índice correspondente será repetido duas vezes.

• F@ indexação de matriz em F

• +/ soma

<': menos que cada anterior (o primeiro do resultado será sempre falsey)

2/ decodificação binária

CJam, 76 74 70 63 59 bytes

2q~{32{2\#I&},}fI+32_,*{WUer$Kf-[UU]/[-2X]*2,/2a*Kf+}fKf#1b

Experimente on-line no intérprete CJam ou verifique todos os casos de teste de uma só vez .

Idéia

Começamos definindo uma variação menor da sequência na pergunta:

G _-2 = 0
G _-1 = 1
G _k = G _k-1 + G _k-2 sempre que k é um número inteiro não negativo

Dessa forma, o bit 0 (LSB) da matriz de bits entrada ou saída corresponde ao número de Fibonacci G ₀ e, em geral, o bit k a G _k .

Agora, substituímos cada bit definido em Z (n) e Z (m) pelo índice que ele codifica.

Por exemplo, a entrada 532 ₁₀ = 1000010100 ₂ é transformada em [2 4 9] .

Isso produz duas matrizes de números inteiros, que podemos concatenar para formar uma única.

Por exemplo, se n = m = 100 , o resultado é A: = [2 4 9 2 4 9] .

Se substituirmos cada k em A por G _k e somarmos os resultados, obteremos n + m = 200 ; portanto, A é uma maneira de decompor 200 em números de Fibonacci, mas certamente não o do teorema de Zeckendorf.

Tendo em mente que G _k + G _{k + 1} = G _{k + 2} e G _k + G _k = G _k + G _k-1 + G _k-2 = G _{k + 1} + G _k-2 , podemos substituir consecutivamente e índices duplicados por outros (a saber, (k, k + 1) por k + 2 e (k, k) por (k + 1, k - 2) ), repetindo essas substituições repetidamente até que a representação de Zeckendorf seja alcançada. ¹

É necessário um caso especial para os índices negativos resultantes. Como G _-2 = 0 , o índice -2 pode ser simplesmente ignorado. Além disso, G _-1 = 0 = G ₀ , portanto, qualquer -1 resultante deve ser substituído por 0 .

Para o nosso exemplo A , obtemos as seguintes representações (classificadas), sendo a última a representação de Zeckendorf.

[2 2 4 4 9 9] → [0 3 4 4 9 9] → [0 5 4 9 9] → [0 6 9 9] → [0 6 7 10] → [0 8 10]

Finalmente, convertemos de volta da matriz de números inteiros para a matriz de bits.

Código

2             e# Push a 2 we'll need later.
q~            e# Read and evaluate the input.
{             e# For each integer I in the input:
  32{         e#   Filter [0 ... 31]; for each J:
    2\#       e#     Compute 2**J.
    I&        e#     Compute its logical AND with I.
  },          e#   Keep J if the result in truthy (non-zero).
}fI           e#
+             e# Concatenate the resulting arrays.
32_,*         e# Repeat [0 ... 31] 32 times.
{             e# For each K:
  WUer        e#   Replace -1's with 0's.
  $           e#   Sort.
  Kf-         e#   Subtract K from each element.
  [UU]/[-2X]* e#   Replace subarrays [0 0] with [-2 1].
  2,/2a*      e#   Replace subarrays [0 1] with [2].
  Kf+         e#   Add K to each element.
}fK           e#
f#            e# Replace each K with 2**K.
1b            e# Cast all to integer (discards 2**-2) and sum.

¹ _{A implementação tenta substituir 32 vezes e não verifica se a representação de Zeckendorf foi realmente alcançada. Não tenho uma prova formal de que isso seja suficiente, mas testei todas as somas possíveis de representações de 15 bits (cujas representações de somas exigem até 17 bits) e 6 repetições foram suficientes para todas elas. Em qualquer caso, é possível aumentar o número de repetições para 99 sem aumentar a contagem de bytes, mas isso prejudicaria o desempenho.}

APL (Dyalog Extended) , 39 bytes

⊥1↓⍧|/⌽(+/g[⍸⌽+/⊤⎕]),↑,\⌽g←(2+/,)⍣38⍨⍳2

Experimente online!

Mudou para um programa completo, tendo um argumento de comprimento 2, e também alterou o gerador de Fibonacci. Obrigado a @ngn por muitas idéias.

Usa ⎕IO←0para que seja ⍳2avaliado como 0 1.

Gerador de Fibonacci (novo)

Observe que os dois últimos números são imprecisos, mas isso não altera a saída do programa.

(2+/,)⍣38⍨⍳2
→ 0 1 ((2+/,)⍣38) 0 1

Step 1
0 1 (2+/,) 0 1
→ 2+/ 0 1 0 1
→ (0+1) (1+0) (0+1) ⍝ 2+/ evaluates sums for moving window of length 2
→ 1 1 1

Step 2
0 1 (2+/,) 1 1 1
→ 2+/ 0 1 1 1 1
→ 1 2 2 2

Step 3
0 1 (2+/,) 1 2 2 2
→ 2+/ 0 1 1 2 2 2
→ 1 2 3 4 4

Zeckendorf para planície (parcial)

⍸⌽+/⊤⎕
     ⎕  ⍝ Take input from stdin, must be an array of 2 numbers
    ⊤   ⍝ Convert each number to base 2; each number is mapped to a column
  +/    ⍝ Sum in row direction; add up the counts at each digit position
 ⌽      ⍝ Reverse
⍸       ⍝ Convert each number n at index i to n copies of i

APL (Dyalog Extended) , 47 bytes

g←1↓(1,+\⍤,)⍣20⍨1
{⊥1↓⍧|/⌽⍵,↑,\⌽g}+⍥{+/g[⍸⌽⊤⍵]}

Experimente online!

A parte 1 da resposta anterior foi alterada para reutilizar os números de Fibonacci. Solte também o duplicado 1 para salvar alguns bytes em outros lugares.

Parte 1 (nova)

{+/g[⍸⌽⊤⍵]}
       ⊤⍵    ⍝ Argument to binary digits
     ⍸⌽      ⍝ Reverse and convert to indices of ones
   g[    ]   ⍝ Index into the Fibonacci array of 1,2,3,5,...
 +/          ⍝ Sum

APL (Dyalog Extended) , 52 bytes

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}+⍥({+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤)

Experimente online!

Como funciona

Nenhum algoritmo sofisticado para fazer adição no Zeckendorf porque o APL não é conhecido por operar em elementos individuais em uma matriz. Em vez disso, fui em frente para converter as duas entradas do Zeckendorf em números inteiros simples, adicioná-las e convertê-las novamente.

Parte 1: Zeckendorf para inteiro simples

{+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤  ⍝ Zeckendorf to plain integer
                ⊤  ⍝ Convert the input to array of binary digits (X)
{    (  ≢⊤⍵)  }    ⍝ Take the length L of the binary digits and
      ⌽⍳           ⍝   generate 1,2..L backwards, so L..2,1
{+∘÷⍣(     )⍨1}    ⍝ Apply "Inverse and add 1" L..2,1 times to 1
                   ⍝ The result looks like ..8÷5 5÷3 3÷2 2 (Y)
               ⊥   ⍝ Mixed base conversion of X into base Y

Base |             Digit value
-------------------------------
13÷8 | (8÷5)×(5÷3)×(3÷2)×2 = 8
 8÷5 |       (5÷3)×(3÷2)×2 = 5
 5÷3 |             (3÷2)×2 = 3
 3÷2 |                   2 = 2
 2÷1 |                   1 = 1

Parte 2: adicione dois inteiros simples

+⍥z2i  ⍝ Given left and right arguments,
       ⍝   apply z2i to each of them and add the two

Parte 3: Converter a soma novamente em Zeckendorf

"Você pode assumir que as representações de entrada e saída de Zeckendorf cabem em 31 bits" foi bastante útil.

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}  ⍝ Convert plain integer N to Zeckendorf
                 (1,+\⍤,)⍣20⍨1   ⍝ First 41 Fibonacci numbers starting with two 1's
                ⌽                ⍝ Reverse
             ↑,\                 ⍝ Matrix of prefixes, filling empty spaces with 0's
          ⌽⍵,                    ⍝ Prepend N to each row and reverse horizontally
        |/                       ⍝ Reduce by | (residue) on each row (see below)
       ⍧                         ⍝ Nub sieve; 1 at first appearance of each number, 0 otherwise
  1↓¯1↓                          ⍝ Remove first and last item
 ⊥                               ⍝ Convert from binary digits to integer

O gerador de Fibonacci

(1,+\⍤,)⍣20⍨1
→ 1 ((1,+\⍤,)⍣20) 1  ⍝ Expand ⍨
→ Apply 1 (1,+\⍤,) x 20 times to 1

First iteration
1(1,+\⍤,)1
→ 1,+\1,1  ⍝ Expand the train
→ 1,1 2    ⍝ +\ is cumulative sum
→ 1 1 2    ⍝ First three Fibonacci numbers

Second iteration
1(1,+\⍤,)1 1 2
→ 1,+\1,1 1 2  ⍝ Expand the train
→ 1 1 2 3 5    ⍝ First five Fibonacci numbers

⍣20  ⍝ ... Repeat 20 times

Isso decorre da propriedade dos números de Fibonacci: se Fibonacci for definido como

então

$1,F_0, \cdots, F_n$$F_1, \cdots, F_{n+2}$

Dígitos de Fibonacci em Zeckendorf

Input: 7, Fibonacci: 1 1 2 3 5 8 13

Matrix
0 0 0 0 0 0 13 7
0 0 0 0 0 8 13 7
0 0 0 0 5 8 13 7
0 0 0 3 5 8 13 7
0 0 2 3 5 8 13 7
0 1 2 3 5 8 13 7
1 1 2 3 5 8 13 7

Reduction by residue (|/)
- Right side always binds first.
- x|y is equivalent to y%x in other languages.
- 0|y is defined as y, so leading zeros are ignored.
- So we're effectively doing cumulative scan from the right.
0 0 0 0 0 0 13 7 → 13|7 = 7
0 0 0 0 0 8 13 7 →  8|7 = 7
0 0 0 0 5 8 13 7 →  5|7 = 2
0 0 0 3 5 8 13 7 →  3|2 = 2
0 0 2 3 5 8 13 7 →  2|2 = 0
0 1 2 3 5 8 13 7 →  1|0 = 0
1 1 2 3 5 8 13 7 →  1|0 = 0
Result: 7 7 2 2 0 0 0

Nub sieve (⍧): 1 0 1 0 1 0 0
1's in the middle are produced when divisor ≤ dividend
(so it contributes to a Zeckendorf digit).
But the first 1 and last 0 are meaningless.

Drop first and last (1↓¯1↓): 0 1 0 1 0
Finally, we apply base 2 to integer (⊥) to match the output format.

Haskell, 325 396 bytes

EDIT: nova versão:

s f[]=[]
s f l=f l
x((a:b):(c:d):(e:r))=x(b:d:(a:e):r)
x(a:b:((c:d:e):r))=x((c:a):b:e:((d:s head r):s tail r))
x[]=[]
x(a:r)=a:x r
w l|x l/=l=w.x$l|True=l
l=length
t n x=take n$repeat x
j 0=[]
j n=t(mod(n)2)1:j(div(n)2)
i n=[[],[]]++j n++t(32-(l$j n))[]
u[]=0
u(a:r)=2*u r+l a
o(_:a:r)=u r+l a
z a b=o$w$zipWith(++)(i a)(i b)

z faz o trabalho.

ES6, 130 bytes

(n,m)=>{for(a={},s=0,i=x=y=1;i<<1;i+=i,z=y,y=x,x+=z)s+=((n&i)+(m&i))/i*(a[i]=x);for(r=0;i;i>>>=1)s>=a[i]?(s-=a[i],r|=i):0;return r}

Originalmente, tentei calcular a soma no local (efetivamente ao longo das linhas da implementação do CJam), mas continuava ficando sem temporários; portanto, apenas converti os números para números anteriores reais.

(Sim, provavelmente posso salvar um byte usando eval.)

Ruby , 85 73 65 bytes

->*a{r=(0..2*a.sum).select{|r|r^r*2==r*3};r[a.sum{|w|r.index w}]}

Experimente online!

Como?

Primeiro, obtenha um limite superior para a soma codificada: (a + b) * 2 está ok.

Agora filtre todos os números não zeckendorf de (0..limit).

Temos uma mesa de pesquisa, é ladeira abaixo daqui.

Python 3, 207 bytes

def s(n):
 p=1
 while n>=2*p:
  p*=2
 return n if n<=p else s(n+p//2)if n>=3*p/2 else s(m)if (m:=s(n-p)+p)!= n else n
a=lambda n,m:(b:=n&m)>-1 and s(a(a(a(s((n|m)-b%4),b//4*2),b//4),b%4*2+b%4//2))if m else n

Experimente Online! (Verifique todos os casos de teste)

Explicação

Este programa manipula diretamente as traduções binárias das representações de Zeckendorf. A função a(n,m)executa os cálculos principais e s(n)é uma função auxiliar que se livra dos números adjacentes contidos na representação Zeckendorf.

Vamos começar com a função s(n)(expandida para maior clareza):

def s(n): 
    p=1                  #This finds the highest digit of the binary form of n.
    while n>=2*p:
        p*=2
    if n<=p:             #If n is a power of two (i.e, our number is already a Fibonnaci number)...
        return n         #Then return it normally.  This also works for zero. (A)
    if n>=3*p/2:         #If n's first digit is followed by a 1 (i.e, it starts with 11X)
        return s(n+p//2) #Then replace that with 100X (B)
    m = s(n-p)+p         #Otherwise, apply s to the rest of the number (C)
    if m==n:             #If this is out final result, we're done! (D)
        return n
    return s(m)          #Otherwise, reapply it. (E)

Por exemplo, o número 107 ( 1101011em binário, representando 1 + 2 + 5 + 13 + 21 = 42), passa pelo seguinte processo:

1+2+5+13+21 [1101011] -> 1+2+5+34 [10001011] (B)
1+2+5+34 [10001011] (C)
 1+2+5 [1011] (C)
  1+2 [11] -> 3 [100] (B)
 ->3+5 [1100] (A/E)
 (E):  3+5 [1100] -> 8 [10000] (B)
->8+34 [10010000] (A/E)
(E): 8+34 [10010000] (C)
->8+34 [10010000] (A/E)

Experimente Online! (s com saída detalhada)

Aqui está uma versão expandida de a(n,m):

def a(n,m):
    if m==0:
        return n
    b=n&m
    t=s((n|m)-b%4)              #(A)
    t=a(t,b//4*2)               #(B)
    t=a(t,b//4)                 #(C)
    return s(a(t,b%4*2+b%4//2)) #(D)

Esta função converte as duas representações de Zeckendorf em quatro números binários que são mais fáceis de combinar. A linha (A) é o OR bit a bit das duas representações binárias de Zeckendorf - elas correspondem a uma cópia de cada número de Fibonacci nos dois grupos. (B) e (C) são AND bit a bit dos dois números deslocados para a direita 1 e 2 vezes, respectivamente. Sabemos que quando os números correspondentes de Fibonacci para (B) e (C) são somados, eles serão equivalentes aos AND bit a bit do nosso ne mporque F (n) = F (n-1) + F (n-2) .

Por exemplo, digamos que temos os números binários n = 101001 (correspondendo a 1 + 5 + 13) e m = 110110 (2 + 3 + 8 + 13). Então teremos (A) = 111111 (1 + 2 + 3 + 5 + 8 + 13), que é convertido em 1010100 (3 + 8 + 21) por nossa função s, (B) = 10000 (8) e ( C) = 1000 (5). Podemos verificar que (1 + 5 + 13) + (2 + 3 + 8 + 13) = (3 + 8 + 21) + (8) + (5) = 45. Esse processo se repete com ((3 + 8 + 21) + (8)) + (5) = ((3 + 8 + 21) + (5) + (3)) + (5), etc.

A única dificuldade desse sistema é que ele não funciona para os números 1 e 2 de Fibonacci, pois eles não obedecem à propriedade F(n)=F(n-1)+F(n-2)(são os dois números mais baixos)! Por isso, sempre que 1 ou 2 está contido em ambos ne m, eles são removidos de A, B e C, sua soma é colocada em D sob a propriedade que 1 + 1 = 2 e 2 + 2 = 1 + 3. Por exemplo, se adicionarmos 1 + 3 (101) + 1 + 3 + 5 (1101), obtemos:

(A): 3 + 5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 2 (10)

Observe que os 3 e 5 foram colocados em A, o duplicado 3 foi dividido em 2 + 1 em B e C e os 1s duplicados foram removidos de A, B e C, somados e inseridos em D. Da mesma forma, se adicione 2 + 3 (110) + 2 + 3 + 5 (1110), obtemos:

(A): 3 + 5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 1 + 3 (101)

Experimente online! (a com saída detalhada)

Wolfram Language (Mathematica) , 218 bytes

Fold[#+##&,Total@PadLeft@IntegerDigits[#,2]//.{{p=n_/;n>1,r=y___}:>{0,n,y},{q=x___,i_,p,j_,k_,r}:>{x,i+1,n-2,j,k+1,y},{q,i_,p,j_}:>{x,i+1,n-2,j+1},{q,i_,p}:>{x,i+1,n-2},{1,1,r}:>{1,0,0,y},{q,i_,1,1,r}:>{x,i+1,0,0,y}}]&

Experimente online!

Simplesmente correspondência de padrões.

Ungolfed:

FromDigits[Total@PadLeft@IntegerDigits[#, 2] //.
   {{n_ /; n > 1, y___} :> {0, n, y},
    {x___, i_, n_ /; n > 1, j_, k_, y___} :> {x, i + 1, n - 2, j, k + 1, y},
    {x___, i_, n_ /; n > 1, j_} :> {x, i + 1, n - 2, j + 1},
    {x___, i_, n_ /; n > 1} :> {x, i + 1, n - 2},
    {1, 1, y___} :> {1, 0, 0, y},
    {x___, i_, 1, 1, y___} :> {x, i + 1, 0, 0, y}}, 2] &