El teorema de Zeckendorf muestra que cada entero positivo puede representarse de manera única como una suma de números de Fibonacci no adyacentes. En este desafío, debes calcular la suma de dos números en la representación de Zeckendorf.

Sea F _n es el n -ésimo número de Fibonacci, donde

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

La representación Z ( n ) de Zeckendorf de un número entero no negativo n es un conjunto de números enteros positivos tales que

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

(en prosa: la representación de Zeckendorf de un número n es un conjunto de enteros positivos de tal manera que los números de Fibonacci para estos índices suman n y no hay dos enteros adyacentes que formen parte de ese conjunto)

Notablemente, la representación de Zeckendorf es única. Estos son algunos ejemplos de representaciones de Zeckendorf:

Z (0) = ∅ (el conjunto vacío)
Z (1) = {1}
Z (2) = {2}
Z (3) = {3} ({1, 2} no es la representación de Zeckendorf de 3)
Z (10) = {5, 2}
Z (100) = {3, 5, 10}

En este desafío, las representaciones de Zeckendorf se codifican como conjuntos de bits donde el bit menos significativo representa si 1es parte del conjunto, etc. Puede suponer que las representaciones de Zeckendorf de entrada y salida encajan en 31 bits.

Su tarea es calcular Z ( n + m ) dados Z ( n ) y Z ( m ). La solución con la longitud más corta en octetos gana.

Puede encontrar una implementación de referencia escrita en ANSI C aquí . También se puede usar para generar representaciones de Zeckendorf o calcular un número a partir de su representación de Zeckendorf.

Aquí hay algunos pares de entrada y salida de muestra, donde las dos primeras columnas contienen la entrada y la tercera columna contiene la salida:

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}

Pruébalo en línea!

Algoritmo de @ Bubbler

{ } funcionar con argumento x

64( )/0 hacer 64 veces, usando 0 como valor inicial:

• 1, anteponer 1

• +': agregue cada prior (deje el primer elemento intacto)

F:asignar a Fpara "secuencia de fibonacci"

| contrarrestar

(.. ){y!x}\.. comenzando con el valor de la izquierda, calcule los residuos acumulativos (de izquierda a derecha) para la lista de la derecha. el valor de la izquierda es la suma simple de las entradas sin representación de zeckendorf:

• 2\xbinario codificar las entradas. esta será una matriz nbits-by-2

• | contrarrestar

• +/' suma cada

• &donde estan los 1s - lista de índices. si hay 2, el índice correspondiente se repite dos veces.

• F@ matriz de indexación en F

• +/ suma

<': menos que cada anterior (el primero del resultado siempre será falsey)

2/ decodificación binaria

CJam, 76 74 70 63 59 bytes

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

Pruébelo en línea en el intérprete de CJam o verifique todos los casos de prueba a la vez .

Idea

Comenzamos definiendo una variación menor de la secuencia en la pregunta:

G _-2 = 0
G _-1 = 1
G _k = G _k-1 + G _k-2 siempre que k sea ​​un entero no negativo

De esta manera, el bit 0 (LSB) de la entrada o salida de las matrices de bits corresponde al número de Fibonacci G ₀ y, en general, el bit k a G _k .

Ahora, reemplazamos cada bit establecido en Z (n) y Z (m) por el índice que codifica.

Por ejemplo, la entrada 532 ₁₀ = 1000010100 ₂ se transforma en [2 4 9] .

Esto produce dos matrices de enteros, que podemos concatenar para formar uno solo.

Por ejemplo, si n = m = 100 , el resultado es A: = [2 4 9 2 4 9] .

Si reemplazamos cada k en A por G _k y sumamos los resultados, obtenemos n + m = 200 , por lo que A es una forma de descomponer 200 en números de Fibonacci, pero ciertamente no es la del teorema de Zeckendorf.

Teniendo en cuenta que G _k + G _{k + 1} = G _{k + 2} y G _k + G _k = G _k + G _k-1 + G _k-2 = G _{k + 1} + G _k-2 , podemos sustituirlos consecutivamente e índices duplicados por otros (a saber, (k, k + 1) por k + 2 y (k, k) por (k + 1, k - 2) ), repitiendo esas sustituciones una y otra vez hasta alcanzar la representación de Zeckendorf. ¹

Debe tomarse un caso especial para los índices negativos resultantes. Como G _-2 = 0 , el índice -2 puede simplemente ignorarse. Además, G _-1 = 0 = G ₀ , por lo que cualquier -1 resultante debe ser reemplazado por 0 .

Para nuestro ejemplo A , obtenemos las siguientes representaciones (ordenadas), siendo la última la representación 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, volvemos de la matriz de enteros a la 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.

¹ _{La implementación intenta sustituir 32 veces y no verifica si se ha alcanzado la representación de Zeckendorf. No tengo una prueba formal de que esto sea suficiente, pero he probado todas las sumas posibles de representaciones de 15 bits (cuyas representaciones requieren hasta 17 bits) y 6 repeticiones fueron suficientes para todas ellas. En cualquier caso, es posible aumentar el número de repeticiones a 99 sin aumentar el recuento de bytes, pero perjudicaría el rendimiento.}

APL (Dyalog Extended) , 39 bytes

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

Pruébalo en línea!

Cambió a un programa completo tomando un argumento de longitud 2, y también cambió el generador de Fibonacci. Gracias a @ngn por muchas ideas.

Utiliza ⎕IO←0para que ⍳2evalúe a 0 1.

Generador de Fibonacci (nuevo)

Tenga en cuenta que los dos últimos números son inexactos, pero no cambia la salida del 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 a llanura (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[⍸⌽⊤⍵]}

Pruébalo en línea!

Cambió la Parte 1 de la respuesta anterior para reutilizar los números de Fibonacci. Además, suelte el duplicado 1 para guardar algunos bytes en otros lugares.

Parte 1 (nueva)

{+/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}⊥⊤)

Pruébalo en línea!

Cómo funciona

No es necesario un algoritmo sofisticado para hacer adiciones en Zeckendorf porque APL no es conocido por su funcionamiento en elementos individuales en una matriz. En cambio, seguí adelante para convertir las dos entradas de Zeckendorf a enteros simples, agregarlos y volver a convertirlos.

Parte 1: Zeckendorf a entero simple

{+∘÷⍣(⌽⍳≢⊤⍵)⍨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: Agregar dos enteros simples

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

Parte 3: Convertir la suma de nuevo a Zeckendorf

"Puede suponer que las representaciones de Zeckendorf de entrada y salida encajan en 31 bits" fue 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

El generador 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

Esto se deduce de la propiedad de los números de Fibonacci: si Fibonacci se define como

entonces

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

Fibonacci a Zeckendorf dígitos

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

EDITAR: nueva versión:

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 hace el trabajo.

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 traté de calcular la suma en el lugar (de manera efectiva a lo largo de las líneas de la implementación de CJam) pero seguí quedando sin temporarios, así que simplemente convertí los números a números enteros reales.

(Sí, probablemente pueda guardar un 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}]}

Pruébalo en línea!

¿Cómo?

Primero obtenga un límite superior para la suma codificada: (a + b) * 2 está bien.

Ahora filtre todos los números no zeckendorf de (0..limit).

Tenemos una tabla de búsqueda, es cuesta abajo desde aquí.

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

Pruébalo en línea! (Verifique todos los casos de prueba)

Explicación

Este programa manipula directamente las traducciones binarias de las representaciones de Zeckendorf. La función a(n,m)realiza los cálculos principales y s(n)es una función auxiliar que elimina los números adyacentes contenidos en la representación de Zeckendorf.

Comencemos con la función s(n)(expandida para mayor claridad):

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 ejemplo, el número 107 ( 1101011en binario, que representa 1 + 2 + 5 + 13 + 21 = 42), se somete al siguiente proceso:

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)

Pruébalo en línea! (s con salida detallada)

Aquí hay una versión ampliada 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 función convierte las dos representaciones de Zeckendorf en cuatro números binarios que son más fáciles de combinar. La línea (A) es el OR bit a bit de las dos representaciones binarias de Zeckendorf, que corresponden a una copia de cada número de Fibonacci en cualquier grupo. (B) y (C) son los bits Y de los dos números desplazados a la derecha 1 y 2 veces, respectivamente. Sabemos que cuando se suman los números de Fibonacci correspondientes para (B) y (C), serán equivalentes al AND a nivel de bits de nuestro ny mporque F (n) = F (n-1) + F (n-2) .

Por ejemplo, supongamos que tenemos los números binarios n = 101001 (correspondientes a 1 + 5 + 13) ym = 110110 (2 + 3 + 8 + 13). Entonces tendremos (A) = 111111 (1 + 2 + 3 + 5 + 8 + 13), que se convierte a 1010100 (3 + 8 + 21) por nuestra función s, (B) = 10000 (8), y ( C) = 1000 (5). Podemos verificar que (1 + 5 + 13) + (2 + 3 + 8 + 13) = (3 + 8 + 21) + (8) + (5) = 45. Este proceso se repite con ((3 + 8 + 21) + (8)) + (5) = ((3 + 8 + 21) + (5) + (3)) + (5), etc.

¡La única dificultad con este sistema es que no funciona para los números 1 y 2 de Fibonacci, ya que no obedecen la propiedad F(n)=F(n-1)+F(n-2)(son los dos números más bajos)! Debido a eso, cuando 1 o 2 está contenido en ambos ny m, se eliminan de A, B y C, su suma se coloca en D debajo de la propiedad que 1 + 1 = 2 y 2 + 2 = 1 + 3. Por ejemplo, si agregamos 1 + 3 (101) + 1 + 3 + 5 (1101), obtenemos:

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

(B): 2 (10)

(C): 1 (1)

(D): 2 (10)

Observe que los 3 y 5 se colocaron en A, el duplicado 3 se dividió en 2 + 1 en B y C, y los duplicados 1 se eliminaron de A, B y C, se agregaron y se pusieron en D. De manera similar, si sumamos 2 + 3 (110) + 2 + 3 + 5 (1110), obtenemos:

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

(B): 2 (10)

(C): 1 (1)

(D): 1 + 3 (101)

Pruébalo en línea! (a con salida detallada)

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}}]&

Pruébalo en línea!

Simplemente coincidencia de patrones.

Sin golf:

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] &