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

Beryllos · 06-29-2017, 08:19 AM

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.

pan64 · 06-29-2017, 08:59 AM

a total of 88 narcissistic numbers exist in base 10 http://mathworld.wolfram.com/NarcissisticNumber.html

Laserbeak · 06-29-2017, 09:07 AM

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.

Beryllos · 06-29-2017, 09:14 AM

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.

Laserbeak · 06-29-2017, 09:29 AM

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.

Beryllos · 06-29-2017, 09:30 AM

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.

Beryllos · 06-29-2017, 09:38 AM

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.

Laserbeak · 06-29-2017, 09:40 AM

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.

Beryllos · 06-29-2017, 09:49 AM

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!

norobro · 06-29-2017, 10:05 AM

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

pan64 · 06-29-2017, 11:02 AM

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.

Beryllos · 06-29-2017, 01:55 PM

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.

grail · 06-30-2017, 01:59 AM

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

pan64 · 06-30-2017, 02:28 AM

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.

Beryllos · 06-30-2017, 11:49 AM

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.