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

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

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

Formula

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

Example

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

Prog

(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

Crossrefs

Cf. A001190, A064064.

Sequence in context: A357274 A307120 A261010 * A195868 A228543 A367928

Adjacent sequences: A063999 A064000 A064001 * A064003 A064004 A064005

Keyword

easy,nonn

Author

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

Status

approved