OFFSET
0,3
COMMENTS
Conjecture: all a(n) are even except a(2^k-1) = 1. Also a(2^k-2) = 2^(k-1). [For proof see link.]
Setting m=0 gives Stern-Brocot sequence (A002487).
a(n) is the number of ways of writing n as a sum of powers of 2, where each power appears p times, with p itself a power of 2.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000
Lambert Herrgesell, Proof of conjecture
Peter Luschny, Rational Trees and Binary Partitions.
FORMULA
G.f.: Product_{k>=0} (1 + Sum_{j>=0} x^(2^(k+j)). [Corrected by Herbert S. Wilf, May 31 2006]
EXAMPLE
From Peter Luschny, Sep 01 2019: (Start)
The sequence splits into rows of length 2^k:
1
1, 2
1, 4, 2, 4
1, 8, 4, 8, 2, 12, 4, 8
1, 18, 8, 16, 4, 26, 8, 16, 2, 34, 12, 24, 4, 36, 8, 16
.
The first few partitions counted are (compare with the list in A174980):
[ 0] [[]]
[ 1] [[1]]
[ 2] [[2], [1, 1]]
[ 3] [[2, 1]]
[ 4] [[4], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
[ 5] [[4, 1], [2, 2, 1]]
[ 6] [[4, 2], [4, 1, 1], [2, 2, 1, 1], [2, 1, 1, 1, 1]]
[ 7] [[4, 2, 1]]
[ 8] [[8], [4, 4], [4, 2, 2], [4, 2, 1, 1], [4, 1, 1, 1, 1], [2, 2, 2, 2],
[2, 2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1]]
[ 9] [[8, 1], [4, 4, 1], [4, 2, 2, 1], [2, 2, 2, 2, 1]]
[10] [[8, 2], [8, 1, 1], [4, 4, 2], [4, 4, 1, 1], [4, 2, 2, 1, 1],
[4, 2, 1, 1, 1, 1], [2, 2, 2, 2, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1]]
[11] [[8, 2, 1], [4, 4, 2, 1]]
[12] [[8, 4], [8, 2, 2], [8, 2, 1, 1], [8, 1, 1, 1, 1], [4, 4, 2, 2],
[4, 4, 2, 1, 1], [4, 4, 1, 1, 1, 1], [4, 2, 2, 2, 2], [4, 2, 2, 1, 1, 1, 1],
[4, 1, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 1, 1, 1, 1],
[2, 2, 1, 1, 1, 1, 1, 1, 1, 1]]
[13] [[8, 4, 1], [8, 2, 2, 1], [4, 4, 2, 2, 1], [4, 2, 2, 2, 2, 1]]
[14] [[8, 4, 2], [8, 4, 1, 1], [8, 2, 2, 1, 1], [8, 2, 1, 1, 1, 1],
[4, 4, 2, 2, 1, 1], [4, 4, 2, 1, 1, 1, 1], [4, 2, 2, 2, 2, 1, 1],
[4, 2, 1, 1, 1, 1, 1, 1, 1, 1]]
[15] [[8, 4, 2, 1]]
(End)
MAPLE
A086449 := proc(n) option remember;
local IndexSet, k; IndexSet := proc(n) local i, j, z;
i := iquo(n, 2); j := i; if odd::n then i := i-1; z := 1;
while 0 <= i do j := j, i; i := i-z; z := z+z od fi; j end:
if n < 2 then 1 else add(A086449(k), k=IndexSet(n)) fi end:
seq(A086449(i), i=0..71); # Peter Luschny, May 06 2011
# second Maple program:
a:= proc(n) option remember; local r; `if`(n=0, 1,
`if`(irem(n, 2, 'r')=1, a(r),
a(r) +add(a(r-2^m), m=0..ilog2(r))))
end:
seq(a(n), n=0..80); # Alois P. Heinz, May 30 2014
MATHEMATICA
nn=30; CoefficientList[Series[Product[1+Sum[x^(2^(k+j)), {j, 0, nn}], {k, 0, nn}], {x, 0, nn}], x] (* Geoffrey Critzer, May 30 2014 *)
PROG
a(n)=local(k): if(n<1, n>=0, if(n%2==0, a(n/2)+sum(k=0, n, a((n-2^(k+1))/2)), a((n-1)/2)))
(Magma) m:=80; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!( (&*[1 + (&+[x^(2^(k+j)): j in [0..m/4]]): k in [0..m/4]]) )); // G. C. Greubel, Feb 11 2019
CROSSREFS
KEYWORD
AUTHOR
Ralf Stephan, Jul 20 2003
STATUS
approved