Davide Aversa Logo

Mastodon Icon RSS Icon GitHub Icon LinkedIn Icon RSS Icon
Math

The Primes Ancestor Tree

This will be just a small theoretical article on the Primes Ancestor Tree. We will explore the possibility to label a generic tree in such way that it will be possible to verify if a node is an ancestor of another node (or to find the common ancestor of two nodes) just by applying integer arithmetic.

In fact, sometimes ago I was trying to implement some fancy algorithm that, given two nodes from the open list of a search algorithm, finds their common ancestor. While I was doing this I asked myself if it was possible to use prime numbers in order to provide a labeling system that encodes the “descendant” relation of the nodes.

I think that I have found a theoretical system. Even if it can not be used in real-world applications, I had fun playing with it looking for the properties of the resulting labeled tree. So, I thought it could be interesting to share.

The Primes Ancestor Tree

A “Primes Ancestor Tree” spread over an infinite binary tree. In orange, you can see the sequential n-th prime number that multiplies the parent label to compute the child label.
Figure 1. A “Primes Ancestor Tree” spread over an infinite binary tree. In orange, you can see the sequential n-th prime number that multiplies the parent label to compute the child label.

The idea behind this is to use prime numbers in order to reduce that problem into a division remainder problem. For simplicity sake, we will assume a binary tree from now on but you can virtually apply the same idea to a generic tree.

Suppose we have a binary tree. We will label the root of the tree with 1. Then, we want to label the two children. The rule is simple: we label each child with the label of the parent times the n-th prime number. Therefore, in our case, the first child of the root will be labeled with “1 times 2”, that is 2, and the second child will be labeled with “1 times 3”, that is three.

We can continue in this way until the tree is fully labeled. For example, the children of the node labeled “2” will be labeled “2 times 5” (10) and “2 times 7” (14). And so on. You can look at the image above for a more complete example.

The resulting tree is a Primes Ancestor Tree and it will benefit from these three beautiful properties:

  1. Every label in a subtree is divisible by the root of the subtree. For example, just look at the subtree starting from “2”. Every node in this subtree is clearly an even number. Moreover: only this subtree contains even numbers.
  2. **Given a node A and a node B, B is an ancestor of A if and only if `A mod B` is equal to zero. **Or, in other words, only if A is divisible by B. This is just a consequence of the way the tree is constructed: if B is an ancestor of A, then B prime factors will be a strict subset of the prime factors of A.
  3. **Given two random nodes in the tree, the common ancestor is the node labeled with the Greatest Common Divisor of the two nodes. **This is a consequence of the point 2.

This tree is quite fascinating because it is possible to find a lot of beautiful properties in it. Unfortunately, it is not possible to use an ancestor prime tree in practical applications. The size of the label numbers increases fast  and the factorization of these numbers, that is required for the verification of the previous properties, will quickly become unfeasible. However, this can be a nice and fun mathematical construction to play with.

UPDATE 11th April 2016:

Good news! If you apply these concepts to a binary tree and read the labels in breadth-first order you obtain an integer sequence, namely 1, 2, 3, 10, 14, 33, 39, 170, 190, 322, 406, 1023, 1221, 1599… and so on and so forth.

Well, this integer sequence has been added into the On-Line Encyclopedia of Integer Sequences! It is now officially the sequence A268878! This is a tiny but funny achievement!