Congruence properties of the function that counts compositions into powers of 2

Alkauskas, Giedrius

Journal of integer sequences, Tome 13 (2010) no. 5

Résumé

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.

Détail

Classification : 11P83, 11P81, 05A17
Keywords: binary compositions, ordered partitions, congruence properties, 2-adic analysis (Concerned with sequences and )