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

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, 19, 19, 21, 23, 11, 13, 15, 17, 17, 19, 21, 19, 13, 15, 17, 19, 19, 21, 23, 21, 23, 15, 17, 19, 21, 21, 23, 25, 23, 25, 27, 17, 19, 21, 23, 23, 25, 27, 25, 27, 29, 31, 11, 13, 15, 17, 17

Offset: 1

Author

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

Keywords

• easy
• nonn

Comments

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

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

Examples

			a(2) = a(1)+a(1)+1 = 3,
a(3) = a(1)+a(2)+1 = 5,
a(4) = a(2)+a(2)+1 = 7,
a(5) = a(1)+a(3)+1 = 7, ...
		

Links

• Kevin Ryde, Table of n, a(n) for n = 1..10000
• C. Colijn and G. Plazzotta, A Metric on Phylogenetic Tree Shapes, Systematic Biology, 67 (1) (2018), 113-126.
• Kevin Ryde, PARI/GP Code
• Wikipedia, Colexicographic order

Crossrefs

Cf. A001190, A064064.

Programs

PARI

\\ See links.

Python

from itertools import count, islice
def bgen(): yield from ((i, j) for j in count(1) for i in range(1, j+1))
def agen():
    a, g = [None, 1], bgen()
    for n in count(2):
        yield a[-1];
        i, j = next(g)
        a.append(a[i] + a[j] + 1)
print(list(islice(agen(), 72))) # Michael S. Branicky, Jul 25 2022

Formula

a(n) = 2*A064064(n-1) - 1. - Kevin Ryde, Jul 25 2022