Own digits power sum

From Rosetta Code
Own digits power sum is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Description

For the purposes of this task, an own digits power sum is a decimal integer which is N digits long and is equal to the sum of its individual digits raised to the power N.


Example

The three digit integer 153 is an own digits power sum because 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.


Task

Find and show here all own digits power sums for N = 3 to N = 8 inclusive.

Optionally, do the same for N = 9 which may take a while for interpreted languages.

ALGOL 68

Non-recursive, generates the possible combinations ands the own digits power sums in reverse order, without duplication.
Uses ideas from various solutions on this page, particularly the observation that the own digits power sum is independent of the order of the digits. Uses the minimum possible highest digit for the number of digits (width) and maximum number of zeros for the width to avoid some combinations. This trys 73 359 combinations. <lang algol68>BEGIN 

   # counts of used digits, check is a copy used to check the number is an own digit power sum #
   [ 0 : 9 ]INT used, check; FOR i FROM 0 TO 9 DO check[ i ] := 0 OD;
   [ 1 : 9, 1 : 9 ]LONG INT power;     # table of digit powers       #
   FOR i TO 9 DO power[ 1, i ] := i OD;
   FOR j FROM 2 TO 9 DO
       FOR i TO 9 DO power[ j, i ] := power[ j - 1, i ] * i OD
   OD;
   # find the lowest possible first digit for each digit combination #
   # this is the roughly the low3est n where P*n^p > 10^p            #
   [ 1 : 9 ]INT lowest digit;
   lowest digit[ 2 ] := lowest digit[ 1 ] := -1;
   LONG INT p10 := 100;
   FOR i FROM 3 TO 9 DO
       FOR p FROM 2 TO 9 WHILE LONG INT np = power[ i, p ] * i;
                               np < p10 DO
           lowest digit[ i ] := p
       OD;
       p10 *:= 10
   OD;
   # find the maximum number of zeros possible for each width and max digit #
   [ 1 : 9, 1 : 9 ]INT max zeros; FOR i TO 9 DO FOR j TO 9 DO max zeros[ i, j ] := 0 OD OD;
   p10 := 1000;
   FOR w FROM 3 TO 9 DO
       FOR d FROM lowest digit[ w ] TO 9 DO
           INT nz := 9;
           WHILE IF nz < 0
                 THEN FALSE
                 ELSE LONG INT np := power[ w, d ] * nz;
                      np > p10
                 FI
           DO
               nz -:= 1
           OD;
           max zeros[ w, d ] := IF nz > w THEN 0 ELSE w - nz FI
       OD;
       p10 *:= 10
   OD;
   # find the numbers, works backeards through the possible combinations of  #
   # digits, starting from all 9s                                            #
   [ 1 : 100 ]LONG INT numbers;  # will hold the own digit power sum numbers #
   INT n count   := 0;           # count of the own digit power sums         #
   INT try count := 0;           # count of digit combinations tried         #
   [ 1 : 9 ]INT digits;          # the latest digit combination to try       #
   FOR d        TO 9 DO digits[ d ] := 9 OD;
   FOR d FROM 0 TO 8 DO used[   d ] := 0 OD; used[ 9 ] := 9;
   INT width     := 9;           # number of digits                          #
   INT last      := width;       # final digit position                      #
   p10           := 100 000 000; # min value for a width digit power sum     #
   WHILE width > 2 DO
       try count   +:= 1;
       LONG INT dps := 0;        # construct the digit power sum             #
       check        := used;
       FOR i TO 9 DO
           IF used[ i ] /= 0 THEN dps +:= used[ i ] * power[ width, i ] FI
       OD;
       # reduce the count of each digit by the number of times it appear in the digit power sum #
       LONG INT n := dps;
       WHILE check[ SHORTEN ( n MOD 10 ) ] -:= 1; # reduce the count of this digit #
             ( n OVERAB 10 ) > 0
       DO SKIP OD;
       BOOL reduce width := dps <= p10;
       IF NOT reduce width THEN
           # dps is not less than the minimum possible width number          #
           # check there are no non-zero check counts left and so result is  #
           # equal to its digit power sum                                    #
           INT z count := 0;
           FOR i FROM 0 TO 9 WHILE check[ i ] = 0 DO z count +:= 1 OD;
           IF z count = 10 THEN
               numbers[ n count +:= 1 ] := dps
           FI;
           # prepare the next digit combination: reduce the last digit #
           used[ digits[ last ] ] -:= 1;
           digits[ last ]         -:= 1;
           IF digits[ last ] = 0 THEN
               # the last digit is now zero - check this number of zeros is possible #
               IF used[ 0 ] >= max zeros[ width, digits[ 1 ] ] THEN
                   # have exceeded the maximum number of zeros for the first digit in this width #
                   digits[ last ] := -1                    
               FI
           FI;
           IF digits[ last ] >= 0 THEN
               # still processing the last digit #
               used[ digits[ last ] ] +:= 1
           ELSE
               # last digit is now -1, start processing the previous digit #
               INT prev := last;
               WHILE IF ( prev -:= 1 ) < 1
                     THEN # processed all digits #
                         FALSE
                     ELSE
                         # have another digit # 
                         used[ digits[ prev ] ] -:= 1;
                         digits[ prev ]         -:= 1;
                         digits[ prev ] < 0
                     FI
               DO SKIP OD;
               IF prev > 0 THEN
                   # still some digits to process #
                   IF prev = 1 THEN
                       IF digits[ 1 ] <= lowest digit[ width ] THEN
                           # just finished the lowest possible maximum digit for this width #
                           prev := 0
                       FI
                   FI;
                   IF prev /= 0 THEN
                       # OK to try a lower digit #
                       used[ digits[ prev ] ] +:= 1;
                       FOR i FROM prev + 1 TO width DO
                           digits[ i ] := digits[ prev ];
                           used[ digits[ prev ] ] +:= 1
                       OD
                   FI
               FI;
               IF prev <= 0 THEN
                   # processed all the digits for this width #
                   reduce width := TRUE
               FI
           FI
       FI;
       IF reduce width THEN
           # reduce the number of digits #
           width   := last -:= 1;
           IF last > 0 THEN
               # iniialise for fewer digits #
               FOR d               TO last DO digits[ d ] :=  9 OD;
               FOR d FROM last + 1 TO 9    DO digits[ d ] := -1 OD;
               FOR d FROM        0 TO 9    DO used[   d ] :=  0 OD;
               used[ 9 ] := last;
               p10   OVERAB 10
           FI
       FI
   OD;
   # show the own digit power sums #
   print( ( "Own digits power sums for N = 3 to 9 inclusive:", newline ) );
   FOR i FROM n count BY -1 TO LWB numbers DO
       print( ( whole( numbers[ i ], 0 ), newline ) )
   OD;
   print( ( "Considered ", whole( try count, 0 ), " digit combinations" ) )

END</lang>

Output:
Own digits power sums for N = 3 to 9 inclusive:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153
Considered 73359 digit combinations

C

Iterative (slow)

Takes about 1.9 seconds to run (GCC 9.3.0 -O3).

Translation of: Wren

<lang c>#include <stdio.h>

  1. include <math.h>
  1. define MAX_DIGITS 9

int digits[MAX_DIGITS];

void getDigits(int i) { 

   int ix = 0;
   while (i > 0) {
       digits[ix++] = i % 10;
       i /= 10;
   }

}

int main() { 

   int n, d, i, max, lastDigit, sum, dp;
   int powers[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
   printf("Own digits power sums for N = 3 to 9 inclusive:\n");
   for (n = 3; n < 10; ++n) {
       for (d = 2; d < 10; ++d) powers[d] *= d;
       i = (int)pow(10, n-1);
       max = i * 10;
       lastDigit = 0;
       while (i < max) {
           if (!lastDigit) {
               getDigits(i);
               sum = 0;
               for (d = 0; d < n; ++d) {
                   dp = digits[d];
                   sum += powers[dp];
               }
           } else if (lastDigit == 1) {
               sum++;
           } else {
               sum += powers[lastDigit] - powers[lastDigit-1];
           }
           if (sum == i) {
               printf("%d\n", i);
               if (lastDigit == 0) printf("%d\n", i + 1);
               i += 10 - lastDigit;
               lastDigit = 0;
           } else if (sum > i) {
               i += 10 - lastDigit;
               lastDigit = 0;
           } else if (lastDigit < 9) {
               i++;
               lastDigit++;
           } else {
               i++;
               lastDigit = 0;
           }
       }
   }
   return 0;

}</lang>

Output:
Same as Wren example.


Recursive (very fast)

Translation of: Pascal

Down now to 14ms. <lang c>#include <stdio.h>

  1. include <string.h>
  1. define MAX_BASE 10

typedef unsigned long long ulong;

int usedDigits[MAX_BASE]; ulong powerDgt[MAX_BASE][MAX_BASE]; ulong numbers[60]; int nCount = 0;

void initPowerDgt() { 

   int i, j;
   powerDgt[0][0] = 0;
   for (i = 1; i < MAX_BASE; ++i) powerDgt[0][i] = 1;
   for (j = 1; j < MAX_BASE; ++j) {
       for (i = 0; i < MAX_BASE; ++i) {
           powerDgt[j][i] = powerDgt[j-1][i] * i;
       }
   }

}

ulong calcNum(int depth, int used[MAX_BASE]) { 

   int i;
   ulong result = 0, r, n;
   if (depth < 3) return 0;
   for (i = 1; i < MAX_BASE; ++i) {
       if (used[i] > 0) result += powerDgt[depth][i] * used[i];
   }
   if (result == 0) return 0;
   n = result;
   do {
       r = n / MAX_BASE;
       used[n-r*MAX_BASE]--;
       n = r;
       depth--;
   } while (r);
   if (depth) return 0;
   i = 1;
   while (i < MAX_BASE && used[i] == 0) i++;
   if (i >= MAX_BASE) numbers[nCount++] = result;
   return 0;

}

void nextDigit(int dgt, int depth) { 

   int i, used[MAX_BASE];
   if (depth < MAX_BASE-1) {
       for (i = dgt; i < MAX_BASE; ++i) {
           usedDigits[dgt]++;
           nextDigit(i, depth+1);
           usedDigits[dgt]--;
       }
   }
   if (dgt == 0) dgt = 1;
   for (i = dgt; i < MAX_BASE; ++i) {
       usedDigits[i]++;
       memcpy(used, usedDigits, sizeof(usedDigits));
       calcNum(depth, used);
       usedDigits[i]--;
   }

}

int main() { 

   int i, j;
   ulong t;
   initPowerDgt();
   nextDigit(0, 0);

   // sort and remove duplicates
   for (i = 0; i < nCount-1; ++i) {
       for (j = i + 1; j < nCount; ++j) {
           if (numbers[j] < numbers[i]) {
               t = numbers[i];
               numbers[i] = numbers[j];
               numbers[j] = t;
           }
       }
   }
   j = 0;
   for (i = 1; i < nCount; ++i) {
       if (numbers[i] != numbers[j]) {
           j++;
           t = numbers[i];
           numbers[i] = numbers[j];
           numbers[j] = t;
       }
   }
   printf("Own digits power sums for N = 3 to 9 inclusive:\n");
   for (i = 0; i <= j; ++i) printf("%lld\n", numbers[i]);
   return 0;

}</lang>

Output:
Same as before.

F#

<lang fsharp> // Own digits power sum. Nigel Galloway: October 2th., 2021 let fN g=let N=[|for n in 0..9->pown n g|] in let rec fN g=function n when n<10->N.[n]+g |n->fN(N.[n%10]+g)(n/10) in (fun g->fN 0 g) {3..9}|>Seq.iter(fun g->let fN=fN g in printf $"%d{g} digit are:"; {pown 10 (g-1)..(pown 10 g)-1}|>Seq.iter(fun g->if g=fN g then printf $" %d{g}"); printfn "") </lang>

Output:
3 digit are: 153 370 371 407
4 digit are: 1634 8208 9474
5 digit are: 54748 92727 93084
6 digit are: 548834
7 digit are: 1741725 4210818 9800817 9926315
8 digit are: 24678050 24678051 88593477
9 digit are: 146511208 472335975 534494836 912985153

FreeBASIC

<lang freebasic> dim as uinteger N, curr, temp, dig, sum

for N = 3 to 9 

   for curr = 10^(N-1) to 10^N-1
       sum = 0
       temp = curr
       do
           dig = temp mod 10
           temp = temp \ 10
           sum += dig ^ N
       loop until temp = 0
       if sum = curr then print curr
   next curr

next N </lang>

Output:
As above.

Go

Iterative (slow)

Translation of: Wren
Library: Go-rcu

Takes about 16.5 seconds to run including compilation time. <lang go>package main

import ( 

   "fmt"
   "math"
   "rcu"

)

func main() { 

   powers := [10]int{0, 1, 4, 9, 16, 25, 36, 49, 64, 81}
   fmt.Println("Own digits power sums for N = 3 to 9 inclusive:")
   for n := 3; n < 10; n++ {
       for d := 2; d < 10; d++ {
           powers[d] *= d
       }
       i := int(math.Pow(10, float64(n-1)))
       max := i * 10
       lastDigit := 0
       sum := 0
       var digits []int
       for i < max {
           if lastDigit == 0 {
               digits = rcu.Digits(i, 10)
               sum = 0
               for _, d := range digits {
                   sum += powers[d]
               }
           } else if lastDigit == 1 {
               sum++
           } else {
               sum += powers[lastDigit] - powers[lastDigit-1]
           }
           if sum == i {
               fmt.Println(i)
               if lastDigit == 0 {
                   fmt.Println(i + 1)
               }
               i += 10 - lastDigit
               lastDigit = 0
           } else if sum > i {
               i += 10 - lastDigit
               lastDigit = 0
           } else if lastDigit < 9 {
               i++
               lastDigit++
           } else {
               i++
               lastDigit = 0
           }
       }
   }

}</lang>

Output:
Same as Wren example.


Recursive (very fast)

Down to about 128 ms now including compilation time. Actual run time only 8 ms!

Translation of: Pascal

<lang go>package main

import "fmt"

const maxBase = 10

var usedDigits = [maxBase]int{} var powerDgt = [maxBase][maxBase]uint64{} var numbers []uint64

func initPowerDgt() { 

   for i := 1; i < maxBase; i++ {
       powerDgt[0][i] = 1
   }
   for j := 1; j < maxBase; j++ {
       for i := 0; i < maxBase; i++ {
           powerDgt[j][i] = powerDgt[j-1][i] * uint64(i)
       }
   }

}

func calcNum(depth int, used [maxBase]int) uint64 { 

   if depth < 3 {
       return 0
   }
   result := uint64(0)
   for i := 1; i < maxBase; i++ {
       if used[i] > 0 {
           result += uint64(used[i]) * powerDgt[depth][i]
       }
   }
   if result == 0 {
       return 0
   }
   n := result
   for {
       r := n / maxBase
       used[n-r*maxBase]--
       n = r
       depth--
       if r == 0 {
           break
       }
   }
   if depth != 0 {
       return 0
   }
   i := 1
   for i < maxBase && used[i] == 0 {
       i++
   }
   if i >= maxBase {
       numbers = append(numbers, result)
   }
   return 0

}

func nextDigit(dgt, depth int) { 

   if depth < maxBase-1 {
       for i := dgt; i < maxBase; i++ {
           usedDigits[dgt]++
           nextDigit(i, depth+1)
           usedDigits[dgt]--
       }
   }
   if dgt == 0 {
       dgt = 1
   }
   for i := dgt; i < maxBase; i++ {
       usedDigits[i]++
       calcNum(depth, usedDigits)
       usedDigits[i]--
   }

}

func main() { 

   initPowerDgt()
   nextDigit(0, 0)

   // sort and remove duplicates
   for i := 0; i < len(numbers)-1; i++ {
       for j := i + 1; j < len(numbers); j++ {
           if numbers[j] < numbers[i] {
               numbers[i], numbers[j] = numbers[j], numbers[i]
           }
       }
   }
   j := 0
   for i := 1; i < len(numbers); i++ {
       if numbers[i] != numbers[j] {
           j++
           numbers[i], numbers[j] = numbers[j], numbers[i]
       }
   }
   numbers = numbers[0 : j+1]
   fmt.Println("Own digits power sums for N = 3 to 9 inclusive:")
   for _, n := range numbers {
       fmt.Println(n)
   }

}</lang>

Output:
Same as before.

Haskell

Using a function from the Combinations with Repetitions task: <lang haskell>import Data.List (sort)

OWN DIGITS POWER SUM -----------------

ownDigitsPowerSums :: Int -> [Int] ownDigitsPowerSums n = sort (ns >>= go) 

 where
   ns = combsWithRep n [0 .. 9]
   go xs
     | digitsMatch m xs = [m]
     | otherwise = []
     where
       m = foldr ((+) . (^ n)) 0 xs

digitsMatch :: Show a => a -> [Int] -> Bool digitsMatch n ds = 

 sort ds == sort (digits n)

TEST -------------------------

main :: IO () main = do 

 putStrLn "N ∈ [3 .. 8]"
 mapM_ print ([3 .. 8] >>= ownDigitsPowerSums)
 putStrLn ""
 putStrLn "N=9"
 mapM_ print $ ownDigitsPowerSums 9

GENERIC ------------------------

combsWithRep :: 

 (Eq a) =>
 Int ->
 [a] ->
 a

combsWithRep k xs = comb k [] 

 where
   comb 0 ys = ys
   comb n [] = comb (pred n) (pure <$> xs)
   comb n peers = comb (pred n) (peers >>= nextLayer)
     where
       nextLayer ys@(h : _) =
         (: ys) <$> dropWhile (/= h) xs

digits :: Show a => a -> [Int] digits n = (\x -> read [x] :: Int) <$> show n</lang>

Output:
N ∈ [3 .. 8]
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477

N=9
146511208
472335975
534494836
912985153

Julia

<lang julia>function isowndigitspowersum(n::Integer, base=10) 

   dig = digits(n, base=base)
   exponent = length(dig)
   return mapreduce(x -> x^exponent, +, dig) == n

end

for i in 10^2:10^9-1 

   isowndigitspowersum(i) && println(i)

end

</lang>

Output:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153

Pascal

recursive solution.Just counting the different combination of digits
See Combinations_with_repetitions
<lang pascal>program PowerOwnDigits; {$IFDEF FPC} 

 //{$R+,O+}
 {$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..31] of Int8;
 tPower = array[tValues] of Uint64;

var 

 PowerDgt: array[tDgtCnt] of tPower;
 Min10Pot : array[tDgtCnt] of Uint64;
 CombIdx: array of Int8;
 Numbers : array of Uint64;
 rec_cnt : NativeInt;

 function InitCombIdx(ElemCount: Byte): pbyte;
 begin
   setlength(CombIdx, ElemCount + 1);
   Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0);
   Result := @CombIdx[0];
 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);
 end;

 function NextCombWithRep(pComb: pByte; MaxVal, ElemCount: UInt32): boolean;
 var
   i,dgt: NativeInt;
 begin
   i := -1;
   repeat
     i += 1;
     dgt := pComb[i];
     if dgt < MaxVal then
       break;
   until i > ElemCount;

   Result := i >= ElemCount;
   dgt +=1;
   repeat
     pComb[i] := dgt;
     i -= 1;
   until i < 0;
 end;

 function GetPowerSum(minpot:nativeInt;digits:pbyte;var UD_tmp :tUsedDigits):NativeInt;
 var
   pPower : pUint64;
   res,r  : Uint64;
   dgt :Int32;
 begin
   r := Min10Pot[minpot];
   pPower := @PowerDgt[minpot,0];
   dgt := minpot;
   res := 0;
   repeat
     dgt -=1;
     res += pPower[digits[dgt]];
   until dgt=0;
   //check if res within bounds of digitCnt
   if (res<r) or (res>r*MAXBASE) then  EXIT(1);

   //convert res into digits
   result := minPot;
   repeat
     dec(result);
     r := res DIV MAXBASE;
     UD_tmp[res-r*MAXBASE]-= 1;
     res := r;
   until r = 0;
 end;

 procedure calcNum(minPot:Int32;digits:pbyte);
 var
   UD :tUsedDigits;
   res: Uint64;
   i: nativeInt;
 begin
   fillchar(UD,SizeOf(UD),#0);
   For i := minpot-1 downto 0 do
     UD[digits[i]]+=1;
   i := GetPowerSum(minpot,digits,UD);

   //number to small
   if i > 0 then
     EXIT;
   if i = 0 then
   begin
     while (i <= minPot) and (UD[digits[i]] = 0) do
       i +=1;
     if i > minPot 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;

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,MaxDgtVal,i);
 end;
 T0 := GetTickCount64-T0;
 writeln(rec_cnt,' recursions in runtime ',T0,' ms');

 writeln('found ',length(Numbers));
 //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);
 {$IFDEF WINDOWS}
 readln;
 {$ENDIF}
 setlength(Numbers, 0);
 setlength(CombIdx,0);

end.</lang>

Output:
TIO.RUN //18 digits 13123099 recursions in runtime 911.00 ms found 37
20029999 recursions in runtime 1434.00 ms
found 41
  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

Brute Force

Use Parallel::ForkManager to obtain concurrency, trading some code complexity for less-than-infinite run time. Still very slow. <lang perl>use strict; use warnings; use feature 'say'; use List::Util 'sum'; use Parallel::ForkManager;

my %own_dps; my($lo,$hi) = (3,9); my $cores = 8; # configure to match hardware being used

my $start = 10**($lo-1); my $stop = 10**$hi - 1; my $step = int(1 + ($stop - $start)/ ($cores+1));

my $pm = Parallel::ForkManager->new($cores);

RUN: for my $i ( 0 .. $cores ) { 

   $pm->run_on_finish (
       sub {
           my ($pid, $exit_code, $ident, $exit_signal, $core_dump, $data_ref) = @_;
           $own_dps{$ident} = $data_ref;
       }
   );

   $pm->start($i) and next RUN;

   my @values;
   for my $n ( ($start + $i*$step) .. ($start + ($i+1)*$step) ) {
       push @values, $n if $n == sum map { $_**length($n) } split , $n;
   }

   $pm->finish(0, \@values)

}

$pm->wait_all_children;

say $_ for sort { $a <=> $b } map { @$_ } values %own_dps;</lang>

Output:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153

Combinatorics

Leverage the fact that all combinations of digits give same DPS. Much faster than brute force, as only non-redundant values tested. <lang perl>use strict; use warnings; use List::Util 'sum'; use Algorithm::Combinatorics qw<combinations_with_repetition>;

my @own_dps; for my $d (3..9) { 

   my $iter = combinations_with_repetition([0..9], $d);
   while (my $p = $iter->next) {
       my $dps = sum map { $_**$d } @$p;
       next unless $d == length $dps and join(, @$p) == join , sort split , $dps;
       push @own_dps, $dps;
   }

}

print join "\n", sort { $a <=> $b } @own_dps;</lang>

Output:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153

Python

Python :: Procedural

slower

<lang python>""" Rosetta code task: Own_digits_power_sum """

def isowndigitspowersum(integer): 

   """ true if sum of (digits of number raised to number of digits) == number """
   digits = [int(c) for c in str(integer)]
   exponent = len(digits)
   return sum(x ** exponent for x in digits) == integer

print("Own digits power sums for N = 3 to 9 inclusive:") for i in range(100, 1000000000): 

   if isowndigitspowersum(i):
       print(i)

</lang>

Output:

Same as Wren example. Takes over a half hour to run.

faster

Translation of: Wren

Same output.

<lang python>""" Rosetta code task: Own_digits_power_sum (recursive method)"""

MAX_BASE = 10 POWER_DIGIT = [[1 for _ in range(MAX_BASE)] for _ in range(MAX_BASE)] USED_DIGITS = [0 for _ in range(MAX_BASE)] NUMBERS = []

def calc_num(depth, used): 

   """ calculate the number at a given recurse depth """
   result = 0
   if depth < 3:
       return 0
   for i in range(1, MAX_BASE):
       if used[i] > 0:
           result += used[i] * POWER_DIGIT[depth][i]
   if result != 0:
       num, rnum = result, 1
       while rnum != 0:
           rnum = num // MAX_BASE
           used[num - rnum * MAX_BASE] -= 1
           num = rnum
           depth -= 1
       if depth == 0:
           i = 1
           while i < MAX_BASE and used[i] == 0:
               i += 1
           if i >= MAX_BASE:
               NUMBERS.append(result)
   return 0

def next_digit(dgt, depth): 

   """ get next digit at the given depth """
   if depth < MAX_BASE - 1:
       for i in range(dgt, MAX_BASE):
           USED_DIGITS[dgt] += 1
           next_digit(i, depth + 1)
           USED_DIGITS[dgt] -= 1

   if dgt == 0:
       dgt = 1
   for i in range(dgt, MAX_BASE):
       USED_DIGITS[i] += 1
       calc_num(depth, USED_DIGITS.copy())
       USED_DIGITS[i] -= 1

for j in range(1, MAX_BASE): 

   for k in range(MAX_BASE):
       POWER_DIGIT[j][k] = POWER_DIGIT[j - 1][k] * k

next_digit(0, 0) print(NUMBERS) NUMBERS = list(set(NUMBERS)) NUMBERS.sort() print('Own digits power sums for N = 3 to 9 inclusive:') for n in NUMBERS: 

   print(n)</lang>

Python :: Functional

Using a function from the Combinations with Repetitions task: <lang python>Own digit power sums

from itertools import accumulate, chain, islice, repeat from functools import reduce


  1. ownDigitsPowerSums :: Int -> [Int]

def ownDigitsPowerSums(n): 

   All own digit power sums of digit length N
   def go(xs):
       m = reduce(lambda a, x: a + (x ** n), xs, 0)
       return [m] if digitsMatch(m)(xs) else []

   return concatMap(go)(
       combinationsWithRepetitions(n)(range(0, 1 + 9))
   )


  1. digitsMatch :: Int -> [Int] -> Bool

def digitsMatch(n): 

   True if the digits in ds contain exactly
      the digits of n, in any order.
   
   def go(ds):
       return sorted(ds) == sorted(digits(n))
   return go


  1. ------------------------- TEST -------------------------
  2. main :: IO ()

def main(): 

   Own digit power sums for digit lengths 3..9
   print(
       '\n'.join([
           'N ∈ [3 .. 8]',
           *map(str, concatMap(ownDigitsPowerSums)(
               range(3, 1 + 8)
           )),
           '\nN=9',
           *map(str, ownDigitsPowerSums(9))
       ])
   )


  1. ----------------------- GENERIC ------------------------
  1. combinationsWithRepetitions :: Int -> [a] -> [kTuple a]

def combinationsWithRepetitions(k): 

   Combinations with repetitions.
      A list of tuples, representing
      sets of cardinality k,
      with elements drawn from xs.
   
   def f(a, x):
       def go(ys, xs):
           return xs + [[x] + y for y in ys]
       return accumulate(a, go)

   def combsBySize(xs):
       return [
           tuple(x) for x in next(islice(
               reduce(
                   f, xs, chain(
                       [[[]]],
                       islice(repeat([]), k)
                   )
               ), k, None
           ))
       ]
   return combsBySize


  1. concatMap :: (a -> [b]) -> [a] -> [b]

def concatMap(f): 

   A concatenated list over which a function has been
      mapped.
      The list monad can be derived by using a function f
      which wraps its output in a list, (using an empty
      list to represent computational failure).
   
   def go(xs):
       return list(chain.from_iterable(map(f, xs)))
   return go


  1. digits :: Int -> [Int]

def digits(n): 

   The individual digits of n as integers
   return [int(c) for c in str(n)]


  1. MAIN ---

if __name__ == '__main__': 

   main()</lang>
Output:
N ∈ [3 .. 8]
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477

N=9
146511208
472335975
534494836
912985153

Raku

<lang perl6>(3..8).map: -> $p { 

   my %pow = (^10).map: { $_ => $_ ** $p };
   my $start = 10 ** ($p - 1);
   my $end   = 10 ** $p;
   my @temp;
   for ^9 -> $i {
       ([X] ($i..9) xx $p).race.map: {
           next unless [<=] $_;
           my $sum = %pow{$_}.sum;
           next if $sum < $start;
           next if $sum > $end;
           @temp.push: $sum if $sum.comb.Bag eqv $_».Str.Bag
       }
   }
   .say for unique sort @temp;

}</lang>

Output:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477

Combinations with repetitions

Using code from Combinations with repetitions task, a version that runs relatively quickly, and scales well. <lang perl6>proto combs_with_rep (UInt, @ ) { * } multi combs_with_rep (0, @ ) { () } multi combs_with_rep ($, []) { () } multi combs_with_rep (1, @a) { map { $_, }, @a } multi combs_with_rep ($n, [$head, *@tail]) { 

   |combs_with_rep($n - 1, ($head, |@tail)).map({ $head, |@_ }),
   |combs_with_rep($n, @tail);

}

say sort gather { 

   for 3..9 -> $d {
       for combs_with_rep($d, [^10]) -> @digits {
           .take if $d == .comb.elems and @digits.join == .comb.sort.join given sum @digits X** $d;
       }
   }

}</lang>

Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153

Ring

<lang ring> see "working..." + nl see "Own digits power sum for N = 3 to 9 inclusive:" + nl

for n = 3 to 9 

   for curr = pow(10,n-1) to pow(10,n)-1
       sum = 0
       temp = curr
       while temp != 0
           dig = temp % 10
           temp = floor(temp/10)
           sum += pow(dig,n)
       end
       if sum = curr
          see "" + curr + nl
       ok
   next

next

see "done..." + nl </lang>

Output:
working...
Own digits power sum for N = 3 to 9 inclusive:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153
done...

Ruby

Repeated combinations allow for N=18 in less than a minute. <lang ruby>DIGITS = (0..9).to_a range = (3..18)

res = range.map do |s| 

 powers = {}
 DIGITS.each{|n| powers[n] = n**s}
 DIGITS.repeated_combination(s).filter_map do |combi| 
   sum = powers.values_at(*combi).sum
   sum if sum.digits.sort == combi.sort
 end.sort

end

puts "Own digits power sums for N = #{range}:", res</lang>

Output:
Own digits power sums for 3..18
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

Visual Basic .NET

Translation of: ALGOL 68

<lang vbnet>Option Strict On Option Explicit On

Imports System.IO

<summary> Finds n digit numbers N such that the sum of the nth powers of their digits = N </summary> Module OwnDigitsPowerSum 

   Public Sub Main

       ' counts of used digits, check is a copy used to check the number is an own digit power sum
       Dim used(9) As Integer
       Dim check(9) As Integer
       Dim power(9, 9) As Long
       For i As Integer = 0 To 9
           check(i) = 0
       Next i
       For i As Integer = 1 To 9
           power(1,  i) = i
       Next i
       For j As Integer =  2 To 9
           For i As Integer = 1 To 9
               power(j, i) = power(j - 1, i) * i
           Next i
       Next j
       ' find the lowest possible first digit for each digit combination
       ' this is the roughly the low3est n where P*n^p > 10^p
       Dim lowestDigit(9) As Integer
       lowestDigit(1) = -1
       lowestDigit(2) = -1
       Dim p10 As Long = 100
       For i As Integer = 3 To 9
           For p As Integer = 2 To 9
               Dim np As Long = power(i, p) * i
               If Not ( np < p10) Then Exit For
               lowestDigit(i) = p
           Next p
           p10 *= 10
       Next i
       ' find the maximum number of zeros possible for each width and max digit
       Dim maxZeros(9, 9) As Integer
       For i As Integer = 1 To 9
           For j As Integer = 1 To 9
               maxZeros(i, j) = 0
           Next j
       Next i
       p10 = 1000
       For w As Integer = 3 To 9
           For d As Integer = lowestDigit(w) To 9
               Dim nz As Integer = 9
               Do
                   If nz < 0 Then
                       Exit Do
                   Else
                       Dim np As Long = power(w, d) * nz
                       IF Not ( np > p10) Then Exit Do
                   End If
                   nz -= 1
               Loop
               maxZeros(w, d) = If(nz > w, 0, w - nz)
           Next d
           p10 *= 10
       Next w
       ' find the numbers, works backeards through the possible combinations of
       ' digits, starting from all 9s
       Dim numbers(100) As Long     ' will hold the own digit power sum numbers
       Dim nCount As Integer = 0    ' count of the own digit power sums
       Dim tryCount As Integer = 0  ' count of digit combinations tried
       Dim digits(9) As Integer     ' the latest digit combination to try
       For d As Integer = 1 To 9
            digits(d) = 9
       Next d
       For d As Integer = 0 To 8
           used(d) = 0
       Next d
       used(9) = 9
       Dim width As Integer = 9     ' number of digits
       Dim last As Integer = width  ' final digit position
       p10 = 100000000              ' min value for a width digit power sum
       Do While width > 2
           tryCount += 1
           Dim dps As Long = 0      ' construct the digit power sum
           check(0) = used(0)
           For i As Integer = 1 To 9
               check(i) = used(i)
               If used(i) <> 0 Then
                   dps += used(i) * power(width, i)
               End If
           Next i
           ' reduce the count of each digit by the number of times it appear in the digit power sum
           Dim n As Long = dps
           Do
               check(CInt(n Mod 10)) -= 1 ' reduce the count of this digit
               n \= 10
           Loop Until n <= 0
           Dim reduceWidth As Boolean = dps <= p10
           If Not reduceWidth Then
               ' dps is not less than the minimum possible width number
               ' check there are no non-zero check counts left and so result is
               ' equal to its digit power sum
               Dim zCount As Integer = 0
               For i As Integer = 0 To 9
                   If check(i) <> 0 Then Exit For
                   zCount+= 1
               Next i
               If zCount = 10 Then
                   nCount += 1
                   numbers(nCount) = dps
               End If
               ' prepare the next digit combination: reduce the last digit
               used(digits(last)) -= 1
               digits(last) -= 1
               If digits(last) = 0 Then
                   ' the last digit is now zero - check this number of zeros is possible
                   If used(0) >= maxZeros(width, digits(1)) Then
                       ' have exceeded the maximum number of zeros for the first digit in this width
                       digits(last) = -1
                   End If
               End If
               If digits(last) >= 0 Then
                   ' still processing the last digit
                   used(digits(last)) += 1
               Else
                   ' last digit is now -1, start processing the previous digit
                   Dim prev As Integer = last
                   Do
                       prev -= 1
                       If prev < 1 Then
                           Exit Do
                       Else
                           used(digits(prev)) -= 1
                           digits(prev) -= 1
                           IF digits(prev) >= 0 Then Exit Do
                       End If
                   Loop
                   If prev > 0 Then
                       ' still some digits to process
                       If prev = 1 Then
                           If digits(1) <= lowestDigit(width) Then
                              ' just finished the lowest possible maximum digit for this width
                              prev = 0
                           End If
                       End If
                       If prev <> 0 Then
                          ' OK to try a lower digit
                           used(digits(prev)) += 1
                           For i As Integer = prev + 1 To width
                               digits(i) = digits(prev)
                               used(digits(prev)) += 1
                           Next i
                       End If
                   End If
                   If prev <= 0 Then
                       ' processed all the digits for this width
                       reduceWidth = True
                   End If
               End If
           End If
           If reduceWidth Then
               ' reduce the number of digits
               last -= 1
               width = last
               If last > 0 Then
                   ' iniialise for fewer digits
                   For d As Integer = 1 To last
                       digits(d) = 9
                   Next d
                   For d As Integer = last + 1 To 9
                       digits(d) = -1
                   Next d
                   For d As Integer = 0 To 8
                       used(d) = 0
                   Next d
                   used(9) = last
                   p10 \= 10
               End If
           End If
       Loop
       ' show the own digit power sums
       Console.Out.WriteLine("Own digits power sums for N = 3 to 9 inclusive:")
       For i As Integer = nCount To 1 Step -1
           Console.Out.WriteLine(numbers(i))
       Next i
       Console.Out.WriteLine("Considered " & tryCount & " digit combinations")

   End Sub


End Module</lang>

Output:
Own digits power sums for N = 3 to 9 inclusive:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153
Considered 73359 digit combinations

Wren

Iterative (slow)

Library: Wren-math

Includes some simple optimizations to try and quicken up the search. However, getting up to N = 9 still took a little over 4 minutes on my machine. <lang ecmascript>import "./math" for Int

var powers = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] System.print("Own digits power sums for N = 3 to 9 inclusive:") for (n in 3..9) { 

   for (d in 2..9) powers[d] = powers[d] * d
   var i = 10.pow(n-1)
   var max = i * 10
   var lastDigit = 0
   var sum = 0
   var digits = null
   while (i < max) {
       if (lastDigit == 0) {
           digits = Int.digits(i)
           sum = digits.reduce(0) { |acc, d|  acc + powers[d] }
       } else if (lastDigit == 1) {
           sum = sum + 1
       } else {
           sum = sum + powers[lastDigit] - powers[lastDigit-1]
       }
       if (sum == i) {
           System.print(i)
           if (lastDigit == 0) System.print(i + 1)
           i = i + 10 - lastDigit
           lastDigit = 0
       } else if (sum > i) {
           i = i + 10 - lastDigit
           lastDigit = 0
       } else if (lastDigit < 9) {
           i = i + 1
           lastDigit = lastDigit + 1
       } else {
           i = i + 1
           lastDigit = 0
       }
   }

}</lang>

Output:
Own digits power sums for N = 3 to 9 inclusive:
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153


Recursive (very fast)

Translation of: Pascal
Library: Wren-seq

Astonishing speed-up. Runtime now only 0.5 seconds! <lang ecmascript>import "./seq" for Lst

var maxBase = 10 var usedDigits = List.filled(maxBase, 0) var powerDgt = List.filled(maxBase, null) var numbers = []

var initPowerDgt = Fn.new { 

   for (i in 0...maxBase) powerDgt[i] = List.filled(maxBase, 0)
   for (i in 1...maxBase) powerDgt[0][i] = 1
   for (j in 1...maxBase) {
       for (i in 0...maxBase) powerDgt[j][i] = powerDgt[j-1][i] * i
   }

}

var calcNum = Fn.new { |depth, used| 

   if (depth < 3) return 0
   var result = 0
   for (i in 1...maxBase) {
       if (used[i] > 0) result = result + used[i] * powerDgt[depth][i]
   }
   if (result == 0) return 0
   var n = result
   while (true) {
       var r = (n/maxBase).floor
       used[n - r*maxBase] = used[n - r*maxBase] - 1
       n = r
       depth = depth - 1
       if (r == 0) break
   }
   if (depth != 0) return 0
   var i = 1
   while (i < maxBase && used[i] == 0) i = i + 1
   if (i >= maxBase) numbers.add(result)
   return 0

}

var nextDigit // recursive function nextDigit = Fn.new { |dgt, depth| 

   if (depth < maxBase-1) {
       for (i in dgt...maxBase) {
           usedDigits[dgt] = usedDigits[dgt] + 1
           nextDigit.call(i, depth + 1)
           usedDigits[dgt] = usedDigits[dgt] - 1
       }
   }
   if (dgt == 0) dgt = 1
   for (i in dgt...maxBase) {
       usedDigits[i] = usedDigits[i] + 1
       calcNum.call(depth, usedDigits.toList)
       usedDigits[i] = usedDigits[i] - 1
   }

}

initPowerDgt.call() nextDigit.call(0, 0) numbers = Lst.distinct(numbers) numbers.sort() System.print("Own digits power sums for N = 3 to 9 inclusive:") System.print(numbers.map { |n| n.toString }.join("\n"))</lang>

Output:
Same as iterative version.
Retrieved from "https://rosettacode.org/wiki/Own_digits_power_sum?oldid=316702"