『ファレー数列』

『ファレー数列』解答

◆神奈川県　＠ＪＪＪＪＪＪ　さんからの解答。

【問題１】

d
―
c - b
―
a = ad-bc
――――
ac = k
――
ac 、

（ad-bc=k＞1）とすると、

b/a と　d/c　との間に数列、

b
―
a ， b
―
a + 1
――
ac ， b
―
a + 2
――
ac ，・・， b
―
a + k-1
――
ac ， b
―
a + k
――
ac = d
―
c

が存在する。
これは、「自然数ｎに対して，分母がｎ以下であるような既約分数のうちで，０以上１以下のもの全てを大きさの順に並べた数列をつくる」という条件に反する。

従って、ad-bc=k=1、でなければならない。

【問題２】

b
―
a ＜ q
―――
n+1 ＜ d
―
c と問題１より、

aq-(n+1)b=1,(n+1)d-qc=1、従って、

a+c=n+1=p,q=a+c

【問題３】

F(3)=(0/1,1/3,1/2,2/3,1/1)

F(4)=F(3)+(1/4,3/4)

F(5)=F(4)+(1/5,2/5,3/5,4/5)

F(6)=F(5)+(1/6,5/6)

従って、

F(n)の項数 = F(n-1)の項数 + (p＜n,pはnと素｜となるpの個数)

◆宮城県　アンパンマン　さんからの解答。

【問題３】

N(n)=F(n)の項数　とすると

N(n)
= N(n-1)+(p＜n,pはnと素｜となるpの個数)
=N(n-1)+φ(n)

ここでφ(n)=オイラー関数

n=p₁^r_1*p₂^r_2*...*p_s^r_sとすると

φ(n)=n*(1-1/p₁)(1-1/p₂)...(1-1/p_s)

N(1)=2　から

N(n)=1+ n
Σ
i=1 φ(n)