3-Digit Narcissistic Numbers Program - Python 🐍

Question

Just wanted to share my Narcissistic Numbers Program with y'all (not sure if it's good, but I gave it my best). Hope you like it!

This program prints out all the narcissistic numbers from the smallest number and biggest number's range. Ex. in the 1-100 range, only the narcissistic numbers will show on the console.

Some of you may be wondering, "What the hell are narcissistic numbers??" Once you go through a number of examples, I'm sure they won't be as bad as they sound (no pun intended). Narcissistic numbers are also known as Armstrong numbers, though I'm going to use the term 'narcissistic' rather than 'Armstrong' to avoid being inconsistent and flipping back and forth.

Overview: Narcissistic numbers are numbers that are equivalent to the sum of the cubes of their digits (3-digit numbers). This definition's verbose structure confused me, but after looking through a couple of examples, it made much more sense.

---

Procedure: (this is only applicable to 3-Digit Numbers)

• Pick a number: 153

FYI: I broke the definition down into my own steps.

• I split the number up into its individual digits; 1, 5 and 3
• or you can just identify which digits the number (153 in this case) is composed of; 1, 5 and 3

Both ways bear the same result, but I tend to over-complicate things, so you can choose which way to use.

• Now that all the digits are split up, we need to cube them all (separately) like this: [1⋅1⋅1] + [5⋅5⋅5] + [3⋅3⋅3]; I included the square brackets for clarity's sake.

If you're not using brackets, then make sure you're following the BEDMAS rules.

If you simply calculate the following in a calculator: 1⋅1⋅1 + 5⋅5⋅5 + 3⋅3⋅3, then the result you will get is: 1025.

---

I believe I have provided a thorough enough over-view as to what narcissistic numbers are. Now, I hope the code will be easier for many people to understand.

The code is as follows:

import time
initial_time = time.time()

# initializing 's_number' (the smallest number) and 'l_num' (the largest number)
s_number = 100
l_number = 500

for number in range(s_number, l_number + 1):

    # order of the numbers
    order = len(str(number))

    # initializing sum
    sum = 0

    var = number
    while var > 0:
        digit = var % 10
        sum += digit ** order
        var //= 10

    # setting restrictions for program
    if number == sum:
        print(number)

total_time = time.time() - initial_time
print('Time to complete task:',total_time)

If there's anything to change/add to make the program more efficient/better please don't hesitate to let me know. I would appreciate your insight on this project.

Answer 1

Nice solution, it's already efficient and easy to understand. Few general suggestions:

• Avoid calling a variable sum: sum is a built-in function in Python, calling a variable sum prevents you from using such function.
• time.perf_counter vs time.time: running your code I get 0.0 running time on Windows, which doesn't provide a useful information. Use time.perf_counter to get a better precision.
• Make a function and return a result: if you wrap the code in a function it is easier to reuse and test. Additionally, instead of printing the numbers, add them to a list and return the final result. Printing only the result is typically faster than printing the numbers one by one.
• Armstrong numbers: a narcissistic number is also called Armstrong number and here there is an efficient approach that I slightly modified to fit this question:

  from itertools import combinations_with_replacement
  
  def armstrong(n):
    numbers = []
    order = len(str(n))
    for k in range(1, order):
        a = [i ** k for i in range(10)]
        for b in combinations_with_replacement(range(10), k):
            x = sum(map(lambda y: a[y], b))
            if x > 0 and tuple(int(d) for d in sorted(str(x))) == b:
                numbers.append(x)
    return sorted(numbers)
  

Extending the definition of Narcissistic number to:

An n-digit number that is the sum of the nth powers of its digits

The Narcissistic numbers till 1000000 are:

1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834

Runtime:

             n=1_000_000      n=10_000_000
Original:     3.374 s            40.26 s
Armstrong:    0.036 s            0.098 s

Full code:

import time
from itertools import combinations_with_replacement


def original(n):
    numbers = []
    for number in range(1, n):
        order = len(str(number))
        total_sum = 0
        var = number
        while var > 0:
            digit = var % 10
            total_sum += digit ** order
            var //= 10
        if number == total_sum:
            numbers.append(number)
    return numbers


def armstrong(n):
    numbers = []
    order = len(str(n))
    for k in range(1, order):
        a = [i ** k for i in range(10)]
        for b in combinations_with_replacement(range(10), k):
            x = sum(map(lambda y: a[y], b))
            if x > 0 and tuple(int(d) for d in sorted(str(x))) == b:
                numbers.append(x)
    return sorted(numbers)

# Correctness
assert original(1000) == armstrong(1000)

# Benchmark
n = 1_000_000

initial_time = time.perf_counter()
original(n)
total_time = time.perf_counter() - initial_time
print(f'Original: {round(total_time, 3)} s')

initial_time = time.perf_counter()
armstrong(n)
total_time = time.perf_counter() - initial_time
print(f'Armstrong: {round(total_time, 3)} s')

Answer 2

For the beginning, I rewrote your code to be a function, which makes it much easier for me to do rapid prototyping:

from time import perf_counter

def find_narcissistic_numbers(limit_low, limit_high):
    results = []
    for number in range(limit_low, limit_high + 1):

        # order of the numbers
        order = len(str(number))

        # initializing sum
        sum = 0

        var = number
        while var > 0:
            digit = var % 10
            sum += digit ** order
            var //= 10

        # setting restrictions for program
        if number == sum:
            results.append(number)

    return results

def benchmark(method):
    t_start = perf_counter()
    result = method(100, 500000)
    t_end = perf_counter()
    print(f'{method.__name__}\t  {1000*(t_end-t_start):.2f} ms')
    if result != [153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084]:
        print(f'{method.__name__} failed! Result incorrect!')

benchmark(find_narcissistic_numbers)

Which currently gives me

find_narcissistic_numbers     1047.52 ms

With that as a starting point, my ideas are:

• try to find algorithmic improvements. That might be hard because the problem is already quite simple.
• benchmark each part of this code, try to find more efficient alternatives for e.g. len(str())
• port the critical part of the code to rust (using pyo3) for improved performance

---

First round

I tried to combine calculating order and splitting the number into digits in one operation. Sadly, it did not yield any performance gain.

def find_narcissistic_numbers(limit_low, limit_high):
    results = []
    for number in range(limit_low, limit_high + 1):

        i = number

        digits = []
        while i > 0:
            digits.append(i % 10)
            i //= 10

        order = len(digits)

        sum_value = 0
        for digit in digits:
            sum_value += digit ** order

        if number == sum_value:
            results.append(number)

    return results

find_narcissistic_numbers     1050.50 ms

---

Second round

After thinking about it more, I don't find any other optimization points. I think your original algorithm is quite the optimum.

So to get any further performance increase, we need to start at a lower level of performance optimization.

Python is in its nature quite a slow language, as it has an entire interpretation layer in between its commands and actual hardware. Therefore it would be beneficial to extract the critical code to another language that compiles directly to native bytecode and uses features like vectorization.

Those are the most promising options in my opinion, as they fulfill that criterium and can be used to implement python functions:

• C
• C++
• Rust

I personally find Rust to be the most convenient function to write Python code, as it automatically makes sure that all the memory management is done right.

I use this skeleton to write the Rust function for Python: https://github.com/Finomnis/PythonCModule

lib.rs:

use pyo3::prelude::*;
use pyo3::wrap_pyfunction;


#[pyfunction]
fn find_narcissistic_numbers_rust(_py: Python, limit_low: u32, limit_high: u32) -> PyResult<Vec<u32>> {
    let mut results = vec![];

    for number in limit_low..=limit_high {
        let mut digits = vec![];

        let mut i = number;
        while i > 0 {
            digits.push(i%10);
            i /= 10;
        }

        let order = digits.len() as u32;

        let sum = digits.iter().fold(0, |acc, x| acc + x.pow(order));

        if number == sum {
            results.push(number);
        }
    }

    Ok(results)
}


/// A Python module implemented in Rust.
#[pymodule]
fn __lib(_py: Python, m: &PyModule) -> PyResult<()> {
    m.add_function(wrap_pyfunction!(find_narcissistic_numbers_rust, m)?)?;
    Ok(())
}

python:

from time import perf_counter
from narcissisticNumbersRustModule import find_narcissistic_numbers_rust

def benchmark(method):
    t_start = perf_counter()
    result = method(100, 500000)
    t_end = perf_counter()
    print(f'{method.__name__}\t  {1000*(t_end-t_start):.2f} ms')
    if result != [153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084]:
        print(f'{method.__name__} failed! Result incorrect!')

benchmark(find_narcissistic_numbers_rust)

Result:

find_narcissistic_numbers_rust    84.00 ms

So that's about ~12 times faster!

---

Third round

Seeing Marc's answer made it painfully clear that algorithmic optimization is by far the most important part and should always be done first.

I ran his code on my machine, to be able to compare it with my attempts:

def armstrong(limit_low, limit_high):
    numbers = []
    order = len(str(limit_high))
    for k in range(1, order+1):
        a = [i ** k for i in range(10)]
        for b in combinations_with_replacement(range(10), k):
            x = sum(map(lambda y: a[y], b))
            if x > 0 and tuple(int(d) for d in sorted(str(x))) == b:
                numbers.append(x)
    return sorted(filter(lambda x: limit_low <= x <= limit_high, numbers))

And the result was:

armstrong     20.71 ms

Optimizing in hardware efficiency, by using a faster programming language or utilizing hardware features, only ever gives you a linear speedup. Algorithmic optimization, however, has the chance to move your algorithm into a different complexity class, which can boost the speed exponentially. Literally exponentially, not a figure of speech.

Now that we know the better algorithm, let's see if we can squeeze a little bit of juice out by porting it to Rust: (sorry, i'm just really in love with Rust recently :D )

use pyo3::prelude::*;
use pyo3::wrap_pyfunction;

use std::iter;
use itertools::Itertools;

struct CombinationsWithReplacementIterator {
    current: Vec<u32>
}

impl Iterator for CombinationsWithReplacementIterator {
    type Item = Vec<u32>;

    fn next(&mut self) -> Option<Vec<u32>> {
        let mut overflow = true;

        for element in self.current.iter_mut().rev() {
            if *element == 9 {
                *element = 0;
            } else {
                *element += 1;
                overflow = false;
                break;
            }
        }

        let mut prev_element = 0;
        for element in self.current.iter_mut() {
            if *element < prev_element {
                *element = prev_element;
            }
            prev_element = *element;
        }

        if overflow {
            None
        } else {
            Some(self.current.clone())
        }
    }
}

fn combinations_with_replacement(order: usize) -> CombinationsWithReplacementIterator {
    CombinationsWithReplacementIterator{current:iter::repeat(0).take(order).collect()}
}

#[pyfunction]
fn armstrong_rust(_py: Python, limit_low: u32, limit_high: u32) -> PyResult<Vec<u32>> {
    let mut results = vec![];

    let order = limit_high.to_string().len() as u32;

    for current_order in 1..=order {
        let power_table: Vec<u32> = (0..10).map(|x:u32| x.pow(current_order)).collect();

        for combination in combinations_with_replacement(current_order as usize) {
            let number: u32 = combination.iter().map(|&x| power_table[x as usize]).sum();
            let mut number_digits = vec![];
            {
                let mut i = number;
                while i > 0 {
                    number_digits.push(i%10);
                    i /= 10;
                }
            }

            if number_digits.iter().sorted().zip(combination.iter()).all(|(a,b)| *a == *b) {
                results.push(number);
            }
        }
    }

    Ok(results.into_iter().filter(|&x| x>=limit_low && x<=limit_high).sorted().collect())
}

/// A Python module implemented in Rust.
#[pymodule]
fn __lib(_py: Python, m: &PyModule) -> PyResult<()> {
    m.add_function(wrap_pyfunction!(armstrong_rust, m)?)?;
    Ok(())
}

Result:

armstrong_rust    2.73 ms

---

Summary

• Algorithmic optimizations are always highest priority
• When best algorithm is established, further low level optimization can be done

Performance comparison:

find_narcissistic_numbers       1047.52 ms
find_narcissistic_numbers_rust    84.00 ms
armstrong                         20.71 ms
armstrong_rust                     2.73 ms