a-conjecture-of-mine

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

main.ex (1695B)

 1 # The following 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 integer.
 5 
 6 defmodule Conjecture do
 7   def main max, n_processes do
 8     if max < 0 or n_processes <= 0 do
 9       :invalid_input
10     else
11       parent_id = self()
12       :ets.new(:sums_cache, [:set, :public, :named_table])
13 
14       # Spawn a new process for each starting index from 0 to `max`
15       f = fn i -> 
16         spawn fn -> counterexpl i, max, n_processes, parent_id end
17       end
18 
19       Enum.map 0..(n_processes - 1), f
20       listen n_processes
21     end
22   end
23 
24   # Listen for messages on all processes
25   def listen 0 do :ok end
26 
27   def listen n do
28     receive do
29       :ok -> listen (n - 1)
30       :fail -> :fail
31     end
32   end
33 
34   def counterexpl a, max, step, parent_id do
35     cond do 
36       iter a, a -> send parent_id, :fail
37       a + step <= max ->
38         counterexpl (a + step), max, step, parent_id
39       true -> send parent_id, :ok
40     end
41   end
42 
43   def iter a, 0 do test a, 0 end
44 
45   def iter a, b do
46     test(a, b) || iter(a, b - 1)
47   end
48 
49   def test a, b do
50     c = a + b
51     sum_a = lookup a
52     sum_b = lookup b
53     sum_c = lookup c
54 
55     0 != rem(sum_c - sum_a - sum_b, 9)
56   end
57 
58   def lookup n do
59     case :ets.lookup(:sums_cache, n) do
60       [{_, sum_n}] -> sum_n
61       [] ->
62         sum_n = sum_digits n
63         :ets.insert(:sums_cache, {n, sum_n})
64         sum_n
65     end
66   end
67 
68   def sum_digits n do sum_digits_tail n, 0 end
69 
70   def sum_digits_tail 0, acc do acc end
71 
72   def sum_digits_tail n, acc do
73     r = rem n, 10
74     d = div n, 10
75     sum_digits_tail d, (acc + r)
76   end 
77 end
78