A349552 a(n) is the number of halving partitions of n (see Comments for definition).

1, 1, 1, 2, 1, 3, 2, 3, 1, 3, 3, 5, 2, 5, 3, 4, 1, 4, 3, 6, 3, 7, 5, 7, 2, 6, 5, 8, 3, 7, 4, 5, 1, 4, 4, 7, 3, 9, 6, 9, 3, 9, 7, 12, 5, 11, 7, 9, 2, 8, 6, 11, 5, 12, 8, 11, 3, 9, 7, 11, 4, 9, 5, 6, 1, 4, 4, 8, 4, 10, 7, 11, 3, 11, 9, 15, 6, 15, 9, 12, 3, 10, 9, 16, 7, 18, 12, 17, 5, 15, 11, 18, 7, 15, 9, 11, 2, 8, 8, 14, 6

Offset: 0

Author

Clark Kimberling, Dec 26 2021

Keywords

• nonn
• look

Comments

For m >= 1, let S(m) = { f(m/2), c(m/2) }, where f = floor and c = ceiling. A halving partition of n is a partition p(1) + p(2) + ... + p(k) of n such that p(1) is in S(n) and p(i) is in S(p(i-1)) for i = 2, 3, ..., k. The basic idea is that each term after the first is about half of the preceding term.

Examples

			a(9) = 3 counts these partitions:
  c(9/2) + f(5/2) + (2/2) + c(1/2) = 5 + 2 + 1 + 1;
  c(9/2) + c(5/2) + f(3/2) = 5 + 3 + 1;
  f(9/2) + (4/2) + (2/2) + c(1/2) = 4 + 2 + 1 + 1.
a(13) = 5 counts these partitions:
  c(13/2) + c(7/2) + (4/2) = 7 + 4 + 2;
  c(13/2) + f(7/2) + c(3/2) + (2/2) = 7 + 3 + 2 + 1;
  c(13/2) + f(7/2) + f(3/2) + (2/2) + c(1/2) = 7 + 3 + 1 + 1 + 1;
  f(13/2) + (6/2) + c(3/2) + (2/2) + c(1/2) = 6 + 3 + 2 + 1 + 1;
  f(13/2) + (6/2) + f(3/2) + (2/2) + c(1/2) + c(1/2) = 6 + 3 + 1 + 1 + 1 + 1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..32768

Crossrefs

Cf. A000079, A000225, A028310, A349553.

Programs

PARI

{ a349552(n,p=n) = if(n==0,1,if(n<0||p==0,0,if(p%2,a(n-p\2-1,p\2+1))+a(n-p\2,p\2))); } \\ Max Alekseyev, Sep 30 2024

Formula

From Alois P. Heinz, Sep 30 2024: (Start)

a(A000079(n)) = 1.

a(A000225(n)) = A028310(n). (End)

Extensions

Corrected and extended by Max Alekseyev, Sep 30 2024