a-conjecture-of-mine

 (* This program is a simple test for the following conjecture:
 
    Let S: N -> N be the sum of the digits of a positive integer.
    For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an 
    interger. *)
 
 let failure = 1
 let invalid_input = 2
 
 (** Returns the sum of the digits of `n`, where `n` is a positive integer. *) 
 let sum_digits n =
   let rec sum_digits_tail n acc =
     match n with
     | 0 -> acc
     | _ -> sum_digits_tail (n / 10) (acc + n mod 10)
   in sum_digits_tail n 0
 
 (** Precompute the values of `sum_digits`.*)
 let get_sums max =
   Array.init (2 * max + 1) sum_digits
 
 (** Returns true if a counterexample (a, b) with 0 <= a, b <= max exists **)
 let counterexempl max =
   let rec sums_cache = get_sums max (* Cache the results of sum_digists *)
   and sum_digits n = Array.get sums_cache n 
 
   (* Returns true if (a, b) is a counterexemple *)
   and test a b = 
     0 <> (sum_digits (a + b) - sum_digits a - sum_digits b) mod 9
 
   (* Returns true if there is b with 0 <= b <= a such that (a, b) is a
       counterexample *)
   and aux a = aux_tail a a false
   and aux_tail a b acc =
     if b <= 0 then acc else aux_tail a (b - 1) (acc || test a b)
 
   and counterexempl_tail a acc =
     if a <= 0 then acc else counterexempl_tail (a - 1) (acc || aux a)
 
   in counterexempl_tail max false
 
 let main () =
   let max_opt = 
     if Array.length Sys.argv > 1 then int_of_string_opt Sys.argv.(1) 
     else None in
   match max_opt with
   | Some max when max > 0 -> if counterexempl max then exit failure else ()
   | _ -> exit invalid_input
 
 let () = 
   main ()