### Fractions involving the number of different ways a number can be expressed as a sum of powers of 2题号：175 难度： 70 中英对照

Define f(0)=1 and f(n) to be the number of ways to write n as a sum of powers of 2 where no power occurs more than twice.

For example, f(10)=5 since there are five different ways to express 10:
10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1

It can be shown that for every fraction p/q (p>0, q>0) there exists at least one integer n such that
f(n)/f(n-1)=p/q.

For instance, the smallest n for which f(n)/f(n-1)=13/17 is 241.
The binary expansion of 241 is 11110001.
Reading this binary number from the most significant bit to the least significant bit there are 4 one's, 3 zeroes and 1 one. We shall call the string 4,3,1 the Shortened Binary Expansion of 241.

Find the Shortened Binary Expansion of the smallest n for which
f(n)/f(n-1)=123456789/987654321.

### Code

import java.math.BigInteger;

public final class p175 {
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() {
// if n is odd
//   f(n)=f(n/2) < f(n-1)=f(n/2)+f(n/2-1)
// if n is even
//   f(n)=f(n/2)+f(n/2-1) > f(n-1)=f(n/2-1)
// that means:
// if q>p then n is odd  and p/q=f(n)/f(n-1) => p/(q-p)=f(n/2)/f(n/2-1)
// if q<p then n is even and p/q=f(n)/f(n-1) => (p-q)/q=f(n/2)/f(n/2-1)
// if and only if p=q=1 then n=1
final long a=123456789,b=987654321;
String res=solve(a,b);
res=res.substring(0,res.length()-1);
return res;
}

static String solve(long a,long b){
long c=gcd(a,b);
a/=c;b/=c;
String res;
if(a==1&&b==1) res="1";
else{
long r=0,newa,newb;
if(a<b){
newa=a;
newb=b%a;
r=b/a;//r个1
if(newb==0){
newb=1;
r--;
}
}
else{
newa=a%b;
newb=b;
r=a/b;//r个0
if(newa==0){
newa=1;
r--;
}
}
res=solve(newa,newb)+r;
}
return  res+",";
}

public static long gcd(long x, long y) {
while (y != 0) {
long z = x % y;
x = y;
y = z;
}
return x;
}
static long get(long n){
BigInteger bi=BigInteger.valueOf(n);
long a = 1;
long b = 0;
for (int i = bi.bitLength()-1; i >=0; i--) {
if (bi.testBit(i)){
b += a;
}
else{
a += b;
}
}
return a;
}
}
1,13717420,8
0ms