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

1, 1, 2, 3, 5, 7, 13, 20, 31, 48, 78, 118, 191, 300, 465, 734, 1175, 1850, 2926, 4597, 7296, 11552, 18278, 28863, 45832, 72356, 114742, 181721, 287926, 455748, 722458, 1144370, 1813975, 2873751, 4553643, 7213620, 11432169, 18120733, 28716294, 45491133

Offset: 0

Author

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

Keywords

• nonn
• more

Comments

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, ...

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

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

Examples

			Row 4 of A294442 contains eight fractions: 1/5, 4/5, 3/7, 4/7, 2/7, 2/7, 3/8, 5/8.
There are five distinct numerators, so a(4) = 5.
		

Links

• R. J. Mathar, Java program to compute the sequence
• R. J. Mathar, The Kepler binary tree of reduced fractions
• Don Reble, C++ program for A135510 and A293160

Crossrefs

Cf. A002487, A049456, A070878, A293161, A293165, A293957.

See A135510 for the smallest positive missing number in each row.

Cf. A294442, A294444, A295783 (first differences).

Programs

Maple

A049456 := proc(n, k)
    option remember;
    if n =1 then
        if k >= 0 and k <=1 then
            1;
        else
            0 ;
        end if;
    elif type(k, 'even') then
        procname(n-1, k/2) ;
    else
        procname(n-1, (k+1)/2)+procname(n-1, (k-1)/2) ;
    end if;
end proc: # R. J. Mathar, Dec 12 2014
# A293160. This is not especially fast, but it will easily calculate the first 26 terms and confirm Barry Carter's values.
rho:=n->[seq(A049456(n,k),k=0..2^(n-1))];
w:=n->nops(convert(rho(n),set));
[seq(w(n),n=1..26)];
# Alternative program:
# 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
S[0]:=[[1, 1]]; S[1]:=[[1, 2]];
nc:=[1, 1]; dc:=[1, 1];
for n from 2 to 18 do
S[n]:=[];
for k from 1 to nops(S[n-1]) do
t1:=S[n-1][k];
a:=[t1[1], t1[1]+t1[2]];
b:=[t1[2], t1[1]+t1[2]];
S[n]:=[op(S[n]), a, b];
od:
listn:={};
for k from 1 to nops(S[n]) do listn:={op(listn), S[n][k][1]}; od:
c:=nops(listn);  nc:=[op(nc), c];
listd:={};
for k from 1 to nops(S[n]) do listd:={op(listd), S[n][k][2]}; od:
c:=nops(listd);  dc:=[op(dc), c];
od:
nc; # this sequence
dc; # A294444
# N. J. A. Sloane, Nov 20 2017

Mathematica

Length[Union[#]]& /@ NestList[Riffle[#, Total /@ Partition[#, 2, 1]]&, {1, 1}, 26] (* Jean-François Alcover, Mar 25 2020, after Harvey P. Dale in A049456 *)
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 *)

Python

from itertools import chain, product
from functools import reduce
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

Extensions

a(28)-a(39) from Don Reble, Oct 16 2017

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