Project Euler 52: Permuted multiples

Detta problem löste jag på en rast på jobbet.

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Här gäller det att tänka på var man ska leta och se till att man inte letar mer än vad man måste. Jag fann två sätt att begränsa var man ska leta:

Lösningen måste ha minst 6 siffror eftersom för första siffran i talet som vi kan kalla n så måste även siffrorna 2*n%10, 3*n%10, 4*n%10, 5*n%10, 6*n%10 finnas i talet.

Om ett tal är delbart med 3 så kommer även summan av siffrorna vara delbart med tre. Eftersom lösningen och 3*lösningen måste ha samma antal siffror så måste även lösningen vara delbar med tre.

Detta kan expanderas eftersom skillnaden mellan varje tal och dess permutationer måste vara delbart med 9.

Alltså kan vi börja med det minsta talet som är jämt delbart med 9 över 100 000 dvs 100 008 och inkrementera med 9 tills vi finns svaret.

problem_52() ->
    Start = os:timestamp(),
    Res = problem_52_helper(100008),
    io:format("Resultatet: ~p och det tog ~p sekunder att beräkna~n", [Res, timer:now_diff(os:timestamp(), Start)/1000000]).

problem_52_helper(A) ->
    A_list = integer_to_list(A),
    IsPerm  = [member(integer_to_list(A*X), A_list) || X - lists:seq(2, 6)],
    case lists:member(false, IsPerm) of
	true -> problem_52_helper(A+9);
	false -> A
    end.	    

member([], _) -> true;
member([H|T], A) ->
    case lists:member(H, A) of
	true -> member(T, A);
	false -> false
    end. 

perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

Resultatet: 142857 och det tog 0.02366 sekunder att beräkna. Notera att 1/7 = 0.142857 142857 …

/André