How to optimize this Python script which checks if a number is equal to its sum of digits multiplied by a factor?

Question

Looking for insight into how to optimize the speed of a Python script.

Challenge: "Which positive integers are equal to 23 times the sum of their digits" >> this is my functioning code:

def sum_of_digits(number):
    sum = 0;
    for c in number:
        sum += ord(c) - 48;
    
    return sum;

upper_limit = 10000000000;
count = 0;
for i in range(1, upper_limit, 1):
    if(23 * sum_of_digits(str(i)) == i):
        print(i);
        count += 1;

Which correctly spits out 207 as an answer (2+0+7 = 9. 9 x 23 = 207).

Problem is the time for execution scales as (n).

Whilst I can pre calculate the sum_of_digits - this wont save time and am looking for Python methods to speed to execution.

I know I can delve into number theory and "maths" it - but am interested in what I can squeeze out of Python.

Finally, I know other languages might be quicker, but I'm a high school physics teacher using this as a STEM example in a summer class.

Answer 1

First of all, this is Python so you don't need to put ; at the end of statements. Since you are looking for numbers which are multiple of 23, you can gain some performance if you iterate over the numbers that are multiples of 23:

for i in range(0, upper_limit, 23):
    # 'i' will take values 0, 23, 46, ...

And your sum_of_digits function would perform better if you work on ints. Taken from here:

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

So the final code will be:

upper_limit = 10000000000
count = 0
for i in range(0, upper_limit, 23):
    if (23 * sum_digits(i) == i):
        print(i)
        count += 1

print(count)

However, this will still perform in O(n*m) because you have nested loops.

Instead of trying to find such numbers blindly, we can do a little bit math and break the loop.

For 1 digit numbers 23 * sum_digits(i) would be 23 * 9 = 207 at maximum.
For 2 digit numbers 23 * sum_digits(i) would be 23 * 18 = 414 at maximum.
For 3 digit numbers 23 * sum_digits(i) would be 23 * 27 = 621 at maximum.
For 4 digit numbers 23 * sum_digits(i) would be 23 * 36 = 828 at maximum.
For 5 digit numbers 23 * sum_digits(i) would be 23 * 45 = 1035 at maximum.
.
.
.

You can see the pattern here. We actually don't need to search for the numbers which have 4 digits or more. Because all the 4 digit numbers are greater than 828 and all the 5 digit numbers are greater than 1035 etc. So here is a better solution which breaks when we are sure that all the remaining numbers won't be valid.

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

upper_limit = 10000000000
count = 0
for i in range(0, upper_limit, 23):
    number_length = len(str(i))
    if number_length * 9 * 23 < i:
        break
    if 23 * sum_digits(i) == i:
        print(i)
        count += 1

print(count)