OFFSET
1,2
COMMENTS
a(n) is the number of n-tuples of nondecreasing integers, which are the exponents of 2 in the partition, the first of which is 0 and which are "reduced". The 1-tuple (0) is reduced. If the tuple is (x(1), ..., x(n)), then it is reduced if (x(1), ..., x(n-1)) is reduced and x(n) <= ceiling(log_2(1 + Sum_{i=1..n-1} 2^x(i))). This sequence arose in analyzing the types of partitions of a positive integer into parts which are powers of 2.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..2285
FORMULA
G.f.: x/(1 - x - B(x)) where B(x) is the g.f. of A002572.
a(n) = F(n,0) where F(0,k) = 1, F(n,0) = F(n-1,1) for n > 0 and F(n,k) = F(n-1,k+1) + F(n, floor(k/2)) for n,k > 0. In this recursion, F(n,k) gives the number of partitions with n parts where the sum of all parts smaller than the current part size being considered is between k and k+1 multiples of the part size. This function is independent of the current part size. In the case that k is zero, the only choice is to add a part of the current part size, otherwise parts of double the size are also a possibility. - Andrew Howroyd, Apr 24 2021
EXAMPLE
The a(2) = 2 partitions are {1,1} and {1,2}.
The a(3) = 5 partitions are {1,1,1}, {1,1,2}, {1,1,4}, {1,2,2}, {1,2,4}.
The a(4) = 13 partitions are {1,1,1,1}, {1,1,1,2}, {1,1,1,4}, {1,1,2,2}, {1,1,2,4}, {1,1,2,8}, {1,1,4,4}, {1,1,4,8}, {1,2,2,2}, {1,2,2,4}, {1,2,2,8}, {1,2,4,4}, {1,2,4,8}.
MAPLE
b:= proc(n, t) option remember; `if`(n=0, 1,
`if`(t=0, 0, b(n, iquo(t, 2))+b(n-1, t+2)))
end:
a:= n-> b(n, 1):
seq(a(n), n=1..30); # Alois P. Heinz, Apr 27 2021
MATHEMATICA
b[n_, t_] := b[n, t] = If[n == 0, 1, If[t == 0, 0, b[n, Quotient[t, 2]] + b[n - 1, t + 2]]];
a[n_] := b[n, 1];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jul 07 2021, after Alois P. Heinz *)
PROG
(PARI) seq(n)={my(v=vector(n), a=vector(n)); a[1]=v[1]=1; for(n=2, n, for(j=1, n-1, v[n-(n-j)\2] += v[j]); a[n]=vecsum(v)); a} \\ Andrew Howroyd, Apr 25 2021
(Python)
from functools import cache
@cache
def r339479(n, k):
if n == 0:
return 1
elif k == 0:
return r339479(n - 1, 1)
else:
return r339479(n - 1, k + 1) + r339479(n, k // 2)
def a339479(n): return r339479(n, 0)
print([a339479(n) for n in range(1, 100)])
CROSSREFS
KEYWORD
nonn
AUTHOR
Victor S. Miller, Apr 24 2021
EXTENSIONS
Terms a(19) and beyond from Andrew Howroyd, Apr 24 2021
STATUS
approved