Mi pregunta viene por cortesía de SMBC:
Es curioso, sí, pero me pregunto cómo resolver para fouriest? En otras palabras, dado un número, ¿cómo se calcula la base en la que ese número tendría la mayoría de los cuatros?
Actualización: me doy cuenta de que sólo podría comenzar en la base 5, contar las patas. Verificación de la base 6, el recuento de los cuatro, y así sucesivamente. Es allí una manera más rápida?
He hecho algunas parcelas en Mathematica para buscar patrones, y he encontrado algunos. Escribí un algoritmo que explota un patrón vi. Con este algoritmo, la cantidad de fuerza bruta intenta será reducido a alrededor de $\frac{1}{2}\sqrt{n}$ donde $n$ es el número que estamos tratando de encontrar una fouriest base. Estoy convencido de más rápido algoritmos pueden ser inventado para solucionar este problema, pero este es el mejor que podía hacer en la cantidad de tiempo que desea invertir en un inútil problema de matemáticas :). Tenga en cuenta que no siempre podemos hablar de "la" fouriest base, ya que puede haber más de una base que es la fouriest. Incluso más, si $n=4$, tenemos infinidad de fouriest bases. Supuse que para mi algoritmo, que no es importante que fouriest base se encuentra.
Algoritmo
El algoritmo funciona para $n \ge 44$.
Compruebe si uno de los siguientes números es un número entero, los números representan una base.
Si usted encuentra uno, entonces esta base es un fouriest base, a menos que encuentre una de fourier en el paso 2. Hay dos patas al $n$ está representado en esta base.
Si ninguno de los números de arriba es un entero, $n-4$ es un fouriest base a menos que encuentre una de fourier en el paso 2. El número de $n$ tiene de uno a cuatro cuando es representado en esta base.
Hacer una búsqueda de fuerza bruta para un fouriest base. La base más bajo que tiene que ser tratado es $5$ y el más alto de la base es $\left \lceil \sqrt{n/4-1} \right \rceil - 1$.
Explicación
En primer lugar, todos aquellos raíces cuadradas tienen un significado. La siguiente tabla muestra cuáles son los dígitos de $n$ cuando se escribe en la base dada por la fórmula, si esa base existe (es un número entero). $$ \begin{array}{lcr} n-4 & \text{ gives } & (1,4) \\ n/4 - 1 & \text{ gives } & (4, 4) \\ \sqrt{n} - 2 & \text{ gives } & (1, 4, 4) \\ \sqrt{n/2 - 1} - 1 & \text{ gives } & (2, 4, 4) \\ \sqrt{n/3 - 8/9} - 2/3 & \text{ gives } & (3, 4, 4) \\ \sqrt{n/4-1} & \text{ gives } & (4,0,4) \end{array}$$ Así que el primer paso comprueba si hay una base tal que los dígitos de $n$ $(4, 4)$, $(1, 4, 4)$, $(2, 4, 4)$ o $(3, 4, 4)$. Y si no la hay, se gira de nuevo a la en la base donde se $n$$(1,4)$.
Ahora la gran pregunta es: al hacer la búsqueda por fuerza bruta, ¿por qué no también tratamos de bases mayor que $\sqrt{n/4-1}$? Así que estamos tratando de encontrar una base+dígitos que no está en la tabla anterior en la que $n$ tiene por lo menos dos patas. Tenga en cuenta que el código de cinco dígitos enumeran en la tabla que tiene dos patas en cualquier base ($\ge 5$) el más pequeño de los cinco números que tienen dos patas. Por ejemplo, $(3,4,4) < (4,0,4)$ porque $3b^2 + 4b + 4 < 4b^2 + 4$ por cada $b \ge 5$. Así, con el fin para encontrar una base y/o números que no está en la tabla, tenemos que encontrar dígitos más grande que $(4,0,4)$. Pero, con más dígitos que necesita de una base más baja para mantener el número de la misma. Así dígitos $> (4,0,4)$ base $< \sqrt{n/4-1}$. Y es por eso que no tenemos que tratar de las bases superiores.
Pequeño detalle: La fórmula en el paso 2 es $\left \lceil \sqrt{n/4-1} \right \rceil - 1$ en lugar de $\left \lfloor \sqrt{n/4-1} \right \rfloor$, porque no tenemos para comprobar $\sqrt{n/4-1}$ sí, porque si $\sqrt{n/4-1}$ es un número entero, de $n/4-1$, lo que también produce dos patas, es también, y ya lo hemos comprobado $n/4-1$.
Comentario: hice una lista de los cinco más pequeño de los dígitos de las listas que tienen dos patas. Teóricamente podría añadir más dígitos listas, pero no creo que mejoraría el rendimiento.
El algoritmo no siempre funciona para $n < 44$. Por ejemplo, cuando se $n = 43$ base $9$ es un fouriest base con $43 = (4, 7)$. Sin embargo, el algoritmo calcula el $\sqrt{n/3 - 8/9} - 2/3 = 3$, y concluye que los dígitos de $43$ base $3$$(3,4,4)$, lo que hace una especie de sentido, ya que el $43 = 3 \cdot 3^2 + 4 \cdot 3 + 4$. Para $n \ge 44$, esos problemas no se producen.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
