# Sum of all numbers whose remainder and quotient are the same

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


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.

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


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.