Digit fifth powers

2014-09-18

Problem 030: Digit fifth powers

Description:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4 8208 = 8^4 + 2^4 + 0^4 + 8^4 9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution:

v                   >55+/ v v    $$_v#!:-1               <<
>01>::9::*:***0\>:#<|#\+1\<>9::*:***>:::55+%::*:**\55+/v>|:
                    >$ -#v_^>$>+\:#<_vv/+55\**:*::%+55:<->^
   ^                   +1<           $>:55+%::*:**\55+/v+
                                     .v/+55\**:*::%+55:<+
                                     @>:55+%::*:**\55+/v+
                                      v/+55\**:*::%+55:<+
                                      >55+%::*:**\55+$++^

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

Yes. This is in fact the first program without put or get instructions. It operates completely on the stack. And that makes it really fast.

But - to be fair - the algorithm is pretty simple:

First get the upper bound for our later search, we search for a number where digitcount(9^5 * n) <= n

After our algorithm calculated that number (I resisted the urge to hard code 354294) we test every number from 0 to limit and sum the fitting ones (there are only 6).
4150, 4151, 54748, 92727, 93084, 194979

Interpreter steps:	51 019 199
Execution time (BefunExec):	7.33s (6.96 MHz)
Program size:	59 x 8 (fully conform befunge-93)
Solution:	443839
Solved at:	2014-09-18