# 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
```