[VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" Special

[PeterP]

Thank you VA for your kind encouragement to post, it was a pleasure to work on for a flight (and a night) so I'm glad I get to share.

Another way to define the selfie is an n-digit number which is identical to the sum of the n-the power of its digits, but does not end in a 0.

To constrain the search space, I used two features:
(1) One can always rank order the digits of a number in a monotonously falling fashion (each digit is smaller or equal than the prior one
(2) As soon as one has a sum of n-th power of digits which is larger than 10^n, one can stop as all combination of digits to the right will yield unqualified results.

The combined application of the above allows to cut of quite substantial swaths of the search tree.

The implementation is based on the specific limitations of the HP41, namely:
1) It can only deal with at most 6 subroutine levels. This makes a recursive approach unfortunately not possible on the 41, yet I would not be surprised if this is possible, indeed advisable for the 71b
2) The 41 is very very slow in dealing with direct number entries. As such, virtually all numbers are stored in registers for faster processing
3) Akin to the JPC rom, my version uses my beloved Sandbox module, for the use of INCX, DECX, and AINT
4) Once a number has been found with a sum of the n-th powers of its digits between 10^n and 10^(n-1), the number is then checked to see if it is a selfie, aka the sum of its digts raised to the n-th power, using AINT and ATOX.

The code below takes as an entry the number of digits and then runs until all n-digit selfies are found. Adding a loop over all digits would be trivial but was not done for the purpose of easier exploration of the results of the code, timing, etc.

Code:


LBL ‘VASSMC’
CLRG
STO 00        ‘’store n-digit
10^x
STO 40        ‘’store upper limit
10
/
STO 42        ‘’store lower limit
48
STO 48        ‘’store const for fast conversion from ASCII to number
21
STO 20        ‘’start space to store found numbers
19
STO 41        ‘’location for full sum
9
RCL 00
-
INCX
10
STO IND Y
GTO IND Y    ‘’this starts the search loop at the right label for the number of digits
LBL 01
   RCL 01    “digit in first spot, initialized with 10
   STO 02    “max digit for second spot
   DECX
   X<0?        “Are we done?
   GTO ‘DONE
   STO 01    “no, store for next loop
   RCL 00    “number of digits
   Y^X
   STO 11    “temp-sum of first digit to n-th power
   LBL 02    “second digit
      RCL 02    “second digit, initialized in prior code to value of first digit
      STO 03    “max digit for third spot
      DECX
      X<0?    “Are we done?
      GTO 01    “yep, count down one more the first digit
      STO 02    “nope. Calc n-th power
      RCL 00
      RCL 11    “get sum from prior digit
      +
      STO 12    “store sum of this digit
      RCL 40    “10^n, upper limit
      X<=Y?    “Is the current sum smaller than this 10^n?
      GTO 02    “Nope, count down on this level by one
      LBL 03    “yes, tackle next digit. 
         RCL 03    “third digit, initialized in prior code to value of first digit
         STO 04    “max digit for fourth spot
         DECX
         X<0?    “Are we done?
         GTO 02    “yep, count down one more the prior digit
         STO 03    “nope. Calc n-th power
         RCL 00
         RCL 12    “get sum from prior digit
         +
         STO 13    “store sum of this digit
         RCL 40    “10^n, upper limit
         X<=Y?    “Is the current sum smaller than this 10^n?
         GTO 03    “Nope, count down on this level by one
         LBL 04
            RCL 04
            STO 05    
            DECX
            X<0?    
            GTO 03    
            STO 04    
            RCL 00
            RCL 13    
            +
            STO 14    
            RCL 40    
            X<=Y?    
            GTO 03
            LBL 05
               […]
               LBL 06
                  […]
                  LBL 07
                     […]
                     LBL 08
                        […]
                        LBL 09
                           RCL 09
                           DECX
                           X<0?
                           GTO 08
                           STO 09
                           RCL 00
                           Y^X
                           RCL 18
                             +
                           STO 19
                           RCL 40
                           X<=y?
                           GTO 09
                           LBL 11        “we have found a candidate
                              RCL 42    “check for lower limit
                      RCL IND 41   “Final sum
                              X<=Y?
                              GTO 09
                              CLA
                      ARCLI    “arcl integer
                              ALENG
                      LBL 00    “calc sum of n-th power of digits of candidate
                         ATOX
                         RCL 48    “value: 48
                         -
                         RCL 00
                         Y^X
                         ST- Z    “subtract from candidate value
                         RDN
                         DSE X
                    GTO 00
                    RDN        “candidate – sum of n-th power of its digits
                          X=0?        “have we found one?
                    XEQ ‘FND    “yes, we have
                    GTO 09
                    LBL ‘FND
                       RCL IND 41
                       ARCLI
                       10        “check for last digit 0
                       /
                          FRC
                       X=0?    “is last digit 0?
                       RTN    “false alarm…
                       AREV    “reverse number in alpha
                       TONE 9
                       AVIEW
                       STO IND 20    “preserver for after the run (for long unmonitored runs)
                       ISG 20
                       CLA
                       RTN
LBL ‘DONE
   BEEP
   ‘DONE
   AVIEW
END

Very much looking forward to comments, in particular ways to make it smarter.