2011/03/01 by Peter J. Grabner, Grabner, Peter J., Wolfgang Steiner +1
Computer Science · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #cs.DM #math.NT
paper · pdf · doi:10.48550/arxiv.1103.0267
arxiv created 2011/03/01 · arxiv updated 2011/03/02
Motivated by multiplication algorithms based on redundant number representations, we study representations of an integer n as a sum n=∑k εk Uk, where the digits εk are taken from a finite alphabet Σ and (Uk)k is a linear recurrent sequence of Pisot type with U0=1. The most prominent example of a base sequence (Uk)k is the sequence of Fibonacci numbers. We prove that the representations of minimal weight ∑k|εk| are recognised by a finite automaton and obtain an asymptotic formula for the average number of representations of minimal weight. Furthermore, we relate the maximal order of magnitude of the number of representations of a given integer to the joint spectral radius of a certain set of matrices.