A086449 a(0) = 1, a(2n+1) = a(n), a(2n) = a(n) + a(n-1) + ... + a(n-2^m) + ... where a(n) = 0 for n < 0.

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, 1, 48, 18, 36, 8, 60, 16, 32, 4, 80, 26, 52, 8, 78, 16, 32, 2, 104, 34, 68, 12, 110, 24, 48, 4, 136, 36, 72, 8, 108, 16, 32, 1, 154, 48, 96, 18, 160, 36, 72, 8

Offset: 0

Author

Ralf Stephan, Jul 20 2003

Keywords

• nonn
• easy
• look
• tabf

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.

Examples

			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)
		

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.

Crossrefs

Cf. A002487, A086450, A174980.

Programs

Magma

m:=80; R:=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

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 *)

Formula

G.f.: Product_{k>=0} (1 + Sum_{j>=0} x^(2^(k+j))). [Corrected by Herbert S. Wilf, May 31 2006]