| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
07 February 2025 |
|
| | | |
|
Article overview
| |
|
On Summand Minimality of Generalized Zeckendorf Decompositions | Katherine Cordwell
; Max Hlavacek
; Chi Huynh
; Steven J. Miller
; Carsten Peterson
; Yen Nhi Truong Vu
; | Date: |
1 Sep 2016 | Abstract: | Zeckendorf proved that every number can be uniquely represented as a sum of
non-consecutive Fibonacci numbers. This has been extended in many ways,
including to linear recurrences $H_n=c_1 H_{n-1} + cdots + c_t H_{n-t}$ where
the $c_i$ are non-negative integers and $c_1$, $c_t ge 1$. Every number has a
unique generalized Zeckendorf decomposition (gzd) -- a representation composed
of blocks that are lexicographically less than $(c_1,dots,c_t)$, which we call
the signature. We prove that the gzd of a positive integer $m$ uses the fewest
number of summands out of all representations for $m$ using the same recurrence
sequence, for all $m$, if and only if the signature of the linear recurrence is
weakly decreasing (i.e., $c_1 ge cdots ge c_t$). Following the parallel with
well-known base $d$ representations, we develop a framework for naturally
moving between representations of the same number using a linear recurrence,
which we then utilize to construct an algorithm to turn any representation of a
number into the gzd. To prove sufficiency, we show that if the signature is
weakly decreasing then our algorithm results in fewer summands. To prove
necessity we proceed by divide and conquer, breaking the analysis into several
cases. When $c_1 > 1$, we give an example of a non-gzd representation of a
number and show that it has fewer summands than the gzd by performing the same
above-mentioned algorithm. When $c_1 = 1$, we non-constructively prove the
existence of a counterexample by utilizing the irreducibility of a certain
family of polynomials together with growth rate arguments. | Source: | arXiv, 1608.8764 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|