Esencialmente, la idea detrás de esta solución es que, en lugar de encontrar la cantidad de términos distintos al contarlos, podemos notar que hay 99 * 99 = 9801 términos totales , y contar el número de duplicados. Esto proporciona una solución mucho más eficiente al problema y, de hecho, el cálculo es lo suficientemente simple como para poder imitarlo a mano.
Tenga en cuenta que estos términos duplicados ocurren cuando la base de nuestro exponente es una potencia entera de algún otro número. Por lo tanto, es bastante simple contar cada una de estas ocurrencias. Comenzamos señalando que el máximo exponente posible (que es un duplicado) es 6, cuando 64 = 2 ^ 6.
La función isPerfect comienza verificando potencias más altas para evitar números de doble conteo como 16 como 2 ^ 4 y 4 ^ 2. Por lo tanto haremos lo mismo.
Tenga en cuenta que 64 es el único número entre 2 y 100, que es una sexta potencia de otro número. Luego, inmediatamente tenemos que para b que va de 2 a 50, que 64 ^ b = 8 ^ (2b), por lo que ya hemos encontrado 49 duplicados. Sin embargo, tenga en cuenta también que para números pares del 52 al 66, tenemos 64 ^ b = 16 ^ (6b / 4), y que para múltiplos de 5 de 55 a 80 (omitiendo 60 como ya lo hemos contado en la iteración anterior ), tenemos 64 ^ b = 32 ^ (6b / 5). Por lo tanto, hemos contado 49 + 8 + 5 = 62 duplicados .
- ¿Cuál es la probabilidad de que un elemento permanezca en la misma posición en la matriz de n elementos distintos (por ejemplo, 0..n-1) después de realizar k intercambios aleatorios (el intercambio se realiza como elegir los índices k1 y k2 (k1 <k2) y cambiar un [k1] y un [k2]) en la matriz? Además, ¿cuál es la probabilidad de que la matriz permanezca igual después de estos k intercambios aleatorios?
- Tome cualquier número natural y agregue los dígitos individuales del número. Luego, agregue los dígitos del resultado. Sigue haciendo esto hasta que termines con un número de un solo dígito = x. ¿Son algunos valores de x más probables que otros?
- ¿Existe una fórmula / algoritmo para encontrar el radio de n círculos necesarios para llenar un área cuadrada?
- Álgebra lineal: ¿Es cierta la siguiente afirmación sobre el complemento ortogonal en un campo finito [matemática] Z_q ^ n [/ matemática]?
- ¿Por qué es cierto que si los rectángulos p se cruzan entre sí debe haber una región (tal vez tan pequeña como un punto) donde todos se superponen?
Ahora consideramos los 5tos poderes. Nuevamente notamos que 32 = 2 ^ 5 es la única quinta potencia de otro número en nuestro rango. Así tenemos que para b de 2 a 20, 32 ^ b = 2 ^ 5b. Luego, nuevamente consideramos que se pueden obtener duplicados al darnos cuenta de que para números pares del 22 al 40, 32 ^ b = 4 ^ (5b / 2). También podemos hacer lo mismo para múltiplos de 3 de 21 a 60, como 32 ^ b = 8 ^ (5b / 3), pero debemos tener mucho cuidado de omitir 24,30 y 36 para evitar contar dos veces nuestros duplicados. Del mismo modo, tenemos eso para múltiplos de 4 de 44 a 80 (nuevamente señalando que debemos omitir 48 y 60, ya que ya los hemos contado), 32 ^ b = 16 ^ (5b / 4), y por lo tanto ahora hemos contado 19 + 10 + 11 + 8 = 48 duplicados .
En 4to poderes ahora. Hay dos números de este tipo en este caso, 16 = 2 ^ 4 y 81 = 3 ^ 4; sin embargo, notamos que es suficiente contar los duplicados para un número, y luego simplemente duplicar, ya que 16 ^ b es un duplicado si y solo 81 ^ b es un duplicado para cualquier b. Al igual que con las sextas potencias, este será el caso para b de 2 a 50 (16 ^ b = 4 ^ 2b). Además, para múltiplos de 3 de 51 a 75, tenemos 16 ^ b = 8 ^ (4b / 3). Por lo tanto, hemos contado otros 2 * (49 + 9) = 116 duplicados .
Ahora para cubos perfectos; tenemos dos de estos, 8 = 2 ^ 3 y 27 = 3 ^ 3 (tenga en cuenta que no contamos 64, ya que ya lo hemos abordado como una sexta potencia). Ahora para b del 2 al 33, tenemos 8 ^ b = 2 ^ 3b, y para los números pares del 34 al 66, tenemos 8 ^ b = 4 ^ (3b / 2). De nuevo, estos mismos valores para b proporcionan los mismos duplicados para 27. Por lo tanto, hemos encontrado otros 2 * (32 + 17) = 98 duplicados .
¡Finalmente, tenemos cuadrados perfectos! Nuevamente, omitimos 16,64 y 81 ya que ya los hemos contado, pero todavía tenemos otros 6 cuadrados perfectos (4,9,25,36,49,100). Este caso es simple de contar, los únicos duplicados son de la forma a ^ b = sqrt (a) ^ (2b) para b que van de 2 a 50. Esto nos da 6 * 49 = 294 duplicados .
Sumando todo esto, hemos contado 62 + 48 + 116 + 98 + 294 = 618 duplicados . Luego, encontrar el número de términos distintos es tan simple como 9801-618 = 9183 términos distintos .
Este es esencialmente el mismo proceso por el que pasa el código cuando lo ejecutas (¡excepto que mucho más rápido, por supuesto!)
NOTA : Si bien esta es una solución manuscrita interesante para el problema, cuando resolví esto en la escuela secundaria, encontré el problema mucho más fácil simplemente con la fuerza bruta en Python usando la estructura de datos establecida. ¡Funciona casi instantáneamente y no requiere ningún cálculo agotador a mano! De hecho, mi solución fue tan simple como esta:
data = set ()
para un rango (2,101):
para b en el rango (2,101):
si a ** b no está en datos: data.add (a ** b)
imprimir len (datos)