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,3

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.

Links

Table of n, a(n) for n=0..41.

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.

Example

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.

Sequence in context: A214795 A287744 A214253 * A306320 A347449 A325347

Adjacent sequences: A375489 A375490 A375491 * A375497 A375498 A375499

Keyword

nonn

Author

David Eppstein, Aug 17 2024

Status

approved