|
%I #47 Jun 20 2022 10:11:38
%S 1,2,3,5,7,13,20,31,48,78,118,191,300,465,734,1175,1850,2926,4597,
%T 7296,11552,18278,28863,45832,72356,114742,181721,287926,455748,
%U 722458,1144370,1813975,2873751,4553643,7213620,11432169,18120733,28716294,45491133
%N Number of distinct terms in row n of Stern's diatomic array, A049456.
%C Equivalently, a(n) is the number of distinct terms in row n of the Stern-Brocot sequence (A002487) when that sequence is divided into blocks of lengths 1, 2, 4, 8, 16, 32, ...
%C It would be nice to have a formula or recurrence, or even some bounds. Empirically, a(n) seems to be roughly 2^(2n/3) for the known values. Note that the first half of row n has about 2^(n-2) terms, and the maximal multiplicity is given by A293957(n), so 2^(n-2)/A293957(n) is a lower bound on a(n), which seems not too bad for the known values. - _N. J. A. Sloane_, Nov 04 2017
%H Don Reble, <a href="/A293160/a293160.txt">C++ program for A135510 and A293160</a>
%p A049456 := proc(n, k)
%p option remember;
%p if n =1 then
%p if k >= 0 and k <=1 then
%p 1;
%p else
%p 0 ;
%p end if;
%p elif type(k, 'even') then
%p procname(n-1, k/2) ;
%p else
%p procname(n-1, (k+1)/2)+procname(n-1, (k-1)/2) ;
%p end if;
%p end proc: # _R. J. Mathar_, Dec 12 2014
%p # A293160. This is not especially fast, but it will easily calculate the first 26 terms and confirm Barry Carter's values.
%p rho:=n->[seq(A049456(n,k),k=0..2^(n-1))];
%p w:=n->nops(convert(rho(n),set));
%p [seq(w(n),n=1..26)];
%t Length[Union[#]]& /@ NestList[Riffle[#, Total /@ Partition[#, 2, 1]]&, {1, 1}, 26] (* _Jean-François Alcover_, Mar 25 2020, after _Harvey P. Dale_ in A049456 *)
%o (Python)
%o from itertools import chain, product
%o from functools import reduce
%o def A293160(n): return n if n <= 1 else len({1}|set(sum(reduce(lambda x,y:(x[0],x[0]+x[1]) if y else (x[0]+x[1],x[1]),chain(k,(1,)),(1,0))) for k in product((False,True),repeat=n-2))) # _Chai Wah Wu_, Jun 20 2022
%Y Cf. A002487, A049456, A070878, A293161, A293165, A293957.
%Y See A135510 for the smallest positive missing number in each row.
%K nonn,more
%O 1,2
%A _N. J. A. Sloane_, Oct 12 2017, answering a question raised by Barry Carter in an email message. Barry Carter worked out the first 26 terms.
%E a(28)-a(39) from _Don Reble_, Oct 16 2017
|
