PE 71 72 73 Farey Neighbours (sequence) (farey序列)

PE 71 72 73 Farey Neighbours (sequence) (farey序列)

Patrick from Woodbridge School proved the first part of this question:If 0

bd

We know F1=01,11 and F2=01,12. The mediant of 01 and 12 is 13 and the mediant of 12 and 11 is 23. So

F3=01,13,12, 23,11.

The mediant of 01 and 13 is 14. The mediant of 13 and 12 is 25 and so is not included in F4. The mediant of 12 and 23 is 35 and so is not included in F4. The mediant of 23 and 11 is 34. Thus

F4=01,14,13,12,23,34,11.

The mediants of F4 are : 15, 27 (not included in F5), 25, 35 , 57 (not included in F5) and 45. Therefore

F5=01,15,14,13,25,12,35,23,34,45,11.

Edd from Sidcot school did the first part in a similar way and used mathematical induction to prove that, in every Farey sequence, if bd and ac are consecutive terms (said to be Farey neighbours) then |ad−bc|=1.

First F1=01,11 and

,so the result is true for n=1.

Assuming the result for Fn we next prove that the result follows for Fn+1.

We have Fn=…bd,ac… and |ad−bc|=1.

If d+c≤n+1 then Fn+1=…bd,(b+a)(d+c)ac… and |d(b+a)−b(d+c)|=|ad−bc|=1. The only other possibility is that d+c>n+1 in which case Fn+1=…bd,ac… with |ad−bc|=1, so the result is true for n+1.

Hence, by the axiom of induction the result is true for all positive integer values of n

.

推荐题目

PKU 2478 Farey Sequence

TJU 2798 Farey Sequence

PKU 3374 Cake Share

PE 71 PE 72 PE 73

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。