$k$-ary equation: How do I solve for $k$? I’m working on a chess engine and wanted to have a complete set of mathematical formulas to keep track of its progress. Of interest to me is the $k$-ary tree equation: $n=(k^{d+1}-1)/(k-1)$, which I modified to include $m$, the number of moves a side can make in a chess board state ($m$ can vary from $k$ so, adding one to d won’t work in most cases). This gives the modified equation: $n=((k^{d+1}-1)/(k-1))m$.
Using my available knowledge of algebra, I was able to solve for $d: (\log((n(k-1)/m)+1)/\log(k))-1$, which gives me a reasonable estimate of what to expect from the decreasing $k$ in my engine. The smaller the $k$, the deeper the search. What I attempted next was to solve for k and apply it to other engines revealing $n$ and $d$, but not $k$ itself. Barring the arguments of how it’s all relatively meaningless engine to engine, I was hoping for a simple comparison to see how these other pieces of software are faring as they head toward $k=1$. However, I seem to have reached my algebraic limit, and was wondering if the steps could be shown to solve for $k$ (preferably in my modified equation).
 A: You want to solve for $k$ the equation $$\frac{k^{d+1}-1}{k-1}=\frac n m$$ If $d$ is an integer, this reduces to a polynomial equation of degree $(d+1)$ which has no explicit solution if $d>3$ and you will need some numerical method.
For more simplcity in notations, let $a=\frac n m$ (which, I suppose is $>1$).
So, for the most general case, consider that you look for the zero  of function
$$f(k)=k^{d+1}-a\,k +a-1$$ which shows a trivial root $k=1$ of no interest; I  assume that there is another one in the real domain.
The first derivatives of the considered function are
$$f'(k)=(d+1) k^d-a$$
$$f''(k)=d(d+1) k^{d-1}$$
Notice that the second derivative is always positive. On the other side, the first derivative cancels at
$$k_*=\left(\frac a{d+1}\right)^{1/d}$$ If $f(k_*) > 0$ there will not be any solution. 
If there is one root, to approximate it, let us make a Taylor expansion around $k_*$ which will give
$$f(k)=f(k_*)+\frac 1 2 f''(k_*)(k-k_*)^2+O((k-k_*)^3)$$ Ignoring the higher order terms, we can generate an estimate
$$k_0=k_*-\sqrt{-2\frac{f(k_*)}{f''(k_*)}}$$ and Newton method (probably the simplest) will update it according to
$$k_{n+1}=k_n-\frac{f(k_n)}{f'(k_n)}$$
To illustrate it, let us use $d=8$, $a=3$. This would give $$k_*=\frac{1}{\sqrt[8]{3}}\approx 0.871686\qquad f(k_*)=2+\frac{1}{3 \sqrt[8]{3}}-3^{7/8}\approx -0.324495$$ and $$k_0=\frac{1}{\sqrt[8]{3}}-\frac{\sqrt{2\ 3^{7/8}-\frac{9}{2}}}{3\ 3^{9/16}}\approx 0.718156$$ Now, Newton iterates would be
$$\left(
\begin{array}{cc}
 n & k_n \\
 0 & 0.7181555758 \\
 1 & 0.6742939153 \\
 2 & 0.6765631426 \\
 3 & 0.6765676886
\end{array}
\right)$$
All of that can easily be done using Excel or even a programmable calculator.
