読者です 読者をやめる 読者になる 読者になる

Problem 33

Project Euler

Problem 33

49/98は面白い分数である. 
「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と
経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである.

我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある.

その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

これは面白い問題ですね。
ただ、あまりにもあっけなく解けてしまいそうな予感。


分母は10の倍数や11の倍数ではないので、
2桁の整数90通りから10の倍数9通りと11の倍数9通りを引いて 72通り、
つまり高々 72×71 = 5,112 通りを調べれば良いことになります。

とりあえず今回も力技で解いてしまいます。
Project Eulerに力技じゃ解けない問題は無いのだろうか…)

def gcd(a, b):
    while True:
        q = a / b
        r = a - b * q
        if r == 0:
            return b
        a, b = b, r

mul_a, mul_b = 1, 1
for a in xrange(10, 100):
    if a % 10 == 0 or a % 11 == 0:
        continue
    str_a = str(a)
    
    for b in xrange(a + 1, 100):
        if b % 10 == 0 or b % 11 == 0:
            continue
        str_b = str(b)
        
        for char_a in str_a:
            x = int(char_a)
            list_a = [int(c) for c in str_a]
            list_b = [int(c) for c in str_b]
            if not x in list_b:
                continue
            
            list_a.remove(x)
            list_b.remove(x)
            if len(list_a) != 1 or len(list_b) != 1:
                continue
            
            if a * list_b[0] == b * list_a[0]:
                mul_a *= a
                mul_b *= b

divider = gcd(mul_a, mul_b)
print mul_b / divider

計算時間は 0.063 [sec] で、
答えは

100

となりました。


ちなみに題意を満たす数は

16/64 = 1/4
19/95 = 1/5
26/65 = 2/5
49/98 = 4/8

の4つとなります。


もっとコード量を少なく、かつ高速に書きたかったとは思いますが、
とりあえずやっつけでブログ更新してみました。
分数の形として

NA/NB
NA/BN
AN/NB
AN/BN
(ただし、A,B,Nは1〜9までの整数)

という4パターンを考えて、
A,B,N にそれぞれ1〜9の9通りの数を入れれば良いので、
4 * 9 * 9 * 9 = 2,916 通りを調べるだけでも大丈夫そうですね。

SANYO NEW eneloop 電池残量表示機能付き急速充電器(単3形4個セット) N-TGR03AS

SANYO NEW eneloop 電池残量表示機能付き急速充電器(単3形4個セット) N-TGR03AS