Square digit chains

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

Download

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