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 solution is tail recursive, but alas, Java and Ruby 1.8 (and C#) don't optimize tail calls, so they overflow. Erlang handles it.

I discovered this the hard way and so I had switch to iteration in Ruby and Java. I am not 100% sure if my Erlang solution is indeed tail recursive (the if statement ends after the last function call) but it does run noticeably faster than the others. I am a novice Ruby and Erlang coder, all code improvement suggestions will be gratefully accepted (expect for ones that call out for hard coding/error handling/better names, this is a puzzle dammit.)

public class Eighteen{

public static void main(String[] args){

System.out.println("answer is "+ new Eighteen().findit(1));

}

private int findit(int multiple){

int n = 180 * multiple - 1;

for(int divisor=17; divisor > 2; divisor--){

if (n % divisor != (divisor-1)) break;

if (divisor == 3) return n;

}

return findit(multiple+1);

}

}

def findit

i = 0

while i = i + 1

n = 180 * i - 1

17.downto 3 do |divisor|

if (n % divisor != (divisor-1))

break

end

if (divisor == 3)

puts "answer is #{n}"

exit

end

end

end

end

% Erlang solution

-module(find18).

-export([findit/0]).

is18(Num) -> is18(Num, 18).

is18(Num, 1) -> true;

is18(Num, Divisor) ->

(Num rem Divisor == (Divisor - 1)) andalso is18(Num, Divisor - 1).

findit() -> findit(1).

findit(Mult) ->

Candidate = 180 * Mult - 1,

Found = is18(Candidate),

if

Found -> Candidate;

true -> findit(Mult+1)

end.

## 6 comments:

seems you should have written divisor > 2 in the for loop instead of divisor < 2

@ Manoj

Thanks.

Sriram, I posted what I think is a slightly more idiomatic erlang solution, along with some comments, on my blog, at http://erl.nfshost.com/2009/05/10/245245/

I'm not sure why, but the link above did not paste properly. The final 245245 should just be 245. I'll try pasting it again and hope for the best.

http://erl.nfshost.com/2009/05/10/245/

My colleague Ramesh Rajamani came up with this little gem of a solution in Erlang.

-module (math2).

-export ([findNum/2]).

findNum(N,1) -> N;

findNum(N,D) ->

if N rem D == D-1 ->

findNum(N,D-1);

true ->

findNum(N+1, 18)

end

I know I'm a little late to the game, but I'd like to offer my solution to the mix.

## Post a Comment

Note: Only a member of this blog may post a comment.