Sum of Digits, properties, hint please

Question

This is the problem:

How many integers 0 ≤ n < 10^18 have the property that the sum of the digits of n equals the sum of digits of 137n?

This solution is grossly inefficient. What am I missing?

#!/usr/bin/env python
#coding: utf-8

import time
from timestrings import *

start = time.clock()

maxpower = 18
count = 0

for i in range(0, 10 ** maxpower - 1):
    if i % 9 == 0:
        result1 = list(str(i))
        result2 = list(str(137 * i))
        sum1 = 0
        for j in result1:
            sum1 += int(j)
        sum2 = 0
        for j in result2:
            sum2 += int(j)
        if sum1 == sum2:
            print (i, sum1)
            count += 1

finish = time.clock()

print ("Project Euler, Project 290")
print ()
print ("Answer:", count)
print ("Time:", stringifytime(finish - start))

Answer 1

First of all, you are to count, not to show the hits.

That is very important. All you have to do is to device an efficient way to count 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."

And to solve this problem, I can't see a way without dynamic programming (dp). In fact, most of those ridiculously huge Euler problems all require some sort of dp. The theory of dp itself is rather academic and dry, but to implement the idea of dp to solve real problems is not, in fact, the practice is fun and colorful.

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. Let's break the the first result "411" down into two parts: the first two digits "41" and the last digit "1". The "1" is staying, but the "41" part is going to be "carried" to further calculations. Let's call "41" the carry, the first element of the signature. The "1" will stay as the rightest digit as we go on calculating 13 * 137, 23 * 137, 33 * 137 or 43 * 137. All these *3 numbers have a "3" as their rightest digit and the last digit of 137*n is always 1. That is, the difference between this "3" and "1" is +2, call this +2 the "diff" as the second element of the signature.

OK, if we are gonna find a two-digit number with 3 as its last digit, we have to find a digit "m" that satisfies

diff_of_digitsum (m, 137*m+carry) = -2 (1)

to neutralize our +2 diff accumulated earlier. If m could do that, then you know m * 10 + 3, on the paper you write: "m3", is a hit.

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 a hit.

Let's see 99. 9 * 137 = 1233. The "diff" is 9 - 3 = +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 it neutralizes our surplus 6. So 99 is a hit!

In code, we just need 18 iteration. In the first round, we deal with the single digit numbers, 2nd round the 2-digit numbers, then 3-digit ... until we get to 18-digit numbers. Make a table before the iterations that with a structure like this:

table[(diff, carry)] = amount_of_numbers_with_the_same_diff_and_carry

Then the iteration begins, you need to keep updating the table as you go. Add new entries if you encounter a new signature, and always update amount_of_numbers_with_the_same_diff_and_carry. First round, the single digits, populate the table:

0: 0 * 137 = 0, diff: 0; carry: 0. table[(0, 0)] = 1

1: 1 * 137 = 137. diff: 1 - 7 = -6; carry: 13. table[(-6, 13)] = 1

2: 2 * 137 = 274. diff: 2 - 7 = -5; carry: 27. table[(-5, 27)] = 1

And so on.

Second iteration, the "10"th digit, we will go over the digit 0-9 as your "m" and use it in (1) to see if it can produce a result that neutralizes the "diff". If yes, it means this m is going to make all those amount_of_numbers_with_the_same_diff_and_carry into hits. 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.

Answer 2

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.