A013583 -id:A013583 - cp's OEIS frontend

A000119 Number of representations of n as a sum of distinct Fibonacci numbers.

1, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 3, 1, 3, 3, 2, 4, 2, 3, 3, 1, 4, 3, 3, 5, 2, 4, 4, 2, 5, 3, 3, 4, 1, 4, 4, 3, 6, 3, 5, 5, 2, 6, 4, 4, 6, 2, 5, 5, 3, 6, 3, 4, 4, 1, 5, 4, 4, 7, 3, 6, 6, 3, 8, 5, 5, 7, 2, 6, 6, 4, 8, 4, 6, 6, 2, 7, 5, 5, 8, 3, 6, 6, 3, 7, 4, 4, 5, 1, 5, 5, 4, 8, 4, 7, 7, 3, 9, 6, 6, 9, 3, 8, 8, 5

Offset: 0

N. J. A. Sloane

Number of partitions into distinct Fibonacci parts (1 counted as single Fibonacci number).
Inverse Euler transform of sequence has generating function Sum_{n>1} (x^F(n) - x^(2*F(n))) where F() are the Fibonacci numbers.
a(n) = 1 if and only if n+1 is a Fibonacci number. The length of such a quasi-period (from Fib(i)-1 to Fib(i+1)-1, inclusive) is a Fibonacci number + 1. The maximum value of a(n) within each subsequent quasi-period increases by a Fibonacci number. For example, from n = 143 to n = 232, the maximum is 13. From 232 to 376, the maximum is 16, an increase of 3. From 376 to 609, 21, an increase of 5. From 609 to 986, 26, increasing by 5 again. Each two subsequent maxima seem to increase by the same increment, the next Fibonacci number. - Kerry Mitchell, Nov 14 2009
The maxima of the quasi-periods are in A096748. - Max Barrentine, Sep 13 2015
Stockmeyer proves that a(n) <= sqrt(n+1) with equality iff n = Fibonacci(m)^2 - 1 for some m >= 2 (cf. A080097). - Michel Marcus, Mar 02 2016

M. Bicknell-Johnson, pp. 53-60 in "Applications of Fibonacci Numbers", volume 8, ed: F. T. Howard, Kluwer (1999); see Theorem 3.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..6765
Federico Ardila, The coefficients of a Fibonacci power series, Fib. Quart. 42 (3) (2004), 202-204.
Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See p. 2.
Jean Berstel, Home Page
Jean Berstel, An Exercise on Fibonacci Representations, RAIRO/Informatique Theorique, Vol. 35, No 6, 2001, pp. 491-498, in the issue dedicated to Aldo De Luca on the occasion of his 60th anniversary.
Pierre Bonardo and Anna E. Frid, Number of valid decompositions of Fibonacci prefixes, arXiv:1806.09534 [math.CO], 2018.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 54.
Leonard Carlitz, Fibonacci Representations, Fibonacci Quarterly, volume 6, number 4, October 1968, pages 193-220, a(n) = R(N).
Sam Chow and Tom Slattery, On Fibonacci partitions, arXiv:2009.08222 [math.NT], 2020.
Sam Chow and Tom Slattery, On Fibonacci partitions, Journal of Number Theory, Volume 225, August 2021, Pages 310-326.
Sam Chow and Owen Jones, On the variance of the Fibonacci partition function, arXiv:2308.15415 [math.NT], 2023.
Michel Dekking and Ad van Loon, Counting base phi representations, arXiv:2304.11387 [math.NT], 2023.
Tom Kempton, The Dynamics of the Fibonacci Partition Function, arXiv:2311.06006 [math.NT], 2023.
David A. Klarner, Representations of N as a sum of distinct elements from special sequences, part 1, part 2, Fib. Quart., 4 (1966), 289-306 and 322.
Ron Knott, Sumthing about Fibonacci Numbers
Neville Robbins, Fibonacci partitions, Fib. Quart. 34 (4) (1996), 306-313.
Jeffrey Shallit, Number theory and formal languages, in D. A. Hejhal, J. Friedman, M. C. Gutzwiller and A. M. Odlyzko, eds., Emerging Applications of Number Theory, IMA Volumes in Mathematics and Its Applications, V. 109, Springer-Verlag, 1999, pp. 547-570. (Eq. 9.2.)
Jeffrey Shallit, Robbins and Ardila meet Berstel, Arxiv preprint arXiv:2007.14930 [math.CO], 2020.
Paul K. Stockmeyer, A Smooth Tight Upper Bound for the Fibonacci Representation Function R(N), Fibonacci Quarterly, Volume 46/47, Number 2, May 2009.
Scott V. Tezlaf, On ordinal dynamics and the multiplicity of transfinite cardinality, arXiv:1806.00331 [math.NT], 2018. See p. 42.

Cf. A007000, A003107, A000121, A080097, A096748. Least inverse is A013583.

a000119 = p $ drop 2 a000045_list where
   p _      0 = 1
   p (f:fs) m = if m < f then 0 else p fs (m - f) + p fs m
-- Reinhard Zumkeller, Dec 28 2012, Oct 21 2011

with(combinat): p := product((1+x^fibonacci(i)), i=2..25): s := series(p,x,1000): for k from 0 to 250 do printf(`%d,`,coeff(s,x,k)) od: # James Sellers, May 29 2000

CoefficientList[ Normal@Series[ Product[ 1+z^Fibonacci[ k ], {k, 2, 13} ], {z, 0, 233} ], z ]
nmax = 104; s = Union@Table[Fibonacci[n], {n, nmax}];
Table[Length@Select[IntegerPartitions[n, All, s], DeleteDuplicates[#] == # &], {n, 0, nmax}] (* Robert Price, Aug 17 2020 *)

a(n)=local(A,m,f); if(n<0,0,A=1+x*O(x^n); m=2; while((f=fibonacci(m))<=n,A*=1+x^f; m++); polcoeff(A,n))

f(x,y,z)=if(xCharles R Greathouse IV, Dec 14 2015

a(A000045(n)) = A065033(n).
a(n) = (1/n)*Sum_{k=1..n} b(k)*a(n-k), b(k) = Sum_{f} (-1)^(k/f+1)*f, where the last sum is taken over all Fibonacci numbers f dividing k. - Vladeta Jovovic, Aug 28 2002
a(n) = 1, if n <= 2; a(n) = a(Fibonacci(i-2)+k)+a(k) if n>2 and 0<=k2 and Fibonacci(i-3)<=kA000045) <= n and k=n-Fibonacci(i). [Bicknell-Johnson] - Ron Knott, Dec 06 2004
a(n) = f(n,1,1) with f(x,y,z) = if xReinhard Zumkeller, Nov 11 2009
G.f.: Product_{n>=1} 1 + q^F(n+1) = 1 + Sum_{n>=1} ( q^F(n+1) * Product_{k=1..n-1} 1 + q^F(k+1) ). - Joerg Arndt, Oct 20 2012
a(A000071(n)) = 1. - Reinhard Zumkeller, Dec 28 2012

More terms from James Sellers, May 29 2000

A083853 Smallest nonnegative integer that can be written as a sum of Fibonacci numbers in n ways, counting 1 twice as Fibonacci number.

Original entry on oeis.org

0, 1, 3, 6, 9, 14, 22, 24, 37, 40, 58, 61, 64, 95, 98, 103, 155, 153, 166, 171, 168, 247, 386, 257, 276, 273, 407, 404, 401, 417, 443, 438, 647, 441, 653, 650, 1011, 705, 674, 708, 1045, 713, 1053, 1048, 1085, 1142, 1051, 1090, 1140, 1153, 1723, 1158, 2661, 1702, 1155, 1710

Offset: 1

R. K. Guy and David W. Wilson, Jun 19 2003

nonn

R. J. Mathar, Table of n, a(n) for n = 1..82

Least inverse of A000121. Cf. A013583.

A000121(a(n)) = n.

A122195 Numbers that are the sum of exactly 3 sets of Fibonacci numbers.

Original entry on oeis.org

8, 11, 13, 14, 18, 19, 22, 23, 30, 31, 36, 38, 49, 51, 59, 62, 80, 83, 96, 101, 130, 135, 156, 164, 211, 219, 253, 266, 342, 355, 410, 431, 554, 575, 664, 698, 897, 931, 1075, 1130, 1452, 1507, 1740, 1829, 2350, 2439, 2816, 2960, 3803, 3947, 4557, 4790, 6154

Offset: 1

Ron Knott, Aug 25 2006, corrected Aug 29 2006

nonn

			8 is the sum of only 3 sets of Fibonacci numbers: {8}, {3,5} and {1,2,5};
11 is the sum of only {3,8}, {1,2,8}, {1,2,3,5}.

G. C. Greubel, Table of n, a(n) for n = 1..1000
M. Bicknell-Johnson & D. C. Fielder, The number of Representations of N Using Distinct Fibonacci Numbers, Counted by Recursive Formulas, Fibonacci Quart. 37.1 (1999) pp. 47 ff.
Ron Knott, Sumthing about Fibonacci Numbers
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1,0,0,1,-1).

Cf. A000045, A000071, A013583, A000119, A122194.

a:=[11,13,14,18,19,22,23,30];; for n in [9..60] do a[n]:=a[n-4]+a[n-8]+1; od; Concatenation([8], a); # G. C. Greubel, Jul 13 2019

R:=PowerSeriesRing(Integers(), 60); Coefficients(R!( (8+3*x+2*x^2+x^3-4*x^4-2*x^5+x^6-5*x^8-3*x^9)/(1 - x-x^4+x^5-x^8+x^9) )); // G. C. Greubel, Jul 13 2019

# first N terms:
series((8+3*x+2*x^2+x^3-4*x^4-2*x^5+x^6-5*x^8-3*x^9)/(x^9-x^8+x^5-x^4-x+1),x,N+1);

CoefficientList[Series[(8+3*x+2*x^2+x^3-4*x^4-2*x^5+x^6-5*x^8-3*x^9)/(1 - x-x^4+x^5-x^8+x^9), {x, 0, 60}], x] (* G. C. Greubel, Jul 13 2019 *)

my(x='x+O('x^60)); Vec((8+3*x+2*x^2+x^3-4*x^4-2*x^5+x^6-5*x^8 -3*x^9)/(1-x-x^4+x^5-x^8+x^9)) \\ G. C. Greubel, Jul 13 2019

((8+3*x+2*x^2+x^3-4*x^4-2*x^5+x^6-5*x^8-3*x^9)/(1 - x-x^4+x^5-x^8+x^9)).series(x, 60).coefficients(x, sparse=False) # G. C. Greubel, Jul 13 2019

G.f.: (8+3*x+2*x^2+x^3-4*x^4-2*x^5+x^6-5*x^8-3*x^9)/(1-x-x^4+x^5-x^8+x^9).
a(n) = a(n-4) + a(n-8) + 1.
a(0)=8, a(1)=11, a(2)=13, a(3)=18, then: a(4n) = A022318(n+3) = 2*A000045(n+5) + A000045(n+3) - 1, a(4n+1) = A022406(n+2) = 4*A000045(n+4) - 1, a(4n+2) = A022308(n+4) = 2*A000045(n+4) + A000045(n+6) - 1, a(4n+3) = 3*A000045(n+4) - 1, for n>=1.
a(n) = a(n-1) +a(n-4) -a(n-5) +a(n-8) -a(n-9). - G. C. Greubel, Jul 13 2019

A046815 Smallest number which can be written as the sum of distinct Fibonacci numbers in n ways and such that the Zeckendorf representation of the number uses only even-subscripted Fibonacci numbers.

Original entry on oeis.org

1, 3, 8, 21, 24, 144, 58, 63, 147, 155, 152, 173, 168, 385, 398, 461, 406, 401, 435, 1215, 440, 1016, 1011, 1063, 1053, 1045, 1066, 2608, 1050, 1139, 1160, 2650, 2642, 1155, 2663, 2807, 2647, 6841, 2969, 2749, 2736, 7145, 2757, 2791

Offset: 1

Marjorie Bicknell-Johnson (marjohnson(AT)earthlink.net)

nonn

Each term is >= corresponding term of A013583, smallest number that can be written as sum of distinct Fibonacci numbers in n ways. Equality holds for n prime, n a Fibonacci number, n a Lucas number as well as some other cases.

			a(9)=147 because 147=F(12)+F(4) and 147 is the smallest such integer having 9 representations: 147=144+3 or 144+2+1 or 89+55+3 or 89+55+2+1 or 89+34+21+3 or 89+34+21+2+1 or 89+34+13+8+3 or 89+34+13+8+2+1 or 89+34+13+5+3+2+1.

Marjorie Bicknell-Johnson, The least integer having p Fibonacci representations (p prime), Fibonacci Quarterly 40 (2002), pp. 260-265.

Cf. A002487, A013583.

A122194 Numbers that are the sum of exactly two sets of Fibonacci numbers.

Original entry on oeis.org

3, 5, 6, 9, 10, 15, 17, 25, 28, 41, 46, 67, 75, 109, 122, 177, 198, 287, 321, 465, 520, 753, 842, 1219, 1363, 1973, 2206, 3193, 3570, 5167, 5777, 8361, 9348, 13529, 15126, 21891, 24475, 35421, 39602, 57313, 64078, 92735, 103681, 150049, 167760, 242785

Offset: 1

Ron Knott, Aug 25 2006

			a(1)=3 as 3 is the sum of just 2 Fibonacci sets {3=Fibonacci(4)} and {1=Fibonacci(2), 2=Fibonacci(3)};
a(2)=5 as 5 is sum of Fibonacci sets {5} and {2,3} only.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
J. Berstel, An Exercise on Fibonacci Representations, RAIRO/Informatique Theorique, Vol. 35, No 6, 2001, pp. 491-498, in the issue dedicated to Aldo De Luca on the occasion of his 60th anniversary.
M. Bicknell-Johnson & D. C. Fielder, The number of Representations of N Using Distinct Fibonacci Numbers, Counted by Recursive Formulas, Fibonacci Quart. 37.1 (1999) pp. 47 ff.
Ron Knott Sumthing about Fibonacci Numbers
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1).

Cf. A000032, A000045, A000071, A000119, A013583, A122195.

a:= function(n)
    if n mod 2=0 then return 2*Fibonacci(Int((n+6)/2)) -1;
    else return Lucas(1,-1, Int((n+5)/2))[2] -1;
    fi;
  end;
List([1..50], n-> a(n) ); # G. C. Greubel, Jul 13 2019

f:=Floor; [(n mod 2) eq 0 select 2*Fibonacci(f((n+6)/2))-1 else Lucas(f((n+5)/2))-1: n in [1..50]]; // G. C. Greubel, Jul 13 2019

fib:= combinat[fibonacci]:
lucas:=n->fib(n-1)+fib(n+1):
a:=n -> if n mod 2 = 0 then 2 *fib(n/2+3) -1 else lucas((n+1)/2+2)-1 fi:
seq(a(n), n=1..50);

LinearRecurrence[{1, 1, -1, 1, -1}, {3, 5, 6, 9, 10, 15}, 40] (* Vincenzo Librandi, Jul 25 2017 *)
Table[If[Mod[n,2]==0, 2*Fibonacci[(n+6)/2]-1, LucasL[(n+5)/2]-1], {n,50}] (* G. C. Greubel, Jul 13 2019 *)

vector(50, n, f=fibonacci; if(n%2==0, 2*f((n+6)/2)-1, f((n+7)/2) + f((n+3)/2)-1)) \\ G. C. Greubel, Jul 13 2019

def a(n):
    if (mod(n,2)==0): return 2*fibonacci((n+6)/2) - 1
    else: return lucas_number2((n+5)/2, 1,-1) -1
[a(n) for n in (1..50)] # G. C. Greubel, Jul 13 2019

a(2n-1) = A000032(n+2) - 1,
a(2n) = 2*A000045(n+3) - 1.
a(2n-1) = A001610(n+2), a(2n) = A001595(n+2).
a(1)=3, a(2)=5, a(3)=6, a(4)=9, a(n) = a(n-2) + a(n-4) + 1, n > 4.
G.f.: (3 + 2*x - 2*x^2 + x^3 - 3*x^4)/(1-x-x^2+x^3-x^4+x^5).
a(n) = A272632(n)-1. - R. J. Mathar, Jan 13 2023

cp's OEIS Frontend

A000119 Number of representations of n as a sum of distinct Fibonacci numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A083853 Smallest nonnegative integer that can be written as a sum of Fibonacci numbers in n ways, counting 1 twice as Fibonacci number.

Views

Author

Keywords

Links

Crossrefs

Formula

A122195 Numbers that are the sum of exactly 3 sets of Fibonacci numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A046815 Smallest number which can be written as the sum of distinct Fibonacci numbers in n ways and such that the Zeckendorf representation of the number uses only even-subscripted Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A122194 Numbers that are the sum of exactly two sets of Fibonacci numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A094607 Rectangular array T by antidiagonals: row n consists of the positive integers k for which there are exactly n sets of Fibonacci numbers whose sum is k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A347349 a(n) is the smallest positive integer which can be represented as the sum of distinct Lucas numbers (A000032) in exactly n ways.

Views

Author

Keywords

Crossrefs

A359391 a(n) is the smallest number which can be represented as the sum of n distinct positive Fibonacci numbers (1 is allowed twice as a part) in exactly n ways, or -1 if no such number exists.

Views

Author

Keywords

Examples

Crossrefs