Geek Answers Handbook

Effective solution to the letter / number problem in Python

If a = 15 and 152 is represented as a2 , and 215 is represented as 2a , then it is necessary to find the number x so 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 takes a huge amount of time to get the right result.

How to optimize the code?

+8
python math
source share
2 answers

There might be a bit of math here: let x be a natural number with n numbers. Then 8x = 8 * 10 ^ n + x and x8 = 10 * x + 8. Therefore, the equation being solved has the form 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 need 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
+10
source share

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

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

+1
source share

More articles:


All Articles