You are trying to solve a Project Euler problem by brute force. That may work for the first few problems, but for most problems you need think of a more sophisticated approach.
Since it is IMHO not OK to give advice specific to this problem, take a look at the general advice in this answer.
As @starblue says, giving advice on solving this specific problem is against the spirit of Project Euler. Optimizations to your Python code, on the other hand...
Instead of throwing out numbers not divisible by nine, why not iterate through them in steps of 9?
for i in range(0, 10 ** maxpower - 1, 9):
...
Also this isn't really any faster but you could write the summations more Pythonic-ly using list comprehensions:
sum1 = sum(int(j) for j in str(i))
sum2 = sum(int(j) for j in str(137 * i))
Hello Folks,
I searched and got to optimize that we must iterate over steps of 9.
But still to reach 10**17 it would take a long time. Can anyone provide a help in this direction or any kind of HINT.
First of all, and the most important aspect of the problem is to count, not to show the numbers. That is very important. All you have to do is to calculate it. Like Jon Bentley wrote in Programming Pearls: "Any methond that considers all permutations of letters for a word is doomed to failure". In fact, I tried in python, as soon as "i" hit 10*9, the system already freezed. 1.5 G memory was consumed. Let alone 10*18. And this also tells us, cite Bentley again, "Defining the problem was about ninety percent of this battle."
One solution to the problem is, we go from 0-9 then 10-99 then 100-999 and so on and extract the signatures of the numbers, summarize numbers with the same signature and deal with all of them as a piece, thus save space and time.
Observation: 3 * 137 = 411 and 13 * 137 = 1781. Compare them two, we see that out of the number 411, the 41 part is going into the second calculation. Let's call 41 the carry, the first element of the signature. The 1 of 411 remains constant no matter if we are gonna calculate 13, 23, 33 or 43. The difference between our 3 and 1(last digit of 411) is 2 (diff), the second element of the signature.
OK, if we are gonna find a two-digit number with the last one fixed to be 3, we have to find a digit that satisfies diff_of_digitsum (digit, 137*digit+carry) = -2. For example, in our case we tried digit 1. diff_of_digitsum (digit, 137*digit+carry) = diff_of_digitsum (1, 137*1+41) = -15. Which is not -2, so 13 is not one of the numbers. Let's see 99. 9 * 137 = 1233. The diff between our 9 and 3 (last digit of 1233) is 6. Carry is 123. In the second iteration when we try to add a digit 9 to 9 and make it 99, we have diff_of_digitsum (digit, 137*digit+carry) = diff_of_digitsum (9, 137*9+123) = diff_of_digitsum (9, 1356) = -6 and this is it! So 99 is the number!
In code, we can go over the 18 digits one by one. Make a table that contains the following three elements: the diff, the carry and the amount of numbers n that share the same signatures. The initial item in the table will be from the number 0. 0* 137 = 0, diff 0 and carry 0. Then we go over the digit 0-9 against all table items to see if their diff_of_digitsum (digit, 137*digit+carry) == -diff just as above, if yes, it means this digit is OK for all those n numbers from the last iteration. Hence counting not showing. And then we can calculate the new diff and carry with this digit added, like in the example 9 has diff 6 and carry 123 but 99 has the diff 9 - 6 ( last digit from 1356) = 3 and carry 135, replace the old table using the new info.
Last comment, be careful the digit 0. It will appear a lot of times in the iteration and don't over count it because 0009 = 009 = 09 = 9. If you use c++, make sure the sum is in unsigned long long and that sort because it is big. Good luck.