# Euler Solution 92

### From ProgSoc Wiki

## Contents |

# Solutions for Problem 92

Every number can be used to create a chain, where each step is the function from a number to the sum of the square of its digits. Eventually all numbers either end at 1 or 89. Find how many numbers in the range 1..10000000 end in 89.

## Caml by SanguineV

Runtime: 15.017 seconds

(* Calculate the square of the digits of a number. *) let rec sqrDigs n = if n < 10 then n * n else let n' = n mod 10 in (n' * n') + (sqrDigs (n / 10)) ;; (* Given a number, determine if it ends with 89 *) let rec end89 = function | 1 -> false | 89 -> true | n -> end89 (sqrDigs n) ;; (* Initialise a hash table with the result of "end89" for each * number 1 to the limit. *) let init tbl lim = let rec inner n = if n > lim then () else (Hashtbl.add tbl n (end89 n);inner (n + 1)) in inner 1 ;; (* Given a number, calculate the maximum square of digits for a number * with that many digits. *) let maxVal n = let rec inner n acc = if n < 10 then (10 * acc) + 9 else inner (n / 10) ((10 * acc) + 9) in inner n 0 ;; (* For any given number there is a limit to the number of of values * for the sum of the square of the digits. Rather than calculate these * exactly, just add every number up to the maximum to the hash table * then search through the hash table for every number up to the limit * and use that result. *) let countTo lim = let valLim = sqrDigs (maxVal lim) in let myTbl = Hashtbl.create valLim in let _ = init myTbl valLim in let rec inner n res = if n = lim then res else if Hashtbl.find myTbl (sqrDigs n) then inner (n + 1) (res + 1) else inner (n + 1) res in inner 1 1 ;; (* Print the result. *) Printf.printf "Total: %u\n" (countTo 9999999);;

## Java by SanguineV

Runtime: 15.067 seconds

/* A program to solve Poject Euler problem 92 */ class euler92 { /* Calculate the square of the digits of an integer */ private static int squareDigits (int i) { int res = 0; int cd; while (i > 9) { cd = i % 10; res = res + (cd * cd); i = i / 10; } res = res + (i * i); return res; } /* Determine if an integer culminates in 89 eventually (only other finish * state is 1). */ private static boolean end89 (int i) { i = squareDigits(i); while (!(i == 1)) { i = squareDigits(i); if (i == 89) { return true; } } return false; } /* Given an integer, determine the maximum value of it's digits squared. */ private static int maxValue (int i) { int max = 81; while (i > 9) { i = i / 10; max = max + 81; } return max; } /* An initialise method to set all the values in an array based on a known * size. A shorter lookup as all other values will end up at one of these * so predetermine them all to save recalculation. */ private static void init (int tsize, boolean[] vals) { while (tsize > 0) { vals[tsize - 1] = end89(tsize); tsize = tsize - 1; } } /* The main method that does most of the work. */ public static void main(String args[]) { // The limit for the Euler Problem. int limit = 9999999; // Set the array size to be the maximum value for the square of // the number of digits in the limit. int arsize = maxValue(limit); // Initialise the count of the ones that end in 89. int count = 0; // Create the array and then initialise it. boolean[] vals = new boolean[arsize]; init(arsize,vals); // Count down from the limit and if the number ends in 89 (based on // pre-calculated values) then increment the count. while (limit > 0) { if (vals[squareDigits(limit) - 1]) { count = count + 1; } limit = limit - 1; } // Print the result! System.out.println("Result is: " + count); } }

Yes I know declaring everything static is lazy and not "true OO style", but I am already annoyed enough that Java on niflheim doesn't seem to support any kind of import/includes (I could do more interesting problems with BigIntegers).

At least we have another Java solution to herald the UTS Java School way.

## Python by Althalus

Runtime: 50 Seconds, 20 seconds with Psyco

def squareDigits(a): res = 0 while a > 9: res,a = res+(a%10)**2,a/10 return res+(a**2) #For every number up to 10,000,000, the first pass always brings it down to a number less than this. for i in xrange(1,568): chain = [] n = i is89 = 0 while 1: if not numbers.has_key(n): numbers[n] = 0 elif numbers[n] == 1: numbers[i] = 1 break elif n == 89: numbers[i] = 89 break n = squareDigits(n) count = 0; for i in xrange(1,10000001): if numbers[squareDigits(i)] == 89: count +=1 print count