2016-08-25

# Problem 092: Square digit chains

Description:

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

``````44 -> 32 -> 13  -> 10 -> 1  -> 1
85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89``````

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

Solution:
v \$\$ T # #######################################################################
# #######################################################################
XX   # #######################################################################
# #######################################################################
# #######################################################################
# #######################################################################
# #######################################################################
# #######################################################################

v                                   p1*93"Y" p0+551 \$<
> "G"8*:32p"}2(("***22p020p030p  >1-:0\:"G"%9+\"G"/p:!|
v     pp02+1:g027:\$<^            >#   v# <
>22g:>:32g`#v_::"G"%9+\"G"/g:!#^_:"Y"-!#v_:1-|    #   >1-:20p7\g50g\:  v
>0\>:55+%:*\ :#v_\$\$11v>30g1+  30p>50p\$20g:|:g02p/"G"\+9%"G"<
>3     v^/+55g05+p05< >\$@  ^     <     v1:: -1\$<
^_^#  _^#># 0# g# .# \$# ^#  <            < *0<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

My approach to this problem is pretty crude. Perhaps I will later come back and try to find a better algorithm. Currently we iterate (brute-force) through all possible numbers and count the chains that end with one. The `next()` function is implemented like this:

``````0\>:55+%:*\ :#v_\$\$
^/+55g05+p05<   ``````

We also remember in an 8x71 cache all previously found numbers so we can abort some sequences before we reach `1` or `89`. This is the main optimization from pure brute-force in this program.

We can prove that an 568-element cache is enough because no number in the sequence (except the first) can be greater than `9^2 * 7` (`= 567`)

 Interpreter steps: 2 959 813 630 Execution time (BefunExec): 6min 19s (7.79 MHz) Program size: 80 x 16 (fully conform befunge-93) Solution: 8581146 Solved at: 2016-08-25

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