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