Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3667
Articles: 2'599'751
Articles rated: 2609

07 February 2025
 
  » arxiv » 1608.8764

 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
AbstractZeckendorf 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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.






ScienXe.org
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2025 - Scimetrica