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.

  • $\begingroup$ My friend said the numbers had a different name, but he said it was something like Champkowski. $\endgroup$ – Jorge Fernández Hidalgo Feb 24 '15 at 6:23
  • $\begingroup$ @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$. $\endgroup$ – 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).

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.