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.
Respuestas
¿Demasiados anuncios?
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).
Andrew Szymczak
Puntos
842
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$.
