Compute the Fibonacci product

Question

Background

We've had challenges before on Fibonacci coding and Zeckendorf representation. These representations follow naturally from Zeckendorf's theorem, which states that every positive integer can be represented uniquely as the sum of one or more distinct, non-consecutive Fibonacci numbers. For example:

$$ \begin{aligned} 64 &= 55 + 8 + 1 \\ &= F_{10} + F_6 + F_2 \\ 171 &= 144 + 21 + 5 + 1 \\ &= F_{12} + F_8 + F_5 + F_2 \\ \end{aligned} $$

where \$F_i\$ is the \$i\$-th Fibonacci number.

What is Fibonacci multiplication?

Extending this concept, Donald Knuth defined "circle multiplication" (the Fibonacci product) on two postive integers \$a\$ and \$b\$ as follows. First assume

$$ \begin{align} a &= \sum_{i=0}^n F_{c_i} \text{ where } c_i \ge 2 \\ b &= \sum_{i=0}^m F_{d_i} \text{ where } d_i \ge 2 \end{align} $$

Then we define the Fibonacci product like so:

$$ a \circ b = \sum_{i=0}^n \sum_{j=0}^m F_{c_i + d_j} $$

See Knuth's original article (pdf) or the Wikipedia entry for more.

Here is a worked example from the Wikipedia page:

$$ \begin{align} 2 &= F_3 \\ 4 &= F_4 + F_2 \\ 2 \circ 4 &= F_{3 + 4} + F_{3 + 2} \\ &= F_7 + F_5 \\ &= 13 + 5 \\ &= 18 \end{align} $$

As an interesting aside not directly related to the challenge, it has been shown that the Fibonacci product:

can be interpreted as the usual multiplication in a multiplicatively closed subset of the ring \$\mathbb{Z}[\phi]\$ of algebraic integers generated by the "golden ratio".

Task

Given two positive integers as input, return their Fibonacci product as defined in the section above.

This is code-golf and standard site rules apply.

Test Cases

1 1 -> 3
1 2 -> 5
1 5 -> 13
2 1 -> 5
2 4 -> 18
4 1 -> 11
4 4 -> 40
4 9 -> 87
7 1 -> 18 
7 2 -> 29
7 9 -> 141
9 9 -> 189

Answer 1

Wolfram Language (Mathematica), 39 34 33 bytes

1##+{#2,#}.⌊+++{##}2/++√5⌋&

Try it online!

Uses the formula in the linked Arnoux paper: \$m\circ n=m n+p_m n+m p_n\$, where \$p_x\$ is defined as the integer such that \$p_x-\frac x\phi\in(\frac1\phi-1,\frac1\phi)\$. A little bit of manipulation gets us \$p_x=\left\lfloor\frac{x+1}\phi\right\rfloor\$.

1##                         m n
   +{#2,#}.                 + (n,m) .
           ⌊+++{##}2/++√5⌋  ⌊(1+(m,n)) / ϕ⌋

Answer 2

Jelly, 9 8 bytes

A port of att's answer and -1 byte thanks to them. Takes input as a pair of integers [a, b].

‘:ØpḋṚ+P

Try it online!

‘          increment each value          [a+1, b+1]
 :Øp       integer divide by phi         [(a+1):phi, (b+1):phi]
    ḋṚ     dot product with the reverse  (a+1):phi×b + (b+1):phi×a
       +P  add the product of the input  (a+1):phi×b + (b+1):phi×a + a×b 

Answer 3

Jelly, 18 bytes

ŒP‘ÆḞS=ɗƇ¹Ḣ)p/§ÆḞS

Try it online!

-1 byte thanks to caird coinheringaahing

---

I have posted a video explanation of this answer and how to approach this problem as well as the mathematical observation below to my YouTube channel. You can see the video here.

---

Assume that there is a sequence of Fibonacci numbers where two are consecutive. Select the largest two such terms and them be \$F_n\$ and \$F_{n+1}\$. Then, \$F_{n+2}\$ cannot be in the sequence because then it would be consecutive with \$F_{n+1}\$ and thus contradict the definition. Therefore, we replace \$F_n,F_{n+1}\$ with \$F_{n+2}\$ in the sequence and we now have a shorter sequence that sums to the same value.

Keep repeating this process indefinitely, and we can see that the shortest sequence of Fibonacci numbers that sums to \$N\$ has to be the unique one containing no consecutive terms, otherwise we can reduce it to something shorter, which would be a contradiction.

Thus, we only need to find the shortest sequence. Here follows the explanation of the Jelly code itself:

ŒP‘ÆḞS=ɗƇ¹Ḣ)p/§ÆḞS    Main Link; accept a list [x, y]
           )          For each k of x and y
ŒP                    Take the powerset of [1, 2, ..., k], shortest & lexicographically least first
  ‘                   Add one (now we have the powerset of [2, 3, ..., k + 1])
        Ƈ             Filter; keep terms where
   ÆḞ                 Taking the Nth fibonacci number
     S                and summing
      =               is equal to
         ¹            k itself
          Ḣ           And take the first (thus shortest) such subset
            p/        Take the cartesian product of the two codings
              §       Sum each pair
               ÆḞ     Get the Nth fibonacci number for each
                 S    and sum

Answer 4

J, 70 bytes

+/@,@(1{:@F@++/)&(F i.2-/\[(0>.]-(<:@I.>:){[)^:a:~F=:_2&(],+/@{.)&1 2)

Try it online!

• F=:_2&(],+/@{.)&1 2) F_1, F_2 … F_n.
• [(0>.]-(<:@I.>:){[)^:a:~ starting with n, greedily find the highest Fibonacci number (with binary search with adjusted indices <:@I.>:), subtract from n and repeat until we hit 0. Return the intermediate results.
• F i.2-/\ From the intermediate results get the Fibonacci numbers, and then their indices.
• …&… do this for both results, then for both Fibonacci index lists do …
• 1{:@F@++/ addition table, get the last F_i for each sum.
• +/@,@ … and sum it again

Answer 5

Jelly, 25 bytes

¹©R‘U;ṖÆḞS>®Ʋ¡¥ƒ“”)p/§ÆḞS

Try it online!

-4 bytes thanks to caird coinheringaahing

Non-brute force answer that should run in \$O(N^2)\$ time. Still trying to figure out how to remove the register usage.

Basically, constructs the Fibonacci coding by starting from an upper bound and counting down, adding in the largest Fibonacci number that can fit each time. Since I am summing the accumulating list each time, and I think the output list is roughly \$O(\log N)\$ in size, I believe this is \$O(N \log N)\$, but I'm not sure, so I'll just put down \$O(N^2)\$ for now.

¹©R‘U;ṖÆḞS>®Ʋ¡¥ƒ“”)p/§ÆḞS        Main Link (monadic): accept [x, y]
                  )              For each k in [x, y]
¹©                               Save it to the register
  R                              Range; [1, 2, ..., k]
   ‘                             Increment; [2, 3, ..., k + 1]
    U                            Reverse; [k + 1, k, ..., 2]
     ;ṖÆḞS>®Ʋ¡¥ƒ“”               Reduce this list starting from []:
     -========¥                  Last two as a dyad:
     ;                           - append the new value to the list
             ¡                   - then, N times (if statement for boolean values)
       ÆḞS>®Ʋ                      - if the sum of those Fibonacci numbers exceeds the desired value
      Ṗ                            - pop the last addition back off
                   p/            Cartesian product of the results
                     §           Sum of each; get the indexes
                      ÆḞ         Convert to Fibonacci numbers
                        S        Sum

Answer 6

Jelly, 22 bytes

ŒP‘I’ẠƊƇÆḞS=ɗƇ)p"/§ÆḞ§

Try it online!

This feels grossly long.

Returns [x] where x is the expected output. This is allowed by default

-1 byte thanks to hyper-neutrino

---

How it works

ŒP‘I’ẠƊƇÆḞS=ɗƇ)p"/§ÆḞ§ - Main link. Takes [a, b] on the left
              )        - For each input:
ŒP                     -   Cast to range, then powerset
  ‘                    -   Increment each one
      ƊƇ               -   Keep those for which the following is true:
   I                   -     Forward differences
    ’                  -     Decrement
     Ạ                       Are all non-zero?
                             This removes all lists with any consecutive indices
            ɗƇ         -   Keep those for which the following is true:
        ÆḞ             -     Convert each index to its Fibonacci number
          S=           -     Does the sum equal the input?
               p"/     - Get the Cartesian product of the indices
                          The " (vectorise) quick allows us to avoid extracting the
                          first element, instead we operate with everything
                          wrapped to an additional depth
                  §    - Sums
                   ÆḞ  - Fibonacci number of each
                     § - Sum

Answer 7

Vyxal as, 11 bytes

›5√›½ḭṘ*⁰ΠJ

Try it Online!

A port of the other ones. No, there isn't a phi builtin.

Answer 8

Ruby, 56 bytes

->a,b{g=->z{(2*z/=1+5**0.5).to_i};a*b+a*g[b+1]+b*g[a+1]}

Try it online!

Same formula as almost everybody else.

Answer 9

JavaScript (ES6),  98  90 bytes

A full implementation.

Expects (a)(b).

a=>g=(x,k,n)=>(F=n=>n<3||F(n-1)+F(n-2))(-~n)>x?x&&(k?F(k+n):g(a,n))+g(x-F(n),k):g(x,k,-~n)

Try it online!

Commented

The helper function \$F\$ just computes the \$n\$-th Fibonacci term, 1-indexed.

F = n => n < 3 || F(n - 1) + F(n - 2)

Main function:

a =>               // outer function taking a
g = (              // the inner function g first takes x = b and later
  x,               // invokes itself for the 2nd pass with x = a
  k,               // k is undefined during the 1st pass, then set to
                   // a positive integer
  n                // n is the Fibonacci term index
) =>               //
  F(-~n) > x ?     // if F(n + 1) is greater than x:
    x && (         //   stop if x = 0, otherwise:
      k ?          //     if k is defined:
        F(k + n)   //       compute F(k + n)
      :            //     else:
        g(a, n)    //       process the 2nd pass with x = a and k = n
    ) +            //
    g(x - F(n), k) //   add the result of a recursive call with F(n)
                   //   subtracted from x and k unchanged
  :                // else:
    g(x, k, -~n)   //   try again with n + 1

---

JavaScript (ES7), 42 bytes

Using @att's closed-form formula is, obviously, significantly shorter.

Expects (a)(b).

a=>b=>~~(p=.5+5**.5/2,b-~b/p)*a-~~(~a/p)*b

Try it online!

Answer 10

Japt, 19 18 bytes

Far too long but just can't seem to do any better. There's gotta be a shorter way to get Phi!

×+UËÄ z5¬Ä ÑÃx_*Uo

Try it

Answer 11

Retina 0.8.2, 123 bytes

.+
$*
(\G1|(?>\2?)(\1))*1
$#1$*01¶
%)+`^(.*).(.*¶)(\1.)¶
$3$2
+`^(0*)1(.*¶¶)(.+)
0$1$2$3¶00$1$3
3A`
0?
;
+`;(1*);1
1;1$1;
1

Try it online! Takes newline-separated inputs but link is to test suite that splits on comma for convenience. Explanation:

.+
$*
(\G1|(?>\2?)(\1))*1
$#1$*01¶
+`^(.*).(.*¶)(\1.)¶
$3$2

Convert the input to its Zeckendorf representation. This is based on my answer to Fibonacci Encoding but without the trailing 1 of course.

%)`

Apply the above to each input separately.

+`^(0*)1(.*¶¶)(.+)
0$1$2$3¶00$1$3
3A`

Long multiply the two inputs. (The final addition is implicitly accomplished after the conversion back to decimal.) Additionally, since the Zeckendorf representation starts at F₂, prefix an additional two zeros to adjust for the 2-indexing.

0?
;
+`;(1*);1
1;1$1;

Convert each Zeckendorf representation back to unary. This is based on my answer to Converting a number from Zeckendorf Representation to Decimal.

1

Sum the unary values and convert to decimal.

Answer 12

C (gcc), 77 62 53 bytes

g(m){m=~m*(1-sqrt(5))/2;}f(m,n){m=m*n+g(m)*n+g(n)*m;}

Try it online!

-15 bytes thanks to ovs
-9 bytes thanks to att

Original submission:

#define X(m,n) +(int)((m+1)*2/(sqrt(5)+1))*n
f(m,n){return m*n X(m,n)X(n,m);}

Basically an adaptation of att's excellent answer.

Thanks to the power of the preprocessor undefined behavior this is way shorter than an equivalent Java version I tried.

Answer 13

Python 2, 68 61 bytes

-7 bytes thanks to ovs, and based on att's answer:

def f(x,y):p=lambda a:~a*(1-5**.5)//2;print x*y+x*p(x)+y*p(y)

Try it online!

As my first golfing experience with python, there might be room for improvement. Suggestions are welcome.

Answer 14

MathGolf, 16 bytes

ê)φ/iêx^~êßmÅε*Σ

MathGolf has a builtin for the golden ratio / phi, but unfortunately it's not too good at taking the product of inner lists..

Try it online.

Explanation:

ê                # Push the input as integer-array: [a,b]
 )               # Increase both values by 1: [a+1,b+1]
  φ/             # Divide both by phi: [(a+1)/phi,(b+1)/phi]
    i            # Floor the decimals to an integer: [(a+1)//phi,(b+1)//phi]
     êx          # Push the input-array again, and reverse it: [b,a]
       ^         # Zip the two lists together: [[(a+1)//phi,b],[(b+1)//phi,a]]
                 # Append the input-pair to this list, by:
        ~        #  Dumping both pairs onto the stack
         ê       #  Push the input-array again
          ß      #  Wrap all three pairs into a list: [[(a+1)//phi,b],[(b+1)//phi,a],[a,b]]
           m     # Map over the inner lists,
            Å    # using the following two characters as inner code-block:
             ε*  #  Take the product of this inner pair: [(a+1)//phi*b,(b+1)//phi*a,a*b]
               Σ # Sum all three values together: (a+1)//phi*b+(b+1)//phi*a+a*b
                 # (after which the entire stack is output implicitly as result)