12
\$\begingroup\$

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} $$

Task

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
\$\endgroup\$
3
  • \$\begingroup\$ Can I take as input the indices in the input which are 1? \$\endgroup\$ Aug 25, 2023 at 5:17
  • \$\begingroup\$ 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}\$. \$\endgroup\$ Aug 25, 2023 at 5:31
  • \$\begingroup\$ @CommandMaster No. \$\endgroup\$
    – Bubbler
    Aug 25, 2023 at 7:05

4 Answers 4

3
\$\begingroup\$

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()
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 41 bytes

Fθ⊞υ∨¬υΣ…⮌υ²≔ΣE⮌θ×Iι§υκθF⮌Φυ¬﹪κ⁴«I÷θι≧﹪ιθ

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

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

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

≔ΣE⮌θ×Iι§υκθ

Convert the input from Zeckendorf to integer.

F⮌Φυ¬﹪κ⁴«I÷θι≧﹪ιθ

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

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 21 19 bytes

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

Try it online, or try all test cases

-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.
\$\endgroup\$
1
  • \$\begingroup\$ ʒN4%<} can be 4ι2è to save 2 bytes. \$\endgroup\$ Aug 25, 2023 at 8:09
1
\$\begingroup\$

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".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.