I was chasing links concerning the lack of tail recursion optimization in ruby and ran across a math problem:

Find the smallest positive integer n such that n % x = x-1 for x from 2 to 18
i.e. The remainder is one less than the divisor for all integral divisors from 2 to 18.

The author, Sriram Narayan, offered java, ruby, and erlang solutions. His erlang solution had a bit of a java accent. Sriram states that he is new to erlang and requested advice and commentary, so I thought I would offer a slightly more idiomatic version of his solution.

The problem Sriram poses is easy enough to solve by hand if one makes a simple observation: n mod x = x-1 if and only if n = k*x + x-1 for some integer k. In particular, n+1 = (k+1)*x, i.e., x divides n+1. So the problem amounts to finding the least positive integer divisible by 18, 17, …, 2. Clearly 18! has the necessary divisors, so a solution exists, and is bounded above by 18!.

Let’s just do a brute force search, in erlang. This solution is tail recursive, as requested.

``````-module(f18).
-export([find_it/0]).
%% N is suitable if divisible by each of 18,17, ... ,2
suitable(N) when is_integer(N), N > 0 ->
suitable(N, 18).

suitable(_N, 1) ->
true;
suitable(N, K) when N rem K == 0 ->
suitable(N, K-1);
suitable(_N, _K) ->
false.

find_it() ->
find_it(19).

%% This will halt since since 18! satisfies suitable/1.
%% 1st suitable N found will be the smallest possible.
find_it(N) ->
case suitable(N) of
true ->
N;
false ->
find_it(N+1)
end.
``````

Running f18:find_it() returns 12252240, so the solution to Sriram’s original problem is 12252239.

In the multilingual spirit of the original post, here is the ruby verification that 12252239 satisfies the original problem.

``````irb(main):001:0> \$y=12252239
=> 12252239
irb(main):002:0> (2..18).map {|x| \$y.modulo(x)}
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
``````
``` ```

I'll leave it as an exercise for the reader to determine how to solve the problem by hand. Hint: consider the prime factorizations of each of the numbers 18, 17, ... , 2.