LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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


Reply
  Search this Thread
Old 06-29-2017, 08:19 AM   #76
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319

Quote:
Originally Posted by Laserbeak View Post
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.
 
Old 06-29-2017, 08:59 AM   #77
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
a total of 88 narcissistic numbers exist in base 10 http://mathworld.wolfram.com/NarcissisticNumber.html
 
1 members found this post helpful.
Old 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: Reputation: 143Reputation: 143
Quote:
Originally Posted by pan64 View Post
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.
 
Old 06-29-2017, 09:14 AM   #79
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by pan64 View Post
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.
 
Old 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: Reputation: 143Reputation: 143
Quote:
Originally Posted by Beryllos View Post
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.
 
Old 06-29-2017, 09:30 AM   #81
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by Laserbeak View Post
@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.
 
Old 06-29-2017, 09:38 AM   #82
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by grail View Post
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.
 
Old 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: Reputation: 143Reputation: 143
Quote:
Originally Posted by Beryllos View Post
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.
 
Old 06-29-2017, 09:49 AM   #84
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by Laserbeak View Post
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!
 
Old 06-29-2017, 10:05 AM   #85
norobro
Member
 
Registered: Feb 2006
Distribution: Debian Sid
Posts: 792

Rep: Reputation: 331Reputation: 331Reputation: 331Reputation: 331
Quote:
Originally Posted by grail View Post
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 View Post
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.
Old 06-29-2017, 11:02 AM   #86
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
Quote:
Originally Posted by Laserbeak View Post
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.
 
Old 06-29-2017, 01:55 PM   #87
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by norobro View Post
@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.
 
Old 06-30-2017, 01:59 AM   #88
grail
LQ Guru
 
Registered: Sep 2009
Location: Perth
Distribution: Manjaro
Posts: 9,813

Rep: Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071Reputation: 3071
Quote:
Originally Posted by norobro View Post
@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
 
Old 06-30-2017, 02:28 AM   #89
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep: Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419Reputation: 5419
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.
 
Old 06-30-2017, 11:49 AM   #90
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 529

Rep: Reputation: 319Reputation: 319Reputation: 319Reputation: 319
Quote:
Originally Posted by pan64 View Post
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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



Similar Threads
Thread Thread Starter Forum Replies Last Post
printing line numbers for code bauer172uw Programming 3 04-13-2006 11:10 PM
C programming - sorting random numbers Gigantor Programming 8 12-05-2005 10:32 PM
Printing numbers from a text file dynamically mrobertson Programming 1 06-28-2005 08:19 AM
printing numbers without using semicolon vijeesh_ep Programming 18 09-08-2004 11:59 AM
printing line numbers? fisheromen1031 Programming 1 07-27-2004 02:19 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 01:59 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration