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

Let $\vartheta (n)$ denote the number of compositions (ordered partitions) of a positive integer

into powers of

. It appears that the function $\vartheta (n)$ satisfies many congruences modulo $2^{N}$ . For example, for every integer

there exists (as

tends to infinity) the limit of $\vartheta (2^k+a)$ in the

adic topology. The parity of $\vartheta (n)$ obeys a simple rule. In this paper we extend this result to higher powers of

. In particular, we prove that for each positive integer

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

, however large the value of

is.

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 Austria and Vilnius University Department of Mathematics and Informatics Naugarduko 24 LT-03225 Vilnius Lithuania

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

and

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