Эффективное решение проблемы буквы / цифры в Python

Question

Если a = 15 и 152 представлены как a2, а 215 представлены как 2a, то число x должно быть найдено таким, что

8x = 8*x8

Я попробовал этот наивный код Python

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

но для получения правильного результата требуется огромное количество времени.

Как оптимизировать код?

Answer 1

Здесь немного математики: пусть x будет натуральным числом с n цифрами. Тогда 8x = 8 * 10 ^ n + x и x8 = 10 * x + 8. Таким образом, уравнение, которое необходимо решить, равно 8 * 10 ^ n + x = 8 * (10 * x + 8) = 80 * x + 64 где x и n должны быть натуральными числами. Из этого сразу следует, что x = (8 * 10 ^ n - 64) / 79. Теперь нам осталось только проверить, какое из чисел вида 8 * 10 ^ n - 64 делится на 79, что очень быстро:

>>> 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

Вы должны попытаться избавиться от преобразований str в int.

Прежде всего 8*int(str(i)+"8") можно записать как 8*(i*10+8), а первую часть можно изменить на 8*( int(log(i)/log(10))+1) + i