1
$\begingroup$

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$.

$\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$ Nov 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$ Nov 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$ Nov 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$ Nov 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$ Nov 24, 2014 at 21:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.