11
\$\begingroup\$

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?

\$\endgroup\$
  • 3
    \$\begingroup\$ If you want to get your hands dirty with math, I bet there is a closed form solution. \$\endgroup\$ – Hurkyl Sep 1 '15 at 3:06
  • 1
    \$\begingroup\$ I suspect there is a fairly quick way to generate these numbers. If n has an even number of digits and is written as XZ, with an equal number of digits in X and Z, then we know that (X-2Z)%7=(Z-2X)%7=0. If we have an odd number of digits and n can be written as XYZ, with X and Z having an equal number of digits and Y having a single digit(possibly 0) we have that (10X-2Z)%7=(10Z-2X)%7=(-Y)%7. Also if floor(log_10 n) divides 3 then the reverse of n divides 7 if and only if n divides 7. \$\endgroup\$ – Taemyr Sep 1 '15 at 10:34
8
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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))
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Good observation. The Reddit post says that you can solve the problem for N = 10000 in 30 secs so there must be a short cut way of finding the sum of all of the numbers. \$\endgroup\$ – ErikR Sep 1 '15 at 13:30
  • \$\begingroup\$ @ErikR imo any statement "problem x can be solved in n time" that doesn't say anything about the computer it's run on and the context isn't worth much. \$\endgroup\$ – Dannnno Sep 2 '15 at 4:38
  • \$\begingroup\$ You're right, it's not saying anything about the computer, but it is saying a lot about the algorithm. Since a CPU can only execute about 10^9 instructions per second, clearly the algorithm referred to in the Reddit post is not examining all 10^10000 numbers (or even a fraction of that.) \$\endgroup\$ – ErikR Sep 2 '15 at 4:48
3
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.