Printing Armstrong numbers from 1 to 500. (C Programming)

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

Python's itertools.combinations_with_replacement() is nice, but I decided to make my own sequential combination generator. It is a short recursive function. It uses the previous combination to generate the next combination in the sequence. Here is a sample program in Python:

Code:

# comb_rep.py
# program to test a combination-with-replacement generator
def next_comb_rep(array, place, base):
if place == 0:
array[place] += 1
elif next_comb_rep(array, place-1, base):
array[place] += 1
for i in range(place):
array[i] = array[place]
return array[place]==base
base = int(input("How many choices? "))
size = int(input("How many items to choose? "))
digits = size*[0]
while True:
print(digits)
if next_comb_rep(digits, size-1, base):
break

Here is the result of a small test:

Code:

How many choices? 3
How many items to choose? 3
[0, 0, 0]
[1, 0, 0]
[2, 0, 0]
[1, 1, 0]
[2, 1, 0]
[2, 2, 0]
[1, 1, 1]
[2, 1, 1]
[2, 2, 1]
[2, 2, 2]

Finally I used combinations to find Armstrong numbers. It is pretty fast, even in this Python implementation:

Code:

# armstrong_by_combinations.py
# program to find Armstrong numbers
# using a sequential combination-with-replacement generator
def next_comb_rep(array, place, base):
if place == 0:
array[place] += 1
elif next_comb_rep(array, place-1, base):
array[place] += 1
for i in range(place):
array[i] = array[place]
return array[place]==base
def sum_of_power_of_digit_array(digits):
power = len(digits)
psum = 0
for d in digits:
psum += d**power
return psum
base = 10
for size in range(3,12):
print("\n", size, ":", sep="")
digit_array = size*[0]
while True:
if next_comb_rep(digit_array, size-1, base):
break
n = sum_of_power_of_digit_array(digit_array)
n_digits = [int(x) for x in str(n)]
n_digits.sort(reverse=True)
if n_digits == digit_array:
print(n)

In the meantime, I did it in Perl using the caching algorithm for all powers. It is amazingly fast!

Code:

#!/usr/bin/perl
#build hash table of powers
my %powerhash = ();
for (my $a = 0; $a < 10; $a++) {
for (my $b = 0; $b < 10; $b++) {
$powerhash{$a}{$b} = $a ** $b;
}
}
# Look for 3-digit Narcissitic Numbers (Armstrong Numbers)
for (my $a = 0; $a < 10; $a++) {
for (my $b = 0; $b < 10; $b++) {
for (my $c = 0; $c < 10; $c++) {
my $value = $a * 100 + $b * 10 + $c;
my $powersum = $powerhash{$a}{3} + $powerhash{$b}{3} + $powerhash{$c}{3};
if ($value == $powersum) {
printf "%03d is an Armstrong number\n", $value;
}
}
}
}

Output:

Code:

| => ./perlarm.pl
000 is an Armstrong number
001 is an Armstrong number
153 is an Armstrong number
370 is an Armstrong number
371 is an Armstrong number
407 is an Armstrong number

...
10:
4679307774
...
real 0m8.814s
user 0m8.808s
sys 0m0.000s
[/CODE]

For me it took 3-4 minutes to find this number (in c). Probably I could improve it and will be able to complete under 1 minute, but this looks still much better. And we can still go further, using multithreaded/multicore environment.

In Perl, you can actually use Berkeley DB (or even a SQL database) as backing for hashes and save the results of the hash of powers (and even already-calculated Narcissistic Numbers) so you don't have to recalculate them every time, so you could make it that after the first time you ran it, the results would be saved and you could work on making the rest of the application more thorough without having to recalculate what you've already done successfully again.

# armstrong_by_combinations.py
# program to find Armstrong numbers
# using a sequential combination-with-replacement generator
def next_comb_rep(array, place, base):
if place == 0:
array[place] += 1
elif next_comb_rep(array, place-1, base):
array[place] += 1
for i in range(place):
array[i] = array[place]
return array[place]==base
# do not need to calculate power, it is known
def sum_of_power_of_digit_array(digits, power):
# power = len(digits)
psum = 0
for d in digits:
psum += d**power
return psum
base = 10
for size in range(3,12):
print("\n", size, ":", sep="")
digit_array = size*[0]
while True:
if next_comb_rep(digit_array, size-1, base):
break
n = sum_of_power_of_digit_array(digit_array, size)
if (len(str(n)) != size):
continue
n_digits = [int(x) for x in str(n)]
n_digits.sort(reverse=True)
if n_digits == digit_array:
print(n)

passing the size gave less than 1% improvement, but checking the size is much faster than checking the digits, that means at about 10% faster execution (at least for me).

additionally, using an array instead of power function will dramatically improve the performance:

Code:

powers=[]
for x in range(11):
powers.append(x**size)
....
def sum_of_power_of_digit_array(digits, power):
psum = 0
for d in digits:
psum += powers[d]
return psum

This is a very compact solution anyway, I like it.

Twenty digits will overflow an unsigned long long (2^64 == 8^20*2) so a large number library is neccessary. Using libgmp slows processing considerably, at least with my code.

Using usigned long long:

Code:

19 digits:
1517841543307505039
3289582984443187032
4929273885928088826
4498128791164624869
real 0m11.977s
user 0m11.968s
sys 0m0.000s

Using libgmp:

Code:

19 digits:
1517841543307505039
3289582984443187032
4929273885928088826
4498128791164624869
real 0m51.818s
user 0m51.792s
sys 0m0.004s

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.