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.

f(n) = n*9^n/10^(n-1)
n is the number of digits, f(n) is the sum of powers of the digits of the biggest n-digit number (n times 9).

based on this function we can see there can be no narcissistic number for n>60, and we can also see:
for 52<n<61 the narcissistic number must begin with 1, so vec should contain at least one 1, which will give us a very good restriction to speed up...
for 48<n<53 we must have at least a 1 or 2 in vec
...
for n<34 unfortunately this logic will not help.
But we can be much stricter. If the given number must contain a 1, f(n) will be n*9^(n-1)/10^(n-1), which will mean there can be no narcissistic number for n>52 ...

I'd like someone do it in a pure shell script lol.

This awk ...

Code:

time awk -F "" 'BEGIN{limit=9999999;
for (num=1;num<=9;num++) for (pwr=3;pwr<=9;pwr++) p[num,pwr]=num^pwr;
for (j=101;j<=limit;j++) {ex=split(j,a); # ex = exponent
cand=p[a[1],ex]
for (k=2;k<=ex;k++) cand=cand+p[a[k],ex] # Candidate Armstrong Number
if (cand==j) print "Armstrong Number:,j}}' >$OutFile1
echo "OutFile1 ..."; cat $OutFile1; echo "End Of OutFile1 ($(wc -l <$OutFile1) lines)"

function Method3 {
echo; echo "Method #3 of LQ Member danielbmartin, 3,4,5,6, and 7-digit integers."
seq 101 9999999 \
|awk -F "" 'BEGIN{for (num=1;num<=9;num++) for (pwr=3;pwr<=9;pwr++) p[num,pwr]=num^pwr};
{cand=p[$1,NF]
for (k=2;k<=NF;k++) cand=cand+p[$k,NF] # Candidate Armstrong Number
if (cand==$0) print "Armstrong Number:",$0}' >$OutFile3
}
time Method3
echo "OutFile3 ..."; cat $OutFile3; echo "End Of OutFile3 ($(wc -l <$OutFile3) lines)"

...produced this result ...

Code:

Method #3 of LQ Member danielbmartin, 3,4,5,6, and 7-digit integers.
real 0m31.251s
user 0m31.400s
sys 0m0.036s
OutFile3 ...
Armstrong Number: 153
Armstrong Number: 370
Armstrong Number: 371
Armstrong Number: 407
Armstrong Number: 1634
Armstrong Number: 8208
Armstrong Number: 9474
Armstrong Number: 54748
Armstrong Number: 92727
Armstrong Number: 93084
Armstrong Number: 548834
Armstrong Number: 1741725
Armstrong Number: 4210818
Armstrong Number: 9800817
Armstrong Number: 9926315
End Of OutFile3 (15 lines)

I did not expect two piped commands to perform better than the single awk in post #108 but it did. Perhaps that is because the split in #108 is not needed.

I'd like someone do it in a pure shell script lol.

Great idea. How about bash?

Code:

#!/bin/bash
# search for Armstrong numbers within a specified range
for number in $(seq $1 $2 $3) # script takes 1, 2, or 3 arguments (as per seq)
do
power=${#number} # get number of characters
power_sum=0 # initialize sum
for digit in $(grep -o . <<< $number) # this grep lists single characters
do
((power_sum+=digit**power)) # bash variable arithmetic
done
if [ $power_sum == $number ] # == is string comparison operator
then # -eq (integer comparison) works just as well
echo $number
fi
done

Normal test:

Code:

time ./arm_range.sh 100 10000
153
370
371
407
1634
8208
9474
real 0m43.473s
user 0m2.744s
sys 0m3.052s

On my system, it works up to 19 digits (64-bit arithmetic):

#!/usr/bin/env bash
power=$1
for (( i = 0; i <= 9; i++ ))
do
raised+=( $(( i**power )) )
done
(( max = 10**power ))
(( min = 10**(power - 1) ))
for (( num = min; num < max; num++ ))
do
sum=0
for (( i = power - 1; i >= 0; i-- ))
do
(( sum > max )) && break
(( sum += raised[${num:i:1}] ))
done
(( sum == num )) && echo $num
done

To run:

Code:

$ time ./arm.sh 3
153
370
371
407
real 0m0.201s
user 0m0.190s
sys 0m0.000s
$ time ./arm.sh 4
1634
8208
9474
real 0m2.190s
user 0m2.100s
sys 0m0.003s

Obviously it just gets slower as the numbers increase

Looks good, and fast... Well, it's only bash, so it's fast in the same way that a Ford Model T is faster than a horse and buggy, while the better C/C++ programs are rockets.

OK, I've done a multi-threaded version in Objective-C for Mac OS X. I'm still working on it, so I don't have any speed numbers. I have to finish it and then figure out how to set Xcode to compile it with optimization and in release not debug mode. But if there are any Mac programmers, please have a look and give me any ideas. It's kind a strange Mac program since it's in Objective-C but just a terminal program (at least for now).

Here are the files:

Code:

//
// main.m
// Narcissists
//
// Created by Douglas Johnston on 7/3/17.
//
#import <Foundation/Foundation.h>
#import "NarcissistsMain.h"
#import "MMStopwatchARC.h"
int main(int argc, const char * argv[]) {
@autoreleasepool {
NarcissistsMain *nm = [NarcissistsMain new];
printf("Enter maximum digits to calculate: ");
char input[5];
fgets(input, 5, stdin);
int digits = atoi(input);
[nm processNumbersWithDigits:digits];
}
return 0;
}

Code:

//
// NarcissistsMain.h
// Narcissists
//
// Created by Douglas Johnston on 7/3/17.
//
#import <Foundation/Foundation.h>
#import "NSMutableArray+shuffle.h"
@interface NarcissistsMain : NSObject
-(void)processNumbersWithDigits:(int)theDigits;
-(NSArray *) calculatePowers;
-(void) reapAnswersFromBlocks :(NSArray *)inArray;
@end

Code:

//
// NarcissistsMain.m
// Narcissists
//
// Created by Douglas Johnston on 7/3/17.
//
#import "NarcissistsMain.h"
unsigned int blockNumber = 0;
@implementation NarcissistsMain
NSMutableArray *narcissisticNumbersArray;
-(void)processNumbersWithDigits:(int)theDigits {
narcissisticNumbersArray = [NSMutableArray new];
NSArray *myPowerCacheArray = [self calculatePowers];
NSUInteger numProcessors = [[NSProcessInfo processInfo] processorCount];
NSLog(@"There are %lu processors.", (unsigned long) numProcessors);
unsigned long numDigits = theDigits;
unsigned long max = powl(10, numDigits) - 1;
NSLog(@"Calculating all numbers to test...");
NSMutableArray *allNumbers = [NSMutableArray arrayWithCapacity:max];
for (unsigned long i = 1; i <= max; i++) {
[allNumbers addObject:[NSNumber numberWithUnsignedLongLong:i]];
}
[allNumbers shuffle];
NSLog(@"All %lu numbers shuffled.", (unsigned long)[allNumbers count]);
unsigned long eachArrayCount = [allNumbers count] / numProcessors;
NSMutableArray *arrayOfArrays = [NSMutableArray array];
unsigned long itemsRemaining = [allNumbers count];
unsigned long j = 0;
while(itemsRemaining) {
NSRange range = NSMakeRange(j, MIN(eachArrayCount, itemsRemaining));
NSArray *subarray = [allNumbers subarrayWithRange:range];
[arrayOfArrays addObject:subarray];
itemsRemaining -= range.length;
j += range.length;
}
[allNumbers removeAllObjects];
allNumbers = NULL;
dispatch_queue_t narcissisticQueue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_group_t narcissisticGroup = dispatch_group_create();
void (^narcissisticBlock)(NSArray *) = ^(NSArray *numbersToTest) {
// unsigned int blockNum = ++blockNumber;
// NSLog (@"Block %d starting...", blockNum);
//
NSMutableArray *answers = [NSMutableArray new];
NSDecimal sum = [[NSNumber numberWithUnsignedLongLong:0] decimalValue];
NSComparisonResult result = NSOrderedDescending;
for (NSNumber *i in numbersToTest) {
NSString *stringValue = [NSString stringWithFormat:@"%llu", [i unsignedLongLongValue]];
NSMutableArray *digits = [NSMutableArray new];
unsigned long numDigits = floor(log10l([i unsignedLongLongValue]) + 1);
for (unsigned long digitIndex = 0; digitIndex <numDigits; digitIndex++) {
digits[digitIndex] = [NSNumber numberWithChar:[stringValue characterAtIndex:digitIndex]];
}
NSDecimal val = [i decimalValue];
for (unsigned long s = 0; s < numDigits; s++) {
NSNumber *digit = [NSNumber numberWithChar:[stringValue characterAtIndex:s]];
NSDecimal powerLookup = [myPowerCacheArray[[digit unsignedLongLongValue] - '0'][numDigits] decimalValue];
NSDecimalAdd(&sum, &sum, &powerLookup , NSRoundPlain);
result = NSDecimalCompare(&val, &sum);
if (result != NSOrderedDescending)
break;
}
if (result == NSOrderedSame) {
[answers addObject: i];
}
sum = [[NSNumber numberWithUnsignedLongLong:0] decimalValue];
}
[self reapAnswersFromBlocks:answers];
//NSLog (@"Block number %d quitting", blockNum);
};
for (NSArray *a in arrayOfArrays)
dispatch_group_async(narcissisticGroup, narcissisticQueue, ^{ narcissisticBlock(a); });
dispatch_group_wait(narcissisticGroup, DISPATCH_TIME_FOREVER);
NSLog(@"Array of Count %lu: %@", [narcissisticNumbersArray count],
[narcissisticNumbersArray sortedArrayUsingSelector:@selector(compare:)]);
}
-(void) reapAnswersFromBlocks :(NSArray *) inArray {
@synchronized (narcissisticNumbersArray) {
[narcissisticNumbersArray addObjectsFromArray:inArray];
}
}
//Calculate each single digit number to the power of each single digit number and store in array
-(NSArray *) calculatePowers {
NSMutableArray *powerCache = [NSMutableArray new];
for (unsigned short i = 0; i < 10; i++) {
[powerCache addObject: [NSMutableArray new]];
for (unsigned short x = 0; x < 10; x++) {
powerCache[i][x] = [NSNumber numberWithUnsignedInteger:(UInt32)powl(i, x)];
}
}
return [NSArray arrayWithArray:powerCache];
}
@end

Code:

//
// NSMutableArray+shuffle.h
// Narcissists
//
// Created by Douglas Johnston on 7/4/17.
//
#import <Foundation/Foundation.h>
@interface NSMutableArray (shuffle)
-(void) shuffle;
@end

Code:

//
// NSMutableArray+shuffle.m
// Narcissists
//
// Created by Douglas Johnston on 7/4/17.
//
#import "NSMutableArray+shuffle.h"
@implementation NSMutableArray (Shuffle)
// Add Fisher-Yates shuffle functionality to NSMutableArray
- (void)shuffle
{
for (NSUInteger i = self.count; i > 1; i--)
[self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)];
}
@end

This uses code blocks/Grand Central Dispatch which were developed by Apple, but they were made open source and released for use in other OSes, but I don't know if they've been adopted in generic versions of gcc etc. or not. I've never done POSIX threading, so this is the best way I know how to do it.

Last edited by Laserbeak; 07-07-2017 at 02:46 PM.
Reason: Ask how many digits

I think I've gotten this compiled with at least -O3 and it still seems slow compared to what others have gotten. This is a sample output with 7 digits:

Code:

| => time ./Narcissists
2017-07-07 07:16:56.404 Narcissists[33389:517588] There are 8 processors.
2017-07-07 07:16:56.405 Narcissists[33389:517588] Calculating all numbers to test...
2017-07-07 07:16:57.987 Narcissists[33389:517588] All 9999999 numbers shuffled.
2017-07-07 07:17:47.472 Narcissists[33389:517588] Array of Count 30: (
1,
2,
3,
4,
5,
6,
7,
8,
9,
153,
370,
371,
407,
1634,
6688,
8208,
9474,
33286,
54748,
91818,
91819,
92727,
93084,
117651,
548834,
1741725,
4210818,
4955603,
9800817,
9926315
)
real 0m51.102s
user 6m24.146s
sys 0m0.624s

Is it a problem with my code or is Objective-C just slow? You can see the multiprocessor effect since user is much more than real, but the C++ version (I think running on one core) posted earlier seemed to be much faster. Maybe I can take that and use Grand Central Dispatch to make it mutiprocessor too, since it works with C++ as well as C and Objective-C.

Edit:
Note: I have a 2.3 GHz Intel Core i7 in a MacBook Pro (Late 2013)

Now I realize I'm getting extra wrong numbers when compared to the Wolfram site. When calculated with a calculator, they also prove to be wrong.

An example from above is 6688. There are many more, all 4 or more digits.

At the moment I do not understand your code, which limits my ability to fix anything, but here are two clues:

6688 = 6**4 + 6**4 + 8**4

33286 = 3**5 + 3**5 + 2**5 + 8**5

So it looks like either the sum of powers is omitting the power of the last digit, or perhaps the comparison is ignoring the last digit of the sum. Or, as they say, it could be anything.

At the moment I do not understand your code, which limits my ability to fix anything, but here are two clues:

6688 = 6**4 + 6**4 + 8**4

33286 = 3**5 + 3**5 + 2**5 + 8**5

So it looks like either the sum of powers is omitting the power of the last digit, or perhaps the comparison is ignoring the last digit of the sum. Or, as they say, it could be anything.

Yes, I did notice that. But why is it working with most of the numbers?

Objective-C is pretty easy to read especially if you make the variable names long and descriptive as I usually do except for small scope iterators.

But thank you :up:

I have a headache and can't really examine it carefully now, but I will. I'm sure it's just some stupid error somewhere.

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