- 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。
問題73：範囲内の分数の数
原文 Problem 73:Counting fractions in a range
問題の要約：分母が$d \le 12000$の既約真分数が$1/3$と$1/2$の間にいくつあるかを求めよ
例題として挙げられているのが$d \le 8$のときで、解は3つです。
素直に考えると以下の式になるので
\frac{1}{3} < \frac{n}{d} < \frac{1}{2} \\
各辺d倍して \\
\frac{d}{3} < n < \frac{d}{2} \\
この条件を満たし既約分数なので$gcd(n,d)=1$を条件に数を数えます。
N=12000
print(f"Answer: {[gcd(n,d)==1 for d in range(2,N+1) for n in range(floor(d/3)+1 ,ceil(d/2))].count(True)}")
Stern–Brocot treeを使った解法
別解としてStern–Brocot tree(Wikipedia)を使う方法があります。日本語のWikipediaはないですがファレイ数列(Wikipedia)に少しだけ説明があります。
以下のような性質があるので、範囲内の既約分数をすべて生成することが可能なのでまさにこの問題どおりです。
- 2つの既約分数の分子どおし、分母どおしを加える事を繰り返して作られる木
- できた分数も既約分数
- すべての分数を網羅する
例えば、以下のプログラムでは$d<8$の既約真分数を範囲を指定して列挙します。
### Stern–Brocot tree
def sternBrocot(nl, dl, nr, dr):
nm, dm = nl+nr, dl+dr
if dm > Dmax: return []
return sternBrocot(nl, dl, nm, dm)+sternBrocot(nm, dm, nr, dr)+[(nm, dm)]
Dmax = 8
rpf = sternBrocot(0,1,1,1) # 0/1 < n/d < 1/1
print(f"Fractions(d<{Dmax}): {len(rpf)}, {rpf}")
rpf = sternBrocot(1,2,1,3) # 1/2 < n/d < 1/3
print(f"Fractions (d<{Dmax}) between (1/3-1/2): {len(rpf)}, {rpf}")
#Fractions(d<8): 21, [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 7), (2, 5), (3, 8), (3, 7), (2, 3), (3, 5), (4, 7), (5, 8), (3, 4), (5, 7), (4, 5), (5, 6), (6, 7), (7, 8)]
#Fractions (d<8) between (1/3-1/2): 3, [(2, 5), (3, 7), (3, 8)]
今回の問題は数だけ数えれば良いので、カウントだけreturnします。
再帰関数だと深くなりすぎるので、dequeを使った実装に変更しました。
from collections import deque
def sternBrocot(n1,d1,n2,d2,dmax):
q = deque([(n1,d1,n2,d2)])
ret = 0
while len(q)>0:
(n1,d1,n2,d2) = q.pop()
nm, dm = n1+n2, d1+d2
if dm <= dmax:
ret += 1
q.append((n1, d1, nm, dm))
q.append((nm, dm, n2, d2))
return ret
print(f"Answer: {sternBrocot(1,2,1,3, 12000)}")
（開発環境：Google Colab）