cp's OEIS Frontend

A293160 Number of distinct terms in row n of Stern's diatomic array, A049456.

%I A293160 #56 Jul 09 2025 04:45:51
%S A293160 1,1,2,3,5,7,13,20,31,48,78,118,191,300,465,734,1175,1850,2926,4597,
%T A293160 7296,11552,18278,28863,45832,72356,114742,181721,287926,455748,
%U A293160 722458,1144370,1813975,2873751,4553643,7213620,11432169,18120733,28716294,45491133
%N A293160 Number of distinct terms in row n of Stern's diatomic array, A049456.
%C A293160 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 A293160 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
%C A293160 The multiset of terms in row n of Stern's diatomic array, with unique elements counted by a(n), is the same as the multiset of numerators of fractions in row n of Kepler's tree. Indeed, a fraction p/q is in row n-1 of Kepler's tree if and only if p/q and q/p are in row n of Calkin-Wilf tree. To form row n of Stern's diatomic array, one should take either numerators and denominators of fractions less than 1 or all numerators from Calkin-Wilf tree row n, in either case p/q and q/p contribute p and q. In Kepler's tree, a fraction p/q contributes p and q as numerators to the next row, i.e. row n. See A294442 for Kepler's tree and A294444 for the number of distinct denominators in it. - _Andrey Zabolotskiy_, Dec 05 2024
%H A293160 R. J. Mathar, <a href="/A294443/a294443.java.txt">Java program to compute the sequence</a>
%H A293160 R. J. Mathar, <a href="/A294443/a294443.pdf">The Kepler binary tree of reduced fractions</a>
%H A293160 Don Reble, <a href="/A293160/a293160.txt">C++ program for A135510 and A293160</a>
%e A293160 Row 4 of A294442 contains eight fractions: 1/5, 4/5, 3/7, 4/7, 2/7, 2/7, 3/8, 5/8.
%e A293160 There are five distinct numerators, so a(4) = 5.
%p A293160 A049456 := proc(n, k)
%p A293160     option remember;
%p A293160     if n =1 then
%p A293160         if k >= 0 and k <=1 then
%p A293160             1;
%p A293160         else
%p A293160             0 ;
%p A293160         end if;
%p A293160     elif type(k, 'even') then
%p A293160         procname(n-1, k/2) ;
%p A293160     else
%p A293160         procname(n-1, (k+1)/2)+procname(n-1, (k-1)/2) ;
%p A293160     end if;
%p A293160 end proc: # _R. J. Mathar_, Dec 12 2014
%p A293160 # A293160. This is not especially fast, but it will easily calculate the first 26 terms and confirm Barry Carter's values.
%p A293160 rho:=n->[seq(A049456(n,k),k=0..2^(n-1))];
%p A293160 w:=n->nops(convert(rho(n),set));
%p A293160 [seq(w(n),n=1..26)];
%p A293160 # Alternative program:
%p A293160 # S[n] is the list of fractions, written as pairs [i, j], in row n of Kepler's triangle; nc is the number of distinct numerators, and dc the number of distinct denominators
%p A293160 S[0]:=[[1, 1]]; S[1]:=[[1, 2]];
%p A293160 nc:=[1, 1]; dc:=[1, 1];
%p A293160 for n from 2 to 18 do
%p A293160 S[n]:=[];
%p A293160 for k from 1 to nops(S[n-1]) do
%p A293160 t1:=S[n-1][k];
%p A293160 a:=[t1[1], t1[1]+t1[2]];
%p A293160 b:=[t1[2], t1[1]+t1[2]];
%p A293160 S[n]:=[op(S[n]), a, b];
%p A293160 od:
%p A293160 listn:={};
%p A293160 for k from 1 to nops(S[n]) do listn:={op(listn), S[n][k][1]}; od:
%p A293160 c:=nops(listn);  nc:=[op(nc), c];
%p A293160 listd:={};
%p A293160 for k from 1 to nops(S[n]) do listd:={op(listd), S[n][k][2]}; od:
%p A293160 c:=nops(listd);  dc:=[op(dc), c];
%p A293160 od:
%p A293160 nc; # this sequence
%p A293160 dc; # A294444
%p A293160 # _N. J. A. Sloane_, Nov 20 2017
%t A293160 Length[Union[#]]& /@ NestList[Riffle[#, Total /@ Partition[#, 2, 1]]&, {1, 1}, 26] (* _Jean-François Alcover_, Mar 25 2020, after _Harvey P. Dale_ in A049456 *)
%t A293160 Map[Length@ Union@ Numerator@ # &, #] &@ Nest[Append[#, Flatten@ Map[{#1/(#1 + #2), #2/(#1 + #2)} & @@ {Numerator@ #, Denominator@ #} &, Last@ #]] &, {{1/1}, {1/2}}, 21] (* _Michael De Vlieger_, Apr 18 2018 *)
%o A293160 (Python)
%o A293160 from itertools import chain, product
%o A293160 from functools import reduce
%o A293160 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 A293160 Cf. A002487, A049456, A070878, A293161, A293165, A293957.
%Y A293160 See A135510 for the smallest positive missing number in each row.
%Y A293160 Cf. A294442, A294444, A295783 (first differences).
%K A293160 nonn,more
%O A293160 0,3
%A A293160 _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 A293160 a(28)-a(39) from _Don Reble_, Oct 16 2017
%E A293160 a(0) prepended and content related to Kepler's tree added from a duplicate entry (where the terms up to a(28) have been independently obtained by _Michael De Vlieger_) by _Andrey Zabolotskiy_, Dec 06 2024