Narcissistic decimal number
You are encouraged to solve this task according to the task description, using any language you may know.
A Narcissistic decimal number is a positive decimal number, in which if there are digits in the number then the sum of all the individual digits of the number raised to the power is equal to .
For example, if is 153 then , the number of digits is 3 and we have and so 153 is a narcissistic decimal number.
The task is to generate and show here, the first 25 narcissistic numbers.
C
<lang c>#include <stdio.h>
typedef long long xint;
- define MAX_LEN 16
xint dpow[MAX_LEN + 1][11];
void init(void) { int i, p; for (p = 0; p <= MAX_LEN; p++) for (i = 0; i <= 10; i++) dpow[p][i] = p ? dpow[p-1][i] * i : 1; }
void narc(int power, int pos, xint value, xint dsum) { xint i, ds, v, ten;
if (!pos) { printf(" %lld", value); return; }
ten = dpow[pos - 1][10]; for (i = (pos == power); i < 10; i++) { ds = dsum + dpow[power][i]; v = value + i * ten;
if (ds >= v + ten) break;
if (v <= ds + dpow[power][9] * (pos - 1)) narc(power, pos - 1, v, ds); } }
int main(void) { int i; init();
for (i = 1; i <= 16; i++) { printf("length %d:", i); narc(i, i, 0, 0); putchar('\n'); }
return 0; }</lang>
- Output:
length 1: 1 2 3 4 5 6 7 8 9 length 2: length 3: 153 370 371 407 length 4: 1634 8208 9474 length 5: 54748 92727 93084 length 6: 548834 length 7: 1741725 4210818 9800817 9926315 length 8: 24678050 24678051 88593477 length 9: 146511208 472335975 534494836 912985153 ^C
D
Simple Version
<lang d>void main() {
import std.stdio, std.algorithm, std.conv, std.range;
immutable isNarcissistic = (in uint n) pure =>
n.text.map!(d => (d - '0') ^^ n.text.length).sum == n;
writefln("%(%(%d %)\n%)",
uint.max.iota.filter!isNarcissistic.take(25).chunks(5));
}</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315
Faster Version
<lang d>import std.stdio, std.algorithm, std.range, std.array;
uint[] narcissists(in uint m) pure nothrow {
typeof(return) result;
foreach (immutable uint digits; 0 .. 10) {
const digitPowers = 10.iota.map!(i => i ^^ digits).array;
foreach (immutable n; 10 ^^ (digits - 1) .. 10 ^^ digits) {
uint div = n, digitPSum;
while (div) {
digitPSum += digitPowers[div % 10];
div /= 10;
}
if (n == digitPSum) {
result ~= n;
if (result.length >= m)
return result;
}
}
}
assert(0);
}
void main() {
writefln("%(%(%d %)\n%)", 25.narcissists.chunks(5));
}</lang> With LDC2 compiler prints the same output in less than 0.3 seconds.
Perl 6
Here is a straightforward, naive implementation. It works but takes ages. <lang perl6>sub is-narcissistic(Int $n) { $n == [+] $n.comb »**» $n.chars }
for 0 .. * {
if .&is-narcissistic {
.say; last if ++state$ >= 25;
}
}</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 153 370 371 407 Ctrl-C
Here the program was interrupted but if you're patient enough you'll see all the 25 numbers.
Here's a faster version that precalculates the values for base 1000 digits: <lang perl6>sub kigits($n) {
my int $i = $n;
my int $b = 1000;
my @result;
while $i { push @result, $i % $b; $i = $i div $b }
@result;
}
constant narcissistic = 0, map -> $d {
my @t = 0..9 X** $d;
my @table = @t X+ @t X+ @t;
sub is-narcissistic(\n) { n == [+] @table[kigits(n)] }
gather take $_ if is-narcissistic($_) for 10**($d-1) ..^ 10**$d;
}, 1..*;
for narcissistic {
say ++state $n, "\t", $_; last if $n == 25;
}</lang>
- Output:
1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 153 12 370 13 371 14 407 15 1634 16 8208 17 9474 18 54748 19 92727 20 93084 21 548834 22 1741725 23 4210818 24 9800817 25 9926315
Python
This solution pre-computes the powers once.
<lang python>from __future__ import print_function from itertools import count, islice
def narcissists():
for digits in count(0):
digitpowers = [i**digits for i in range(10)]
for n in range(int(10**(digits-1)), 10**digits):
div, digitpsum = n, 0
while div:
div, mod = divmod(div, 10)
digitpsum += digitpowers[mod]
if n == digitpsum:
yield n
for i, n in enumerate(islice(narcissists(), 25), 1):
print(n, end=' ') if i % 5 == 0: print()
print()</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315
REXX
Programming note: The three REXX examples below use the standard definition of a narcissistic number, and
that definition includes 0 (zero).
idomatic
<lang rexx>/*REXX program to generate and display a number of narcissistic numbers.*/ numeric digits 39 /*be able to handle the largest #*/ parse arg N .; if N== then N=25 /*get number of narcissistic #'s.*/ N=min(N,89) /*there are 89 narcissistic #s.*/
- =0 /*number of narcissistic # so far*/
do j=0 until #==N; L=length(j) /*get the length of the J number.*/
s=left(j,1)**L /*1st digit in J raised to L pow.*/
do k=2 for L-1 until s>j /*perform for each digit in J. */
s=s + substr(j,k,1)**L /*add digit raised to pow to sum.*/
end /*k*/ /* [↑] calculate the rest of sum*/
if s\==j then iterate /*does sum equal to J? No ··· */
#=#+1 /*bump the narcissistic num count*/
say right(#,9) ' narcissistic:' j /*display index & narcissistic #.*/
end /*j*/ /* [↑] this list starts at 0. */
/*stick a fork in it, we're done.*/</lang>
output when using the default input:
1 narcissistic: 0
2 narcissistic: 1
3 narcissistic: 2
4 narcissistic: 3
5 narcissistic: 4
6 narcissistic: 5
7 narcissistic: 6
8 narcissistic: 7
9 narcissistic: 8
10 narcissistic: 9
11 narcissistic: 153
12 narcissistic: 370
13 narcissistic: 371
14 narcissistic: 407
15 narcissistic: 1634
16 narcissistic: 8208
17 narcissistic: 9474
18 narcissistic: 54748
19 narcissistic: 92727
20 narcissistic: 93084
21 narcissistic: 548834
22 narcissistic: 1741725
23 narcissistic: 4210818
24 narcissistic: 9800817
25 narcissistic: 9926315
optimized
This REXX version is optimized to pre-compute all the ten (single) digits raised to all possible powers (which is 39). <lang rexx>/*REXX program to generate and display a number of narcissistic numbers.*/ numeric digits 39 /*be able to handle the largest #*/ parse arg N .; if N== then N=25 /*get number of narcissistic #'s.*/ N=min(N,89) /*there are 89 narcissistic #s.*/
do w=1 for 39 /*generate tables: digits ^ L pow*/
do i=0 for 10; @.w.i=i**w; end /*build table of 10 digs ^ L pow.*/
end /*w*/ /* [↑] table is of a fixed size.*/
- =0 /*number of narcissistic # so far*/
do j=0 until #==N; L=length(j) /*get the length of the J number.*/
_=left(j,1) /*select the first digit to sum. */
s=@.L._ /*sum of the J digs ^ L (so far)*/
do k=2 for L-1 until s>j /*perform for each digit in J. */
_=substr(j,k,1) /*select the next digit to sum. */
s=s+@.L._ /*add digit raised to pow to sum.*/
end /*k*/ /* [↑] calculate the rest of sum*/
if s\==j then iterate /*does sum equal to J? No ··· */
#=#+1 /*bump the narcissistic num count*/
say right(#,9) ' narcissistic:' j /*display index & narcissistic #.*/
end /*j*/ /* [↑] this list starts at 0. */
/*stick a fork in it, we're done.*/</lang>
output is the same as 1st REXX version.
optimized, unrolled
This REXX version is optimized by unrolling part of the DO loop that sums the digits.
The unrolling also necessitated the special handling of one- and two-digit narcissistic numbers.
<lang rexx>/*REXX program to generate and display a number of narcissistic numbers.*/
numeric digits 39 /*be able to handle the largest #*/
parse arg N .; if N== then N=25 /*get number of narcissistic #'s.*/
N=min(N,89) /*there are 89 narcissistic #s.*/
do w=1 for 39 /*generate tables: digits ^ L pow*/
do i=0 for 10; @.w.i=i**w; end /*build table of 10 digs ^ L pow.*/
end /*w*/ /* [↑] table is of a fixed size.*/
- =0 /*number of narcissistic # so far*/
do low=0 for 10; call tell low; end /*handle the first one-digit nums*/
/* [↓] skip the 2-digit numbers.*/
do j=100; L=length(j) /*get the length of the J number.*/
_1=left(j,1); _2=substr(j,2,1) /*select 1st & 2nd digit to sum. */
_R=right(j,1) /*select the right digit to sum. */
s=@.L._1 + @.L._2 + @.L._R /*sum of the J digs ^ L (so far)*/
do k=3 for L-3 until s>j /*perform for each digit in J. */
_=substr(j,k,1) /*select the next digit to sum. */
s=s + @.L._ /*add digit raised to pow to sum.*/
end /*k*/ /* [↑] calculate the rest of sum*/
if s==j then call tell j /*does sum equal to J? Yes ···*/
end /*j*/ /* [↑] this list starts at 0. */
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────TELL subroutine─────────────────────*/ tell: parse arg y /*get narcissistic # to display. */
#=#+1 /*bump the narcissistic # count. */
say right(#,9) ' narcissistic:' y /*display index & narcissistic #.*/
if #==N then exit /*stick a fork in it, we're done.*/
return /*return and keep on truckin'. */</lang>
output is the same as 1st REXX version.