resolver eficazmente un problema letras/números en Python

Question

Si a = 15 y 152 se representa como a2 mientras 215 se representa como 2a entonces un número x tiene que ser encontrado tal que

8x = 8*x8

probé este Python ingenua código

>>> i = 0 
>>> while(i<=100000000000000000): 
... if(int("8"+str(i))==8*int(str(i)+"8")): 
...  break 
... i = i+1 
... print i 

pero está tardando una gran cantidad de tiempo para producir un resultado correcto.

¿Cómo optimizar el código?

Answer 1

Un poco de matemáticas ayuda aquí: Vamos x ser un número natural n con dígitos. Entonces 8x = 8 * 10^n + x, y x8 = 10 * x + 8. Entonces la ecuación a ser resuelta es 8 * 10^n + x = 8 * (10 * x + 8) = 80 * x + 64 , donde x y n deben ser números naturales. Sigue inmediatamente que x = (8 * 10^n - 64)/79. Ahora solo tenemos que verificar cuál de los números de la forma 8 * 10^n - 64 es divisible por 79, que es muy rápido:

>>> n = 0 
>>> while True: 
...  y = 8 * 10**n - 64 
...  if y % 79 == 0: 
...   x = y/79 
...   break 
...  n += 1 
... 
>>> print x 
101265822784 
>>> print int("8"+str(x))==8*int(str(x)+"8") 
True 

Answer 2

Debería tratar de deshacerse de las conversiones str to int.

En primer lugar 8*int(str(i)+"8") podría escribir como 8*(i*10+8) y la primera parte podría ser cambiado a 8*(int(log(i)/log(10))+1) + i