Efficiently solving a letter/number problem in Python

Question

If a = 15 and 152 is represented as a2 while 215 is represented as 2a then a number x has to be found such that

8x = 8*x8

I tried this naive Python code

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

but it is taking a huge amount of time to produce a correct result.

How to optimize the code?

Answer 1

A bit of math helps here: Let x be a natural number with n digits. Then 8x = 8 * 10^n + x, and x8 = 10*x + 8. So the equation to be solved is 8 * 10^n + x = 8 * (10*x + 8) = 80*x + 64, where x and n must be natural numbers. It immediately follows that x = (8 * 10^n - 64) / 79. Now we only have to check which of the numbers of the form 8 * 10^n - 64 is divisible by 79, which is very fast:

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

You should try to get rid of str to int conversions.

First of all 8*int(str(i)+"8") could be written as 8*(i*10+8) and first part could be changed to 8*( int(log(i)/log(10))+1) + i