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, , that is equal to the sum of the -th powers of each of the digits in the decimal representation of , where is the number of digits in the decimal representation of .
Narcissistic (decimal) numbers are sometimes called Armstrong numbers, named after Michael F. Armstrong.
They are also known as Plus Perfect numbers.
- An example
-
- if is 153
- then , (the number of decimal digits) is 3
- we have 13 + 53 + 33 = 1 + 125 + 27 = 153
- and so 153 is a narcissistic decimal number
- Task
Generate and show here the first 25 narcissistic decimal numbers.
Note: , the first in the series.
- See also
- the OEIS entry: Armstrong (or Plus Perfect, or narcissistic) numbers.
- MathWorld entry: Narcissistic Number.
- Wikipedia entry: Narcissistic number.
11l
<lang 11l>F narcissists(m)
[Int] result
L(digits) 0..
V digitpowers = (0.<10).map(i -> i ^ @digits)
L(n) Int(10 ^ (digits - 1)) .< 10 ^ digits
V (div, digitpsum) = (n, 0)
L div != 0
(div, V mod) = divmod(div, 10)
digitpsum += digitpowers[mod]
I n == digitpsum
result [+]= n
I result.len == m
R result
L(n) narcissists(25)
print(n, end' ‘ ’)
I (L.index + 1) % 5 == 0
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
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
Agena
Tested with Agena 2.9.5 Win32 <lang agena>scope
# print the first 25 narcissistic numbers
local power := reg( 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 ); local count := 0; local maxCount := 25; local candidate := 0; local prevDigits := 0; local digits := 1;
for d9 from 0 to 2 while count < maxCount do
if d9 > 0 and digits < 9 then digits := 9 fi;
for d8 from 0 to 9 while count < maxCount do
if d8 > 0 and digits < 8 then digits := 8 fi;
for d7 from 0 to 9 while count < maxCount do
if d7 > 0 and digits < 7 then digits := 7 fi;
for d6 from 0 to 9 while count < maxCount do
if d6 > 0 and digits < 6 then digits := 6 fi;
for d5 from 0 to 9 while count < maxCount do
if d5 > 0 and digits < 5 then digits := 5 fi;
for d4 from 0 to 9 while count < maxCount do
if d4 > 0 and digits < 4 then digits := 4 fi;
for d3 from 0 to 9 while count < maxCount do
if d3 > 0 and digits < 3 then digits := 3 fi;
for d2 from 0 to 9 while count < maxCount do
if d2 > 0 and digits < 2 then digits := 2 fi;
for d1 from 0 to 9 do
if prevDigits <> digits then
# number of digits has increased - increase the powers
prevDigits := digits;
for i from 2 to 9 do mul power[ i + 1 ], i od;
fi;
# sum the digits'th powers of the digits of candidate
local sum := power[ d1 + 1 ] + power[ d2 + 1 ] + power[ d3 + 1 ]
+ power[ d4 + 1 ] + power[ d5 + 1 ] + power[ d6 + 1 ]
+ power[ d7 + 1 ] + power[ d8 + 1 ] + power[ d9 + 1 ]
;
if candidate = sum
then
# found another narcissistic decimal number
io.write( " ", candidate );
inc count, 1
fi;
inc candidate, 1
od; # d1
od; # d2
od; # d3
od; # d4
od; # d5
od; # d6
od; # d7
od; # d8
od; # d9
io.writeline()
epocs</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
ALGOL 68
<lang algol68># find some narcissistic decimal numbers #
- returns TRUE if n is narcissitic, FALSE otherwise; n should be >= 0 #
PROC is narcissistic = ( INT n )BOOL:
BEGIN
# count the number of digits in n #
INT digits := 0;
INT number := n;
WHILE digits +:= 1;
number OVERAB 10;
number > 0
DO SKIP OD;
# sum the digits'th powers of the digits of n #
INT sum := 0;
number := n;
TO digits DO
sum +:= ( number MOD 10 ) ^ digits;
number OVERAB 10
OD;
# n is narcissistic if n = sum #
n = sum
END # is narcissistic # ;
- print the first 25 narcissistic numbers #
INT count := 0; FOR n FROM 0 WHILE count < 25 DO
IF is narcissistic( n ) THEN
# found another narcissistic number #
print( ( " ", whole( n, 0 ) ) );
count +:= 1
FI
OD; print( ( newline ) )</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
ALGOL W
<lang algolw>begin
% print the first 25 narcissistic numbers %
integer array power( 0 :: 9 ); integer count, candidate, prevDigits, digits;
power( 0 ) := 0; for i := 1 until 9 do power( i ) := 1;
count := 0; candidate := 0; prevDigits := 0; digits := 1;
for d9 := 0 until 2 do begin
if d9 > 0 and digits < 9 then digits := 9;
for d8 := 0 until 9 do begin
if d8 > 0 and digits < 8 then digits := 8;
for d7 := 0 until 9 do begin
if d7 > 0 and digits < 7 then digits := 7;
for d6 := 0 until 9 do begin
if d6 > 0 and digits < 6 then digits := 6;
for d5 := 0 until 9 do begin
if d5 > 0 and digits < 5 then digits := 5;
for d4 := 0 until 9 do begin
if d4 > 0 and digits < 4 then digits := 4;
for d3 := 0 until 9 do begin
if d3 > 0 and digits < 3 then digits := 3;
for d2 := 0 until 9 do begin
if d2 > 0 and digits < 2 then digits := 2;
for d1 := 0 until 9 do begin
integer number, sum;
if prevDigits <> digits then begin
% number of digits has increased %
% - increase the powers %
prevDigits := digits;
for i := 2 until 9 do power( i ) := power( i ) * i;
end;
% sum the digits'th powers of the %
% digits of candidate %
sum := power( d1 ) + power( d2 ) + power( d3 )
+ power( d4 ) + power( d5 ) + power( d6 )
+ power( d7 ) + power( d8 ) + power( d9 )
;
if candidate = sum then begin
% found another narcissistic %
% decimal number %
writeon( i_w := 1, s_w := 1, candidate );
count := count + 1;
if count >= 25 then goto done
end;
candidate := candidate + 1
end d1;
end d2;
end d3;
end d4;
end d5;
end d6;
end d7;
end d8;
end d9;
done:
write()
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
APL
<lang apl> ∇r ← digitsOf n;digitList
digitList ← ⍬
loop:→((⌊n)=0)/done
digitList ← digitList,(⌊n|⍨10) n ← n÷10 →loop
done: r ← ⊖digitList ∇
∇r ← getASN n;idx;list
idx ← 0 list ← 0⍴0
loop:
→(n=⍴list)/done →(isArmstrongNumber idx)/add →next
add:
list ← list,idx
next:
idx ← idx+1 →loop
done:
r ← list
∇
∇r ← isArmstrongNumber n;digits;nd
digits ← digitsOf n ⍝⍝ (⍎¨⍕n) is equivalent, but about 45% slower!! nd ← ≢ digits r ← n = +/digits * nd
∇
getASN 25
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>
AppleScript
Functional
AppleScript is a little out of its depth here, and imposes unproductively time-consuming hand-optimisation on the scripter, even with restriction of the search space (see the JavaScript and Haskell discussions).
For an algorithm which in JavaScript for Automation – the alternative idiom for osascript use on macOS – returns all 25 numbers in about 120 milliseconds, nearly 14 minutes are required in the AppleScript version (on the system here) for the full 7 digit search that finds the 25th number
(four seconds to scan the 5 digit combinations, and find the first 20, and 103 seconds to scan the six digit combinations for the first 21 narcissi).
For an imperative hand-optimisation, and a contrasting view, see the variant approach below :-)
<lang AppleScript>------------------------- NARCISSI -----------------------
-- isDaffodil :: Int -> Int -> Bool on isDaffodil(e, n)
set ds to digitList(n) (e = length of ds) and (n = powerSum(e, ds))
end isDaffodil
-- digitList :: Int -> [Int] on digitList(n)
if n > 0 then
{n mod 10} & digitList(n div 10)
else
{}
end if
end digitList
-- powerSum :: Int -> [Int] -> Int on powerSum(e, ns)
script
on |λ|(a, x)
a + x ^ e
end |λ|
end script
foldl(result, 0, ns) as integer
end powerSum
-- narcissiOfLength :: Int -> [Int] on narcissiOfLength(nDigits)
script nthPower
on |λ|(x)
{x, x ^ nDigits as integer}
end |λ|
end script
set powers to map(nthPower, enumFromTo(0, 9))
script combn
on digitTree(n, parents)
if n > 0 then
if parents ≠ {} then
script nextLayer
on |λ|(pair)
set {digit, intSum} to pair
script addPower
on |λ|(dp)
set {d, p} to dp
{d, p + intSum}
end |λ|
end script
map(addPower, items 1 thru (digit + 1) of powers)
end |λ|
end script
set nodes to concatMap(nextLayer, parents)
else
set nodes to powers
end if
digitTree(n - 1, nodes)
else
script
on |λ|(pair)
isDaffodil(nDigits, item 2 of pair)
end |λ|
end script
filter(result, parents)
end if
end digitTree
end script
script snd
on |λ|(ab)
item 2 of ab
end |λ|
end script
map(snd, combn's digitTree(nDigits, {}))
end narcissiOfLength
TEST -------------------------
on run
{0} & concatMap(narcissiOfLength, enumFromTo(1, 5))
-- 4 seconds, 20 narcissi
-- {0} & concatMap(narcissiOfLength, enumFromTo(1, 6))
-- 103 seconds, 21 narcissi
-- {0} & concatMap(narcissiOfLength, enumFromTo(1, 7))
-- 13.75 minutes, 25 narcissi
end run
GENERIC FUNCTIONS -------------------
-- concatMap :: (a -> [b]) -> [a] -> [b] on concatMap(f, xs)
set lst to {}
set lng to length of xs
tell mReturn(f)
repeat with i from 1 to lng
set lst to (lst & |λ|(item i of xs, i, xs))
end repeat
end tell
return lst
end concatMap
-- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m, n)
if n < m then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
-- filter :: (a -> Bool) -> [a] -> [a] on filter(f, xs)
tell mReturn(f)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |λ|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter
-- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- map :: (a -> b) -> [a] -> [b] on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn</lang>
- Output:
<lang AppleScript>{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>
Idiomatic
When corrected actually to return the 25 numbers required by the task, the JavaScript/Haskell translation above takes seven minutes fifty-three seconds on my current machine. By contrast, the code here was written from scratch in AppleScript, takes the number of results required as its parameter rather than the numbers of digits in them, and returns the 25 numbers in just under a sixth of a second. The first 41 numbers take just under four-and-a-half seconds, the first 42 twenty-seven, and the first 44 a minute thirty-seven-and-a-half. The 43rd and 44th numbers are both displayed in Script Editor's result pane as 4.33828176939137E+15, but appear to be the correct values when tested. The JavaScript/Haskell translation's problems are certainly not due to AppleScript being "a little out of its depth here", but the narcissistic decimal numbers beyond the 44th are admittedly beyond the resolution of AppleScript's number classes.
<lang applescript>(*
Return the first q narcissistic decimal numbers (or as many of the q as can be represented by AppleScript number values).
- )
on narcissisticDecimalNumbers(q)
script o
property output : {}
property listOfDigits : missing value
property m : 0 -- Digits per collection/number.
property done : false
-- Recursive subhandler. Builds lists containing m digit values while summing the digits' mth powers.
on recurse(digitList, sumOfPowers, digitShortfall)
-- If m digits have been obtained, compare the sum of powers's digits with the values in the list.
-- Otherwise continue branching the recursion to derive longer lists.
if (digitShortfall is 0) then
-- Assign the list to a script property to allow faster references to its items (ie. incl. reference to script).
set listOfDigits to digitList
set temp to sumOfPowers
set unmatched to m
repeat until (temp = 0)
set sumDigit to temp mod 10
if (sumDigit is in digitList) then
repeat with d from 1 to unmatched
if (sumDigit = number d of my listOfDigits) then
set number d of my listOfDigits to missing value
set unmatched to unmatched - 1
exit repeat
end if
end repeat
else
exit repeat
end if
set temp to temp div 10
end repeat
-- If all the digits have been matched, the sum of powers is narcissistic.
if (unmatched is 0) then
set end of my output to sumOfPowers div 1
-- If it's the qth find, signal the end of the process.
if ((count my output) = q) then set done to true
end if
else
-- If fewer than m digits at this level, derive longer lists from the current one.
-- Adding only values that are less than or equal to the last one makes each
-- collection unique and turns up the narcissistic numbers in numerical order.
repeat with additionalDigit from 0 to end of digitList
recurse(digitList & additionalDigit, sumOfPowers + additionalDigit ^ m, digitShortfall - 1)
if (done) then exit repeat
end repeat
end if
end recurse
end script
(* Rest of main handler code. *)
if (q > 89) then set q to 89 -- Number of narcissistic decimal integers known to exist.
set maxM to 16 -- Maximum number of decimal digits (other than trailing zeros) in AppleScript numbers.
tell o
-- Begin with zero, which is narcissistic by definition and is never the only digit used in other numbers.
if (q > 0) then set end of its output to 0
if (q < 2) then set its done to true
-- Initiate the recursive building and testing of collections of increasing numbers of digit values.
repeat until (its done)
set its m to (its m) + 1
if (its m > maxM) then
set end of its output to "Remaining numbers beyond AppleScript's number precision"
set its done to true
else
repeat with digit from 1 to 9
recurse({digit}, digit ^ (its m), (its m) - 1)
if (its done) then exit repeat
end repeat
end if
end repeat
return its output
end tell
end narcissisticDecimalNumbers
return narcissisticDecimalNumbers(25)</lang>
- Output:
<lang applescript>{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>
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
Befunge
This can take several minutes to complete in most interpreters, so it's probably best to use a compiler if you want to see the full sequence.
<lang befunge>p55*\>:>:>:55+%\55+/00gvv_@ >1>+>^v\_^#!:<p01p00:+1<>\> >#-_>\>20p110g>\20g*\v>1-v| ^!p00:-1g00+$_^#!:<-1<^\.:<</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
BQN
B10 is a BQNcrate idiom to get the digits of a number.
<lang bqn>B10 ← 10{⌽𝕗|⌊∘÷⟜𝕗⍟(↕1+·⌊𝕗⋆⁼1⌈⊢)} IsNarc ← {𝕩=+´⋆⟜≠B10 𝕩}
/IsNarc¨ ↕1e7</lang><lang bqn>⟨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>
A much faster method is to generate a list of digit sums as addition tables (+⌜). A different list of digit sums is generated for each digit count, 0 to 7. To avoid leading 0s, 0 is removed from the first digit list with (0=↕)↓¨. Then all that needs to be done is to join the lists and return locations where the index (number) and value (digit power sum) are equal.
<lang bqn>/ ↕∘≠⊸= ∾ (⥊0+⌜´(0=↕)↓¨(<↕10)⋆⊢)¨↕8</lang>
C
For a much longer but faster solution, see Narcissistic decimal number/C.
The following 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 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
All 89 terms
(FreeBASIC, GMP version)
Why stop at 25? Even using ulong instead of int only gets one to the 44th item. The 89th (last) item has 39 digits, which BigInteger easily handles. Of course, the BigInteger implementation is slower than native data types. But one can compensate a bit by calculating in parallel. Not bad, it can get all 89 items in under 7 1/2 minutes on a core i7. The calculation to the 25th item takes a fraction of a second. The calculation for all items up to 25 digits long (67th item) takes about half a minute with sequential processing and less than a quarter of a minute using parallel processing. Note that parallel execution involves some overhead, and isn't a time improvement unless computing around 15 digits or more. This program can test all numbers up to 61 digits in under half an hour, of course the highest item found has only 39 digits.
<lang csharp>using System; using System.Collections.Generic; using System.Linq; using System.Threading.Tasks; using System.Numerics;
static class Program {
public static void nar(int max, bool only1 = false)
{
int n, n1, n2, n3, n4, n5, n6, n7, n8, n9;
int[] d; // digits tally
char [] bs; // BigInteger String
List<BigInteger> res = new List<BigInteger>(); // per n digits results
BigInteger[,] p = new BigInteger[10, max + 1]; // powers array
// BigIntegers for intermediate results
BigInteger x2, x3, x4, x5, x6, x7, x8, x9;
for (n = only1 ? max : 1; n <= max; n++) // main loop
{
for (int i = 1; i <= 9; i++) // init powers array for this n
{
p[i, 1] = BigInteger.Pow(i, n);
for (int j = 2; j <= n; j++) p[i, j] = p[i, 1] * j;
}
for (n9 = n; n9 >= 0; n9--) // nested loops...
{
x9 = p[9, n9];
for (n8 = n - n9; n8 >= 0; n8--)
{
x8 = x9 + p[8, n8];
for (n7 = n - n9 - n8; n7 >= 0; n7--)
{
x7 = x8 + p[7, n7];
for (n6 = n - n9 - n8 - n7; n6 >= 0; n6--)
{
x6 = x7 + p[6, n6];
for (n5 = n - n9 - n8 - n7 - n6; n5 >= 0; n5--)
{
x5 = x6 + p[5, n5];
for (n4 = n - n9 - n8 - n7 - n6 - n5; n4 >= 0; n4--)
{
x4 = x5 + p[4, n4];
for (n3 = n - n9 - n8 - n7 - n6 - n5 - n4; n3 >= 0; n3--)
{
x3 = x4 + p[3, n3];
for (n2 = n - n9 - n8 - n7 - n6 - n5 - n4 - n3; n2 >= 0; n2--)
{
x2 = x3 + p[2, n2];
for (n1 = n - n9 - n8 - n7 - n6 - n5 - n4 - n3 - n2; n1 >= 0; n1--)
{
bs = (x2 + n1).ToString().ToCharArray();
switch (bs.Length.CompareTo(n))
{ // Since all the for/next loops step down, when the digit count
// becomes smaller than n, it's time to try the next n value.
case -1: { goto Next_n; }
case 0:
{
d = new int[10]; foreach (char c in bs) d[c - 48] += 1;
if (n9 == d[9] && n8 == d[8] && n7 == d[7] &&
n6 == d[6] && n5 == d[5] && n4 == d[4] &&
n3 == d[3] && n2 == d[2] && n1 == d[1] &&
n - n9 - n8 - n7 - n6 - n5 - n4 - n3 - n2 - n1 == d[0])
res.Add(BigInteger.Parse(new string(bs)));
break;
}
}
}
}
}
}
}
}
}
}
}
Next_n: if (only1) {
Console.Write("{0} ", n); lock (resu) resu.AddRange(res); return;
} else {
res.Sort(); Console.WriteLine("{2,3} {0,3}: {1}",
Math.Ceiling((DateTime.Now - st).TotalSeconds), string.Join(" ", res), n); res.Clear();
}
}
}
private static DateTime st = default(DateTime);
private static List<BigInteger> resu = new List<BigInteger>();
private static bool para = true; // parallel (default) or sequential calcualtion
private static int lim = 7; // this is the number of digits to calcualate, not the nth entry.
// for up to the 25th item, use lim = 7 digits.
// for all 89 items, use lim = 39 digits.
public static void Main(string[] args)
{
if (args.Count() > 0)
{
int t = lim; int.TryParse(args[0], out t);
if (t < 1) t = 1; // number of digits must be > 0
if (t > 61) t = 61; // no point when lim * math.pow(9, lim) < math.pow(10, lim - 1)
lim = t;
// default is parallel, will do sequential when any 2nd command line parameter is present.
para = !(args.Count() > 1);
}
st = DateTime.Now;
if (para)
{
Console.Write("Calculations in parallel... "); // starts the bigger ones first
Parallel.ForEach(Enumerable.Range(1, lim).Reverse().ToArray(), n => { nar(n, true); } );
resu.Sort(); int[] g = Enumerable.Range(1, resu.Count).ToArray();
var both = g.Zip(resu, (a, b) => a.ToString() + " " + b.ToString());
Console.WriteLine("\n{0}", string.Join("\n", both));
}
else { Console.WriteLine("Sequential calculations:"); nar(lim); }
Console.WriteLine("Total elasped: {0} seconds", (DateTime.Now - st).TotalSeconds);
if (System.Diagnostics.Debugger.IsAttached) Console.ReadKey();
}
} </lang>
- Output:
(with command line parameter = "39")
Calculations in parallel... 7 6 5 4 3 2 1 11 10 9 8 15 14 13 12 19 18 17 16 23 22 20 21 26 27 25 24 30 31 29 34 28 35 38 33 39 32 37 36 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 26 24678050 27 24678051 28 88593477 29 146511208 30 472335975 31 534494836 32 912985153 33 4679307774 34 32164049650 35 32164049651 36 40028394225 37 42678290603 38 44708635679 39 49388550606 40 82693916578 41 94204591914 42 28116440335967 43 4338281769391370 44 4338281769391371 45 21897142587612075 46 35641594208964132 47 35875699062250035 48 1517841543307505039 49 3289582984443187032 50 4498128791164624869 51 4929273885928088826 52 63105425988599693916 53 128468643043731391252 54 449177399146038697307 55 21887696841122916288858 56 27879694893054074471405 57 27907865009977052567814 58 28361281321319229463398 59 35452590104031691935943 60 174088005938065293023722 61 188451485447897896036875 62 239313664430041569350093 63 1550475334214501539088894 64 1553242162893771850669378 65 3706907995955475988644380 66 3706907995955475988644381 67 4422095118095899619457938 68 121204998563613372405438066 69 121270696006801314328439376 70 128851796696487777842012787 71 174650464499531377631639254 72 177265453171792792366489765 73 14607640612971980372614873089 74 19008174136254279995012734740 75 19008174136254279995012734741 76 23866716435523975980390369295 77 1145037275765491025924292050346 78 1927890457142960697580636236639 79 2309092682616190307509695338915 80 17333509997782249308725103962772 81 186709961001538790100634132976990 82 186709961001538790100634132976991 83 1122763285329372541592822900204593 84 12639369517103790328947807201478392 85 12679937780272278566303885594196922 86 1219167219625434121569735803609966019 87 12815792078366059955099770545296129367 88 115132219018763992565095597973971522400 89 115132219018763992565095597973971522401 Total elasped: 443.8791684 seconds
(without any command line parameters)
Calculations in parallel... 1 3 2 4 5 7 6 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 Total elasped: 0.0279259 seconds
(with command line parameters= "7 x")
Sequential calculations: 1 1: 0 1 2 3 4 5 6 7 8 9 2 1: 3 1: 153 370 371 407 4 1: 1634 8208 9474 5 1: 54748 92727 93084 6 1: 548834 7 1: 1741725 4210818 9800817 9926315 Total elasped: 0.0175957 seconds
(with command line parameters= "25 x")
Sequential calculations: 1 1: 0 1 2 3 4 5 6 7 8 9 2 1: 3 1: 153 370 371 407 4 1: 1634 8208 9474 5 1: 54748 92727 93084 6 1: 548834 7 1: 1741725 4210818 9800817 9926315 8 1: 24678050 24678051 88593477 9 1: 146511208 472335975 534494836 912985153 10 1: 4679307774 11 1: 32164049650 32164049651 40028394225 42678290603 44708635679 49388550606 82693916578 94204591914 12 1: 13 1: 14 1: 28116440335967 15 1: 16 1: 4338281769391370 4338281769391371 17 2: 21897142587612075 35641594208964132 35875699062250035 18 3: 19 4: 1517841543307505039 3289582984443187032 4498128791164624869 4929273885928088826 20 6: 63105425988599693916 21 9: 128468643043731391252 449177399146038697307 22 12: 23 17: 21887696841122916288858 27879694893054074471405 27907865009977052567814 28361281321319229463398 35452590104031691935943 24 23: 174088005938065293023722 188451485447897896036875 239313664430041569350093 25 31: 1550475334214501539088894 1553242162893771850669378 3706907995955475988644380 3706907995955475988644381 4422095118095899619457938 Total elasped: 30.5658944 seconds
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
Clojure
Find N first Narcissistic numbers. <lang Clojure> (ns narcissistic.core
(:require [clojure.math.numeric-tower :as math]))
(defn digits [n] ;; digits of a number.
(->> n str (map (comp read-string str))))
(defn narcissistic? [n] ;; True if the number is a Narcissistic one.
(let [d (digits n)
s (count d)]
(= n (reduce + (map #(math/expt % s) d)))))
(defn firstNnarc [n] ;;list of the first "n" Narcissistic numbers.
(take n (filter narcissistic? (range))))
</lang>
- Output:
by Average-user
(time (doall (firstNnarc 25))) "Elapsed time: 186430.429966 msecs" (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)
COBOL
<lang COBOL>
PROGRAM-ID. NARCISSIST-NUMS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 num-length PIC 9(2) value 0.
01 in-sum PIC 9(9) value 0.
01 counter PIC 9(9) value 0.
01 current-number PIC 9(9) value 0.
01 narcissist PIC Z(9).
01 temp PIC 9(9) value 0.
01 modulo PIC 9(9) value 0.
01 answer PIC 9 .
PROCEDURE DIVISION.
MAIN-PROCEDURE.
DISPLAY "the first 20 narcissist numbers:" .
MOVE 20 TO counter.
PERFORM UNTIL counter=0
PERFORM 000-NARCISSIST-PARA
IF answer = 1
SUBTRACT 1 from counter
GIVING counter
MOVE current-number TO narcissist
DISPLAY narcissist
END-IF
ADD 1 TO current-number
END-PERFORM
STOP RUN.
000-NARCISSIST-PARA.
MOVE ZERO TO in-sum.
MOVE current-number TO temp.
COMPUTE num-length =1+ FUNCTION Log10(temp)
PERFORM UNTIL temp=0
DIVIDE temp BY 10 GIVING temp
REMAINDER modulo
COMPUTE modulo=modulo**num-length
ADD modulo to in-sum GIVING in-sum
END-PERFORM.
IF current-number=in-sum
MOVE 1 TO answer
ELSE MOVE 0 TO answer
END-IF.
END PROGRAM NARCISSIST-NUMS.
</lang>
- Output:
the first 20 narcissist numbers:
0
1
2
3
4
5
6
7
8
9
153
370
371
407
1634
8208
9474
54748
92727
93084
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.
Elixir
<lang elixir>defmodule RC do
def narcissistic(m) do
Enum.reduce(1..10, [0], fn digits,acc ->
digitPowers = List.to_tuple(for i <- 0..9, do: power(i, digits))
Enum.reduce(power(10, digits-1) .. power(10, digits)-1, acc, fn n,result ->
sum = divsum(n, digitPowers, 0)
if n == sum do
if length(result) == m-1, do: throw Enum.reverse(result, [n])
[n | result]
else
result
end
end)
end)
end
defp divsum(0, _, sum), do: sum
defp divsum(n, digitPowers, sum) do
divsum(div(n,10), digitPowers, sum+elem(digitPowers,rem(n,10)))
end
defp power(n, m), do: power(n, m, 1)
defp power(_, 0, pow), do: pow
defp power(n, m, pow), do: power(n, m-1, pow*n)
end
try do
RC.narcissistic(25)
catch
x -> IO.inspect x
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]
ERRE
<lang ERRE>PROGRAM NARCISISTIC
!$DOUBLE
BEGIN
N=0
LOOP
C$=MID$(STR$(N),2)
LENG=LEN(C$)
SUM=0
FOR I=1 TO LENG DO
C=VAL(MID$(C$,I,1))
SUM+=C^LENG
END FOR
IF N=SUM THEN
PRINT(N;)
COUNT=COUNT+1
EXIT IF COUNT=25
END IF
N=N+1
END LOOP
END PROGRAM</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
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
Factor
<lang>USING: io kernel lists lists.lazy math math.functions math.text.utils prettyprint sequences ; IN: rosetta-code.narcissistic-decimal-number
- digit-count ( n -- count ) log10 floor >integer 1 + ;
- narcissist? ( n -- ? ) dup [ 1 digit-groups ]
[ digit-count [ ^ ] curry ] bi map-sum = ;
- first25 ( -- seq ) 25 0 lfrom [ narcissist? ] lfilter
ltake list>array ;
- main ( -- ) first25 [ pprint bl ] each ;
MAIN: main</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
Forth
<lang forth>
: dig.num \ returns input number and the number of its digits ( n -- n n1 )
dup 0 swap
begin
swap 1 + swap dup 10 >= while 10 /
repeat
drop ;
: zero.divmod \ /mod that returns zero if number is zero
dup 0 = if drop 0 else
/mod
then ;
: zero.div \ division that returns zero if divisor is zero
dup 0 = if drop else
/
then ;
: next.last
depth 2 - roll ; \ gets next-to-last number from the stack
: ten.to \ ( n -- 10^n ) returns 1 for zero and negative
dup 0 <= if drop 1 else dup 1 = if drop 10 else 10 swap 1 do 10 * loop then then ;
: split.div \ returns input number and its digits ( n -- n n1 n2 n3....)
dup 10 < if dup else \ duplicates single digit numbers dig.num \ provides number of digits swap dup rot dup 1 - ten.to swap \ stack juggling, ten raised to number of digits - 1... 1 do \ ... is the needed divisor, counter on top and ... dup rot swap zero.divmod swap rot 10 / \ ...division loop loop drop then ;
: to.pow \ nth power of positive numbers ( n m -- n^m )
swap dup rot dup 0 <= if 2drop drop 1 else 0 do swap dup rot * loop swap zero.div then ;
: num.pow \ raises each digit to the power of (number of digits)
depth 1 - 0 do next.last depth 1 - to.pow loop ;
: add.num
depth 2 > if begin + depth 2 = until then ;
: narc.check
split.div
num.pow
add.num ;
: narc.num 0 { a b } \ ( m -- n1 n2 n3 ... nm )
page \ displays m narcissistic decimal numbers... 999999999 0 do \ ...beginning with 0 a b = if leave then i narc.check = if i . cr b 1 + to b then loop ;
25 narc.num
</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 ok
FreeBASIC
Simple Version
<lang FreeBASIC>' normal version: 14-03-2017 ' compile with: fbc -s console ' can go up to 18 digits (ulongint is 64bit), above 18 overflow will occur
Dim As Integer n, n0, n1, n2, n3, n4, n5, n6, n7, n8, n9, a, b Dim As Integer d() Dim As ULongInt d2pow(0 To 9) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Dim As ULongInt x Dim As String str_x
For n = 1 To 7
For n9 = n To 0 Step -1
For n8 = n-n9 To 0 Step -1
For n7 = n-n9-n8 To 0 Step -1
For n6 = n-n9-n8-n7 To 0 Step -1
For n5 = n-n9-n8-n7-n6 To 0 Step -1
For n4 = n-n9-n8-n7-n6-n5 To 0 Step -1
For n3 = n-n9-n8-n7-n6-n5-n4 To 0 Step -1
For n2 = n-n9-n8-n7-n6-n5-n4-n3 To 0 Step -1
For n1 = n-n9-n8-n7-n6-n5-n4-n3-n2 To 0 Step -1
n0 = n-n9-n8-n7-n6-n5-n4-n3-n2-n1
x = n1 + n2*d2pow(2) + n3*d2pow(3) + n4*d2pow(4) + n5*d2pow(5)_
+ n6*d2pow(6) + n7*d2pow(7) + n8*d2pow(8) + n9*d2pow(9)
str_x = Str(x)
If Len(str_x) = n Then
ReDim d(10)
For a = 0 To n-1
d(Str_x[a]- Asc("0")) += 1
Next a
If n0 = d(0) AndAlso n1 = d(1) AndAlso n2 = d(2) AndAlso n3 = d(3)_
AndAlso n4 = d(4) AndAlso n5 = d(5) AndAlso n6 = d(6)_
AndAlso n7 = d(7) AndAlso n8 = d(8) AndAlso n9 = d(9) Then
Print x
End If
End If
Next n1
Next n2
Next n3
Next n4
Next n5
Next n6
Next n7
Next n8
Next n9
For a As Integer = 2 To 9
d2pow(a) = d2pow(a) * a
Next a
Next n
' empty keyboard buffer While InKey <> "" : Wend Print : Print "hit any key to end program" Sleep End</lang>
- Output:
9 8 7 6 5 4 3 2 1 0 407 371 370 153 9474 8208 1634 93084 92727 54748 548834 9926315 9800817 4210818 1741725
GMP Version
It takes about 35 min. to find all 88 numbers (39 digits). To go all the way it takes about 2 hours.
<lang FreeBASIC>' gmp version: 17-06-2015 ' uses gmp ' compile with: fbc -s console
- Include Once "gmp.bi"
' change the number after max for the maximum n-digits you want (2 to 61)
- Define max 61
Dim As Integer n, n0, n1, n2, n3, n4, n5, n6, n7, n8, n9 Dim As Integer i, j Dim As UInteger d() Dim As ZString Ptr gmp_str gmp_str = Allocate(100)
' create gmp integer array, Dim d2pow(9, max) As Mpz_ptr ' initialize array and set start value, For i = 0 To 9
For j = 0 To max d2pow(i, j) = Allocate(Len(__mpz_struct)) : Mpz_init(d2pow(i, j)) Next j
Next i
' gmp integers for to hold intermediate result Dim As Mpz_ptr x1 = Allocate(Len(__mpz_struct)) : Mpz_init(x1) Dim As Mpz_ptr x2 = Allocate(Len(__mpz_struct)) : Mpz_init(x2) Dim As Mpz_ptr x3 = Allocate(Len(__mpz_struct)) : Mpz_init(x3) Dim As Mpz_ptr x4 = Allocate(Len(__mpz_struct)) : Mpz_init(x4) Dim As Mpz_ptr x5 = Allocate(Len(__mpz_struct)) : Mpz_init(x5) Dim As Mpz_ptr x6 = Allocate(Len(__mpz_struct)) : Mpz_init(x6) Dim As Mpz_ptr x7 = Allocate(Len(__mpz_struct)) : Mpz_init(x7) Dim As Mpz_ptr x8 = Allocate(Len(__mpz_struct)) : Mpz_init(x8)
For n = 1 To max
For i = 1 To 9
'Mpz_set_ui(d2pow(i,0), 0)
Mpz_ui_pow_ui(d2pow(i,1), i, n)
For j = 2 To n
Mpz_mul_ui(d2pow(i, j), d2pow(i, 1), j)
Next j
Next i
For n9 = n To 0 Step -1
For n8 = n-n9 To 0 Step -1
Mpz_add(x8, d2pow(9, n9), d2pow(8, n8))
For n7 = n-n9-n8 To 0 Step -1
Mpz_add(x7, x8, d2pow(7, n7))
For n6 = n-n9-n8-n7 To 0 Step -1
Mpz_add(x6, x7, d2pow(6, n6))
For n5 = n-n9-n8-n7-n6 To 0 Step -1
Mpz_add(x5, x6, d2pow(5, n5))
For n4 = n-n9-n8-n7-n6-n5 To 0 Step -1
Mpz_add(x4, x5, d2pow(4, n4))
For n3 = n-n9-n8-n7-n6-n5-n4 To 0 Step -1
Mpz_add(x3, x4, d2pow(3, n3))
For n2 = n-n9-n8-n7-n6-n5-n4-n3 To 0 Step -1
Mpz_add(x2, x3, d2pow(2, n2))
For n1 = n-n9-n8-n7-n6-n5-n4-n3-n2 To 0 Step -1
Mpz_add_ui(x1, x2, n1)
n0 = n-n9-n8-n7-n6-n5-n4-n3-n2-n1
Mpz_get_str(gmp_str, 10, x1)
If Len(*gmp_str) = n Then
ReDim d(10)
For i = 0 To n-1
d(gmp_str[i] - Asc("0")) += 1
Next i
If n9 = d(9) AndAlso n8 = d(8) AndAlso n7 = d(7) AndAlso n6 = d(6)_
AndAlso n5 = d(5) AndAlso n4 = d(4) AndAlso n3 = d(3)_
AndAlso n2 = d(2) AndAlso n1 = d(1) AndAlso n0 = d(0) Then
Print *gmp_str
End If
ElseIf Len(*gmp_str) < n Then
' all for next loops have a negative step value
' if len(str_x) becomes smaller then n it's time to try the next n value
' GoTo label1 ' old school BASIC
' prefered FreeBASIC style
Exit For, For, For, For, For, For, For, For, For
' leave n1, n2, n3, n4, n5, n6, n7, n8, n9 loop
' and continue's after next n9
End If
Next n1
Next n2
Next n3
Next n4
Next n5
Next n6
Next n7
Next n8
Next n9
' label1:
Next n
' empty keyboard buffer While InKey <> "" : Wend Print : Print "hit any key to end program" Sleep End</lang>
- Output:
Left side: program output, right side: sorted on length, value
9 0 8 1 7 2 6 3 5 4 4 5 3 6 2 7 1 8 0 9 407 153 371 370 370 371 153 407 9474 1634 8208 8208 1634 9474 93084 54748 92727 92727 54748 93084 548834 548834 9926315 1741725 9800817 4210818 4210818 9800817 1741725 9926315 88593477 24678050 24678051 24678051 24678050 88593477 912985153 146511208 534494836 472335975 472335975 534494836 146511208 912985153 4679307774 4679307774 94204591914 32164049650 82693916578 32164049651 49388550606 40028394225 44708635679 42678290603 42678290603 44708635679 40028394225 49388550606 32164049651 82693916578 32164049650 94204591914 28116440335967 28116440335967 4338281769391371 4338281769391370 4338281769391370 4338281769391371 35875699062250035 21897142587612075 35641594208964132 35641594208964132 21897142587612075 35875699062250035 4929273885928088826 1517841543307505039 4498128791164624869 3289582984443187032 3289582984443187032 4498128791164624869 1517841543307505039 4929273885928088826 63105425988599693916 63105425988599693916 449177399146038697307 128468643043731391252 128468643043731391252 449177399146038697307 35452590104031691935943 21887696841122916288858 28361281321319229463398 27879694893054074471405 27907865009977052567814 27907865009977052567814 27879694893054074471405 28361281321319229463398 21887696841122916288858 35452590104031691935943 239313664430041569350093 174088005938065293023722 188451485447897896036875 188451485447897896036875 174088005938065293023722 239313664430041569350093 4422095118095899619457938 1550475334214501539088894 3706907995955475988644381 1553242162893771850669378 3706907995955475988644380 3706907995955475988644380 1553242162893771850669378 3706907995955475988644381 1550475334214501539088894 4422095118095899619457938 177265453171792792366489765 121204998563613372405438066 174650464499531377631639254 121270696006801314328439376 128851796696487777842012787 128851796696487777842012787 121270696006801314328439376 174650464499531377631639254 121204998563613372405438066 177265453171792792366489765 23866716435523975980390369295 14607640612971980372614873089 19008174136254279995012734741 19008174136254279995012734740 19008174136254279995012734740 19008174136254279995012734741 14607640612971980372614873089 23866716435523975980390369295 2309092682616190307509695338915 1145037275765491025924292050346 1927890457142960697580636236639 1927890457142960697580636236639 1145037275765491025924292050346 2309092682616190307509695338915 17333509997782249308725103962772 17333509997782249308725103962772 186709961001538790100634132976991 186709961001538790100634132976990 186709961001538790100634132976990 186709961001538790100634132976991 1122763285329372541592822900204593 1122763285329372541592822900204593 12679937780272278566303885594196922 12639369517103790328947807201478392 12639369517103790328947807201478392 12679937780272278566303885594196922 1219167219625434121569735803609966019 1219167219625434121569735803609966019 12815792078366059955099770545296129367 12815792078366059955099770545296129367 115132219018763992565095597973971522401 115132219018763992565095597973971522400 115132219018763992565095597973971522400 115132219018763992565095597973971522401
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]
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
In this page you can see the program(s) related to this task and their results.
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]
GW-BASIC
Maximum for N (double) is14 digits, there are no 15 digits numbers <lang qbasic>1 DEFINT A-W : DEFDBL X-Z : DIM D(9) : DIM X2(9) : KEY OFF : CLS 2 FOR A = 0 TO 9 : X2(A) = A : NEXT A 3 FOR N = 1 TO 7 4 FOR N9 = N TO 0 STEP -1 5 FOR N8 = N-N9 TO 0 STEP -1 6 FOR N7 = N-N9-N8 TO 0 STEP -1 7 FOR N6 = N-N9-N8-N7 TO 0 STEP -1 8 FOR N5 = N-N9-N8-N7-N6 TO 0 STEP -1 9 FOR N4 = N-N9-N8-N7-N6-N5 TO 0 STEP -1 10 FOR N3 = N-N9-N8-N7-N6-N5-N4 TO 0 STEP -1 11 FOR N2 = N-N9-N8-N7-N6-N5-N4-N3 TO 0 STEP -1 12 FOR N1 = N-N9-N8-N7-N6-N5-N4-N3-N2 TO 0 STEP -1 13 N0 = N-N9-N8-N7-N6-N5-N4-N3-N2-N1 14 X = N1 + N2*X2(2) + N3*X2(3) + N4*X2(4) + N5*X2(5) + N6*X2(6) + N7*X2(7) + N8*X2(8) + N9*X2(9) 15 S$ = MID$(STR$(X),2) 16 IF LEN(S$) < N THEN GOTO 25 17 IF LEN(S$) <> N THEN GOTO 24 18 FOR A = 0 TO 9 : D(A) = 0 : NEXT A 19 FOR A = 0 TO N-1 20 B = ASC(MID$(S$,A+1,1))-48 21 D(B) = D(B) + 1 22 NEXT A 23 IF N0 = D(0) AND N1 = D(1) AND N2 = D(2) AND N3 = D(3) AND N4 = D(4) AND N5 = D(5) AND N6 = D(6) AND N7 = D(7) AND N8 = D(8) AND N9 = D(9) THEN PRINT X, 24 NEXT N1 : NEXT N2 : NEXT N3 : NEXT N4 : NEXT N5 : NEXT N6 : NEXT N7 : NEXT N8 : NEXT N9 25 FOR A = 2 TO 9 26 X2(A) = X2(A) * A 27 NEXT A 28 NEXT N 29 PRINT 30 PRINT "done" 31 END</lang>
- Output:
9 8 7 6 5 4 3 2 1 0 407 371 370 153 9474 8208 1634 93084 92727 54748 548834 9926315 9800817 4210818 1741725
Haskell
Exhaustive search (integer series)
<lang Haskell>import Data.Char (digitToInt)
isNarcissistic :: Int -> Bool isNarcissistic n = (sum ((^ digitCount) <$> digits) ==) n
where digits = digitToInt <$> show n digitCount = length digits
main :: IO () main = mapM_ print $ take 25 (filter isNarcissistic [0 ..])</lang>
Reduced search (unordered digit combinations)
As summing the nth power of the digits is unaffected by digit order, we can reduce the search space by filtering digit combinations of given length and arbitrary order, rather than filtering a full integer sequence.
In this way we can find the 25th narcissistic number after length $ concatMap digitPowerSums [1 .. 7] == 19447 tests – an improvement on the exhaustive trawl through 9926315 integers.
<lang haskell>import Data.Bifunctor (second)
narcissiOfLength :: Int -> [Int] narcissiOfLength nDigits = snd <$> go nDigits []
where
powers = ((,) <*> (^ nDigits)) <$> [0 .. 9]
go n parents
| 0 < n = go (pred n) (f parents)
| otherwise = filter (isDaffodil nDigits . snd) parents
where
f parents
| null parents = powers
| otherwise =
parents >>=
(\(d, pwrSum) -> second (pwrSum +) <$> take (succ d) powers)
isDaffodil :: Int -> Int -> Bool isDaffodil e n =
(((&&) . (e ==) . length) <*> (n ==) . powerSum e) (digitList n)
powerSum :: Int -> [Int] -> Int powerSum n = foldr ((+) . (^ n)) 0
digitList :: Int -> [Int] digitList 0 = [0] digitList n = go n
where go 0 = [] go x = rem x 10 : go (quot x 10)
TEST ---------------------------
main :: IO () main =
putStrLn $ fTable "Narcissistic decimal numbers of length 1-7:\n" show show narcissiOfLength [1 .. 7]
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String fTable s xShow fxShow f xs =
let rjust n c = drop . length <*> (replicate n c ++)
w = maximum (length . xShow <$> xs)
in unlines $
s : fmap (((++) . rjust w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs</lang>
- Output:
Narcissistic decimal numbers of length 1-7: 1 -> [0,1,2,3,4,5,6,7,8,9] 2 -> [] 3 -> [153,370,371,407] 4 -> [1634,8208,9474] 5 -> [54748,92727,93084] 6 -> [548834] 7 -> [1741725,4210818,9800817,9926315]
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
The statics and the System.exit(0) stem from having first developed a version that is not limited by the amount of narcisstic numbers that are to be calculated. I then read that this is a criterion and thus the implementation is an afterthought and looks awkwardish... but still... works! <lang java5> import java.util.stream.IntStream; public class NarcissisticNumbers {
static int numbersToCalculate = 25;
static int numbersCalculated = 0;
public static void main(String[] args) {
IntStream.iterate(0, n -> n + 1).limit(Integer.MAX_VALUE).boxed().forEach(i -> {
int length = i.toString().length();
int addedDigits = 0;
for (int count = 0; count < length; count++) {
int value = Integer.parseInt(String.valueOf(i.toString().charAt(count)));
addedDigits += Math.pow(value, length);
}
if (i == addedDigits) {
numbersCalculated++;
System.out.print(addedDigits + " ");
}
if (numbersCalculated == numbersToCalculate) {
System.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
JavaScript
ES5
<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"
ES6
Exhaustive search (integer series)
<lang JavaScript>(() => {
'use strict';
// digits :: Int -> [Int]
const digits = n => n.toString()
.split()
.map(x => parseInt(x, 10));
// pow :: Int -> Int -> Int
const pow = Math.pow;
// isNarc :: Int -> Bool
const isNarc = n => {
const
ds = digits(n),
len = ds.length;
return ds.reduce((a, x) =>
a + pow(x, len), 0) === n;
};
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = (p, f, x) => {
let v = x;
while (!p(v)) v = f(v);
return v;
};
return until(
x => x.narc.length > 24,
x => ({
n: x.n + 1,
narc: (isNarc(x.n) ? x.narc.concat(x.n) : x.narc)
}), {
n: 0,
narc: []
}
)
.narc
})();</lang>
- Output:
<lang JavaScript>[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>
Reduced search (unordered digit combinations)
As summing the nth power of the digits is unaffected by digit order, we can reduce the search space by filtering digit combinations of given length and arbitrary order, rather than filtering a full integer sequence.
In this way we can find the 25th narcissistic number after length(concatMap(digitPowerSums, enumFromTo(0, 7))) === 19447 tests – an improvement on the exhaustive trawl through 9926315 integers.
(Generating the unordered digit combinations directly as power sums allows faster testing later, and needs less space) <lang JavaScript>(() => {
'use strict';
// main :: IO ()
const main = () =>
console.log(
fTable(
'Narcissistic decimal numbers of lengths [1..7]:\n'
)(show)(show)(
narcissiOfLength
)(enumFromTo(1)(7))
);
// narcissiOfLength :: Int -> [Int]
const narcissiOfLength = n =>
0 < n ? filter(isDaffodil(n))(
digitPowerSums(n)
) : [0];
// powerSum :: Int -> [Int] -> Int
const powerSum = n =>
xs => xs.reduce(
(a, x) => a + pow(x, n), 0
);
// isDaffodil :: Int -> Int -> Bool
const isDaffodil = e => n => {
// True if the decimal digits of N,
// each raised to the power E, sum to N.
const ds = digitList(n);
return e === ds.length && n === powerSum(e)(ds);
};
// The subset of integers of n digits that actually need daffodil checking:
// (Flattened leaves of a tree of unique digit combinations, in which // order is not significant. Digit sequence doesn't affect power summing)
// digitPowerSums :: Int -> [Int]
const digitPowerSums = nDigits => {
const
digitPowers = map(x => [x, pow(x, nDigits)])(
enumFromTo(0)(9)
),
treeGrowth = (n, parentPairs) => 0 < n ? (
treeGrowth(n - 1,
isNull(parentPairs) ? (
digitPowers
) : concatMap(
([parentDigit, parentSum]) =>
map(([leafDigit, leafSum]) => //
[leafDigit, parentSum + leafSum])(
take(parentDigit + 1)(digitPowers)
)
)(parentPairs)
)
) : parentPairs;
return map(snd)(treeGrowth(nDigits, []));
};
// ---------------------GENERIC FUNCTIONS---------------------
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = m => n =>
Array.from({
length: 1 + n - m
}, (_, i) => m + i);
// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = f =>
xs => xs.flatMap(f);
// cons :: a -> [a] -> [a]
const cons = x =>
xs => [x].concat(xs);
// digitList :: Int -> [Int]
const digitList = n => {
const go = x => 0 < x ? (
cons(x % 10)(
go(Math.floor(x / 10))
)
) : [];
return 0 < n ? go(n) : [0];
}
// filter :: (a -> Bool) -> [a] -> [a] const filter = f => xs => xs.filter(f);
// map :: (a -> b) -> [a] -> [b]
const map = f =>
xs => xs.map(f);
// isNull :: [a] -> Bool
// isNull :: String -> Bool
const isNull = xs =>
1 > xs.length;
// length :: [a] -> Int const length = xs => xs.length;
// pow :: Int -> Int -> Int const pow = Math.pow;
// take :: Int -> [a] -> [a]
const take = n =>
xs => xs.slice(0, n);
// snd :: (a, b) -> b const snd = tpl => tpl[1];
// show :: a -> String const show = x => JSON.stringify(x)
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f => xs => ys =>
xs.slice(
0, Math.min(xs.length, ys.length)
).map((x, i) => f(x)(ys[i]));
// ------------------------FORMATTING-------------------------
// fTable :: String -> (a -> String) -> (b -> String)
// -> (a -> b) -> [a] -> String
const fTable = s => xShow => fxShow => f => xs => {
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
const
ys = xs.map(xShow),
w = Math.max(...ys.map(length));
return s + '\n' + zipWith(
a => b => a.padStart(w, ' ') + ' -> ' + b
)(ys)(
xs.map(x => fxShow(f(x)))
).join('\n');
};
// MAIN --- return main();
})();</lang>
- Output:
Narcissistic decimal numbers of lengths [1..7]: 1 -> [0,1,2,3,4,5,6,7,8,9] 2 -> [] 3 -> [153,370,371,407] 4 -> [1634,8208,9474] 5 -> [54748,92727,93084] 6 -> [548834] 7 -> [1741725,4210818,9800817,9926315]
jq
A function for checking whether a given non-negative integer is narcissistic could be implemented in jq as follows: <lang jq>def is_narcissistic:
def digits: tostring | explode[] | [.] | implode | tonumber; def pow(n): . as $x | reduce range(0;n) as $i (1; . * $x);
(tostring | length) as $len | . == reduce digits as $d (0; . + ($d | pow($len)) ) end;</lang>
In the following, this definition is modified to avoid recomputing (d ^ i). This is accomplished introducing the array [i, [0^i, 1^i, ..., 9^i]]. To update this array for increasing values of i, the function powers(j) is defined as follows: <lang jq># Input: [i, [0^i, 1^i, 2^i, ..., 9^i]]
- Output: [j, [0^j, 1^j, 2^j, ..., 9^j]]
- provided j is i or (i+1)
def powers(j):
if .[0] == j then . else .[0] += 1 | reduce range(0;10) as $k (.; .[1][$k] *= $k) end;</lang>
The function is_narcisstic can now be modified to use powers(j) as follows: <lang jq># Input: [n, [i, [0^i, 1^i, 2^i,...]]] where i is the number of digits in n. def is_narcissistic:
def digits: tostring | explode[] | [.] | implode | tonumber; .[1][1] as $powers | .[0] | if . < 0 then false else . == reduce digits as $d (0; . + $powers[$d] ) end;</lang>
The task <lang jq># If your jq has "while", then feel free to omit the following definition: def while(cond; update):
def _while: if cond then ., (update | _while) else empty end; _while;
- The first k narcissistic numbers, beginning with 0:
def narcissistic(k):
# State: [n, is_narcissistic, count, [len, [0^len, 1^len, ...]]]
# where len is the number of digits in n.
[0, true, 1, [1, [range(0;10)]]]
| while( .[2] <= k;
.[3] as $powers
| (.[0]+1) as $n
| ($n | tostring | length) as $len
| ($powers | powers($len)) as $powersprime | if [$n, $powersprime] | is_narcissistic then [$n, true, .[2] + 1, $powersprime] else [$n, false, .[2], $powersprime ] end )
| select(.[1]) | "\(.[2]): \(.[0])" ;
narcissistic(25)</lang>
- Output:
<lang sh>jq -r -n -f Narcissitic_decimal_number.jq 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</lang>
Julia
This easy to implement brute force technique is plenty fast enough to find the first few Narcissistic decimal numbers. <lang Julia>using Printf # for Julia version 1.0+
function isnarcissist(n, b=10)
-1 < n || return false d = digits(n, base=b) m = length(d) n == mapreduce((x)->x^m, +, d)
end
function findnarcissist(verbose=false)
goal = 25
ncnt = 0
verbose && println("Finding the first ", goal, " Narcissistic numbers:")
for i in 0:typemax(1)
isnarcissist(i) || continue
ncnt += 1
verbose && println(@sprintf " %2d %7d" ncnt i)
ncnt < goal || break
end
end
findnarcissist() @time findnarcissist(true)
</lang>
- Output:
Finding the first 25 Narcissistic numbers:
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
3.054463 seconds (19.90 M allocations: 1.466 GiB, 14.27% gc time)
Kotlin
<lang scala>// version 1.1.0
fun isNarcissistic(n: Int): Boolean {
if (n < 0) throw IllegalArgumentException("Argument must be non-negative")
var nn = n
val digits = mutableListOf<Int>()
val powers = IntArray(10) { 1 }
while (nn > 0) {
digits.add(nn % 10)
for (i in 1..9) powers[i] *= i // no need to calculate powers[0]
nn /= 10
}
val sum = digits.filter { it > 0 }.map { powers[it] }.sum()
return n == sum
}
fun main(args: Array<String>) {
println("The first 25 narcissistic (or Armstrong) numbers are:")
var i = 0
var count = 0
do {
if (isNarcissistic(i)) {
print("$i ")
count++
}
i++
}
while (count < 25)
}</lang>
- Output:
The first 25 narcissistic (or Armstrong) numbers are: 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
Ksh
<lang ksh>
- !/bin/ksh
- Narcissistic decimal number
- # Variables:
- # Functions:
- # Function _isnarcissist(n) - return 1 if n is a narcissistic decimal number
function _isnarcissist { typeset _n ; integer _n=$1
(( ${_n} == $(_sumpowdigits ${_n}) )) && return 1 return 0 }
- # Function _sumpowdigits(n) - return sum of the digits raised to #digit power
function _sumpowdigits { typeset _n ; integer _n=$1 typeset _i ; typeset -si _i typeset _sum ; integer _sum=0
for ((_i=0; _i<${#_n}; _i++)); do (( _sum+=(${_n:_i:1}**${#_n}) )) done echo ${_sum} }
######
- main #
######
integer i cnt=0 for ((i=0; cnt<25; i++)); do _isnarcissist ${i} ; (( $? )) && printf "%3d. %d\n" $(( ++cnt )) ${i} done </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. 980081725. 9926315
Lua
This is a simple/naive/slow method but it still spits out the requisite 25 in less than a minute using LuaJIT on a 2.5 GHz machine. <lang Lua>function isNarc (n)
local m, sum, digit = string.len(n), 0
for pos = 1, m do
digit = tonumber(string.sub(n, pos, pos))
sum = sum + digit^m
end
return sum == n
end
local n, count = 0, 0 repeat
if isNarc(n) then
io.write(n .. " ")
count = count + 1
end
n = n + 1
until count == 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
Maple
<lang Maple>
Narc:=proc(i) local num,len,j,sums: sums:=0: num := parse~(StringTools:-Explode((convert(i,string)))): len:=numelems(num): for j from 1 to len do sums:=sums+(num[j]^(len)): end do; if sums = i then return i; else return NULL; end if; end proc:
i:=0: NDN:=[]: while numelems(NDN)<25 do NDN:=[op(NDN),(Narc(i))]: i:=i+1: end do: NDN; </lang>
Mathematica /Wolfram Language
<lang Mathematica>narc[1] = 0; narc[n_] := narc[n] = NestWhile[# + 1 &, narc[n - 1] + 1, Plus @@ (IntegerDigits[#]^IntegerLength[#]) != # &]; narc /@ Range[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}
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
Nanoquery
<lang Nanoquery>def is_narcissist(num) digits = {} for digit in str(num) digits.append(int(digit)) end
sum = 0 for digit in digits sum += digit ^ len(num) end
return sum = num end
def narcissist(n) results = {}
i = 0 while len(results) < n if is_narcissist(i) results.append(i) end i += 1 end
return results end
// get 25 narcissist numbers for num in narcissist(25) print num + " " end println</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
Nim
A simple solution which runs in about one second. <lang Nim>import sequtils, strutils
func digits(n: Natural): seq[int] =
result.add n mod 10 var n = n div 10 while n != 0: result.add n mod 10 n = n div 10
proc findNarcissistic(count: Natural): seq[int] =
var
n = 0
m = 10
powers = toseq(0..9)
while true:
while n < m:
var s = 0
for d in n.digits:
inc s, powers[d]
if s == n:
result.add n
if result.len == count: return
inc n
for i in 0..9: powers[i] *= i
m *= 10
echo findNarcissistic(25).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
Oforth
<lang Oforth>: isNarcissistic(n) | i m |
n 0 while( n ) [ n 10 /mod ->n swap 1 + ] ->m 0 m loop: i [ swap m pow + ] == ;
- genNarcissistic(n)
| l |
ListBuffer new dup ->l 0 while(l size n <>) [ dup isNarcissistic ifTrue: [ dup l add ] 1 + ] drop ;
</lang>
- Output:
>genNarcissistic(25) . [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] ok
PARI/GP
Naive code, could be improved by splitting the digits in half and meeting in the middle. <lang parigp>isNarcissistic(n)=my(v=digits(n)); sum(i=1, #v, v[i]^#v)==n v=List();for(n=1,1e9,if(isNarcissistic(n),listput(v,n);if(#v>24, return(Vec(v)))))</lang>
- Output:
%1 = [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]
Pascal
Free 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
alternative
recursive solution.Just counting the different combination of digits
See Combinations_with_repetitions
<lang pascal>program PowerOwnDigits;
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} uses
SysUtils;
const
MAXBASE = 10; MaxDgtVal = MAXBASE - 1; MaxDgtCount = 19;
type
tDgtCnt = 0..MaxDgtCount; tValues = 0..MaxDgtVal; tUsedDigits = array[0..23] of Int8; tpUsedDigits = ^tUsedDigits; tPower = array[tValues] of Uint64;
var
PowerDgt: array[tDgtCnt] of tPower; Min10Pot : array[tDgtCnt] of Uint64; gblUD : tUsedDigits; CombIdx: array of Int8; Numbers : array of Uint64; rec_cnt : NativeInt;
procedure OutUD(const UD:tUsedDigits);
var
i : integer;
begin
For i in tValues do
write(UD[i]:3);
writeln;
For i := 0 to MaxDgtCount do
write(CombIdx[i]:3);
writeln;
end;
function InitCombIdx(ElemCount: Byte): pbyte; begin setlength(CombIdx, ElemCount + 1); Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0); Result := @CombIdx[0]; Fillchar(gblUD[0], sizeOf(gblUD[0]) * (ElemCount + 1), #0); gblUD[0]:= 1; end;
function Init(ElemCount:byte):pByte;
var
pP1,Pp2 : pUint64;
i, j: Int32;
begin
Min10Pot[0]:= 0;
Min10Pot[1]:= 1;
for i := 2 to High(tDgtCnt) do
Min10Pot[i]:=Min10Pot[i-1]*MAXBASE;
pP1 := @PowerDgt[low(tDgtCnt)];
for i in tValues do
pP1[i] := 1;
pP1[0] := 0;
for j := low(tDgtCnt) + 1 to High(tDgtCnt) do
Begin
pP2 := @PowerDgt[j];
for i in tValues do
pP2[i] := pP1[i]*i;
pP1 := pP2;
end;
result := InitCombIdx(ElemCount);
gblUD[0]:= 1;
end;
function GetPowerSum(minpot:nativeInt;digits:pbyte;var UD :tUsedDigits):NativeInt;
var
pPower : pUint64;
res,r : Uint64;
dgt :Int32;
begin
r := Min10Pot[minpot];
dgt := minpot;
res := 0;
pPower := @PowerDgt[minpot,0];
repeat
dgt -=1;
res += pPower[digits[dgt]];
until dgt=0;
//check if res within bounds of digitCnt
result := 0;
if (res<r) or (res>r*MAXBASE) then EXIT;
//convert res into digits
repeat
r := res DIV MAXBASE;
result+=1;
UD[res-r*MAXBASE]-= 1;
res := r;
until r = 0;
end;
procedure calcNum(minPot:Int32;digits:pbyte);
var
UD :tUsedDigits;
res: Uint64;
i: nativeInt;
begin
UD := gblUD;
If GetPowerSum(minpot,digits,UD) <>0 then
Begin
//don't check 0
i := 1;
repeat
If UD[i] <> 0 then
Break;
i +=1;
until i > MaxDgtVal;
if i > MaxDgtVal then
begin
res := 0;
for i := minpot-1 downto 0 do
res += PowerDgt[minpot,digits[i]];
setlength(Numbers, Length(Numbers) + 1);
Numbers[high(Numbers)] := res;
end;
end;
end;
function NextCombWithRep(pComb: pByte;pUD :tpUsedDigits;MaxVal, ElemCount: UInt32): boolean;
var
i,dgt: NativeInt;
begin
i := -1;
repeat
i += 1;
dgt := pComb[i];
if dgt < MaxVal then
break;
dec(pUD^[dgt]);
until i >= ElemCount;
Result := i >= ElemCount;
if i = 0 then
begin
dec(pUD^[dgt]);
dgt +=1;
pComb[i] := dgt;
inc(pUD^[dgt]);
end
else
begin
//decrements digit 0 too.This is false, but not checked.
dec(pUD^[dgt]);
dgt +=1;
pUD^[dgt]:=i+1;
repeat
pComb[i] := dgt;
i -= 1;
until i < 0;
end;
end;
var
digits : pByte; T0 : Int64; tmp: Uint64; i, j : Int32;
begin
digits := Init(MaxDgtCount);
T0 := GetTickCount64;
rec_cnt := 0;
// i > 0
For i := 2 to MaxDgtCount do
Begin
digits := InitCombIdx(MaxDgtCount);
repeat
calcnum(i,digits);
inc(rec_cnt);
until NextCombWithRep(digits,@gblUD,MaxDgtVal,i);
writeln(i:3,' digits with ',Length(Numbers):3,' solutions in ',GetTickCount64-T0:5,' ms');
end;
T0 := GetTickCount64-T0;
writeln(rec_cnt,' recursions');
//sort
for i := 0 to High(Numbers) - 1 do
for j := i + 1 to High(Numbers) do
if Numbers[j] < Numbers[i] then
begin
tmp := Numbers[i];
Numbers[i] := Numbers[j];
Numbers[j] := tmp;
end;
setlength(Numbers, j + 1);
for i := 0 to High(Numbers) do
writeln(i+1:3,Numbers[i]:20);
setlength(Numbers, 0);
setlength(CombIdx,0);
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end. </lang>
- @TIO.RUN:
2 digits with 0 solutions in 0 ms 3 digits with 4 solutions in 0 ms 4 digits with 7 solutions in 0 ms 5 digits with 10 solutions in 0 ms 6 digits with 11 solutions in 0 ms 7 digits with 15 solutions in 0 ms 8 digits with 18 solutions in 1 ms 9 digits with 22 solutions in 3 ms 10 digits with 23 solutions in 6 ms 11 digits with 31 solutions in 13 ms 12 digits with 31 solutions in 25 ms 13 digits with 31 solutions in 46 ms 14 digits with 32 solutions in 82 ms 15 digits with 32 solutions in 141 ms 16 digits with 34 solutions in 238 ms 17 digits with 37 solutions in 395 ms 18 digits with 37 solutions in 644 ms 19 digits with 41 solutions in 1028 ms 20029999 recursions 1 153 2 370 3 371 4 407 5 1634 6 8208 7 9474 8 54748 9 92727 10 93084 11 548834 12 1741725 13 4210818 14 9800817 15 9926315 16 24678050 17 24678051 18 88593477 19 146511208 20 472335975 21 534494836 22 912985153 23 4679307774 24 32164049650 25 32164049651 26 40028394225 27 42678290603 28 44708635679 29 49388550606 30 82693916578 31 94204591914 32 28116440335967 33 4338281769391370 34 4338281769391371 35 21897142587612075 36 35641594208964132 37 35875699062250035 38 1517841543307505039 39 3289582984443187032 40 4498128791164624869 41 4929273885928088826
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>
Phix
with javascript_semantics function narcissistic(integer n) string d = sprintf("%d",n) integer l = length(d) atom sumn = 0 for i=1 to l do sumn += power(d[i]-'0',l) end for return sumn=n end function sequence s = {} integer n = 0 while length(s)<25 do if narcissistic(n) then s &= n end if n += 1 end while pp(s)
- 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
At least 100 times faster, gets the first 47 (the native precision limit) before the above gets the first 25.
I tried a gmp version, but it was 20-odd times slower, presumably because it uses that mighty sledgehammer for many small int cases.
with javascript_semantics -- Begin with zero, which is narcissistic by definition and is never the only digit used in other numbers. sequence output = {`0`} bool done = false integer m = 0 integer q atom t0 = time() procedure recurse(string digits, atom powsum, integer rem) -- Recursive subhandler. Builds lists containing m digit values while summing the digits' mth powers. -- If m digits have been obtained, compare the sum of powers's digits with the values in the list. -- Otherwise continue branching the recursion to derive longer lists. if rem=0 then atom temp = powsum integer unmatched = m while temp do integer d = find('0'+remainder(temp,10),digits) if d=0 then exit end if digits[d] = ' ' unmatched -= 1 temp = floor(temp/10) end while -- If all the digits have been matched, the sum of powers is narcissistic. if unmatched=0 then output = append(output,sprintf("%d",powsum)) if length(output)=q then done = true end if end if else -- If fewer than m digits at this level, derive longer lists from the current one. -- Adding only values that are less than or equal to the last one makes each -- collection unique and turns up the narcissistic numbers in numerical order. -- -- ie/eg if sum(sq_power({9,7,4,4},4))==9474, and as shown sort(digits)==list, -- then 9474 is the one and only permutation that is narcissistic, obviously, -- and there is no point looking at any other permutation of that list, ever. -- Also 1000,1100,1110,1111 are the only 4 lists beginning 1, as opposed to -- the 999 four-digit numbers beginning 1 that might otherwise be checked, -- and likewise 9000..9999 is actually just 220 rather than the full 999. -- (I can see that exploring smaller partial sums first will tend to issue -- results in numeric order, but cannot see an absolute certainty of that) -- for d=0 to digits[$]-'0' do recurse(digits & d+'0', powsum + power(d,m), rem-1) if done then exit end if end for end if end procedure function narcissisticDecimalNumbers(integer qp) atom t1 = time()+1 q = qp -- Initiate the recursive building and testing of collections of increasing numbers of digit values. while not done do m += 1 if m > iff(machine_bits()=32?16:17) then output = append(output,"Remaining numbers beyond number precision") done = true else for digit=1 to 9 do recurse(""&'0'+digit, power(digit,m), m-1) if done then exit end if end for if not done and time()>t1 and platform()!=JS then printf(1,"searching... %d found, length %d, %s\n", {length(output),m,elapsed(time()-t0)}) t1 = time()+1 end if end if end while return output end function sequence r = narcissisticDecimalNumbers(iff(machine_bits()=32?44:47)) pp(r) printf(1,"found %d in %s\n",{length(r),elapsed(time()-t0)})
- Output:
searching... 41 found, length 13, 1.0s
searching... 42 found, length 15, 3.3s
searching... 44 found, length 16, 5.7s
{`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`, `24678050`, `24678051`,
`88593477`, `146511208`, `472335975`, `534494836`, `912985153`,
`4679307774`, `32164049650`, `32164049651`, `40028394225`, `42678290603`,
`44708635679`, `49388550606`, `82693916578`, `94204591914`,
`28116440335967`, `4338281769391370`, `4338281769391371`,
`21897142587612075`, `35641594208964132`, `35875699062250035`}
found 47 in 8.2s
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
PowerShell
<lang PowerShell> function Test-Narcissistic ([int]$Number) {
if ($Number -lt 0) {return $false}
$total = 0 $digits = $Number.ToString().ToCharArray()
foreach ($digit in $digits)
{
$total += [Math]::Pow([Char]::GetNumericValue($digit), $digits.Count)
}
$total -eq $Number
}
[int[]]$narcissisticNumbers = @()
[int]$i = 0
while ($narcissisticNumbers.Count -lt 25) {
if (Test-Narcissistic -Number $i)
{
$narcissisticNumbers += $i
}
$i++
}
$narcissisticNumbers | Format-Wide {"{0,7}" -f $_} -Column 5 -Force </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
Python
Procedural
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
Functional
<lang python>Narcissistic decimal numbers
from itertools import chain from functools import reduce
- main :: IO ()
def main():
Narcissistic numbers of digit lengths 1 to 7
print(
fTable(main.__doc__ + ':\n')(str)(str)(
narcissiOfLength
)(enumFromTo(1)(7))
)
- narcissiOfLength :: Int -> [Int]
def narcissiOfLength(n):
List of Narcissistic numbers of
(base 10) digit length n.
return [
x for x in digitPowerSums(n)
if isDaffodil(n)(x)
]
- digitPowerSums :: Int -> [Int]
def digitPowerSums(e):
The subset of integers of e digits that are potential narcissi.
(Flattened leaves of a tree of unique digit combinations, in which
order is not significant. The sum is independent of the sequence.)
powers = [(x, x ** e) for x in enumFromTo(0)(9)]
def go(n, parents):
return go(
n - 1,
chain.from_iterable(map(
lambda pDigitSum: (
map(
lambda lDigitSum: (
lDigitSum[0],
lDigitSum[1] + pDigitSum[1]
),
powers[0: 1 + pDigitSum[0]]
)
),
parents
)) if parents else powers
) if 0 < n else parents
return [xs for (_, xs) in go(e, [])]
- isDaffodil :: Int -> Int -> Bool
def isDaffodil(e):
True if n is a narcissistic number
of decimal digit length e.
def go(n):
ds = digitList(n)
return e == len(ds) and n == powerSum(e)(ds)
return lambda n: go(n)
- powerSum :: Int -> [Int] -> Int
def powerSum(e):
The sum of a list obtained by raising
each element of xs to the power of e.
return lambda xs: reduce(
lambda a, x: a + x ** e,
xs, 0
)
- -----------------------FORMATTING------------------------
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
- GENERIC -------------------------------------------------
- digitList :: Int -> [Int]
def digitList(n):
A decomposition of n into a
list of single-digit integers.
def go(x):
return go(x // 10) + [x % 10] if x else []
return go(n) if n else [0]
- enumFromTo :: Int -> Int -> [Int]
def enumFromTo(m):
Enumeration of integer values [m..n]
def go(n):
return list(range(m, 1 + n))
return lambda n: go(n)
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
Narcissistic numbers of digit lengths 1 to 7: 1 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 2 -> [] 3 -> [153, 370, 371, 407] 4 -> [1634, 8208, 9474] 5 -> [54748, 92727, 93084] 6 -> [548834] 7 -> [1741725, 4210818, 9800817, 9926315]
Quackery
<lang Quackery> [ [] swap
[ 10 /mod
rot join swap
dup 0 = until ]
drop ] is digits ( n --> [ )
[ dup digits
0 over size rot
witheach
[ over ** rot + swap ]
drop = ] is narcissistic ( n --> b )
[] 0
[ dup narcissistic if
[ tuck join swap ]
1+ over size 25 = until ]
drop echo</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 ]
R
For loop solution
This is a slow method and it needed above 5 minutes on a i3 machine. <lang rsplus>for (u in 1:10000000) { j <- nchar(u) set2 <- c() for (i in 1:j) { set2[i] <- as.numeric(substr(u, i, i)) } control <- c() for (k in 1:j) { control[k] <- set2[k]^(j) } if (sum(control) == u) print(u) }</lang>
- Output:
[1] 1 [1] 2 [1] 3 [1] 4 [1] 5 [1] 6 [1] 7 [1] 8 [1] 9 [1] 153 [1] 370 [1] 371 [1] 407 [1] 1634 [1] 8208 [1] 9474 [1] 54748 [1] 92727 [1] 93084 [1] 548834 [1] 1741725 [1] 4210818 [1] 9800817 [1] 9926315
While loop solution
As with the previous solution, this is rather slow. Regardless, we have made the following improvements:
- This solution allows us to control how many Armstrong numbers we generate.
- Rather than using a for loop that assumes that we will be done by the 10000000th case, we use a while loop.
- Rather than using nchar or as.character, which both misbehave if the inputs are large enough for R to default to scientific notation, we use format.
- We exploit many of R's vectorized functions, letting us avoid using any for loops.
- As we are using format anyway, we take the chance to make the output look nicer.
<lang rsplus>generateArmstrong <- function(howMany) {
resultCount <- i <- 0
while(resultCount < howMany)
{
#The next line looks terrible, but I know of no better way to convert a large integer in to its digits in R.
digits <- as.integer(unlist(strsplit(format(i, scientific = FALSE), "")))
if(i == sum(digits^(length(digits)))) cat("Armstrong number ", resultCount <- resultCount + 1, ": ", format(i, big.mark = ","), "\n", sep = "")
i <- i + 1
}
} generateArmstrong(25)</lang>
- Output:
Armstrong number 1: 0 Armstrong number 2: 1 Armstrong number 3: 2 Armstrong number 4: 3 Armstrong number 5: 4 Armstrong number 6: 5 Armstrong number 7: 6 Armstrong number 8: 7 Armstrong number 9: 8 Armstrong number 10: 9 Armstrong number 11: 153 Armstrong number 12: 370 Armstrong number 13: 371 Armstrong number 14: 407 Armstrong number 15: 1,634 Armstrong number 16: 8,208 Armstrong number 17: 9,474 Armstrong number 18: 54,748 Armstrong number 19: 92,727 Armstrong number 20: 93,084 Armstrong number 21: 548,834 Armstrong number 22: 1,741,725 Armstrong number 23: 4,210,818 Armstrong number 24: 9,800,817 Armstrong number 25: 9,926,315
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)
Raku
(formerly 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;
}
}
for (1..*) -> $d {
my @t = 0..9 X** $d;
my @table = @t X+ @t X+ @t;
sub is-narcissistic(\n) { n == [+] @table[kigits(n)] };
state $l = 2;
FIRST say "1\t0";
say $l++, "\t", $_ if .&is-narcissistic for 10**($d-1) ..^ 10**$d;
last if $l > 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
REXX
idiomatic
<lang rexx>/*REXX program generates and displays a number of narcissistic (Armstrong) numbers. */ numeric digits 39 /*be able to handle largest Armstrong #*/ parse arg N . /*obtain optional argument from the CL.*/ if N== | N=="," then N=25 /*Not specified? Then use the default.*/ N=min(N, 89) /*there are only 89 narcissistic #s. */
- =0 /*number of narcissistic numbers so far*/
do j=0 until #==N; L=length(j) /*get length of the J decimal number.*/
$=left(j, 1) **L /*1st digit in J raised to the L pow.*/
do k=2 for L-1 until $>j /*perform for each decimal digit in J.*/
$=$ + substr(j, k, 1) ** L /*add digit raised to power to the sum.*/
end /*k*/ /* [↑] calculate the rest of the sum. */
if $\==j then iterate /*does the sum equal to J? No, skip it*/
#=# + 1 /*bump count of narcissistic numbers. */
say right(#, 9) ' narcissistic:' j /*display index and narcissistic number*/
end /*j*/ /*stick a fork in it, we're all 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 (there are
only 39 possible widths/powers of narcissistic numbers).
It is about 77% faster then 1st REXX version. <lang rexx>/*REXX program generates and displays a number of narcissistic (Armstrong) numbers. */ numeric digits 39 /*be able to handle largest Armstrong #*/ parse arg N . /*obtain optional argument from the CL.*/ if N== | N=="," then N=25 /*Not specified? Then use the default.*/ N=min(N, 89) /*there are only 89 narcissistic #s. */
do p=1 for 39 /*generate tables: digits ^ P power. */
do i=0 for 10; @.p.i= i**p /*build table of ten digits ^ P power. */
end /*i*/
end /*w*/ /* [↑] table is a fixed (limited) size*/
- =0 /*number of narcissistic numbers so far*/
do j=0 until #==N; L=length(j) /*get length of the J decimal number.*/
_=left(j, 1) /*select the first decimal digit to sum*/
$=@.L._ /*sum of the J dec. digits ^ L (so far)*/
do k=2 for L-1 until $>j /*perform for each decimal digit in J.*/
_=substr(j, k, 1) /*select the next decimal digit to sum.*/
$=$ + @.L._ /*add dec. digit raised to power to sum*/
end /*k*/ /* [↑] calculate the rest of the sum. */
if $\==j then iterate /*does the sum equal to J? No, skip it*/
#=# + 1 /*bump count of narcissistic numbers. */
say right(#, 9) ' narcissistic:' j /*display index and narcissistic number*/
end /*j*/ /*stick a fork in it, we're all done. */</lang>
- output is identical to the 1st REXX version.
optimized, unrolled
This REXX version is further optimized by unrolling part of the do loop that sums the decimal digits.
The unrolling also necessitated the special handling of one─ and two─digit narcissistic numbers.
It is about 44% faster then 2nd REXX version, and
it is about 154% faster then 1st REXX version.
<lang rexx>/*REXX program generates and displays a number of narcissistic (Armstrong) numbers. */
numeric digits 39 /*be able to handle largest Armstrong #*/
parse arg N . /*obtain optional argument from the CL.*/
if N== | N=="," then N=25 /*Not specified? Then use the default.*/
N=min(N, 89) /*there are only 89 narcissistic #s. */
@.=0 /*set default for the @ stemmed array. */
- =0 /*number of narcissistic numbers so far*/
do p=0 for 39+1; if p<10 then call tell p /*display the 1st 1─digit dec. numbers.*/
do i=1 for 9; @.p.i= i**p /*build table of ten digits ^ P power. */
end /*i*/
end /*p*/ /* [↑] table is a fixed (limited) size*/
/* [↓] skip the 2─digit dec. numbers. */
do j=100; L=length(j) /*get length of the J decimal number.*/
parse var j _1 2 _2 3 m -1 _R /*get 1st, 2nd, middle, last dec. digit*/
$=@.L._1 + @.L._2 + @.L._R /*sum of the J decimal digs^L (so far).*/
do k=3 for L-3 until $>j /*perform for other decimal digits in J*/
parse var m _ +1 m /*get next dec. dig in J, start at 3rd.*/
$=$ + @.L._ /*add dec. digit raised to pow to sum. */
end /*k*/ /* [↑] calculate the rest of the sum. */
if $==j then do; call tell j /*does the sum equal to J? Show the #*/
if #==n then leave /*does the sum equal to J? Show the #*/
end
end /*j*/ /* [↑] the J loop list starts at 100*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ tell: #=# + 1 /*bump the counter for narcissistic #s.*/
say right(#,9) ' narcissistic:' arg(1) /*display index and narcissistic number*/
if #==n & n<11 then exit /*finished showing of narcissistic #'s?*/
return /*return to invoker & keep on truckin'.*/</lang>
- output is identical to the 1st REXX version.
optimized, 3-digit chunks
This REXX version is further optimized by pre-computing the narcissistic sums of all two-digit and three-digit numbers (and also including those with leading zeros).
It is about 65% faster then 3rd REXX version, and
it is about 136% faster then 2nd REXX version, and
it is about 317% faster then 1st REXX version.
<lang rexx>/*REXX program generates and displays a number of narcissistic (Armstrong) numbers. */
numeric digits 39 /*be able to handle largest Armstrong #*/
parse arg N . /*obtain optional argument from the CL.*/
if N== | N=="," then N=25 /*Not specified? Then use the default.*/
N=min(N, 89) /*there are only 89 narcissistic #s. */
@.=0 /*set default for the @ stemmed array. */
- =0 /*number of narcissistic numbers so far*/
do p=0 for 39+1; if p<10 then call tell p /*display the 1st 1─digit dec. numbers.*/
do i=1 for 9; @.p.i= i**p /*build table of ten digits ^ P power. */
zzj= '00'j; @.p.zzj= @.p.j /*assign value for a 3-dig number (LZ),*/
end /*i*/
do j=10 to 99; parse var j t 2 u /*obtain 2 decimal digits of J: T U */
@.p.j = @.p.t + @.p.u /*assign value for a 2─dig number. */
zj= '0'j; @.p.zj = @.p.j /* " " " " 3─dig " (LZ),*/
end /*j*/ /* [↑] T≡ tens digit; U≡ units digit.*/
do k=100 to 999; parse var k h 2 t 3 u /*obtain 3 decimal digits of J: H T U */
@.p.k= @.p.h + @.p.t + @.p.u /*assign value for a three-digit number*/
end /*k*/ /* [↑] H≡ hundreds digit; T≡ tens ···*/
end /*p*/ /* [↑] table is a fixed (limited) size*/
/* [↓] skip the 2─digit dec. numbers. */
do j=100; L=length(j) /*get length of the J decimal number.*/
parse var j _ +3 m /*get 1st three decimal digits of J. */
$=@.L._ /*sum of the J decimal digs^L (so far).*/
do while m\== /*do the rest of the dec. digs in J. */
parse var m _ +3 m /*get the next 3 decimal digits in M. */
$=$ + @.L._ /*add dec. digit raised to pow to sum. */
end /*while*/ /* [↑] calculate the rest of the sum. */
if $==j then do; call tell j /*does the sum equal to J? Show the #*/
if #==n then leave /*does the sum equal to J? Show the #*/
end
end /*j*/ /* [↑] the J loop list starts at 100*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ tell: #=# + 1 /*bump the counter for narcissistic #s.*/
say right(#,9) ' narcissistic:' arg(1) /*display index and narcissistic number*/
if #==n & n<11 then exit /*finished showing of narcissistic #'s?*/
return /*return to invoker & keep on truckin'.*/</lang>
- output is identical to the 1st REXX version.
Further optimization could be utilized by increasing the chunk size to four or five decimal digits,
but with an accompanying increase in the size of the pre-computed values.
Ring
<lang ring> n = 0 count = 0 size = 15 while count != size
m = isNarc(n)
if m=1 see "" + n + " is narcisstic" + nl
count = count + 1 ok
n = n + 1
end
func isNarc n
m = len(string(n))
sum = 0
digit = 0
for pos = 1 to m
digit = number(substr(string(n), pos, 1))
sum = sum + pow(digit,m)
next
nr = (sum = n)
return nr
</lang>
Ruby
<lang ruby>class Integer
def narcissistic?
return false if negative?
digs = self.digits
m = digs.size
digs.map{|d| d**m}.sum == self
end
end
puts 0.step.lazy.select(&:narcissistic?).first(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
Rust
<lang rust> fn is_narcissistic(x: u32) -> bool {
let digits: Vec<u32> = x
.to_string()
.chars()
.map(|c| c.to_digit(10).unwrap())
.collect();
digits
.iter()
.map(|d| d.pow(digits.len() as u32))
.sum::<u32>()
== x
}
fn main() {
let mut counter = 0;
let mut i = 0;
while counter < 25 {
if is_narcissistic(i) {
println!("{}", i);
counter += 1;
}
i += 1;
}
} </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
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
Sidef
<lang ruby>func is_narcissistic(n) {
n.digits »**» n.len -> sum == n
} var count = 0 for i in ^Inf {
if (is_narcissistic(i)) {
say "#{++count}\t#{i}"
break if (count == 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
Swift
<lang swift>extension BinaryInteger {
@inlinable
public var isNarcissistic: Bool {
let digits = String(self).map({ Int(String($0))! })
let m = digits.count
guard m != 1 else {
return true
}
return digits.map({ $0.power(m) }).reduce(0, +) == self
}
@inlinable
public func power(_ n: Self) -> Self {
return stride(from: 0, to: n, by: 1).lazy.map({_ in self }).reduce(1, *)
}
}
let narcs = Array((0...).lazy.filter({ $0.isNarcissistic }).prefix(25))
print("First 25 narcissistic numbers are \(narcs)")</lang>
- Output:
First 25 narcissistic numbers are [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
VBA
<lang vb>Private Function narcissistic(n As Long) As Boolean
Dim d As String: d = CStr(n)
Dim l As Integer: l = Len(d)
Dim sumn As Long: sumn = 0
For i = 1 To l
sumn = sumn + (Mid(d, i, 1) - "0") ^ l
Next i
narcissistic = sumn = n
End Function
Public Sub main()
Dim s(24) As String
Dim n As Long: n = 0
Dim found As Integer: found = 0
Do While found < 25
If narcissistic(n) Then
s(found) = CStr(n)
found = found + 1
End If
n = n + 1
Loop
Debug.Print Join(s, ", ")
End Sub</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
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,
Wren
<lang ecmascript>var narc = Fn.new { |n|
var power = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
var limit = 10
var result = []
var x = 0
while (result.count < n) {
if (x >= limit) {
for (i in 0..9) power[i] = power[i] * i
limit = limit * 10
}
var sum = 0
var xx = x
while (xx > 0) {
sum = sum + power[xx%10]
xx = (xx/10).floor
}
if (sum == x) result.add(x)
x = x + 1
}
return result
}
System.print(narc.call(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]
XPL0
This is based on Ring's version for Own Digits Power Sum. <lang XPL0>func IPow(A, B); \A^B int A, B, T, I; [T:= 1; for I:= 1 to B do T:= T*A; return T; ];
int Count, M, N, Sum, T, Dig; [Text(0, "0 "); Count:= 1; for M:= 1 to 9 do
for N:= IPow(10, M-1) to IPow(10, M)-1 do
[Sum:= 0;
T:= N;
while T do
[T:= T/10;
Dig:= rem(0);
Sum:= Sum + IPow(Dig, M);
];
if Sum = N then
[IntOut(0, N); ChOut(0, ^ );
Count:= Count+1;
if Count >= 25 then exit;
];
];
]</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,m := n.split(), 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 [const] powers=(10).pump(List,'wrap(n){
(1).pump(15,List,'wrap(p){ n.toFloat().pow(p).toInt() }) });
fcn isNarcissistic2(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)
ZX Spectrum Basic
Array index starts at 1. Only 1 character long variable names are allowed for For-Next loops. 8 Digits or higher numbers are displayed as floating point numbers. Needs about 2 hours (3.5Mhz) <lang zxbasic> 1 DIM K(10): DIM M(10)
2 FOR Y=0 TO 9: LET M(Y+1)=Y: NEXT Y 3 FOR N=1 TO 7 4 FOR J=N TO 0 STEP -1 5 FOR I=N-J TO 0 STEP -1 6 FOR H=N-J-I TO 0 STEP -1 7 FOR G=N-J-I-H TO 0 STEP -1 8 FOR F=N-J-I-H-G TO 0 STEP -1 9 FOR E=N-J-I-H-G-F TO 0 STEP -1
10 FOR D=N-J-I-H-G-F-E TO 0 STEP -1 11 FOR C=N-J-I-H-G-F-E-D TO 0 STEP -1 12 FOR B=N-J-I-H-G-F-E-D-C TO 0 STEP -1 13 LET A=N-J-I-H-G-F-E-D-C-B 14 LET X=B+C*M(3)+D*M(4)+E*M(5)+F*M(6)+G*M(7)+H*M(8)+I*M(9)+J*M(10) 15 LET S$=STR$ (X) 16 IF LEN (S$)<N THEN GO TO 34 17 IF LEN (S$)<>N THEN GO TO 33 18 FOR Y=1 TO 10: LET K(Y)=0: NEXT Y 19 FOR Y=1 TO N 20 LET Z= CODE (S$(Y))-47 21 LET K(Z)=K(Z)+1 22 NEXT Y 23 IF A<>K(1) THEN GO TO 33 24 IF B<>K(2) THEN GO TO 33 25 IF C<>K(3) THEN GO TO 33 26 IF D<>K(4) THEN GO TO 33 27 IF E<>K(5) THEN GO TO 33 28 IF F<>K(6) THEN GO TO 33 29 IF G<>K(7) THEN GO TO 33 30 IF H<>K(8) THEN GO TO 33 31 IF I<>K(9) THEN GO TO 33 32 IF J=K(10) THEN PRINT X, 33 NEXT B: NEXT C: NEXT D: NEXT E: NEXT F: NEXT G: NEXT H: NEXT I: NEXT J 34 FOR Y=2 TO 9 35 LET M(Y+1)=M(Y+1)*Y 36 NEXT Y 37 NEXT N 38 PRINT 39 PRINT "DONE"</lang>
- Output:
9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 407 371 370 153 9474 8208 1634 93084 92727 54748 548834 9926315 9800817 4210818 1741725
- Programming Tasks
- Solutions by Programming Task
- 11l
- Ada
- Agena
- ALGOL 68
- ALGOL W
- APL
- AppleScript
- AutoHotkey
- AWK
- Befunge
- BQN
- C
- C sharp
- System.Numerics
- C++
- Clojure
- COBOL
- Common Lisp
- D
- Elixir
- ERRE
- F Sharp
- Factor
- Forth
- FreeBASIC
- FunL
- Fōrmulæ
- Go
- GW-BASIC
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Ksh
- Lua
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Nanoquery
- Nim
- Oforth
- PARI/GP
- Pascal
- Free Pascal
- Perl
- Phix
- PicoLisp
- PL/I
- PowerShell
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- Ruby
- Rust
- Scala
- Sidef
- Swift
- Tcl
- UNIX Shell
- VBA
- VBScript
- Wren
- XPL0
- Zkl
- ZX Spectrum Basic