Euler Solution 92

From ProgSoc Wiki

Jump to: navigation, search

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
Personal tools