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
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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript