Representation of a 2-power as sum of \(k\) 2-powers: a recursive formula
type: Item
instance of: scholarly article
title: Representation of a 2-power as sum of \(k\) 2-powers: a recursive formula
zbMATH Open document ID: 1284.11048
author: Antonio Giorgilli
author: Giuseppe Molteni
published in: Journal of Number Theory
publication date: 2013-02-21T00:00:00Z
review text: Let \(U(\ell,k)\) denote the number of distinct compositions of \(\ell\) as a sum of \(k\) powers of two (where order matters). Thus, for example, \(U(10,3) = 6\), arising from the representations \(10 = 8+1+1\) and \(10 = 4+4+2\) and their permutations. The behavior of \(U(\ell,k)\) is quite erratic; it can be regularized by defining \(W(\sigma, k) = \max_{\ell:s_2(\ell) = \sigma} \{ U(\ell,k) \}\), where \(s_2(\ell)\) is the number of \(1\) bits in the binary representation of \(\ell\). In a previous paper [J. Number Theory 130, No. 9, 2011--2027 (2010; Zbl 1198.11074)], the second author proved that \[ W(\sigma,k) = k! \sum_{1 \leq n < k} {{W(1,n)}\over {n!}} \cdot {{W(\sigma-1,k-n)} \over {(k-n)!}}, \] thus reducing the computation of \(W\) to \(W(1,n)\). In this paper the authors give a recursive formula, involving binomial coefficients, for \(W(1,n)\). From this they derive the congruence \(W(1,n) \equiv 4 + (-1)^n \pmod 8\) for \(n \geq 3\). They also state some conjectures for congruence modulo higher powers of \(2\).
Mathematics Subject Classification ID: 11B75
Mathematics Subject Classification ID: 11A99
zbMATH DE Number: 6138267
zbMATH Keywords: compositions into powers of 2
zbMATH Keywords: sum of digits
zbMATH Keywords: binomial coefficient
zbMATH Keywords: congruence
reviewed by: Jeffrey Shallit
MaRDI profile type: Publication
full work available at URL: j.jnt.2012.09.013
OpenAlex ID: W2153505620
cites work: Lucas' theorem for prime powers
cites work: Q3358798
cites work: Generation and enumeration of all solutions of the characteristic sum condition
cites work: Binomial Coefficients Modulo a Prime
cites work: Q5754490
cites work: Q4377092
cites work: Q5569569
cites work: Cancellation in a short exponential sum
cites work: REPRESENTATION OF A 2-POWER AS SUM OF k 2-POWERS: THE ASYMPTOTIC BEHAVIOR
DOI: 10.1016/J.JNT.2012.09.013
description: scientific article; zbMATH DE number 6138267