# Zeckendorf to F(4k+2) representation

## Background

Fibonacci numbers are defined as follows:

$$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$

The Zeckendorf representation is a representation of positive integers as a sum of one or more non-adjacent Fibonacci numbers, using indices 2 and higher. It is known that such a representation is unique for every positive integer (Zeckendorf's theorem), and it can be written as a positional base system using digits 0 and 1. For example:

$$65 = 55 + 8 + 2 = F_{10} + F_{6} + F_{3} = \overline{100010010}_F$$

The $$\F_{4k+2}\$$ representation is a similar representation but using every fourth Fibonacci number only, and with digits of at most 9. Some examples:

\begin{align} 7 &= 7F_2 = \overline{7}_{F_{4k+2}} \\ 8 &= 8F_2 = \overline{8}_{F_{4k+2}} \\ &= F_6 = \overline{10}_{F_{4k+2}} \\ 65 &= F_{10} + F_6 + 2F_2 = \overline{112}_{F_{4k+2}} \\ \end{align}

Note that this representation is not unique in general.

I invented this to multiply two numbers in Zeckendorf representation in subquadratic time, from the fact that the product of two $$\F_{4k+2}\$$s can be expanded to a sum of $$\F_{4k+2}\$$s:

\begin{align} F_2 F_n &= F_n \\ F_6 F_n &= F_{n-4} + F_n + F_{n+4} \\ F_{10} F_n &= F_{n-8} + F_{n-4} + F_n + F_{n+4} + F_{n+8} \\ &\cdots \\ F_{4k+2} F_n &= \sum_{i=-k}^{k} F_{n+4i} \end{align}

Given a positive integer in Zeckendorf representation, output the same number in $$\F_{4k+2}\$$ representation. If there are multiple possible representations, output any of them.

Both the input and output may be represented using a list or string of digits, in the order of increasing or decreasing positional value. For example, if the given number is 11, you may choose to take e.g. "10100", "00101", [1, 0, 1, 0, 0], or [0, 0, 1, 0, 1] as input, and give "13", "31", [1, 3], or [3, 1] as output.

## Test cases

Number Zeckendorf      F4k+2 (not showing all possible answers)
7      1010            7
10     10010           12
12     10101           14
51     10100101        63
144    10000000000     242
233    100000000000    415
490    1001001000100   1203 or 1172 or 862
986    10101010101010  2414

• Can I take as input the indices in the input which are 1? Aug 25, 2023 at 5:17
• Some equalities which might be useful: $3 F_{4k+3} = 5 F_{4k+2} - F_{4(k-1)+2}$, $3 F_{4k+1} = 2 F_{4k+2} - F_{4(k-1)+2}$, $3 F_{4k} = F_{4k+2} + F_{4(k-1)+2}$. Aug 25, 2023 at 5:31
• @CommandMaster No. Aug 25, 2023 at 7:05

# JavaScript (ES6), 88 bytes

Expects a binary array in reverse order. Returns an array which may include leading 0's.

a=>a.reduce((q,c,i)=>(t+=c*=x=y+(y=x),i&3?q:[x,...q]),[],t=y=0,x=1).map(x=>t/(t%=x,x)|0)


Try it online!

### How?

We have two steps:

1. During the reduce() step, we convert the input array $$\a[\:]\$$ of length $$\L\$$ into an integer $$\t\$$ by computing Fibonacci numbers $$\F_2\$$ to $$\F_{L+1}\$$ and adding those for which the corresponding entry in $$\a[\:]\$$ is set. At the same time, we store the Fibonacci numbers of the form $$\F_{4k+2}\$$ in this range in an array $$\q[\:]\$$, from highest to lowest.

2. During the map() step, we convert $$\q[\:]\$$ into the final output by computing $$\\lfloor t/x\rfloor\$$ for each entry $$\x\$$ and reducing $$\t\$$ modulo $$\x\$$ after each iteration.

### Commented

a =>                     // a[] = input array
a.reduce((q, c, i) =>    // for each value c at index i in a[],
(                      // using q[] as the accumulator:
t +=                 //   add to t ...
c *=               //     c multiplied by ...
x = y + (y = x), //       the next Fibonacci number x
i & 3 ?              //   if i is not a multiple of 4:
q                  //     leave q[] unchanged
:                    //   else:
[x, ...q]          //     append x at the beginning of q[]
),                     //
[],                    //   start with q = []
t = y = 0,             //   start with t = 0, y = 0
x = 1                  //   start with x = 1
)                        // end of reduce()
.map(x =>                // for each value x in q[]:
t / (t %= x, x)        //   return floor(t / x)
| 0                    //   and reduce t modulo x
)                        // end of map()


# Charcoal, 41 bytes

Ｆθ⊞υ∨¬υΣ…⮌υ²≔ΣＥ⮌θ×Ｉι§υκθＦ⮌Φυ¬﹪κ⁴«Ｉ÷θι≧﹪ιθ


Try it online! Link is to verbose version of code. Explanation:

Ｆθ⊞υ∨¬υΣ…⮌υ²


Generate F(2)...F(n+1) where n is the number of bits in the input.

≔ΣＥ⮌θ×Ｉι§υκθ


Convert the input from Zeckendorf to integer.

Ｆ⮌Φυ¬﹪κ⁴«Ｉ÷θι≧﹪ιθ


Greedily convert the input from integer to F(4k+2).

# 05AB1E, 21 19 bytes

ƶ+ÅfODÅF4ι2èRvy‰s?


-2 thanks to @Kevin Cruijssen

Takes the input as a reversed list. Turns the number from Zeckendorf representation to an integer, and then finds an $$\F_{4k+2}\$$ representation greedily.

## Explanation

ƶ      multiply each number by its 1-based index
+      and add that to the original list, so effectively we multiplied by the 2-based index
Åf     get the n-th Fibonacci number, for each N in that list
O      and sum, let's call it V
D      duplicate
ÅF     list the fibonacci numbers less than or equal to it
4ι     uninterleave to four lists [a[0::4], a[1::4], a[2::4], a[3::4]]
2è     and take the third element, a[2::4]
R      reverse that list
v      and for each element in the list:
y      push it
‰      calculate divmod(V, element)
dump (division, mod)  to the stack
s      swap, to get (mod, division)
?      and print the result of the division without a newline, leaving the modulo in the stack in place of V.

• ʒN4%<} can be 4ι2è to save 2 bytes. Aug 25, 2023 at 8:09

# Python, 150 bytes

def f(i):
a=b=g=1;o=0
def n(o):
while(z:=(o+g-1)//8&g):o-=o//8%2-(z*145>>4)
return o
while i:o=n(o+i%2*b);a,b=b,n(a+b);i//=2;g=16*g+1
return o


Attempt This Online!

Expects binary coded Zeckendorf and returns hex coded F4k+2.

## How?

Uses the identity $$\7F_n= F_{n-4}+F_{n+4}\$$ to express addition in F4k+2 using "two-sided carry".