Reversing a number

Question

I was working through a programming challenge I found on Reddit and it seemed easy enough:

Find all numbers less than \$10^n\$ where the number and its reverse (the reverse of \$123\$ is \$321\$) are both divisible by \$7\$ and then sum them all together.

def challenge_229(power):
    numbers = []
    for x in range(0, 10**power, 7):
        if x % 7 == 0 and int(str(x)[::-1]) % 7 == 0:
            numbers.append(x)
    print(sum(numbers))

challenge_229(3) # <-- Change this value.

Which works great for the example input of \$3\$, which results in the output \$10,787\$. However, it does not scale very well at all. To reach the goal requiring 10^11 will not be practical.

I figured the worst part of my program was the int(str(x)[::-1]) % 7 == 0 bit I used to reverse the number, but I'm unsure how I would go about making it more efficient. Does anyone have any ideas how I can optimize my program or think of a way I could solve it with relatively condense code that doesn't use brute force?

Answer 1

There is a better way to implement the design you seem to be using. Rather than generating numbers and storing them in a list, just generate the numbers:

def generate_numbers(power):
    for x in range(0, 10**power, 7):
        if x % 7 == 0 and int(str(x)[::-1]) % 7 == 0:
            yield x

Then do what you want with the generated sequence; e.g.

print( sum(generate_numbers(3)) )

This is more a point of design than optimization, but I imagine it would be faster too.

Answer 2

There are more efficient ways to reverse the digits, but a string reverse is not completely horrible.

I think your most immediate problem is probably the numbers array. There is no need to have that at all. Remove it, and keep a simple sum and accumulate to it:

    if x % 7 == 0 and int(str(x)[::-1]) % 7 == 0:
        sum = sum + x

Arrays and memory allocation are a real problem in any language, and I suspect there's a lot to gain from removing the need entirely.

Oh, now that I look, there's also no need for the x % 7 == 0 either. Your range is carefully constructed so that x will always be a multiple.

Now, having read that reddit thread, there's a lot of other more structural and algorithmic changes you can do.

Answer 3

This can be done in one line using a generator expression:

print(sum(x for x in range(0, 10**power, 7) if not int(str(x)[::-1])%7))

Answer 4

If your range step is 7, then your sequence would be like this:

0, 7, 14, 21, 28, 35, ...

So your x would always be divisible by 7, then checking x%7==0 is redundant.

A normal single processor computer can do about \$10^9\$ instructions per second (if it has multiple cores, a single instance of a Python interpreter can't use it. Search for "python GIL" on Google for more info).

The upper bound of this problem shows us that you can't loop over all number less than \$10^{11}\$ that can be divided by 7, because there are \$\frac{10^{11}}{7}\$ numbers with that property. the instructions for just looping through these numbers is far more than the number that a normal computer can handle in a feasible time.

Checking the reverse of a number that is divisible by 7 to find out whether it is divisible by 7 too, so it satisfies the condition of the problem, is not feasible.

In my opinion, if there is a way to solve this problem, it would be by the construction of such numbers, and not by looping over candidates.

Answer 5

• Don't store the numbers in a list before you sum them up. there is no need to remember this numbers and this will slow down the program considerably and you will use a large amount of storage (that is growing with power) without any reason.

So int(str(x)[::-1]) % 7 == 0 isn't the worst part of your program. But to get a really fast solution you have to implement different algorithms. Such algorithms ( including a link to the solution of the author of the problem) can be found on the page where you found the problem.