Iterated digits squaring

editable example

Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.

ghul

use IO.Std.write_line

use Collections.LIST

digit_square_sum(value: int) -> int => (

let rest mut = value

let total mut = 0

while rest > 0 do

let digit = rest % 10

total = total + digit * digit

rest = rest / 10

od

total

)

reaches_89(value: int) -> bool => (

let current mut = value

while current != 1 /\ current != 89 do

current = digit_square_sum(current)

od

current == 89

)

let limit = 100000000

let max_after_one_step = 648

let memo = LIST[bool]([false])

for value in 1::max_after_one_step do

memo.add(reaches_89(value))

od

let chains mut = 0

for value in 1..limit do

if memo[digit_square_sum(value)] then

chains = chains + 1

fi

od

write_line("{chains:N0} chains starting below {limit:N0} reach 89")

85,744,333 chains starting below 100,000,000 reach 89