login
List pairs (i,j) with 1 <= i <= j in colexicographic order: (1,1), (1,2), (2,2), (1,3), (2,3), (3,3), (1,4), ... Let a(1) = 1. Then for n>=2 if the (n-1)-st pair is (i,j) then a(n) = a(i) + a(j) + 1.
6

%I #16 Feb 06 2024 11:32:09

%S 1,3,5,7,7,9,11,9,11,13,15,9,11,13,15,15,11,13,15,17,17,19,13,15,17,

%T 19,19,21,23,11,13,15,17,17,19,21,19,13,15,17,19,19,21,23,21,23,15,17,

%U 19,21,21,23,25,23,25,27,17,19,21,23,23,25,27,25,27,29,31,11,13,15,17,17

%N List pairs (i,j) with 1 <= i <= j in colexicographic order: (1,1), (1,2), (2,2), (1,3), (2,3), (3,3), (1,4), ... Let a(1) = 1. Then for n>=2 if the (n-1)-st pair is (i,j) then a(n) = a(i) + a(j) + 1.

%C All entries are odd. There are A001190(n) occurrences of 2n-1 in this sequence.

%C a(n) is the number of vertices in the rooted binary tree (every vertex 0 or 2 children) with Colijn-Plazzotta tree number n. - _Kevin Ryde_, Jul 25 2022

%H Kevin Ryde, <a href="/A064002/b064002.txt">Table of n, a(n) for n = 1..10000</a>

%H C. Colijn and G. Plazzotta, <a href="https://doi.org/10.1093/sysbio/syx046">A Metric on Phylogenetic Tree Shapes</a>, Systematic Biology, 67 (1) (2018), 113-126.

%H Kevin Ryde, <a href="/A064002/a064002.gp.txt">PARI/GP Code</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lexicographic_order#Colexicographic_order">Colexicographic order</a>

%F a(n) = 2*A064064(n-1) - 1. - _Kevin Ryde_, Jul 25 2022

%e a(2) = a(1)+a(1)+1 = 3,

%e a(3) = a(1)+a(2)+1 = 5,

%e a(4) = a(2)+a(2)+1 = 7,

%e a(5) = a(1)+a(3)+1 = 7, ...

%o (PARI) See links.

%o (Python)

%o from itertools import count, islice

%o def bgen(): yield from ((i, j) for j in count(1) for i in range(1, j+1))

%o def agen():

%o a, g = [None, 1], bgen()

%o for n in count(2):

%o yield a[-1];

%o i, j = next(g)

%o a.append(a[i] + a[j] + 1)

%o print(list(islice(agen(), 72))) # _Michael S. Branicky_, Jul 25 2022

%Y Cf. A001190, A064064.

%K easy,nonn

%O 1,2

%A Claude Lenormand (claude.lenormand(AT)free.fr), Sep 14 2001