OFFSET
0,3
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
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
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
See A135510 for the smallest positive missing number in each row.
KEYWORD
nonn,more
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.
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
STATUS
approved