Robert Eisele
Engineer, Systems Architect and DBA

Connectedness of tree height, b-adic numbers and repunits

The cool thing about math is that abstraction allows us to see similar patterns where we wouldn't expect them to be. A quite trivial but in the same way amazing thing connects number systems, trees, combinatorics and repunits.

Complete Trees

A complete search tree with branching factor \(b\) has 1 node at the root, \(b\) nodes beneath the root node and since every node will have \(b\) child nodes again until it's a leaf, the number of elements at height \(k\) is \(b^k\). If we want to find the total number of nodes in the tree we get to

\[s_n = \sum\limits_{k=0}^n b^k\]

Binary unit system

If we have a complete binary search tree, what we actually do is summing over the positions of a number in base two, where all digits are one, meaning that for all \(a_i=1\) in

\[s_n = \sum\limits_{k=0}^n a_i\cdot 2^k\]

b-adic unit system

For a general base \(b\) we can sum over all the positions in the number and arrive at

\[\begin{array}{rrl}& s_n =\sum\limits_{k=0}^n b^k &= 1+b+b^2+...+b^n\\\Leftrightarrow & b\cdot\sum\limits_{k=0}^n b^k &= b+b^2+b^3+...+b^{n+1}\\\Leftrightarrow & \sum\limits_{k=0}^n b^k - b\cdot\sum\limits_{k=0}^n b^k &= (1+b+b^2+...+b^n)- (b+b^2+b^3+...+b^{n+1})\\\Leftrightarrow & (1-b)\cdot\sum\limits_{k=0}^n b^k &= 1-b^{n+1}\\\Leftrightarrow & \sum\limits_{k=0}^n b^k &= \frac{1-b^{n+1}}{1-b}\\\end{array}\]

which is the famous partial geometric series, which was already known by Euclid. Now the interesting thing. For a problem I needed to construct a \(n\) digit number of all 1. Intuitively this can be done by calculating \(10^n\), subtracting one to get n nines and divide by 9, or more formally \(\frac{10^n-1}{9}\). This can be expressed differently as \(\sum\limits_{i=0}^{n-1}10^k\) and is called repunit, since it repeats the unit of a base \(n\) times.

To make a long story short - the conclusion from all that is, that a partial geometric series with base \(b\) and a completely filled tree with branching factor \(b\) are all just repunits, which means that they all are just a number with all 1 in base \(b\).

You might also be interested in the following

 

Sorry, comments are closed for this article. Contact me if you want to leave a note.