Otdfbt

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 standard module for work with decimal numbers: decimal. Your code (still C/C++-style) can be replaced with this code:

import decimal

# A separate function to check if the number is an 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 performance:

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 returned:

'0:00:02.568923'

Two and a half seconds. I think it is not the sort of code where one should worry about performance. 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 compares favorably 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 aren't familiar with Big O notation, check this article in Wikipedia.

It would save a lot of time to start from the other end, by making the sums first. Notice that a digit combination like (1, 2, 3) is shared by six numbers: 123, 132, 213, 231, 312, 321. They all have the same digit cube sum 1^3 + 2^3 + 3^3 = 36. Your code will iterate over those numbers and recalculate the same sum 6 times.

Instead, you could use the digit combination (1, 2, 3) and calculate the digit cube sum 36 once. Then check if the digits in that sum is a permutation of those in the digit combination - if so, it's an Armstrong number. Then move to the next digit combination (1, 2, 4) to check another six numbers in one fell swoop.

The digit combinations can be iterated over using itertools.combinations_with_replacement. Here's an example that generates all Armstrong numbers of length 1 to 10 (so under 10 billion), running in under 3 seconds on my machine:

from itertools import combinations_with_replacement

armstrongs = []
for length in range(1, 11):
found = []
for digits in combinations_with_replacement(range(10), length):

 # make the digit power sum
 s = sum(pow(d, length) for d in digits)

 # collect the digits of the sum
 temp = s
 sumdigits = []
 while temp:
 temp, d = divmod(temp, 10)
 sumdigits.append(d)

 # compare the two digit groups. Notice that "digits" is already sorted
 if list(digits) == sorted(sumdigits):
 found.append(s)

# the sum-first-method doesn't find Armstrong numbers in order, so
# an additional sorting is thrown in here.
armstrongs.extend(sorted(found))

print(armstrongs)

This could be optimized further, by for example checking if sumdigits has the right length before sorting. You could also check the digit d as it's chopped off from the sum and make sure it exists at all within digits. If not, the two digit groups are clearly different and you can move to the next iteration.

Now, this example doesn't limit the results to a range. But it can quite easily be modified to do so: Check the lengths of the boundary numbers, then use those in the for length in range(1, 11): line to only generate Armstrong numbers of relevant length. So modify the top to:

lower = 400
upper = 15000

lowerlength = len(str(lower))
upperlength = len(str(upper))
armstrongs = []
for length in range(lowerlength, upperlength + 1):

Then generate the numbers as before, and once you have them, filter down:

armstrongs = [n for n in armstrongs if lower <= n <= upper]

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 10⁶⁰ can be an armstrong number. This means we can work out every possible answer for digit^order 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, xⁿ is also even. If x is odd xⁿ 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 1**3 (odd) + 8³ (even) + X³ 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)