1 ! Copyright (c) 2008 Aaron Schaefer, Slava Pestov.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: kernel math ranges project-euler.common sequences ;
6 ! https://projecteuler.net/problem=92
11 ! A number chain is created by continuously adding the square of
12 ! the digits in a number to form a new number until it has been
17 ! 44 -> 32 -> 13 -> 10 -> 1 -> 1
18 ! 85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89
20 ! Therefore any chain that arrives at 1 or 89 will become stuck
21 ! in an endless loop. What is most amazing is that EVERY
22 ! starting number will eventually arrive at 1 or 89.
24 ! How many starting numbers below ten million will arrive at 89?
32 : next-link ( n -- m )
33 number>digits [ sq ] map-sum ;
35 : chain-ending ( n -- m )
36 dup [ 1 = ] [ 89 = ] bi or [ next-link chain-ending ] unless ;
38 : lower-endings ( -- seq )
39 567 [1..b] [ chain-ending ] map ;
41 : fast-chain-ending ( seq n -- m )
42 dup 567 > [ next-link ] when 1 - swap nth ;
46 : euler092 ( -- answer )
47 lower-endings 9999999 [1..b] [ fast-chain-ending 89 = ] with count ;
49 ! [ euler092 ] 10 ave-time
50 ! 33257 ms ave run time - 624.27 SD (10 trials)
52 ! TODO: this solution is not very efficient, much better optimizations exist