|
%I #44 Jul 07 2021 11:03:23
%S 1,2,5,13,35,95,259,708,1938,5308,14543,39852,109216,299326,820378,
%T 2248484,6162671,16890790,46294769,126886206,347774063,953191416,
%U 2612541157,7160547089,19625887013,53791344195,147433273080,404090482159,1107545909953,3035602173663
%N Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.
%C 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.
%H Alois P. Heinz, <a href="/A339479/b339479.txt">Table of n, a(n) for n = 1..2285</a>
%F G.f.: x/(1 - x - B(x)) where B(x) is the g.f. of A002572.
%F 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
%e The a(2) = 2 partitions are {1,1} and {1,2}.
%e The a(3) = 5 partitions are {1,1,1}, {1,1,2}, {1,1,4}, {1,2,2}, {1,2,4}.
%e 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}.
%p b:= proc(n, t) option remember; `if`(n=0, 1,
%p `if`(t=0, 0, b(n, iquo(t, 2))+b(n-1, t+2)))
%p end:
%p a:= n-> b(n, 1):
%p seq(a(n), n=1..30); # _Alois P. Heinz_, Apr 27 2021
%t b[n_, t_] := b[n, t] = If[n == 0, 1, If[t == 0, 0, b[n, Quotient[t, 2]] + b[n - 1, t + 2]]];
%t a[n_] := b[n, 1];
%t Table[a[n], {n, 1, 30}] (* _Jean-François Alcover_, Jul 07 2021, after _Alois P. Heinz_ *)
%o (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
%o (Python)
%o from functools import cache
%o @cache
%o def r339479(n, k):
%o if n == 0:
%o return 1
%o elif k == 0:
%o return r339479(n - 1, 1)
%o else:
%o return r339479(n - 1, k + 1) + r339479(n, k // 2)
%o def a339479(n): return r339479(n,0)
%o print([a339479(n) for n in range(1, 100)])
%Y Cf. A002572, A018819, A086449, A174980, A343801.
%K nonn
%O 1,2
%A _Victor S. Miller_, Apr 24 2021
%E Terms a(19) and beyond from _Andrew Howroyd_, Apr 24 2021
|
