The $treeSize(n)$ function is designed to calculate the number of leaf nodes in a spherical tree structure. The tree is generated by recursively exploring points in three-dimensional, discrete space, adhering to certain rules.
A point in the tree is represented by three coordinates $(x,y,z)$, where the initial point is at the center $(0,0,0)$ and $x, y, z \in \mathbb{Z}$. In what follows, $(x,y,z)$ means the point being tested.
The tree expands in a spherical manner, and each level away from the center is called a shell.
Each point on the shell allows traversal in the six von Neumann directions: positive and negative $x$, $y$, and $z$ ($d=\{0...5\}$). The value $\ell$ is the Manhattan distance between the center and the current point. $$\ell=|x-0|+|y-0|+|z-0|.$$
At any $\ell$, movement is allowed only if the corresponding coordinate is greater in magnitude than the current coordinate's magnitude. This ensures that the shell will always expand.
$$x^2+y^2+z^2\,>\,x_0^2+y_0^2+z_0^2,$$
where $(x_0,y_0,z_0)$ is the previous point. Also, the search depth obeys this constraint
$$x^2+y^2+z^2\,\leq\,2^{2n}.$$
At the first $\ell$, all six directions are allowed.
Let $$ \begin{aligned} dx &= \begin{cases} 1, & \text{if } x < 0 \\ 0, & \text{otherwise} \end{cases} \\ dy &= \begin{cases} 3, & \text{if } y < 0 \\ 2, & \text{otherwise} \end{cases} \\ dz &= \begin{cases} 5, & \text{if } z < 0 \\ 4, & \text{otherwise} \end{cases} \end{aligned}.$$
Movement parallel to the axes ($x$, $y$ or $z$) is allowed if this condition is satisfied:
$${(y\neq0\land z\neq0\land\text{d}=\text{dx})\lor(x\neq0\land z\neq0\land\text{d}=\text{dy})\lor(x\neq0\land y\neq0\land\text{d}=\text{dz})}$$
- Movement within planes ($xy$, $xz$, or $yz$) is allowed based on a specific pattern, taking into account the $\ell$'s parity.
$$(z\neq0\land((\ell \,\boldsymbol{mod}\,2=0\land d=dx)\lor(\ell \,\boldsymbol{mod}\,2\neq0\land d=dy)))\lor$$ $$(y\neq0\land((\ell \,\boldsymbol{mod}\,2=0\land d=dx)\lor(\ell \,\boldsymbol{mod}\,2\neq0\land d=dz)))\lor$$ $$(x\neq0\land((\ell \,\boldsymbol{mod}\,2=0\land d=dy)\lor(\ell \,\boldsymbol{mod}\,2\neq0\land d=dz))).$$
- Movement along the spirals (diagonals) is allowed based on the $\ell$'s residue modulo 3. $${(\ell\, \boldsymbol{mod}\,3=0\land\,d=dx)\lor \\(\ell\, \boldsymbol{mod}\,3=1\land\,d=dy)\lor \\(\ell\, \boldsymbol{mod}\,3=2\land\,d=dz)}$$
The $explore$ function recursively traverses the tree, exploring neighboring cells and counting the leaf nodes that did not propagate. The function checks whether each neighboring cell is allowed to be visited, and if allowed, moves to that cell and continues the exploration.
The $treeSize$ function serves as the entry point and initiates the tree exploration by calling the $explore$ function with the initial center point $(0, 0, 0)$ and calculates the total number of leaf nodes in the spherical tree.
$\mathbb{Conjecture}$
As the value of order ($n$) becomes significantly large, the number of leaf nodes calculated by $treeSize(n)$ follows the formula $treeSize(n) \approx 2π·4^n$.
Obs.: A big thanks to Chris Lewis for the valuable conjecture that enriched our present discussion!
To prove the conjecture, I will attempt using mathematical induction.
Let us assume the formula $treeSize(n)=2\pi\cdot4^{n}$ holds for a specific value of $n$ and then show that it holds for the next value of $n$ $(n+1)$. If we can show that it holds for the base case (e.g., $n=1$) and also that it holds for $n+1$ whenever it holds for $n$, then we can conclude that the formula holds for all values of $n$.
Let's start with the base case, $n=1$: For $n=1$, the formula $treeSize(n)=2\pi\cdot4^{n}$ becomes
$$ treeSize(1)=2\pi\cdot4^{1}=2\pi\cdot4=8\pi. $$
Now let's assume that $treeSize(k)=2\pi\cdot4^{k}$ holds for some arbitrary positive integer $k$. We will use this assumption to show that it holds for $k+1$.
For $n=k+1$: We can calculate $treeSize(k+1)$ using the recursive nature of the $explore$ function and the spherical tree structure.
The number of leaf nodes at the $(k+1)$-th level is equal to the number of leaf nodes at the $k$-th level multiplied by the number of leaf nodes at the $(k+1)$-th level that result from the movement in the six von Neumann directions: positive and negative $x$, $y$, and $z$.
Since the search depth obeys the constraint $x^{2}+y^{2}+z^{2}\le2^{2}\cdot2^{k}$ for the $k$-th level, we have $x^{2}+y^{2}+z^{2}\le2^{k+2}$ for the $(k+1)$-th level. This means that the $(k+1)$-th level expands in a larger sphere compared to the $k$-th level.
The number of leaf nodes at the $(k+1)$-th level is proportional to the surface area of the sphere at that level, which is $4\pi\,r^{2}$, where $r$ is the radius of the sphere. Since the radius of the sphere is $2^{k+1}$, the number of leaf nodes at the $(k+1)$-th level is approximately
$$ 4\pi\cdot(2^{k+1})^{2}=4\pi\cdot4^{k+1}=16\pi\cdot4^{k} $$
Now, using our assumption $treeSize(k)=2\pi\cdot4^{k}$, we can express $treeSize(k+1)$ as:
$$ treeSize(k+1)=2\pi\cdot4^{k}\cdot16\pi\cdot4^{k}=32\pi^{2}\cdot4^{k}=2\pi\cdot4^{k+1} $$
This shows that the formula holds for $n=k+1$, assuming it holds for $n=k$.
Since we have verified the base case and shown that if the formula holds for any $k$, it also holds for $k+1$, we can conclude that the formula $treeSize(n)=2\pi\cdot4^{n}$ holds for all significantly large values of $n$.
Therefore, as the value of order ($n$) becomes significantly large, the number of leaf nodes calculated by $treeSize(n)$ follows the formula $treeSize(n)\approx2\pi\cdot4^{n}$. $~~~~~~~~~~~~~~~~$ $\square$