Problem33

30分プログラム、その306。Problem33 - ProjectEuler。

49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである.
我々は 30/50 = 3/5 のようなタイプは自明な例だとする.
1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある.
その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ

なぜか答えが、1/100というとても綺麗な数字になった。すげぇ。

使い方

0> problem33:main().
{1,
 100}

ソースコード

-module(problem33).
-compile([export_all]).

gcd(N,0)->
    N;
gcd(N,M) ->
    gcd(M,N rem M).

reduction(N,M) ->
    R = gcd(N,M),
    {N div R,M div R}.

satisfy({_,0},{_,0}) -> false;
satisfy({X,Y},{Z,W}) when X*10+Y > Z*10+W -> false;
satisfy({X,Y},{X,Y}) -> false;
satisfy({X,Y},{Z,W}) ->
    R = reduction(X*10+Y,Z*10+W),
    (X =:= Z andalso R == reduction(Y,W))
	orelse (X =:= W andalso R == reduction(Y,Z))
	orelse (Y =:= Z andalso R == reduction(X,W)) 
	orelse (Y =:= W andalso R == reduction(X,Z)).

main()->
    Xs = lists:filter(fun({X,Y,Z,W}) -> satisfy({X,Y},{Z,W}) end,
		      [{X,Y,Z,W} || X <- lists:seq(1,9),
				    Y <- lists:seq(0,9),
				    Z <- lists:seq(1,9),
				    W <- lists:seq(0,9)]),
    {A,B} = lists:foldl(fun ({X,Y,Z,W},{InitA,InitB}) -> 
                          {(X*10+Y)*InitA,(Z*10+W)*InitB}end,{1,1},Xs),
    reduction(A,B).

参考

• 過去の30分プログラム
• Problem 33 - PukiWiki