Square digit chains


Fork me on GitHub
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