Visit Jeremy's Blog.
 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-29-2017, 08:19 AM   #76
Beryllos
Member

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

Rep:

Quote:
 Originally Posted by Laserbeak This is very interesting (really). but according to everything I've read the only way to determine Narcissistic Numbers (of which Armstrong Numbers are just a subset of three-digit numbers) is by brute force, i.e. testing each number to see if it is one. Even if your algorithm works, how can you make sure that you've found all of the Narcissistic numbers within a range?
That's right. There is some probability that you will find each Armstrong number, but you don't know what the probabilities are.

As an example, in 1 hour, my Python implementation was able to find 3 of the 5 Armstrong numbers of 23-digits. After another 5 hours, it had found one more. I have no idea how long it would take to find the last one. If I didn't know that there are only 5, I wouldn't have any way of knowing when the search is completed.

It's just a mathematical curiosity and a small programming challenge.

Last edited by Beryllos; 06-29-2017 at 09:40 AM.

 06-29-2017, 08:59 AM #77 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 16,207 Rep: a total of 88 narcissistic numbers exist in base 10 http://mathworld.wolfram.com/NarcissisticNumber.html 1 members found this post helpful.
06-29-2017, 09:07 AM   #78
Laserbeak
Member

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

Rep:
Quote:
 Originally Posted by pan64 a total of 88 narcissistic numbers exist in base 10 http://mathworld.wolfram.com/NarcissisticNumber.html
Yes, you can look them all up, but that doesn't help you be a better programmer.

06-29-2017, 09:14 AM   #79
Beryllos
Member

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

Rep:
Quote:
 Originally Posted by pan64 I'm sorry, but that is incorrect. The leading zeroes cannot be taken into account, they modify the "length", the number of digits. The valid result is: Code: ``` (?) 0 153 1634 54748 548834 1741725 24678050 146511208 1 370 8208 92727 4210818 24678051 472335975 2 371 9474 93084 9800817 88593477 534494836 3 407 9926315 912985153 4 5 6 7 8 9``` execution time is at about 23 sec on my box (with -O3)
You are right. Had I followed the specs, I would have omitted anything with leading zeroes.

06-29-2017, 09:29 AM   #80
Laserbeak
Member

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

Rep:
Quote:
 Originally Posted by Beryllos It's just a mathematical curiosity and a small programming challenge.
Yes. It's totally dependent on the base , and not any sort of real mathematical property. That's why I think there's no real way to calculate them other than brute force.

06-29-2017, 09:30 AM   #81
Beryllos
Member

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

Rep:
Quote:
 Originally Posted by Laserbeak @Beryllos -- You really don't have to explicitly free() all that memory before you quit, when the process ends, the kernel will clean it up for you. You only have to free() memory that you malloc() when you're running a program that continues to run indefinitely and you want that memory back.
Thanks. I know there is a system garbage collector that takes care of this, but without knowing the details, I thought maybe it's faster to free the memory explicitly at the application level. The benefit, if any, is probably insignificant.

06-29-2017, 09:38 AM   #82
Beryllos
Member

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

Rep:
Quote:
 Originally Posted by grail Here is another idea ... if we look at the 1000 numbers with 3 digit combinations, there are only 220 effective combinations that need to be tested as all others are repeats, as per Beryllos' example of 145, 154, 415, 451, 514, and 541 all yielding the same solution. The nice thing on working from this direction is the growth of numbers to be tested as the power increases is considerably less than the total number added: Code: ```10 ^ 3 = 220 to test 10 ^ 4 = 715 to test 10 ^ 5 = 2002 to test 10 ^ 6 = 5005 to test 10 ^ 7 = 11440 to test``` Of course the problem with the above scenario is trying to come up with what numbers are in the shortlist to be checked against. As an idea, I tried this in Ruby and just getting the number above took ages, as you can see I never got to 8 or 9
Great idea. I don't have a clear idea how to generate the sequence. It's the sequence of unique n-digit numbers with sorted digits. I'm thinking a recursive approach might work. I'll try to get back to that later.

06-29-2017, 09:40 AM   #83
Laserbeak
Member

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

Rep:
Quote:
 Originally Posted by Beryllos Thanks. I know there is a system garbage collector that takes care of this, but without knowing the details, I thought maybe it's faster to free the memory explicitly at the application level. The benefit, if any, is probably insignificant.
Sorry I didn't mean to criticize you, it probably looks better to do it that way anyway, I was just commenting. But when your program quits, the kernel has to do a lot to get rid of your process's resources and a few malloc'ed data variables really are insignificant, so I'd bet it's actually slower to do it and then just quit. But again it probably looks nicer.

06-29-2017, 09:49 AM   #84
Beryllos
Member

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

Rep:
Quote:
 Originally Posted by Laserbeak Sorry I didn't mean to criticize you, it probably looks better to do it that way anyway, I was just commenting. But when your program quits, the kernel has to do a lot to get rid of your process's resources and a few malloc'ed data variables really are insignificant, so I'd bet it's actually slower to do it and then just quit. But again it probably looks nicer.
No worries. Just don't criticize my style of using braces!

06-29-2017, 10:05 AM   #85
norobro
Member

Registered: Feb 2006
Distribution: Debian Sid
Posts: 792

Rep:
Quote:
 Originally Posted by grail Here is another idea ... if we look at the 1000 numbers with 3 digit combinations, there are only 220 effective combinations that need to be tested as all others are repeats, as per Beryllos' example of 145, 154, 415, 451, 514, and 541 all yielding the same solution. The nice thing on working from this direction is the growth of numbers to be tested as the power increases is considerably less than the total number added: Code: ```10 ^ 3 = 220 to test 10 ^ 4 = 715 to test 10 ^ 5 = 2002 to test 10 ^ 6 = 5005 to test 10 ^ 7 = 11440 to test``` Of course the problem with the above scenario is trying to come up with what numbers are in the shortlist to be checked against. As an idea, I tried this in Ruby and just getting the number above took ages, as you can see I never got to 8 or 9
Quote:
 Originally Posted by Beryllos Great idea. I don't have a clear idea how to generate the sequence. It's the sequence of unique n-digit numbers with sorted digits. I'm thinking a recursive approach might work. I'll try to get back to that later.
@grail - I had thought about your idea also. Although I've only gotten as far as generating the combinations.

Python executes those combinations pretty quickly using the intertools module. https://docs.python.org/3/library/itertools.html
Code:
```#!/usr/bin/python3

from itertools import combinations_with_replacement

digits=[0,1,2,3,4,5,6,7,8,9]

for i in range(3,16):
nums=combinations_with_replacement(digits, i)
x=0
for tup in nums:  # iterate the container
x=x+1
print("10^", i, "\t= ", x, sep='')```
The results on my machine:
Code:
```\$ time ./counts.py
10^3    = 220
10^4    = 715
10^5    = 2002
10^6    = 5005
10^7    = 11440
10^8    = 24310
10^9    = 48620
10^10   = 92378
10^11   = 167960
10^12   = 293930
10^13   = 497420
10^14   = 817190
10^15   = 1307504

real    0m0.798s
user    0m0.788s
sys     0m0.008s```

1 members found this post helpful.
06-29-2017, 11:02 AM   #86
pan64
LQ Guru

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

Rep:
Quote:
 Originally Posted by Laserbeak Yes, you can look them all up, but that doesn't help you be a better programmer.
that was posted just to be able to check if your code works properly. From the other hand it looks like we may need to prove somehow the statement: we have only 88 numbers, you cannot do that with brute force programs.

06-29-2017, 01:55 PM   #87
Beryllos
Member

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

Rep:
Quote:
 Originally Posted by norobro @grail - I had thought about your idea also. Although I've only gotten as far as generating the combinations. Python executes those combinations pretty quickly using the intertools module. https://docs.python.org/3/library/itertools.html...
I looked up the formula for number of combinations with replacement. Here it is on an online calculator. For 39 digits (the largest Armstrong numbers), there are about 1.7 billion combinations, which is feasible for an exhaustive brute-force search.

06-30-2017, 01:59 AM   #88
grail
LQ Guru

Registered: Sep 2009
Location: Perth
Distribution: Manjaro
Posts: 9,813

Rep:
Quote:
 Originally Posted by norobro @grail - I had thought about your idea also. Although I've only gotten as far as generating the combinations. Python executes those combinations pretty quickly using the intertools module. https://docs.python.org/3/library/itertools.html Code: ```#!/usr/bin/python3 from itertools import combinations_with_replacement digits=[0,1,2,3,4,5,6,7,8,9] for i in range(3,16): nums=combinations_with_replacement(digits, i) x=0 for tup in nums: # iterate the container x=x+1 print("10^", i, "\t= ", x, sep='')``` The results on my machine: Code: ```\$ time ./counts.py 10^3 = 220 10^4 = 715 10^5 = 2002 10^6 = 5005 10^7 = 11440 10^8 = 24310 10^9 = 48620 10^10 = 92378 10^11 = 167960 10^12 = 293930 10^13 = 497420 10^14 = 817190 10^15 = 1307504 real 0m0.798s user 0m0.788s sys 0m0.008s```
Not so surprisingly, when you don't use the correct command, cause you thought you had a better idea, you get crap processing.
So when you use the right commands, I also get good times:
Code:
```\$ cat uniq_digits.rb
#!/usr/bin/env ruby

digits = [0,1,2,3,4,5,6,7,8,9]

3.upto(15){|n| puts "10^#{n} = #{digits.repeated_combination(n).size}"}

\$ time ./uniq_digits.rb
10^3 = 220
10^4 = 715
10^5 = 2002
10^6 = 5005
10^7 = 11440
10^8 = 24310
10^9 = 48620
10^10 = 92378
10^11 = 167960
10^12 = 293930
10^13 = 497420
10^14 = 817190
10^15 = 1307504

real	0m0.213s
user	0m0.173s
sys	0m0.023s```

 06-30-2017, 02:28 AM #89 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 16,207 Rep: grail, please correct me if I'm wrong (back to post #73), but: 1. there are only 900 3-digit numbers exist, not 1000. 2. as you told there are 220 different combinations available, so we need to check only these. 3. but what does this check really mean? - First we should create the sum of powers and we will have 220 possible results. - Obviously we can drop all but the 3-digit ones (like 111 -> 3 or 999 -> 2187). - Now we need to check all of rest if those results can be constructed from the original set of digits - or you can say the result is one of the combinations. It means you need to count the number of digits (both the result and original) and compare them.
06-30-2017, 11:49 AM   #90
Beryllos
Member

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

Rep:
Quote:
 Originally Posted by pan64 grail, please correct me if I'm wrong (back to post #73), but: 1. there are only 900 3-digit numbers exist, not 1000. 2. as you told there are 220 different combinations available, so we need to check only these. 3. but what does this check really mean? - First we should create the sum of powers and we will have 220 possible results. - Obviously we can drop all but the 3-digit ones (like 111 -> 3 or 999 -> 2187). - Now we need to check all of rest if those results can be constructed from the original set of digits - or you can say the result is one of the combinations. It means you need to count the number of digits (both the result and original) and compare them.
That is mostly right. You only have to check 219 combinations, because one of the combinations is 000. Every other combination (e.g., 001) must be checked because it can be rearranged to a 3-digit number (e.g., 100). Check means calculate the sum of powers and see if it has the same combination of digits. It is not necessary to check the number of digits because out-of-range numbers are just combinations having different lengths. Comparison can be accomplished by making a list of digits, sorting the list, and comparing lists. I'll show an example in Python later.

 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 01:59 PM.

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