当前位置:首页 » Project Euler » 详细页

Ambiguous Numbers 题号:198 难度: 80 中英对照

A best approximation to a real number x for the denominator bound d is a rational number r/s (in reduced form) with sd, so that any rational number p/q which is closer to x than r/s has q > d.

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. 9/40 has the two best approximations 1/4 and 1/5 for the denominator bound 6. We shall call a real number x ambiguous, if there is at least one denominator bound for which x possesses two best approximations. Clearly, an ambiguous number is necessarily rational.

How many ambiguous numbers x = p/q, 0 < x < 1/100, are there whose denominator q does not exceed 108?

Solution

Farey数列是一个在区间$[0,1]$的最简分数序列,且容易看出除了$0$和$1$以外都是真分数,这个序列包括所有分母不超过给定数字$k$的最简分数且从小到大排列,记为$F[k]$,为表述方便,$0$和$1$一般表示为$0/1$和$1/1$,例如: $$F[1]=\{0/1,1/1\}$$ $$F[2]=\{0/1,1/2,1/1\}$$ $$F[3]=\{0/1,1/3,1/2,2/3,1/1\}$$ $$F[4]=\{0/1,1/4,1/3,1/2,2/3,3/4,1/1\}$$ $$F[5]=\{0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1\}$$ $$……$$ Farey数列有三个很重要的基本性质: 1. $a/b$和$c/d$是某个$F[k]$数列的相邻两项,当且仅当$bc-ad=1$ 2. 若$bc-ad=1$,则处于$a/b$和$c/d$之间的分母最小的分数是$(a+c)/(b+d)$,且不能约分,且是唯一的,即这个区间中不存在其他以$b+d$为分母的分数 3. 若$a/b< c/d< e/f$是某个$F[k]$数列的连续三项,则$c/d=(a+e)/(b+f)$ $x$为一个两可数当且仅当对于某个$a/b$和$c/d$,$x-a/b=c/d-x$,于是解得 $$x=(ad+bc)/(2bd)$$ 于是就可以从数列$\{0/1,1/50\}$开始,按照Farey数列的生成规则,用递归搜索所有$a/b$和$c/d$,计算$x$,其中$b$、$d$和$x$的分母都不超过$10^8$,且$x< 1/100$即可。

Code

import java.util.ArrayDeque;

public final class p198 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }


    static public String run() {

		final long size = 100000000;
		final long boundn = 1, boundd = 100;
		ArrayDeque<Long> list = new ArrayDeque<Long>();
		long leftn = 0, leftd = 1; // Farey number on the left
		long rghtn = 1, rghtd = 50; // Farey number on the right
		long count = 0;
		while (true) {
			long ambigd = 2 * leftd * rghtd; // get ambiguous number in this
												// interval
			if (ambigd <= size) {
				long ambign = leftd * rghtn + leftn * rghtd;
				if (ambign * boundd < boundn * ambigd)
					count++; // count it if it is in range
				long medn = leftn + rghtn, medd = leftd + rghtd; // split
																	// interval
																	// by
																	// mediant
				if ((medn * boundd <= boundn * medd)) {
					list.push(leftd);
					list.push(leftn); // save lhs interval
					leftn = medn;
					leftd = medd; // use rhs interval
				} else {
					rghtd = medd;
					rghtn = medn; // use lhs interval
				}
			} else { // bottomed out
				if (list.isEmpty())
					break; // get next interval, if any
				rghtn = leftn;
				rghtd = leftd;
				leftn = list.pop();
				leftd = list.pop();
			}
		}
		return count+"";
	}

}
52374425
3710ms