Really cute counting problem (Finding the $k$'th $n$-Champkowski number) A friend of mine gave me this problem I wanted to share. We call a positive integer  a $n$-Champkowski number if the sum of its digits in base $n$ is a multiple of $n$. Give the fastest method to find the $k$'th $n$-Chapkowski number you can.
 A: To find the $k$-th Champkowski number in base $n$:
Write $k$ in base $n$ and then right-append a digit to make the resulting number Champkowski.
Example: Find the $59$th base five Champkowski number:  $59=214_{\text{five}}$.  The $59$th base five Champkowski number is $2143_{\text{five}}$.
Reasoning: Any base $n$ number has a unique base $n$ digit that can be right appended to it to form a Champkowski number.  So the first Champkowski number will be $1*$, the second will be $2*$, etc. (where $*$ represents the Champkowski fulfilling digit).
A: I'm guessing there is an easier solution because you called it "cute", but I would do a binary search to find the number of digits. Then a binary search to determine the leading digit. Then a binary search to determine the next digit, and so forth.
It's 4am here so I'll explain it tomorrow, but in short, we are searching for $k$ in the space of Chapkowski numbers, which are easily counted (by inclusion exclusion or generating functions) because they are simply nonnegative integer solutions to  
$$ x_m + x_{m-1} + \ldots + x_1 = \lambda \,n$$  
where each $0 \leq x_i < n$. Note $\lambda \leq m$. So first you double $m$ until you count more than $k$ Chapkowski numbers, then you binary search to find the exact $m$. Then you binary search on the digit $x_m$, which you know is between 0 and $n$ (exclusive). Then, given $x_m$, you subtract it off the right hand side and repeat for $x_{m-1}$. 
A quick (probably wrong) calculation in my head gives an estimate for the computation to be a sum of about $(m^2 \log m + m^4 \log n) \lessapprox \log k \, (\log\log k + \log n)$ binomial coefficients that depend on $n$. So perhaps multiply that by $n^2$.
