A375492 Number of compositions of n into powers of two that each divide the sum of previous powers.

1, 1, 2, 2, 5, 5, 10, 10, 26, 26, 52, 52, 130, 130, 260, 260, 677, 677, 1354, 1354, 3385, 3385, 6770, 6770, 17602, 17602, 35204, 35204, 88010, 88010, 176020, 176020, 458330, 458330, 916660, 916660, 2291650, 2291650, 4583300, 4583300, 11916580, 11916580

Offset: 0

Author

David Eppstein, Aug 17 2024

Keywords

• nonn

Comments

If n = 2^k, a(n) = A003095(k). Otherwise, a(n) is the product of terms from A003095 corresponding to the powers of two in the binary representation of n. If n is odd, the final term of the composition must be 1, so a(n) = a(n-1).

Pieter Mostert points out that, after the first two values, this is a subsequence of A000404 (sums of two nonzero squares), because each term is either a square + 1 or a product of two earlier terms.

Examples

			For n = 4 the a(4) = 5 compositions are 1+1+1+1, 1+1+2, 2+1+1, 2+2, and 4. The composition 1+2+1 is not allowed, because 2 does not divide the sum of previous terms.
		

Crossrefs

Cf. A023359, A003095.

Formula

Let p be the largest power of two less than n; then a(n) = a(p)a(n-p) if n is not a power of two, or a(n) = a(p)^2 + 1 if n is a power of two.