Narcissistic decimal number

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 non-negative integer, $n$ in which if there are $m$ digits in its decimal representation then the sum of all the individual digits of the decimal representation raised to the power $m$ is equal to $n$.

For example, if $n$ is 153 then $m$, the number of digits is 3 and we have $1^{3}+5^{3}+3^{3}=1+125+27=153$ and so 153 is a narcissistic decimal integer number.

The task is to generate and show here, the first 25 narcissistic integer numbers.

Note: $0^{1}=0$, the first in the series.

C

It prints the first 25 numbers, though not in order... <lang c>#include <stdio.h>

1. include <gmp.h>

1. define MAX_LEN 81

mpz_t power[10]; mpz_t dsum[MAX_LEN + 1]; int cnt[10], len;

void check_perm(void) { char s[MAX_LEN + 1]; int i, c, out[10] = { 0 };

mpz_get_str(s, 10, dsum[0]); for (i = 0; s[i]; i++) { c = s[i]-'0'; if (++out[c] > cnt[c]) return; }

if (i == len) gmp_printf(" %Zd", dsum[0]); }

void narc_(int pos, int d) { if (!pos) { check_perm(); return; }

do { mpz_add(dsum[pos-1], dsum[pos], power[d]); ++cnt[d]; narc_(pos - 1, d); --cnt[d]; } while (d--); }

void narc(int n) { int i; len = n; for (i = 0; i < 10; i++) mpz_ui_pow_ui(power[i], i, n);

mpz_init_set_ui(dsum[n], 0);

printf("length %d:", n); narc_(n, 9); putchar('\n'); }

int main(void) { int i;

for (i = 0; i <= 10; i++) mpz_init(power[i]); for (i = 1; i <= MAX_LEN; i++) narc(i);

return 0; }</lang>

Output:

length 1: 9 8 7 6 5 4 3 2 1 0
length 2:
length 3: 407 371 370 153
length 4: 9474 8208 1634
length 5: 93084 92727 54748
length 6: 548834
length 7: 9926315 9800817 4210818 1741725
length 8: 88593477 24678051 24678050
length 9: 912985153 534494836 472335975 146511208
length 10: 4679307774
length 11: 94204591914 82693916578 49388550606 44708635679 42678290603 40028394225 32164049651 32164049650
length 12:
length 13:
length 14: 28116440335967
length 15:
length 16: 4338281769391371 4338281769391370
length 17: 35875699062250035 35641594208964132 21897142587612075
length 18:
^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.

J

<lang j>getDigits=: "."0@": NB. get digits from number isNarc=: (= +/@(] ^ #)@getDigits)"0 NB. test numbers for Narcissism</lang> Example Usage <lang j> (#~ isNarc) i.1e7 NB. display Narcissistic numbers 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</lang>

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, (1..*).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;

}

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

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.*/

1. =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.*/

1. =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.*/

1. =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. =#+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.