Integers with a maximal number of Fibonacci representations

Authors
Publication Date
Source
Legacy

Abstract

ita0432.dvi RAIRO-Inf. Theor. Appl. 39 (2005) 343-359 DOI: 10.1051/ita:2005022 INTEGERS WITH A MAXIMAL NUMBER OF FIBONACCI REPRESENTATIONS Petra Koca´bova´1, Zuzana Masa´kova´1 and Edita Pelantova´1 Abstract. We study the properties of the function R(n) which deter- mines the number of representations of an integer n as a sum of distinct Fibonacci numbers Fk. We determine the maximum and mean values of R(n) for Fk ≤ n < Fk+1. Mathematics Subject Classification. 11A67, 11B39. 1. Introduction Let (Fk)k≥0 be the Fibonacci sequence defined by F0 = F1 = 1 , Fk+1 = Fk + Fk−1 for k ≥ 1. Every positive integer n can be written as a sum of distinct Fibonacci numbers, i.e. in the form n = Fmr + Fmr−1 + · · ·+ Fm1 , where mr > mr−1 > · · · > m1 ≥ 1. (1) The expression (1) is called a representation of the number n in the Fibonacci number system. The index of the maximal Fibonacci number that appears in the representation of n is called the length of the representation. Every Fibonacci representation can be written in the form of a finite word w = wmrwmr−1 . . . w1 in the alphabet {0, 1}, where wi = 1 for i = m1, . . . ,mr, and wi = 0 otherwise. For example the number n = 32 can be represented as 32 = 21 + 5 + 3 + 2 + 1 = F7 + F4 + F3 + F2 + F1 Keywords and phrases. Fibonacci numbers, Zeckendorf representation. 1 Department of Mathematics, FNSPE, Czech Technical University, Trojanova 13, 120 00 Praha 2, Czech Republic; petra.kocabova@centrum.cz, masakova@km1.fjfi.cvut.cz, pelantova@km1.fjfi.cvut.cz c© EDP Sciences 2005 344 P. KOCA´BOVA´, Z. MASA´KOVA´ AND E. PELANTOVA´ and this representation corresponds to the word 1001111. Due to the recurrence relation for Fibonacci numbers, different representations of the number n can be obtained by substituting the string 011 by 100 and vice versa. All representations of 32 correspond to words 1010100, 1010011, 1001111, 111111. The number of different Fibonacci representations of n will be denoted by R(n). Let us enumerate the firs

Seen <100 times