The path to find the $n$-th node within a complete, rooted, ordered $k$-ary tree can be represented by a number to the base $(k+1)$ that contains no zero digits. See A245905 in OEIS as an example for a ternary tree ($k=3$) that gives the path number to find the $n$-th node and uses base $4$ numbers for path directions. In this sequence, the path number to the $5$th, $26$th and $107$th term is (in base $10$ notation) $5$, $26$ and $107$ respectively. Are these $3$ solutions exhaustive for $k=3$? I have checked all nodes up to $10^9$ without further solutions. Are there any know formulas for determining these solutions for a general $k$? Obviously there will always be at least one solution because for each $k$-ary tree the $(k+2)$-th node will have a path number $k+2$.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ A node can either be described by giving the path from the root, as a base $(k+1)$ number $\mathrm{path}(a) = a_0+(k+1)a_1+\cdots+(k+1)^m a_m$ or by its position $\mathrm{pos}(a) = 1 + a_m + \cdots + a_1 k^{m-1} + a_0 k^m$ in a breadth first traversal. You are asking for sequences of digits $a_j\in[1,k]$ such that $\mathrm{path}(a) = \mathrm{pos}(a)$. Clearly, there are only a finite number of $a$ (for a fixed $k$), since $\mathrm{path}(a)$ grows faster. Also, as you said $a=(1,1)$ is such a sequence, giving $k+2$. $\endgroup$– Bruno Le FlochNov 23, 2014 at 3:46
-
$\begingroup$ A simple piece of code solves small values of $k$. For $k=2$: (1,1). For $k=3$: (1,1), (2,2,1), (3,2,2,1). For $k=4$: (1,1), (3,2,2,2,1). For $k=5$: (1,1), (3,3,2), (4,3,4,2), (5,3,4,4,2), (5,1,5,1,5,4,1). For $k=6$: (1,1), (4,5,6,4,2), (5,4,6,6,4,2), (4,2,2,5,1,5,1), perhaps more. $\endgroup$– Bruno Le FlochNov 23, 2014 at 3:51
-
$\begingroup$ @bruno Please explain (or give a reference) why for fixed $k$ there are only a finite number of $a$. Also is there a method for determining whether the values of $a$ found are exhaustive and a search can be halted? $\endgroup$– Frank M JacksonNov 23, 2014 at 8:43
-
1$\begingroup$ With notations as in my first comment, $\mathrm{pos}(a)\leq 1+k+\cdots+k^{m+1} = (k^{m+2}-1)/(k-1) < k^m k^2 / (k-1)$ while $\mathrm{path}(a)\geq (k+1)^m = k^m (1+1/k)^m$. For $m$ large enough, $(1+1/k)^m \geq k^2 / (k-1)$ so $\mathrm{path}(a)>\mathrm{pos}$ and the two cannot be equal. This means that you only need to try all values of $m$ less than $\frac{\log(k^2 / (k-1))}{\log(1+1/k)}$. For $k$ large, this is $\simeq k\log k$. $\endgroup$– Bruno Le FlochNov 23, 2014 at 21:04
-
1$\begingroup$ Using some simple Mathematica code gives two more sequences similar to the $m=1$ solution where $a=(1,1)$ for all k. They are: for $m=2$, $a=(n+1,n,n)$ for all odd $k=2n+1$ with $n>0$ and for $m=3$, $a=(n+2,n+1,2n,n)$ for all odd $k=2n+1$ with $n>0$ $\endgroup$– Frank M JacksonNov 24, 2014 at 21:00
Add a comment
|