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

• My friend said the numbers had a different name, but he said it was something like Champkowski. – Jorge Fernández Hidalgo Feb 24 '15 at 6:23
• @DietrichBurde These aren't quite Harshad numbers. An $n$-Harshad number is divisible by the sum of its base-$n$ digits. An $n$-Chapkowski number has base-$n$ digits that sum to a multiple of the base $n$. – Andrew Szymczak Feb 24 '15 at 9:34

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

• Yup. Thats what I did. – Jorge Fernández Hidalgo Feb 24 '15 at 14:52
• @The Emperor: It is a nice problem! – paw88789 Feb 24 '15 at 15:06
• Oh very nice! Way better than my solution, which is awesome because now I don't need to explain myself! – Andrew Szymczak Feb 24 '15 at 18:00
• @Drew: Thanks!! – paw88789 Feb 24 '15 at 18:08

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