Journal of Integer Sequences, Vol. 13 (2010), Article 10.5.3

Congruence Properties of the Function that Counts Compositions into Powers of 2

Giedrius Alkauskas
Institute of Mathematics, Department of Integrative Biology
Universität für Bodenkultur
Gregor Mendel-Straße 33
A-1180 Wien


Vilnius University
Department of Mathematics and Informatics
Naugarduko 24
LT-03225 Vilnius


Let $ \vartheta (n)$ denote the number of compositions (ordered partitions) of a positive integer $ n$ into powers of $ 2$. It appears that the function $ \vartheta (n)$ satisfies many congruences modulo $ 2^{N}$. For example, for every integer $ a$ there exists (as $ k$ tends to infinity) the limit of $ \vartheta (2^k+a)$ in the $ 2-$adic topology. The parity of $ \vartheta (n)$ obeys a simple rule. In this paper we extend this result to higher powers of $ 2$. In particular, we prove that for each positive integer $ N$ there exists a finite table which lists all the possible cases of this sequence modulo $ 2^{N}$. One of our main results claims that $ \vartheta (n)$ is divisible by $ 2^{N}$ for almost all $ n$, however large the value of $ N$ is.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000120 A000123 A018819 A023359.)

Received March 4 2010; revised version received April 29 2010. Published in Journal of Integer Sequences, May 3 2010.

Return to Journal of Integer Sequences home page