A341904 Number of representations of n as a linear combination of positive Fibonacci numbers with coefficients {0,1,2} only.

1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 7, 9, 10, 10, 12, 12, 13, 15, 13, 16, 17, 17, 20, 18, 21, 23, 21, 25, 24, 25, 28, 24, 29, 30, 29, 34, 31, 35, 37, 33, 39, 39, 39, 44, 38, 45, 46, 43, 49, 46, 48, 52, 44, 53, 53, 52, 59, 53, 60, 63, 56, 66, 63, 64, 70, 60, 71

Offset

0,3

Comments

This sequence is "Fibonacci-regular"; there are vectors v, w and matrices M0, M1 (dimension 19) such that a(n) = v M_{a_1} ... M_{a_k} w if a_1 ... a_k is the Fibonacci representation of n. This allows efficient computation of a(n).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..17711

Zuzana Masáková and Élise Vandomme, Redundance in the Signed m-Bonacci Numeration System, J. Integer Sequences 24 (2021), Article 21.7.2.

Example

For n = 5 the 4 representations are 5, 3+2, 3+2*1, 2*2+1.

Maple

h:= proc(n) option remember; `if`((t->
      issqr(t+4) or issqr(t-4))(5*n^2), n, h(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0 or i=1, `if`(n<3, 1, 0),
      add(b(n-i*j, h(min(n-i*j, i-1))), j=0..min(2, n/i)))
    end:
a:= n-> b(n, h(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 04 2021

Mathematica

h[n_] := h[n] = If[IntegerQ@Sqrt[#+4] || IntegerQ@Sqrt[#-4]&[5*n^2], n, h[n-1]];
b[n_, i_] := b[n, i] = If[n == 0 || i == 1, If[n < 3, 1, 0], Sum[b[n-i*j, h[Min[n-i*j, i-1]]], {j, 0, Min[2, n/i]}]];
a[n_] := b[n, h[n]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 08 2022, after Alois P. Heinz *)

Crossrefs

Cf. A000045, A000119, for the sequence where the coefficients are taken from {0,1} instead of {0,1,2}.

Sequence in context: A074239 A248333 A303905 * A237638 A343205 A334483

Adjacent sequences: A341901 A341902 A341903 * A341905 A341906 A341907

Keyword

nonn

Author

Jeffrey Shallit, Jun 04 2021

Status

approved