cp's OEIS Frontend

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.

%I A086449 #48 Jan 12 2025 03:08:14
%S A086449 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,
%T A086449 16,1,48,18,36,8,60,16,32,4,80,26,52,8,78,16,32,2,104,34,68,12,110,24,
%U A086449 48,4,136,36,72,8,108,16,32,1,154,48,96,18,160,36,72,8
%N 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.
%C A086449 Conjecture: all a(n) are even except a(2^k-1) = 1. Also a(2^k-2) = 2^(k-1). [For proof see link.]
%C A086449 Setting m=0 gives Stern-Brocot sequence (A002487).
%C A086449 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.
%H A086449 Alois P. Heinz, <a href="/A086449/b086449.txt">Table of n, a(n) for n = 0..10000</a>
%H A086449 Lambert Herrgesell, <a href="/A086449/a086449.txt">Proof of conjecture</a>
%H A086449 Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/SternsDiatomic"> Rational Trees and Binary Partitions</a>.
%F A086449 G.f.: Product_{k>=0} (1 + Sum_{j>=0} x^(2^(k+j))). [Corrected by Herbert S. Wilf, May 31 2006]
%e A086449 From _Peter Luschny_, Sep 01 2019: (Start)
%e A086449 The sequence splits into rows of length 2^k:
%e A086449   1
%e A086449   1,  2
%e A086449   1,  4, 2,  4
%e A086449   1,  8, 4,  8, 2, 12, 4,  8
%e A086449   1, 18, 8, 16, 4, 26, 8, 16, 2, 34, 12, 24, 4, 36, 8, 16
%e A086449   ...
%e A086449 The first few partitions counted are (compare with the list in A174980):
%e A086449 [ 0]  [[]]
%e A086449 [ 1]  [[1]]
%e A086449 [ 2]  [[2], [1, 1]]
%e A086449 [ 3]  [[2, 1]]
%e A086449 [ 4]  [[4], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
%e A086449 [ 5]  [[4, 1], [2, 2, 1]]
%e A086449 [ 6]  [[4, 2], [4, 1, 1], [2, 2, 1, 1], [2, 1, 1, 1, 1]]
%e A086449 [ 7]  [[4, 2, 1]]
%e A086449 [ 8]  [[8], [4, 4], [4, 2, 2], [4, 2, 1, 1], [4, 1, 1, 1, 1], [2, 2, 2, 2],
%e A086449       [2, 2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1]]
%e A086449 [ 9]  [[8, 1], [4, 4, 1], [4, 2, 2, 1], [2, 2, 2, 2, 1]]
%e A086449 [10]  [[8, 2], [8, 1, 1], [4, 4, 2], [4, 4, 1, 1], [4, 2, 2, 1, 1],
%e A086449       [4, 2, 1, 1, 1, 1], [2, 2, 2, 2, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1]]
%e A086449 [11]  [[8, 2, 1], [4, 4, 2, 1]]
%e A086449 [12]  [[8, 4], [8, 2, 2], [8, 2, 1, 1], [8, 1, 1, 1, 1], [4, 4, 2, 2],
%e A086449       [4, 4, 2, 1, 1], [4, 4, 1, 1, 1, 1], [4, 2, 2, 2, 2], [4, 2, 2, 1, 1, 1, 1],
%e A086449       [4, 1, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 1, 1, 1, 1],
%e A086449       [2, 2, 1, 1, 1, 1, 1, 1, 1, 1]]
%e A086449 [13]  [[8, 4, 1], [8, 2, 2, 1], [4, 4, 2, 2, 1], [4, 2, 2, 2, 2, 1]]
%e A086449 [14]  [[8, 4, 2], [8, 4, 1, 1], [8, 2, 2, 1, 1], [8, 2, 1, 1, 1, 1],
%e A086449       [4, 4, 2, 2, 1, 1], [4, 4, 2, 1, 1, 1, 1], [4, 2, 2, 2, 2, 1, 1],
%e A086449       [4, 2, 1, 1, 1, 1, 1, 1, 1, 1]]
%e A086449 [15]  [[8, 4, 2, 1]]
%e A086449 (End)
%p A086449 A086449 := proc(n) option remember;
%p A086449 local IndexSet, k; IndexSet := proc(n) local i, j, z;
%p A086449 i := iquo(n,2); j := i; if odd::n then i := i-1; z := 1;
%p A086449 while 0 <= i do j := j,i; i := i-z; z := z+z od fi; j end:
%p A086449 if n < 2 then 1 else add(A086449(k),k=IndexSet(n)) fi end:
%p A086449 seq(A086449(i),i=0..71); # _Peter Luschny_, May 06 2011
%p A086449 # second Maple program:
%p A086449 a:= proc(n) option remember; local r; `if`(n=0, 1,
%p A086449       `if`(irem(n, 2, 'r')=1, a(r),
%p A086449        a(r) +add(a(r-2^m), m=0..ilog2(r))))
%p A086449     end:
%p A086449 seq(a(n), n=0..80);  # _Alois P. Heinz_, May 30 2014
%t A086449 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 *)
%o A086449 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)))
%o A086449 (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
%Y A086449 Cf. A002487, A086450, A174980.
%K A086449 nonn,easy,look,tabf
%O A086449 0,3
%A A086449 _Ralf Stephan_, Jul 20 2003