Share your knowledge at the LQ Wiki.
 LinuxQuestions.org Printing Armstrong numbers from 1 to 500. (C Programming)
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

06-30-2017, 12:02 PM   #91
Beryllos
Member

Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep:

Quote:
 Originally Posted by norobro Python executes those combinations pretty quickly using the intertools module. https://docs.python.org/3/library/itertools.html
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]```

 06-30-2017, 12:07 PM #92 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 529 Rep: 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)``` And here is a timed test: Code: ```time python3 armstrong_by_combinations.py 3: 370 407 153 371 4: 8208 1634 9474 5: 93084 92727 54748 6: 548834 7: 9800817 4210818 1741725 9926315 8: 24678050 24678051 88593477 9: 146511208 912985153 472335975 534494836 10: 4679307774 11: 32164049650 40028394225 42678290603 49388550606 32164049651 94204591914 44708635679 82693916578 real 0m8.814s user 0m8.808s sys 0m0.000s```
 06-30-2017, 10:49 PM #93 Laserbeak Member   Registered: Jan 2017 Location: Manhattan, NYC NY Distribution: Mac OS X, iOS, Solaris Posts: 508 Rep: Now we have to do it in assembly!
 07-01-2017, 01:21 AM #94 Laserbeak Member   Registered: Jan 2017 Location: Manhattan, NYC NY Distribution: Mac OS X, iOS, Solaris Posts: 508 Rep: 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``` Last edited by Laserbeak; 07-01-2017 at 01:24 AM.
07-01-2017, 03:06 AM   #95
pan64
LQ Guru

Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep:
Quote:
 Originally Posted by Beryllos ... 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.

 07-01-2017, 03:27 AM #96 Laserbeak Member   Registered: Jan 2017 Location: Manhattan, NYC NY Distribution: Mac OS X, iOS, Solaris Posts: 508 Rep: I'd like someone do it in a pure shell script lol.
 07-01-2017, 03:35 AM #97 Laserbeak Member   Registered: Jan 2017 Location: Manhattan, NYC NY Distribution: Mac OS X, iOS, Solaris Posts: 508 Rep: 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.
07-01-2017, 04:00 AM   #98
pan64
LQ Guru

Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep:
Two improvements:
Quote:
 Originally Posted by Beryllos 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 # 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.

Last edited by pan64; 07-01-2017 at 05:46 AM.

 07-01-2017, 03:18 PM #99 Laserbeak Member   Registered: Jan 2017 Location: Manhattan, NYC NY Distribution: Mac OS X, iOS, Solaris Posts: 508 Rep: Here is a full solution to the Narcissistic Numbers problem written in Perl: Code: ```#!/usr/bin/perl my \$MAX_DIGITS = 10; #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; } } #Find the Narcissistic Numbers for \$num_digits (1..\$MAX_DIGITS) { print "\n\nCalculating narcissistic numbers with \$num_digits digits.\n\n"; my \$minnum = "1" . "0" x (\$num_digits - 1); my \$maxnum = "9" x \$num_digits; for (\$testnum = \$minnum; \$testnum <= \$maxnum; \$testnum++) { @digits = split //, \$testnum; @digits_power = (); for (0 .. \$#digits) { \$digits_power[\$_] = \$powerhash{\$digits[\$_]}{\$num_digits}; } my \$sum = 0; for (@digits_power) { \$sum += \$_; } if (\$testnum == \$sum) { my \$format_string = "%0" . \$num_digits . "d" . " is a narcisstic number.\n"; printf \$format_string, \$testnum; } } } exit (0);``` Last edited by Laserbeak; 07-01-2017 at 03:32 PM. Reason: spelling
 07-01-2017, 08:28 PM #100 norobro Member   Registered: Feb 2006 Distribution: Debian Sid Posts: 792 Rep: I converted Beryllos' algorithm to c++ and it runs very quickly. For example: Code: ```1 digits: 1 2 3 4 5 6 7 8 9 ... ... 10 digits: 4679307774 11 digits: 32164049650 40028394225 42678290603 49388550606 32164049651 94204591914 44708635679 82693916578 real 0m0.282s user 0m0.276s sys 0m0.004s``` 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``` I'll post my code if anyone is interested.
07-02-2017, 01:06 AM   #101
Laserbeak
Member

Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep:
Quote:
 Originally Posted by norobro I'll post my code if anyone is interested.
Sure...

I was just thinking C++ has a lot of the tricks I used the Perl version and would run much faster.

 07-02-2017, 03:22 AM #102 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 16,207 Rep: you ought to sort the result Code: ```11 digits: sorted 32164049650 32164049650 40028394225 32164049651 42678290603 40028394225 49388550606 42678290603 32164049651 44708635679 94204591914 49388550606 44708635679 82693916578 82693916578 94204591914```
07-02-2017, 07:20 AM   #103
Beryllos
Member

Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep:
Quote:
 Originally Posted by pan64 you ought to sort the result Code: ```11 digits: sorted 32164049650 32164049650 40028394225 32164049651 42678290603 40028394225 49388550606 42678290603 32164049651 44708635679 94204591914 49388550606 44708635679 82693916578 82693916578 94204591914```
Yes, I noticed that my numbers came out in order of the permutations. I could sort them at the end.

07-02-2017, 09:34 AM   #104
norobro
Member

Registered: Feb 2006
Distribution: Debian Sid
Posts: 792

Rep:
Here is the "unsigned long long int" version which is basically a conversion of Beryllos' python code in post #42.
Code:
```#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::vector;
typedef unsigned long long ull;

bool next_comb_rep(vector<ull> &vec, int place) {
if(place == 0){
vec[place] += 1;
} else {
if(next_comb_rep(vec, place-1)) {
vec[place] += 1;
for(int j=0; j<place; ++j) {
vec[j] = vec[place];
}
}
}
return vec[place]==10;
}

ull sum_of_power_of_digit(vector<ull> &digits) {
unsigned power = digits.size();
ull sum = 0;
for(unsigned i=0; i<power; ++i) {
ull res = 1;
unsigned digit = digits[i];
for(unsigned pow=0; pow<power; ++pow) {
res *= digit;
}
sum += res;
}
return sum;
}

int main() {
for(int i=1; i<12; ++i) {
cout << "\n" << i << " digits:\n";
vector<ull> vec(i);
vector<ull> out_vec;
while(1){
if(next_comb_rep(vec, i-1)) {
break;
}
ull num = sum_of_power_of_digit(vec);
ull tmp_num = num;
vector<ull> tmp;
while(tmp_num>0){
tmp.emplace_back(tmp_num % 10);
tmp_num /=10;
}
sort(tmp.begin(), tmp.end(), [](const ull a, const ull b) {return a > b; });
if(tmp == vec) {
out_vec.emplace_back(num);
}
}
std::sort(out_vec.begin(), out_vec.end());
for(ull i : out_vec){
cout << i << "\n";
}
}
}```
Quote:
 Originally Posted by pan64 you ought to sort the result
Agreed. I mistakenly used an older version. for the 11 digit run. Notice that the 19 digit results are in order.

Last edited by norobro; 07-04-2017 at 09:50 PM. Reason: Note to self: have eyes checked. 19 digit results are not sorted.

 07-02-2017, 10:33 AM #105 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 16,207 Rep: and again, using an array instead of recalculating powers will significantly increase the speed: Code: ```include #include #include using std::cout; using std::vector; typedef unsigned long long ull; static vector powers(12); bool next_comb_rep(vector &vec, int place) { if(place == 0){ vec[place] += 1; } else { if(next_comb_rep(vec, place-1)) { vec[place] += 1; for(int j=0; j &digits, int power) { ull sum = 0; for(int i=0; i vec(base); vector out_vec; for (int i=1; i<12; i++) { powers[i] = i; for(int pow=1; pow tmp; while(tmp_num>0){ tmp.emplace_back(tmp_num % 10); tmp_num /=10; } // <= line 60 sort(tmp.begin(), tmp.end(), [](const ull a, const ull b) {return a > b; }); if(tmp == vec) { out_vec.emplace_back(num); } } std::sort(out_vec.begin(), out_vec.end()); for(ull i : out_vec){ cout << i << "\n"; } } }``` with power function 23 seconds, with array 15.5, with additional length check it was again almost 10% faster (14.4) Code: ```# after line 60 if (tmp.size() != (unsigned)base ) continue;``` Furthermore adding a function: Code: ```bool del (vector &v, int i) { auto it = std::find(v.begin(), v.end(), i); if(it == v.end()) return false; v.erase(it); return true; }``` and replacing the while loop: Code: ``` while(1){ if(next_comb_rep(vec, base-1)) { break; } ull num = sum_of_power_of_digit(vec, base); ull tmp_num = num; vector vec1 = vec; while(tmp_num>0){ if ( ! del(vec1, tmp_num % 10) ) break; tmp_num /=10; } if (vec1.size() != 0 ) continue; out_vec.emplace_back(num); }``` will lead to 3.4 sec, which is approximately 15% of "original" execution time. 2 members found this post helpful.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post bauer172uw Programming 3 04-13-2006 11:10 PM Gigantor Programming 8 12-05-2005 10:32 PM mrobertson Programming 1 06-28-2005 08:19 AM vijeesh_ep Programming 18 09-08-2004 11:59 AM fisheromen1031 Programming 1 07-27-2004 02:19 PM

LinuxQuestions.org

All times are GMT -5. The time now is 02:44 PM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -