Sum of all numbers whose remainder and quotient are the same

Question

This prints out the sum of the numbers that have same remainder and quotient according to the input number. It's an online judge problem, and it currently throws a time-out since it's taking too long. Yes, the number being divided could be any positive integer.

Are there any suggestions on speeding up this code? And are there any small tips or good practice habits that makes Python code faster and more memory efficient?

import sys
n = input()
result = 0
for num in xrange(1, sys.maxint):
    if num % n == num / n:
        result += num

    if num / n > n:
        break
print result

Answer 1

Since this is Code Review, here's a clean-up of your code:

from itertools import count

def sum_numbers_with_equal_quot_rem(divisor):
    result = 0

    for num in count(1):
        if num % divisor == num // divisor:
            result += num

        if num // divisor > divisor:
            break

    return result

sum_numbers_with_equal_quot_rem(40)
#>>> 31980

sys.maxint is the largest int, but not the largest integer, so your loop was broken (although it would have taken a while to find out). This fixes that and makes it Python 3 compatible.

Now, let's add some introspection:

if num % divisor == num // divisor:
    result += num
    print(num % divisor, num // divisor)

and for divisor = 40 we get

1 1
2 2
3 3
4 4
5 5
...
37 37
38 38
39 39

This makes sense as num is fully determined by its divisor and remainder and there must be at least one number with divisor = remainder = k for k in range(1, divisor). There isn't one for 0 or less and there isn't one for divisor or more. This suggest we use:

def sum_numbers_with_equal_quot_rem(divisor):
    result = 0

    for quot_rem in range(1, divisor):
        num = quot_rem * divisor + quot_rem
        result += num

    return result

where num = quot_rem * divisor + quot_rem comes from

help(divmod)
#>>> Help on built-in function divmod in module builtins:
#>>>
#>>> divmod(...)
#>>>     divmod(x, y) -> (div, mod)
#>>>     
#>>>     Return the tuple ((x-x%y)/y, x%y).  Invariant: div*y + mod == x.
#>>>

Namely, the invariant div * y + mod == x.

This gives us an even better option, if we look carefully.

Compare these:

k * divisor + k
(k+1) * divisor + (k+1)

They differ by 1 * divisor + 1. So we are adding up:

$$ 1 \, (\text{divisor} + 1) + 2 \, (\text{divisor} + 1) + \cdots + (\text{divisor} - 1)(\text{divisor} + 1) $$

Letting \$\text{divisor} = d\$, this is just

$$ (d + 1) \sum_{k=1}^{d - 1} k = (d + 1) \left( \frac{1}{2} (d-1) \, d \right) = \frac{d^3 - d}{2} $$

giving the much simpler

def sum_numbers_with_equal_quot_rem(divisor):
    return (divisor**3 - divisor) // 2

sum_numbers_with_equal_quot_rem(40)
#>>> 31980

Answer 2

The answer is always going to be 1*n+1 + 2*n+2 + 3*n+3 + ... + (n-1)*n+(n-1).

So you might as well use the following loop in order to calculate this value:

for i in xrange(1,n):
    result += i*n+i

Note that each term in this series is a multiple of n+1.

Hence the answer can be written as (n+1)*(1+2+3+...+n-1).

Therefore you can calculate it as simple as result = (n+1)*n*(n-1)/2.