Etydhv

I have written a Python program to check for Armstrong numbers in a certain range.

An Armstrong number of three digits is an integer such that the sum of the cubes of its digits is equal to the number itself. For example, 371 is an Armstrong number since 3**3 + 7**3 + 1**3 = 371.

Here is my code:

lower = int(input("Enter lower range: "))
upper = int(input("Enter upper range: "))

for num in range(lower, upper + 1):

 order = len(str(num))

 sum = 0

 temp = num
 while temp > 0:
 digit = temp % 10
 sum += digit ** order
 temp //= 10

 if num == sum:
 print(num)

Here is an example output:

Enter lower range: 200
Enter upper range: 5000

370
371
407
1634

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Names

Using sum as a variable name is not adviced as it hides the sum builtin. I'd suggest sum_pow as an alternative.

Also, temp does not convey much information. I'd use remaining even though I am not fully convinced.

Extracting digits from a number

You've used divisions and modulo to compute the different digits for a number. You can use divmod which is a pretty unknown builtin which returns the result for both operations in one go.

That would give:

 remaining = num
 while remaining:
 remaining, digit = divmod(remaining, 10)
 sum_pow += digit ** order

Also, a better alternative would be to avoid doing this ourselves: extracting the different digits is pretty much what str does for us. Also, we already call it anyway, we could make the most out of it and reuse the result.

 num_str = str(num)
 order = len(num_str)
 sum_pow = 0
 for digit in num_str:
 sum_pow += int(digit) ** order

More builtins

Disclaimer: next comment may be a bit overwhelming for a beginner. Don't worry, just take your time and read documentation online if need be.

We've already delegated most of the hard work to Python builtins but we can go further. The summing part could be handled by the sum builtin along with generator expressions.

for num in range(lower, upper + 1):
 num_str = str(num)
 order = len(num_str)
 sum_pow = sum(int(digit) ** order for digit in num_str)
 if num == sum_pow:
 print(num)

Going further

A few other things could be improved from an organisation point of view:

• split the code in functions


• use the if name == "main" check

Going even further, we could write unit tests for the logic.

Python has a good standart module for work with decimal numbers: decimal. Your code (still C/C++-style) can be replaced with this code:

import decimal

# A separated function to check if the number is Armstrong number
def is_armstrong(number):
 # Get tuple of number digits
 num_digits = decimal.Decimal(number).as_tuple().digits
 # Return the result of check if it is an Armstrong number
 return number == sum(d ** len(num_digits) for d in num_digits)

lower = int(input("Enter lower range: "))
upper = int(input("Enter upper range: "))

for num in range(lower, upper):
 if is_armstrong(num):
 print(num)

About perfomance:

I checked how long your code works for one million numbers:

import datetime

t1 = datetime.datetime.now()
for num in range(1, 1000000):
 order = len(str(num))
 sum_ = 0
 temp = num
 while temp > 0:
 digit = temp % 10
 sum_ += digit ** order
 temp //= 10
 if num == sum_:
 q = num
t2 = datetime.datetime.now()
str(t2-t1)

And it returns me:

'0:00:02.568923'

Two and the half seconds. I think it is not the program one should think about perfomance. Moreover, the complexity of each is_armstrong() call is O(log(N)) (we summarize powers O(1) of digits O(log(N))) for each number so the result complexity is O(N log(N)). For one BILLION numbers this script will work less than hour! It is uncomparable with, for example, some kind of graph algorithms with O(N^3 E^2) complexity that works for days and every little improvement can save literally hours of CPU working.

P.S. If you can't understand what I am talking about, check this article in Wikipedia.

I'm going to focus on the performance aspect, as I believe other parts already have good answers. While the program may be simple and performant, it is still fun to go in and micro-optimize a little. In general I would recommend against it.

Here is your code put into a function to make it clear what changes in the future. I've made the function return the numbers since that was easier for me to work with. I don't have anything new that I would suggest changing.

def armstrong(lower, upper):
 armstrong_numbers = []
 for num in range(lower, upper + 1):
 order = len(str(num))
 sum = 0

 temp = num
 while temp > 0:
 digit = temp % 10
 sum += digit ** order
 temp //= 10

 if num == sum:
 armstrong_numbers.append(num)

 return armstrong_numbers

Precompute

A google search says another name for these numbers are narcissistic numbers and that there are only a finite number of them (88 to be exact). We could make a list of the numbers, loop over the list and return the numbers between lower and upper. This only works if someone else has done the work and generated all the numbers already.

Precompute a little

The above point could be useful though, the first 9 armstrong numbers are the numbers 1 through 9. Let's "precompute" as many of those as we need. We should really add a check to make sure lower <= upper, but alas...

def armstrong(lower, upper):
 cutoff = min(10, upper + 1)
 armstrong_numbers = list(range(lower, cutoff))
 if lower < 10:
 lower = 10

 for num in range(lower, upper + 1):
 order = len(str(num))
 sum = 0

 temp = num
 while temp > 0:
 digit = temp % 10
 sum += digit ** order
 temp //= 10

 if num == sum:
 armstrong_numbers.append(num)

 return armstrong_numbers

Optimize the powers

Another good point that showed up when googling armstrong numbers is that no number bigger than 1060 can be an armstrong number. This means we can work out every possible answer for digitorder ahead of time and reuse it each loop. This should be useful as I think computing arbitrary powers is not as fast as looking up the answer in a table.

As plainly as I can state it, there are only 10 digits, and order is at most 60, so we can make a table 10 * 60 big that stores all the answers to digit**order and use that instead.

def armstrong(lower, upper):
 cutoff = min(10, upper + 1)
 armstrong_numbers = list(range(lower, cutoff))
 if lower < 10:
 lower = 10

 powers_table = [[d ** n for d in range(10)] for n in range(60)]

 for num in range(lower, upper + 1):
 order = len(str(num))
 row = powers_table[order] # We only care about one row of the table at a time.
 sum = 0

 temp = num
 while temp > 0:
 digit = temp % 10
 sum += row[digit]
 temp //= 10

 if num == sum:
 armstrong_numbers.append(num)

 return armstrong_numbers

Check less numbers

The last idea that I found online (see section 5) is to skip numbers with certain prefixes. We can guarantee a number will never work if it the sum of all of its digits except the last one is odd.

The reason for this is as follows. Raising a number to a power won't change its parity. In other words if a number x is even, xn is also even. If x is odd xn is also odd. The sum of the digits raised to a power n will have the same parity as the sum of the digits. For example if we have the 3 digit number 18X. The sum of it's digits cubed is 13 (odd) + 83 (even) + X**3 which is the same as 1 (odd) + 8 (even) + X.

Assume the sum of all the digits of an armstrong number excluding the last digit is odd then we have either

(A**n + B**n + C**n + ...W**n) + X**n == odd + X**n == odd if X is even or
(A**n + B**n + C**n + ...W**n) + X**n == odd + X**n == even if X is odd

But if the last digit (X) is even, the sum has to be even it to which it isn't.
If the last digit is odd, the sum has to be odd, but it isn't. Either way, we get a contradiction, so our assumption must be wrong.

The code is a bit messy, but it gives the idea. It agrees with the other snippets above for the query (1, 100000)

def armstrong3(lower, upper): 
 cutoff = min(10, upper + 1) 
 armstrong_numbers = list(range(lower, cutoff)) 
 if lower < 10: 
 lower = 10 

 powers_table = [[d ** n for d in range(10)] for n in range(60)] 

 start, end = lower // 10, upper // 10 
 for leading_digits in range(start, end + 1): 
 if sum(c in "13579" for c in str(leading_digits)) % 2 == 1: 
 # Skip numbers with an odd sum parity 
 continue 

 order = len(str(leading_digits)) + 1 # We will add a last digit later 
 row = powers_table[order] # We only care about one row of the table at a time. 
 sum = 0 

 temp = leading_digits 
 while temp > 0: 
 digit = temp % 10 
 sum += row[digit] 
 temp //= 10 

 for last_digit in range(10): 
 final_total = sum + row[last_digit] 
 if 10 * leading_digits + last_digit == final_total and final_total <= upper: 
 armstrong_numbers.append(num) 

 return armstrong_numbers

Micro-benchmarked locally I get the following

%timeit armstrong(1, 100000)
143 ms ± 104 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit armstrong2(1, 100000)
69.4 ms ± 2.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit armstrong3(1, 100000)
14.9 ms ± 31.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

So the extra tuning was worth it.

Other work

I didn't get around to implementing the ideas at this github project. The code is in java and run with N < 10 at the smallest (above you can see my benchmarks were only for N < 5), so I don't think the performance is anywhere near as good as that code. It would be the next place to go if you are interested in pushing things further.

I looked at using divmod instead of modding and dividing by 10. The performance was worse for me, so I chose not to use it.

%timeit armstrong(1, 100000)
143 ms ± 104 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit armstrong_divmod(1, 100000)
173 ms ± 5.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)