A375492 - OEIS

%I #11 Aug 18 2024 20:18:42

%S 1,1,2,2,5,5,10,10,26,26,52,52,130,130,260,260,677,677,1354,1354,3385,

%T 3385,6770,6770,17602,17602,35204,35204,88010,88010,176020,176020,

%U 458330,458330,916660,916660,2291650,2291650,4583300,4583300,11916580,11916580

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

%C 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).

%C 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.

%F 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.

%e 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.

%Y Cf. A023359, A003095.

%K nonn

%O 0,3

%A _David Eppstein_, Aug 17 2024