Muy lindo el conteo problema (la Búsqueda de la $k$'th $n$-Champkowski número)

Question

Un amigo mío me dio este problema quise compartir. Llamamos a un número entero positivo de una $n$-Champkowski número si la suma de sus dígitos en base $n$ es un múltiplo de a $n$. Dar el método más rápido para encontrar el $k$'th $n$-Chapkowski número puede.

Answer 1

Para encontrar el $k$-th Champkowski número en base $n$:

Escribir $k$ base $n$ y, a continuación, haga anexar un dígito para hacer que el número de Champkowski.

Ejemplo: Hallar el $59$th base de cinco Champkowski número: $59=214_{\text{five}}$. El $59$th base de cinco Champkowski número es $2143_{\text{five}}$.

Razonamiento: Cualquier base $n$ número tiene una única base de $n$ dígitos que puede ser derecho que se anexa a éste para formar un Champkowski número. Así que el primer Champkowski número se $1*$, el segundo va a ser $2*$, etc. (donde $*$ representa la Champkowski el cumplimiento de dígitos).

Answer 2

Estoy suponiendo que hay una solución más fácil porque se llama "lindo", pero me gustaría hacer una búsqueda binaria para encontrar el número de dígitos. A continuación, una búsqueda binaria para determinar que el primer dígito. A continuación, una búsqueda binaria para determinar el dígito siguiente, y así sucesivamente.

Es 4am aquí, así que voy a explicar es mañana, pero en resumen, estamos en la búsqueda de $k$ en el espacio de Chapkowski números, que son fáciles de contado (por la inclusión o exclusión de generación de funciones), ya que son simplemente entero no negativo soluciones a

$$x_m + x_{m-1} + \ldots + x_1 = \lambda \,n$$

donde cada una de las $0 \leq x_i < n$. Nota:$\lambda \leq m$. Así que lo primero es el doble de $m$ hasta que el recuento de más de $k$ Chapkowski números, entonces usted binarios de búsqueda para encontrar exactamente $m$. Entonces una búsqueda binaria en el dígito $x_m$, que usted sabe que está entre 0 y $n$ (exclusivo). Entonces, dado $x_m$, se resta de la mano derecha y repita el proceso para $x_{m-1}$.

Un rápido (probablemente equivocada) de cálculo en mi cabeza da una estimación para el cálculo a ser una suma de alrededor de $(m^2 \log m + m^4 \log n) \lessapprox \log k \, (\log\log k + \log n)$ los coeficientes binomiales que dependen de $n$. Así que tal vez que se multiplican por $n^2$.