FANDOM

10,226 Pages

Not to be confused with TREE sequence, or Friedman's finite trees.
Exploding Tree Function
TypeCombinatorial
Growth rate$$f_{\omega+1}(n)$$

The Exploding Tree Function is a fast-growing googological function.[1]

Definition Edit

We have the binary tree T with m left nodes and n right nodes, some constant p and two transformation rules:

• Replace T with a right-branching chain of length (n+p);
• For each of the (n+p) nodes in the new subtree, attach a right-branching chain of length (m-1) as its left child.

The function determines iff becomes a chain of right-branching nodes.

Values Edit

Since writing trees in full is impractical, let f(xLnR,m) is the obtained by the full transform tree with left-branching "length" of x and right-branching "length" of n and constant is m. Then E(n) = f(nL0R,n), a left-branching tree with n nodes and the constant n.

$$E(0) = 0$$
$$E(1) = 1$$
$$E(2) = 2$$
$$E(3) = 6,561$$
$$E(4) > 4 \uparrow^{4 \uparrow\uparrow 4} 4 = \{4,4,\{4,4,2\}\} > \{4,2,1,2\}$$
$$E(5) > \{5,5,\{5,5,\{5,5,3\}\}\} > \{5,3,1,2\}$$
$$E(6) > \{6,6,\{6,6,\{6,6,\{6,6,4\}\}\}\} > \{6,4,1,2\}$$

In general:

$$E(n) > \{n,n-2,1,2\}$$

Comparison with other functions Edit

In the fast growing hierarchy, E(n) is comparable to $$f_{\omega+1}(n)$$, and therefore it exhibits the expandal growth rate.

Sources Edit

1. Exploding Tree Function