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

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

1,2

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

Links

Table of n, a(n) for n=1..39.

Don Reble, C++ program for A135510 and A293160

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)];

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 *)

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

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

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

Sequence in context: A301776 A178570 A294443 * A249309 A250253 A119717

Adjacent sequences: A293157 A293158 A293159 * A293161 A293162 A293163

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

Status

approved