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.