Farey数列 (法雷数列)

Dear 丶 2022-09-17 11:24 135阅读 0赞

以下整理自：http://www.cnblogs.com/genyuan/archive/2012/08/29/2662598.html

及http://blog.csdn.net/ji414341055/article/details/5793166

修正了部分错误，整理了代码。

**法雷数列的来源：**

约翰·法雷 是英国一位多才多艺的“ 杂家” , 生活在拿破仑时代, 职业是土地丈量员, 却有着广泛的爱好, 喜欢搜集奇异的石头、矿物, 兴致来潮, 撰写小块科普文章在《哲学杂志》上发表, 题材广泛涉及到地质、音乐、钱币、车轮、慧星, 偶尔也涉及数学小品。1816年, 当他审读亨利 戈德温所编的“ 小数商表” 时,忽然有一个问题涌上心头， 既约最简真分数有多少呢能不能把它们按一定的顺序排列出来兴致所及, 急切难忍, 他立即推开戈氏冗繁的“商表” , 动手排列起来, 一遍又一遍, 没有头绪。这时他想到两点：一是真分数有无限多个, 要“ 全部” 排出, 必须限制分母的大小二是可按递增的顺序去排列, 容易发现规律 他终于排出来了, 还发现了若干性质。发表后, 立即被当时数学家们抓住, 后来数学家柯西发现这分数串在数学中很有用,并名之为法雷数列。 没成想早在14年前, 一位名叫哈罗斯的人, 就发现并公布了自己的研究结故。名之哈罗斯一法雷数列。

**定义和定理**

定义一： 最简分数（也称既约分数或不可约分数）。若p,q的最大公约数是1，我们称分数p/q是最简分数。

定义二： 真分数，若p,q是正整数，0<p/q<1, 我们说p/q是真分数

定理：

分数a/b, c/d是最简真分数（也可以是0/1或者1/1）且a/b <c/d, 则有

1) 数(a+c)/(b+d)是一个最简分数

2) a/b < (a+c)/(b+d) < c/d

证明略

**法雷数列的定义：**

对任意给定的一个自然数n，将分母小于等于n的不可约的真分数按升序排列，并且在第一个分数之前加上0/1，在最后一个分数之后加上1/1，这个序列称为n级法雷数列，以Fn表示。

如F6为：0/1，1/6，1/5，1/4，1/3，2/5，1/2，3/5，2/3，3/4，4/5，5/6，1/1。

如F5为：1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5.

**推导法雷数列方法：**

应用定理中的(2),如果 a/b 和 c/d 是一个法雷数列，则在它们中间可以插入 p/q =(a+c)/(b+d),（前提是得出的q值小于或者等于给定的n值）所以可以二分构造，直到不比如

N = 5：

step1: 准备两个数 0/1, 1/1 作为整个法雷数列的第一个元素和最后一个元素0/1, 1/1

step2: 在两个数中间插入1个数1/2, 变为0/1, 1/2, 1/1

step3: 在每对相邻两个数中间插入1个数，变为0/1, 1/3, 1/2, 2/3, 1/1

step4: 在每对相邻两个数中间插入1个数，变为0/1, 1/4, 1/3, 2/5 , 1/2, 3/5, 2/3, 3/4 , 1/1

step5: 0/1 和 1/4 之间 和3/4和 1/1 仍然可插入1个数，且插入的数分母不大于5 0/1, 1/5 , 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5 , 1/1

至此，该序列包含了所有分母不大于5的最简真分数，且各个分数以递增顺序排 列。

附递归构造法雷数列的程序:

#include <cstdio>
    #include <cstring>
    using namespace std;
    
    int N;
    void farey (int a,int b,int c,int d)
    {
        if (b+d > N) return ;
        if (b+d == N)
    	{
            printf("%d/%d",a+c,b+d);
            if(a+c != N-1) printf(",");
            return ;
        }
        farey(a,b,a+c,b+d);
        printf("%d/%d,",a+c,b+d);
        farey(a+c,b+d,c,d);
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        while (T--)
    	{
            scanf("%d",&N);
            farey(0,1,1,1);
            printf("\n");
        }
    }

**法雷数列的一些性质：**

> 性质1：n级法雷数列中相邻两个分数a/b和c/d的差为1/bd，并且所有的差中最小值为1/（n\*（n-1））；
> 
> 性质2：除了1级法雷数列外，所有的法雷数列都有奇数个元素，其中居于正中间的那个元素一定是1/2；
> 
> 性质3：当n趋于正无穷时，n级法雷数列包含的元素的个数趋于3/(pi\*pi) \* n^2 ≈ 0.30396355 \* n^2。
> 
> 性质4：Farey序列是一个对称序列，头尾之和为1。
> 
> 性质5：假如序列中有三个连续元素x1/y1, x2/y2, x3/y3，则有x2 = x1+x3; y2 = y1+y3;并且有x1\*y2 – x2\*y1 = 1。这条性质保证构造出来的分式肯定是不可约分式。

**用法雷数列逼近一个实数的方法：**

Step1: 置实数f 的下界为a/b=0/1, 上界为c/d =1/1。

Step2: 计算出下界和上界之间的数p/q = (a+c)/(b+d)

Step3: 若q>n(分母大于指定值），计算中止。

若p/q = f，a/b <p/q , c/d >p/q, 计算中止。

若p/q < f, 置下界a/b为p/q

若p/q > f, 置上界c/d为p/q

Step4, 重复step 2-3

当计算终止时，a/b为这个实数的下界，c/d为这个实数的上界。

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    void Farey (double A,int limit)
    {//法雷序列，最大值限制为limit，逼近实数A,a/b<A<c/d
    	//A要求0<A<1,p和q会超过limit
    	int a=0,b=1,c=1,d=1;
    	int p=a+c,q=b+d;
    	while (q <= limit && p<limit)
    	{
    		if (A > 1.0*p/q)
    		{
    			a = p;
    			b = q;
    		}
    		else 
    		{
    			c = p;
    			d = q;
    		}
    		p = a + c;
    		q = b + d;
    	}
    	printf("%d/%d < %lf < %d/%d\n",a,b,A,c,d);
    	printf("%d/%d\n",p,q);
    }
     
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	double A;
    	int limit;
    	while (~scanf("%lf%d",&A,&limit))
    	{
    		Farey(A,limit);
    	}
    	return 0;
    }