A390616 Sum of depths of leaves in a complete ternary tree with n nodes.

0, 1, 2, 3, 4, 6, 8, 9, 11, 13, 14, 16, 18, 19, 22, 25, 26, 29, 32, 33, 36, 39, 40, 43, 46, 47, 50, 53, 54, 57, 60, 61, 64, 67, 68, 71, 74, 75, 78, 81, 82, 86, 90, 91, 95, 99, 100, 104, 108, 109, 113, 117, 118, 122, 126, 127, 131, 135, 136, 140

Offset

1,3

Comments

The values are invariant for left-complete and right-complete ternary trees.

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Formula

a(n) = (h-1)*L + (n - M), where h = floor(log_3(2*n - 1)), M = (3^h - 1)/2, L = n - floor((n+1)/3).

Example

For n=5 the tree is as follows and the leaves are 3, 4, 5 with depths a(5) = 1 + 1 + 2 = 4.
       1
     / | \
    2  3  4
   /
  5
For n = 14, there are 9 leaves in total: 8 leaves at depth 2 and 1 leaf at depth 3, so a(14) = 2*8 + 3 = 19.

Mathematica

A390616[n_] := (#-1)*(n - Quotient[n+1, 3]) + n - (3^#-1)/2 & [IntegerLength[2*n-1, 3] - 1];
Array[A390616, 100] (* Paolo Xausa, Jan 13 2026 *)

Prog

(Python)
def a(n):
    if n <= 1: return 0
    h = 0
    while (3**(h+1) - 1) // 2 < n:
        h += 1
    M = (3**h - 1) // 2
    L = n - (n + 1) // 3
    return (h-1)*L + (n - M)

Crossrefs

Cf. A003462 (nodes in perfect ternary tree), A213511 (total depths all nodes).

Cf. A392221 (binary tree).

Sequence in context: A084829 A018649 A341159 * A374177 A214977 A135676

Adjacent sequences: A390613 A390614 A390615 * A390617 A390618 A390619

Keyword

nonn,easy

Author

Kaloian Ivanov, Jan 04 2026

Status

approved