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 digitorder 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 1**3 (odd) + 83 (even) + X3 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)
performancetag was necessary as a larger range takes more time to print the output and therefore I needed the code to be as efficient as possible. \$\endgroup\$ – Justin May 22 '19 at 15:46