a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

main.ml (1581B)

 1 (* This program is a simple test for the following conjecture:
 2 
 3    Let S: N -> N be the sum of the digits of a positive integer.
 4    For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an 
 5    interger. *)
 6 
 7 let failure = 1
 8 let invalid_input = 2
 9 
10 (** Returns the sum of the digits of `n`, where `n` is a positive integer. *) 
11 let sum_digits n =
12   let rec sum_digits_tail n acc =
13     match n with
14     | 0 -> acc
15     | _ -> sum_digits_tail (n / 10) (acc + n mod 10)
16   in sum_digits_tail n 0
17 
18 (** Precompute the values of `sum_digits`.*)
19 let get_sums max =
20   Array.init (2 * max + 1) sum_digits
21 
22 (** Returns true if a counterexample (a, b) with 0 <= a, b <= max exists **)
23 let counterexempl max =
24   let rec sums_cache = get_sums max (* Cache the results of sum_digists *)
25   and sum_digits n = Array.get sums_cache n 
26 
27   (* Returns true if (a, b) is a counterexemple *)
28   and test a b = 
29     0 <> (sum_digits (a + b) - sum_digits a - sum_digits b) mod 9
30 
31   (* Returns true if there is b with 0 <= b <= a such that (a, b) is a
32       counterexample *)
33   and aux a = aux_tail a a false
34   and aux_tail a b acc =
35     if b <= 0 then acc else aux_tail a (b - 1) (acc || test a b)
36 
37   and counterexempl_tail a acc =
38     if a <= 0 then acc else counterexempl_tail (a - 1) (acc || aux a)
39 
40   in counterexempl_tail max false
41 
42 let main () =
43   let max_opt = 
44     if Array.length Sys.argv > 1 then int_of_string_opt Sys.argv.(1) 
45     else None in
46   match max_opt with
47   | Some max when max > 0 -> if counterexempl max then exit failure else ()
48   | _ -> exit invalid_input
49 
50 let () = 
51   main ()
52