Как найти все трехзначные числа армстронга питон

Число Армстронга. Числом Армстронга считается натуральное число, сумма цифр которого, возведенных в N-ную степень (N – количество цифр в числе) равна самому числу.
Например, 153 = 1^3 + 5^3 + 3^3.

Можно использовать только циклы и условный оператор, без списков, массивов и.т.д. Я написал вот так:

1
2
3

for i in range(100,1000):
    if i%10**3 + i//10%10**3 + i//100**3 == i:
        print(i)

Но вообще ничего не выводит. Помогите!
P.S у меня от 100 до 1000, потому что я сначала хотел на этом отрезке попробовать.

Михаил

Профи

(754),
закрыт

3 года назад

Натуральное число называется числом Армстронга, если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 13 + 53 + 33. Найдите все трёхзначные Армстронга. На языке Python (Питон) пожалуйста!

Given a number x, determine whether the given number is Armstrong number or not. A positive integer of n digits is called an Armstrong number of order n (order is number of digits) if.

abcd... = pow(a,n) + pow(b,n) + pow(c,n) + pow(d,n) + .... 

Example:

Input : 153
Output : Yes
153 is an Armstrong number.
1*1*1 + 5*5*5 + 3*3*3 = 153

Input : 120
Output : No
120 is not a Armstrong number.
1*1*1 + 2*2*2 + 0*0*0 = 9

Input : 1253
Output : No
1253 is not a Armstrong Number
1*1*1*1 + 2*2*2*2 + 5*5*5*5 + 3*3*3*3 = 723

Input : 1634
Output : Yes
1*1*1*1 + 6*6*6*6 + 3*3*3*3 + 4*4*4*4 = 1634

Time complexity: O((logn)²)

Auxiliary Space: O(1)

Method: A positive integer is called an Armstrong number if an Armstrong number of 3 digits, the sum of cubes of each digit is equal to the number itself. For example, 153 is an Armstrong number because
   153 = 1*1*1 + 5*5*5 + 3*3*3
    The while loop iterates like first, it checks if the number is not equal to zero or not. if it is not equal to zero then enter into the loop and find the reminder of number ex: 153%10 gives reminder 3. In the next step add the cube of a number to the sum1(3*3*3). Then the step gives the quotient of the number (153//10=15). this loop will continue till the given number is equal to zero.
 

The given number 153 is armstrong number

Please refer complete article on Program for Armstrong Numbers for more details!

Time complexity: O(logn)

Auxiliary Space: O(1)

Approach#3: Using string manipulation

This approach involves converting the input number into a string and iterating through each digit in the string. For each digit, we raise it to the power of the number of digits in the input number, and sum up the results. If the final sum equals the input number, it is an Armstrong number.

Algorithm

1. Convert the input number into a string using str(num).
2. Find the length of the string using len(num_str) and store it in n.
3. Initialize a variable sum to zero.
4. Iterate through each digit in the string using a for loop, and convert each digit back to an integer using int(digit).
5. Raise each digit to the power of n using int(digit)**n, and add the result to sum.
6. After the loop is complete, check whether sum is equal to num.
7. If sum is equal to num, return True (the input number is an Armstrong number).
8. If sum is not equal to num, return False (the input number is not an Armstrong number).

Time complexity: O(n), wheer n is length of number
Auxiliary Space: O(1)

Method: Digit by digit sum approach to check for Armstrong number

1. Find the number of digits in the given number.
2. Initialize a variable sum to zero.
3. Extract each digit from the given number and raise it to the power of the number of digits and add it to the sum.
4. If the sum is equal to the given number, then it is an Armstrong number, else it is not. #include <iostream>
    

1634 is an Armstrong number.
120 is not an Armstrong number.

Time Complexity: O(log n), where n is the given number.
Auxiliary Space: O(1)

Last Updated :
11 Apr, 2023

Like Article

Save Article

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)