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, in which if there are digits in its decimal representation then the sum of all the individual digits of the decimal representation 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 integer number.
The task is to generate and show here, the first 25 narcissistic integer numbers.
Note: , the first in the series.
Ada
<lang Ada>with Ada.Text_IO;
procedure Narcissistic is
function Is_Narcissistic(N: Natural) return Boolean is Decimals: Natural := 1; M: Natural := N; Sum: Natural := 0; begin while M >= 10 loop
M := M / 10; Decimals := Decimals + 1;
end loop; M := N; while M >= 1 loop
Sum := Sum + (M mod 10) ** Decimals; M := M/10;
end loop; return Sum=N; end Is_Narcissistic; Count, Current: Natural := 0;
begin
while Count < 25 loop if Is_Narcissistic(Current) then
Ada.Text_IO.Put(Integer'Image(Current)); Count := Count + 1;
end if; Current := Current + 1; end loop;
end Narcissistic;</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
AutoHotkey
<lang AutoHotkey>
- NoEnv ; Do not try to use environment variables
SetBatchLines, -1 ; Execute as quickly as you can
StartCount := A_TickCount Narc := Narc(25) Elapsed := A_TickCount - StartCount
MsgBox, Finished in %Elapsed%ms`n%Narc% return
Narc(m) { Found := 0, Lower := 0 Progress, B2 Loop { Max := 10 ** Digits:=A_Index Loop, 10 Index := A_Index-1, Powers%Index% := Index**Digits While Lower < Max { Sum := 0 Loop, Parse, Lower Sum += Powers%A_LoopField% Loop, 10 {
if (Lower + (Index := A_Index-1) == Sum + Powers%Index%) { Out .= Lower+Index . (Mod(++Found,5) ? ", " : "`n") Progress, % Found/M*100 if (Found >= m) { Progress, Off return Out } } } Lower += 10 } } } </lang>
- Output:
Finished in 17690ms 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
This is a derivative of the python example, but modified for speed reasons.
Instead of summing all the powers of all the numbers at once, we sum the powers for this multiple of 10, then check each number 0 through 9 at once before summing the next multiple of 10. This way, we don't have to calculate the sum of 174172_ for every number 1741720 through 1741729.
AWK
<lang AWK>
- syntax: GAWK -f NARCISSISTIC_DECIMAL_NUMBER.AWK
BEGIN {
for (n=0;;n++) { leng = length(n) sum = 0 for (i=1; i<=leng; i++) { c = substr(n,i,1) sum += c ^ leng } if (n == sum) { printf("%d ",n) if (++count == 25) { break } } } exit(0)
} </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
C
It prints the first 25 numbers, though not in order... <lang c>#include <stdio.h>
- include <gmp.h>
- 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
C++
<lang cpp>
- include <iostream>
- include <vector>
using namespace std; typedef unsigned int uint;
class NarcissisticDecs { public:
void makeList( int mx ) {
uint st = 0, tl; int pwr = 0, len;
while( narc.size() < mx )
{ len = getDigs( st ); if( pwr != len ) { pwr = len; fillPower( pwr ); }
tl = 0;
for( int i = 1; i < 10; i++ ) tl += static_cast<uint>( powr[i] * digs[i] );
if( tl == st ) narc.push_back( st ); st++; }
}
void display() {
for( vector<uint>::iterator i = narc.begin(); i != narc.end(); i++ ) cout << *i << " "; cout << "\n\n";
}
private:
int getDigs( uint st ) {
memset( digs, 0, 10 * sizeof( int ) ); int r = 0; while( st ) { digs[st % 10]++; st /= 10; r++; }
return r; }
void fillPower( int z ) {
for( int i = 1; i < 10; i++ ) powr[i] = pow( static_cast<float>( i ), z );
}
vector<uint> narc; uint powr[10]; int digs[10];
};
int main( int argc, char* argv[] ) {
NarcissisticDecs n; n.makeList( 25 ); n.display(); return system( "pause" );
} </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
C#
<lang csharp> using System;
namespace Narcissistic {
class Narcissistic { public bool isNarcissistic(int z) { if (z < 0) return false; string n = z.ToString(); int t = 0, l = n.Length; foreach (char c in n) t += Convert.ToInt32(Math.Pow(Convert.ToDouble(c - 48), l));
return t == z; } }
class Program { static void Main(string[] args) { Narcissistic n = new Narcissistic(); int c = 0, x = 0; while (c < 25) { if (n.isNarcissistic(x)) { if (c % 5 == 0) Console.WriteLine(); Console.Write("{0,7} ", x); c++; } x++; } Console.WriteLine("\n\nPress any key to continue..."); Console.ReadKey(); } }
} </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
or
<lang csharp> //Narcissistic numbers: Nigel Galloway: February 17th., 2015 using System; using System.Collections.Generic; using System.Linq;
namespace RC {
public static class NumberEx { public static IEnumerable<int> Digits(this int n) { List<int> digits = new List<int>(); while (n > 0) { digits.Add(n % 10); n /= 10; } return digits.AsEnumerable(); } }
class Program { static void Main(string[] args) { foreach (int N in Enumerable.Range(0, Int32.MaxValue).Where(k => { var digits = k.Digits(); return digits.Sum(x => Math.Pow(x, digits.Count())) == k; }).Take(25)) { System.Console.WriteLine(N); } } }
} </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
Common Lisp
<lang lisp> (defun integer-to-list (n)
(map 'list #'digit-char-p (prin1-to-string n)))
(defun narcissisticp (n)
(let* ((lst (integer-to-list n)) (e (length lst))) (= n
(reduce #'+ (mapcar (lambda (x) (expt x e)) lst)))))
(defun start ()
(loop for c from 0 while (< narcissistic 25) counting (narcissisticp c) into narcissistic do (if (narcissisticp c) (print c))))
</lang>
- Output:
CL-USER> (start) 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 NIL
D
Simple Version
<lang d>void main() {
import std.stdio, std.algorithm, std.conv, std.range;
immutable isNarcissistic = (in uint n) pure @safe => 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
Fast Version
<lang d>import std.stdio, std.algorithm, std.range, std.array;
uint[] narcissists(in uint m) pure nothrow @safe {
typeof(return) result;
foreach (immutable uint digits; 0 .. 10) { const digitPowers = 10.iota.map!(i => i ^^ digits).array;
foreach (immutable uint n; 10 ^^ (digits - 1) .. 10 ^^ digits) { uint digitPSum, div = n; 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.
Faster Version
<lang d>import std.stdio, std.bigint, std.conv;
struct Narcissistics(TNum, uint maxLen) {
TNum[10] power; TNum[maxLen + 1] dsum; uint[10] count; uint len;
void checkPerm() const { uint[10] mout;
immutable s = dsum[0].text; foreach (immutable d; s) { immutable c = d - '0'; if (++mout[c] > count[c]) return; }
if (s.length == len) writef(" %d", dsum[0]); }
void narc2(in uint pos, uint d) { if (!pos) { checkPerm; return; }
do { dsum[pos - 1] = dsum[pos] + power[d]; count[d]++; narc2(pos - 1, d); count[d]--; } while (d--); }
void show(in uint n) { len = n; foreach (immutable i, ref p; power) p = TNum(i) ^^ n; dsum[n] = 0; writef("length %d:", n); narc2(n, 9); writeln; }
}
void main() {
enum maxLength = 16; Narcissistics!(ulong, maxLength) narc; //Narcissistics!(BigInt, maxLength) narc; // For larger numbers. foreach (immutable i; 1 .. maxLength + 1) narc.show(i);
}</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
With LDC2 compiler and maxLength=16 the run-time is about 0.64 seconds.
F#
<lang fsharp> //Naïve solution of Narcissitic number: Nigel Galloway - Febryary 18th., 2015 open System let rec _Digits (n,g) = if n < 10 then n::g else _Digits(n/10,n%10::g)
seq{0 .. Int32.MaxValue} |> Seq.filter (fun n ->
let d = _Digits (n, []) d |> List.fold (fun a l -> a + int ((float l) ** (float (List.length d)))) 0 = n) |> Seq.take(25) |> Seq.iter (printfn "%A")
</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
FunL
<lang funl>def narcissistic( start ) =
power = 1 powers = array( 0..9 )
def narc( n ) = num = n.toString() m = num.length()
if power != m power = m powers( 0..9 ) = [i^m | i <- 0..9]
if n == sum( powers(int(d)) | d <- num ) n # narc( n + 1 ) else narc( n + 1 )
narc( start )
println( narcissistic(0).take(25) )</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]
Go
Nothing fancy as it runs in a fraction of a second as-is. <lang go>package main
import "fmt"
func narc(n int) []int { power := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} limit := 10 result := make([]int, 0, n) for x := 0; len(result) < n; x++ { if x >= limit { for i := range power { power[i] *= i // i^m } limit *= 10 } sum := 0 for xx := x; xx > 0; xx /= 10 { sum += power[xx%10] } if sum == x { result = append(result, x) } } return result }
func main() { fmt.Println(narc(25)) }</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]
Haskell
<lang Haskell>import System.IO
digits :: (Read a, Show a) => a -> [a] digits n = map (read . (:[])) $ show n
isNarcissistic :: (Show a, Read a, Num a, Eq a) => a -> Bool isNarcissistic n =
let dig = digits n len = length dig in n == (sum $ map (^ len) $ dig)
main :: IO () main = do
hSetBuffering stdout NoBuffering putStrLn $ unwords $ map show $ take 25 $ filter isNarcissistic [(0 :: Int)..]</lang>
Icon and Unicon
The following is a quick, dirty, and slow solution that works in both languages: <lang unicon>procedure main(A)
limit := integer(A[1]) | 25 every write(isNarcissitic(seq(0))\limit)
end
procedure isNarcissitic(n)
sn := string(n) m := *sn every (sum := 0) +:= (!sn)^m return sum = n
end</lang>
Sample run:
->ndn 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 ->
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>
Java
<lang java5>public class Narc{ public static boolean isNarc(long x){ if(x < 0) return false;
String xStr = Long.toString(x); int m = xStr.length(); long sum = 0;
for(char c : xStr.toCharArray()){ sum += Math.pow(Character.digit(c, 10), m); } return sum == x; }
public static void main(String[] args){ for(long x = 0, count = 0; count < 25; x++){ if(isNarc(x)){ System.out.print(x + " "); count++; } } } }</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
JavaScript
<lang javascript>function isNarc(x) {
var str = x.toString(), i, sum = 0, l = str.length; if (x < 0) { return false; } else { for (i = 0; i < l; i++) { sum += Math.pow(str.charAt(i), l); } } return sum == x;
} function main(){
var n = []; for (var x = 0, count = 0; count < 25; x++){ if (isNarc(x)){ n.push(x); count++; } } return n.join(' ');
}</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"
MATLAB
<lang MATLAB>function testNarcissism
x = 0; c = 0; while c < 25 if isNarcissistic(x) fprintf('%d ', x) c = c+1; end x = x+1; end fprintf('\n')
end
function tf = isNarcissistic(n)
dig = sprintf('%d', n) - '0'; tf = n == sum(dig.^length(dig));
end</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
Oforth
<lang Oforth>func: isNarcissistic(n) { | m i |
n 0 while(n 0 <>) [ n 10 divrem ->n swap 1 + ] ->m 0 m loop: i [ swap m pow asInteger + ] ==
}
func: genNarcissistic { | l |
ListBuffer new ->l 0 while(l size 25 <>) [ dup isNarcissistic ifTrue: [ dup l add ] 1 + ] drop l println
}</lang>
- Output:
>genNarcissistic [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]
Pascal
A recursive version starting at the highest digit and recurses to digit 0. Bad runtime. One more digit-> 10x runtime runtime ~ 10^(count of Digits). <lang pascal> program NdN; //Narcissistic decimal number const
Base = 10; MaxDigits = 16;
type
tDigit = 0..Base-1; tcntDgt= 0..MaxDigits-1;
var
powDgt : array[tDigit] of NativeUint; PotdgtPos: array[tcntDgt] of NativeUint; UpperSum : array[tcntDgt] of NativeUint;
tmpSum, tmpN, actPot : NativeUint;
procedure InitPowDig; var
i,j : NativeUint;
Begin
j := 1; For i := 0 to High(tDigit) do Begin powDgt[i] := i; PotdgtPos[i] := j; j := j*Base; end; actPot := 0;
end;
procedure NextPowDig; var
i,j : NativeUint;
Begin
// Next power of digit = i ^ actPot,always 0 = 0 , 1 = 1 For i := 2 to High(tDigit) do powDgt[i] := powDgt[i]*i; // number of digits times 9 ^(max number of digits) j := powDgt[High(tDigit)]; For i := 0 to High(UpperSum) do UpperSum[i] := (i+1)*j; inc(actPot);
end; procedure OutPutNdN(n:NativeUint); Begin
write(n,' ');
end;
procedure NextDgtSum(dgtPos,i,sumPowDgt,n:NativeUint); begin
//unable to reach sum IF (sumPowDgt+UpperSum[dgtPos]) < n then EXIT; repeat tmpN := n+PotdgtPos[dgtPos]*i; tmpSum := sumPowDgt+powDgt[i]; //unable to get smaller if tmpSum > tmpN then EXIT; IF tmpSum = tmpN then OutPutNdN(tmpSum); IF dgtPos>0 then NextDgtSum(dgtPos-1,0,tmpSum,tmpN); inc(i); until i >= Base;
end;
var
i : NativeUint;
Begin
InitPowDig; For i := 1 to 9 do Begin write(' length ',actPot+1:2,': '); //start with 1 in front, else you got i-times 0 in front NextDgtSum(actPot,1,0,0); writeln; NextPowDig; end;
end.</lang>
- output
time ./NdN length 1: 1 2 3 4 5 6 7 8 9 length 2: length 3: 153 370 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 24678050 24678051 88593477 length 9: 146511208 472335975 534494836 912985153 real 0m1.000s
Perl
Simple version using a naive predicate. About 15 seconds. <lang perl>sub is_narcissistic {
my $n = shift; my($k,$sum) = (length($n),0); $sum += $_**$k for split(//,$n); $n == $sum;
} my $i = 0; for (1..25) {
$i++ while !is_narcissistic($i); say $i++;
}</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; gather while $i { take $i % $b; $i = $i div $b; }
}
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
PicoLisp
<lang PicoLisp>(let (C 25 N 0 L 1)
(loop (when (= N (sum ** (mapcar format (chop N)) (need L L)) ) (println N) (dec 'C) ) (inc 'N) (setq L (length N)) (T (=0 C) 'done) ) )
(bye)</lang>
PL/I
version 1
<lang pli> narn: Proc Options(main);
Dcl (j,k,l,nn,n,sum) Dec Fixed(15)init(0); Dcl s Char(15) Var; Dcl p(15) Pic'9' Based(addr(s)); Dcl (ms,msa,ela) Dec Fixed(15); Dcl tim Char(12); n=30; ms=milliseconds(); Do j=0 By 1 Until(nn=n); s=dec2str(j); l=length(s); sum=left(s,1)**l; Do k=2 To l; sum=sum+substr(s,k,1)**l; If sum>j Then Leave; End; If sum=j Then Do nn=nn+1; msa=milliseconds(); ela=msa-ms; /*Put Skip Data(ms,msa,ela);*/ ms=msa; /*yyyymmddhhmissmis*/ tim=translate('ij:kl:mn.opq',datetime(),'abcdefghijklmnopq'); Put Edit(nn,' narcissistic:',j,ela,tim) (Skip,f(9),a,f(12),f(15),x(2),a(12)); End; End; dec2str: Proc(x) Returns(char(16) var); Dcl x Dec Fixed(15); Dcl ds Pic'(14)z9'; ds=x; Return(trim(ds)); End; milliseconds: Proc Returns(Dec Fixed(15)); Dcl c17 Char(17); dcl 1 * Def C17, 2 * char(8), 2 hh Pic'99', 2 mm Pic'99', 2 ss Pic'99', 2 ms Pic'999'; Dcl result Dec Fixed(15); c17=datetime(); result=(((hh*60+mm)*60)+ss)*1000+ms; /* Put Edit(translate('ij:kl:mn.opq',datetime(),'abcdefghijklmnopq'), result) (Skip,a(12),F(15)); */ Return(result); End End;</lang>
- Output:
1 narcissistic: 0 0 16:10:17.586 2 narcissistic: 1 0 16:10:17.586 3 narcissistic: 2 0 16:10:17.586 4 narcissistic: 3 0 16:10:17.586 5 narcissistic: 4 0 16:10:17.586 6 narcissistic: 5 0 16:10:17.586 7 narcissistic: 6 0 16:10:17.586 8 narcissistic: 7 0 16:10:17.586 9 narcissistic: 8 0 16:10:17.586 10 narcissistic: 9 0 16:10:17.586 11 narcissistic: 153 0 16:10:17.586 12 narcissistic: 370 0 16:10:17.586 13 narcissistic: 371 0 16:10:17.586 14 narcissistic: 407 0 16:10:17.586 15 narcissistic: 1634 10 16:10:17.596 16 narcissistic: 8208 30 16:10:17.626 17 narcissistic: 9474 10 16:10:17.636 18 narcissistic: 54748 210 16:10:17.846 19 narcissistic: 92727 170 16:10:18.016 20 narcissistic: 93084 0 16:10:18.016 21 narcissistic: 548834 1630 16:10:19.646 22 narcissistic: 1741725 4633 16:10:24.279 23 narcissistic: 4210818 10515 16:10:34.794 24 narcissistic: 9800817 28578 16:11:03.372 25 narcissistic: 9926315 510 16:11:03.882 26 narcissistic: 24678050 73077 16:12:16.959 27 narcissistic: 24678051 0 16:12:16.959 28 narcissistic: 88593477 365838 16:18:22.797 29 narcissistic: 146511208 276228 16:22:59.025 30 narcissistic: 472335975 1682125 16:51:01.150
version 2
Precompiled powers <lang>*process source xref attributes or(!);
narn3: Proc Options(main); Dcl (i,j,k,l,nn,n,sum) Dec Fixed(15)init(0); Dcl s Char(15) Var; dcl t Char(15); Dcl p9(15) Pic'9' Based(addr(t)); Dcl (ms,msa,ela) Dec Fixed(15); Dcl tim Char(12); n=30; Dcl power(0:9,1:9) Dec Fixed(15); Do i=0 To 9; Do j=1 To 9; Power(i,j)=i**j; End; End; ms=milliseconds(); Do j=0 By 1 Until(nn=n); s=dec2str(j); t=s; l=length(s); sum=power(p9(1),l); Do k=2 To l; sum=sum+power(p9(k),l); If sum>j Then Leave; End; If sum=j Then Do; nn=nn+1; msa=milliseconds(); ela=msa-ms; ms=msa; /*yyyymmddhhmissmis*/ tim=translate('ij:kl:mn.opq',datetime(),'abcdefghijklmnopq'); Put Edit(nn,' narcissistic:',j,ela,tim) (Skip,f(9),a,f(12),f(15),x(2),a(12)); End; End;
dec2str: Proc(x) Returns(char(15) var); Dcl x Dec Fixed(15); Dcl ds Pic'(14)z9'; ds=x; Return(trim(ds)); End;
milliseconds: Proc Returns(Dec Fixed(15)); Dcl c17 Char(17); dcl 1 * Def C17, 2 * char(8), 2 hh Pic'99', 2 mm Pic'99', 2 ss Pic'99', 2 ms Pic'999'; Dcl result Dec Fixed(15); c17=datetime(); result=(((hh*60+mm)*60)+ss)*1000+ms; Return(result); End; End;</lang>
- Output:
1 narcissistic: 0 0 00:41:43.632 2 narcissistic: 1 0 00:41:43.632 3 narcissistic: 2 0 00:41:43.632 4 narcissistic: 3 0 00:41:43.632 5 narcissistic: 4 0 00:41:43.632 6 narcissistic: 5 0 00:41:43.632 7 narcissistic: 6 0 00:41:43.632 8 narcissistic: 7 0 00:41:43.632 9 narcissistic: 8 0 00:41:43.632 10 narcissistic: 9 0 00:41:43.632 11 narcissistic: 153 0 00:41:43.632 12 narcissistic: 370 0 00:41:43.632 13 narcissistic: 371 0 00:41:43.632 14 narcissistic: 407 0 00:41:43.632 15 narcissistic: 1634 0 00:41:43.632 16 narcissistic: 8208 20 00:41:43.652 17 narcissistic: 9474 10 00:41:43.662 18 narcissistic: 54748 130 00:41:43.792 19 narcissistic: 92727 120 00:41:43.912 20 narcissistic: 93084 0 00:41:43.912 21 narcissistic: 548834 1310 00:41:45.222 22 narcissistic: 1741725 3642 00:41:48.864 23 narcissistic: 4210818 7488 00:41:56.352 24 narcissistic: 9800817 22789 00:42:19.141 25 narcissistic: 9926315 550 00:42:19.691 26 narcissistic: 24678050 45358 00:43:05.049 27 narcissistic: 24678051 0 00:43:05.049 28 narcissistic: 88593477 237960 00:47:03.009 29 narcissistic: 146511208 199768 00:50:22.777 30 narcissistic: 472335975 1221384 01:10:44.161
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
Faster Version
<lang python>try:
import psyco psyco.full()
except:
pass
class Narcissistics:
def __init__(self, max_len): self.max_len = max_len self.power = [0] * 10 self.dsum = [0] * (max_len + 1) self.count = [0] * 10 self.len = 0 self.ord0 = ord('0')
def check_perm(self, out = [0] * 10): for i in xrange(10): out[i] = 0
s = str(self.dsum[0]) for d in s: c = ord(d) - self.ord0 out[c] += 1 if out[c] > self.count[c]: return
if len(s) == self.len: print self.dsum[0],
def narc2(self, pos, d): if not pos: self.check_perm() return
while True: self.dsum[pos - 1] = self.dsum[pos] + self.power[d] self.count[d] += 1 self.narc2(pos - 1, d) self.count[d] -= 1 if d == 0: break d -= 1
def show(self, n): self.len = n for i in xrange(len(self.power)): self.power[i] = i ** n self.dsum[n] = 0 print "length %d:" % n, self.narc2(n, 9) print
def main():
narc = Narcissistics(14) for i in xrange(1, narc.max_len + 1): narc.show(i)
main()</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
Racket
<lang racket>;; OEIS: A005188 defines these as positive numbers, so I will follow that definition in the function
- definitions.
- 0
- assuming it is represented as the single digit 0 (and not an empty string, which is not the
- usual convention for 0 in decimal), is not
- sum(0^0), which is 1. 0^0 is a strange one,
- wolfram alpha calls returns 0^0 as indeterminate -- so I will defer to the brains behind OEIS
- on the definition here, rather than copy what I'm seeing in some of the results here
- lang racket
- Included for the serious efficientcy gains we get from fxvectors vs. general vectors.
- We also use fx+/fx- etc. As it stands, they do a check for fixnumness, for safety.
- We can link them in as "unsafe" operations (see the documentation on racket/fixnum);
- but we get a result from this program quickly enough for my tastes.
(require racket/fixnum)
- uses a precalculated (fx)vector of powers -- caller provided, please.
(define (sub-narcissitic? N powered-digits)
(let loop ((n N) (target N)) (cond [(fx> 0 target) #f] [(fx= 0 target) (fx= 0 n)] [(fx= 0 n) #f] [else (loop (fxquotient n 10) (fx- target (fxvector-ref powered-digits (fxremainder n 10))))])))
- Can be used as standalone, since it doesn't require caller to care about things like order of
- magnitude etc. However, it *is* slow, since it regenerates the powered-digits vector every time.
(define (narcissitic? n) ; n is +ve
(define oom+1 (fx+ 1 (order-of-magnitude n))) (define powered-digits (for/fxvector ((i 10)) (expt i oom+1))) (sub-narcissitic? n powered-digits))
- next m primes > z
(define (next-narcissitics z m) ; naming convention following math/number-theory's next-primes
(let-values ([(i l) (for*/fold ((i (fx+ 1 z)) (l empty)) ((oom (in-naturals)) (dgts^oom (in-value (for/fxvector ((i 10)) (expt i (add1 oom))))) (n (in-range (expt 10 oom) (expt 10 (add1 oom)))) #:when (sub-narcissitic? n dgts^oom) ; everyone else uses ^C to break... ; that's a bit of a manual process, don't you think? #:final (= (fx+ 1 (length l)) m)) (values (+ i 1) (append l (list n))))]) l)) ; we only want the list
(module+ main
(next-narcissitics 0 25) ; here's another list... depending on whether you believe sloane or wolfram :-) (cons 0 (next-narcissitics 0 25)))
(module+ test
(require rackunit) ; example given at head of task (check-true (narcissitic? 153)) ; rip off the first 12 (and 0, since Armstrong numbers seem to be postivie) from ; http://oeis.org/A005188 for testing (check-equal? (for/list ((i (in-range 12)) (n (sequence-filter narcissitic? (in-naturals 1)))) n) '(1 2 3 4 5 6 7 8 9 153 370 371)) (check-equal? (next-narcissitics 0 12) '(1 2 3 4 5 6 7 8 9 153 370 371)))</lang>
- Output:
(1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050) (0 1 2 ... 9926315)
Faster Version
This version uses lists of digits, rather than numbers themselves. <lang racket>#lang racket (define (non-decrementing-digital-sequences L)
(define (inr d l) (cond [(<= l 0) '(())] [(= d 9) (list (make-list l d))] [else (append (map (curry cons d) (inr d (- l 1))) (inr (+ d 1) l))])) (inr 0 L))
(define (integer->digits-list n)
(let inr ((n n) (l null)) (if (zero? n) l (inr (quotient n 10) (cons (modulo n 10) l)))))
(define (narcissitic-numbers-of-length L)
(define tail-digits (non-decrementing-digital-sequences (sub1 L))) (define powers-v (for/fxvector #:length 10 ((i 10)) (expt i L))) (define (powers-sum dgts) (for/sum ((d (in-list dgts))) (fxvector-ref powers-v d))) (for*/list ((dgt1 (in-range 1 10)) (dgt... (in-list tail-digits)) (sum-dgt^l (in-value (powers-sum (cons dgt1 dgt...)))) (dgts-sum (in-value (integer->digits-list sum-dgt^l))) #:when (= (car dgts-sum) dgt1) ; only now is it worth sorting the digits #:when (equal? (sort (cdr dgts-sum) <) dgt...)) sum-dgt^l))
(define (narcissitic-numbers-of-length<= L)
(cons 0 ; special! (apply append (for/list ((l (in-range 1 (+ L 1)))) (narcissitic-numbers-of-length l)))))
(module+ main
(define all-narcissitics<10000000 (narcissitic-numbers-of-length<= 7)) ; conveniently, this *is* the list of 25... but I'll be a bit pedantic anyway (take all-narcissitics<10000000 25))
(module+ test
(require rackunit) (check-equal? (non-decrementing-digital-sequences 1) '((0) (1) (2) (3) (4) (5) (6) (7) (8) (9))) (check-equal? (non-decrementing-digital-sequences 2) '((0 0) (0 1) (0 2) (0 3) (0 4) (0 5) (0 6) (0 7) (0 8) (0 9) (1 1) (1 2) (1 3) (1 4) (1 5) (1 6) (1 7) (1 8) (1 9) (2 2) (2 3) (2 4) (2 5) (2 6) (2 7) (2 8) (2 9) (3 3) (3 4) (3 5) (3 6) (3 7) (3 8) (3 9) (4 4) (4 5) (4 6) (4 7) (4 8) (4 9) (5 5) (5 6) (5 7) (5 8) (5 9) (6 6) (6 7) (6 8) (6 9) (7 7) (7 8) (7 9) (8 8) (8 9) (9 9))) (check-equal? (integer->digits-list 0) null) (check-equal? (integer->digits-list 7) '(7)) (check-equal? (integer->digits-list 10) '(1 0)) (check-equal? (narcissitic-numbers-of-length 1) '(1 2 3 4 5 6 7 8 9)) (check-equal? (narcissitic-numbers-of-length 2) '()) (check-equal? (narcissitic-numbers-of-length 3) '(153 370 371 407)) (check-equal? (narcissitic-numbers-of-length<= 1) '(0 1 2 3 4 5 6 7 8 9)) (check-equal? (narcissitic-numbers-of-length<= 3) '(0 1 2 3 4 5 6 7 8 9 153 370 371 407)))</lang>
- Output:
'(0 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 93084 92727 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.*/
- =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.
Ruby
<lang ruby>class Integer
def narcissistic? return false if self < 0 len = to_s.size n = self sum = 0 while n > 0 n, r = n.divmod(10) sum += r ** len end sum == self end
end
numbers = [] n = 0 while numbers.size < 25
numbers << n if n.narcissistic? n += 1
end
- or
- numbers = 0.step.lazy.select(&:narcissistic?).first(25) # Ruby ver 2.1
max = numbers.max.to_s.size g = numbers.group_by{|n| n.to_s.size} g.default = [] (1..max).each{|n| puts "length #{n} : #{g[n].join(", ")}"}</lang>
- Output:
length 1 : 0, 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
Scala
<lang Scala>object NDN extends App {
val narc: Int => Int = n => (n.toString map (_.asDigit) map (math.pow(_, n.toString.size)) sum) toInt val isNarc: Int => Boolean = i => i == narc(i)
println((Iterator from 0 filter isNarc take 25 toList) mkString(" "))
}</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
Tcl
<lang tcl>proc isNarcissistic {n} {
set m [string length $n] for {set t 0; set N $n} {$N} {set N [expr {$N / 10}]} {
incr t [expr {($N%10) ** $m}]
} return [expr {$n == $t}]
}
proc firstNarcissists {target} {
for {set n 0; set count 0} {$count < $target} {incr n} {
if {[isNarcissistic $n]} { incr count lappend narcissists $n }
} return $narcissists
}
puts [join [firstNarcissists 25] ","]</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
UNIX Shell
<lang bash>function narcissistic {
integer n=$1 len=${#n} sum=0 i for ((i=0; i<len; i++)); do (( sum += pow(${n:i:1}, len) )) done (( sum == n ))
}
nums=() for ((n=0; ${#nums[@]} < 25; n++)); do
narcissistic $n && nums+=($n)
done echo "${nums[*]}" echo "elapsed: $SECONDS"</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 elapsed: 436.639
VBScript
<lang vb>Function Narcissist(n) i = 0 j = 0 Do Until j = n sum = 0 For k = 1 To Len(i) sum = sum + CInt(Mid(i,k,1)) ^ Len(i) Next If i = sum Then Narcissist = Narcissist & i & ", " j = j + 1 End If i = i + 1 Loop End Function
WScript.StdOut.Write Narcissist(25)</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,
zkl
<lang zkl>fcn isNarcissistic(n){
ns:=n.split(); m:=ns.len()-1; ns.reduce('wrap(s,d){ z:=d; do(m){z*=d} s+z },0) == n
}</lang> Pre computing the first 15 powers of 0..9 for use as a look up table speeds things up quite a bit but performance is pretty underwhelming. <lang zkl>var powers=(10).pump(List,'wrap(n){
(1).pump(15,List,'wrap(p){ n.toFloat().pow(p).toInt() })});
fcn isNarcissistic(n){
m:=(n.numDigits-1); n.split().reduce('wrap(s,d){ s+powers[d][m] },0) == n
}</lang> Now stick a filter on a infinite lazy sequence (ie iterator) to create an infinite sequence of narcissistic numbers (iterator.filter(n,f) --> n results of f(i).toBool()==True). <lang zkl>ns:=[0..].filter.fp1(isNarcissistic); ns(15).println(); ns(5).println(); ns(5).println();</lang>
- Output:
L(0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634) L(8208,9474,54748,92727,93084) L(548834,1741725,4210818,9800817,9926315)