### Counting fractions in a range题号：73 难度： 15 中英对照

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

### Code


public final class p73 {
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" );
}
/*
* The Stern-Brocot tree is an infinite binary search tree of all positive rational numbers,
* where each number appears only once and is in lowest terms.
* It is formed by starting with the two sentinels 0/1 and 1/1. Iterating infinitely in any order,
* between any two currently adjacent fractions Ln/Ld and Rn/Rd, insert a new fraction (Ln+Rn)/(Ld+Rd).
* See MathWorld for a visualization: http://mathworld.wolfram.com/Stern-BrocotTree.html
*
* This algorithm uses a lot of stack space (about 12000 frames). You probably need to use a JVM option like "-Xss4M".
*/
static public String run(){
return Integer.toString(sternBrocotCount(1, 3, 1, 2));

}
// Counts the number of reduced fractions n/d such that leftN/leftD < n/d < rightN/rightD and d <= 12000.
// leftN/leftD and rightN/rightD must be adjacent in the Stern-Brocot tree at some point in the generation process.
private static int sternBrocotCount(int leftN, int leftD, int rightN, int rightD) {
int n = leftN + rightN;
int d = leftD + rightD;
if (d > 12000)
return 0;
else
return 1 + sternBrocotCount(leftN, leftD, n, d) + sternBrocotCount(n, d, rightN, rightD);
}
}
7295372
154ms