128 lines
3.3 KiB
Java
128 lines
3.3 KiB
Java
import java.util.ArrayDeque;
|
|
import java.util.Deque;
|
|
|
|
public final class CalkinWilfSequence {
|
|
|
|
public static void main(String[] aArgs) {
|
|
Rational term = Rational.ONE;
|
|
System.out.println("First 20 terms of the Calkin-Wilf sequence are:");
|
|
for ( int i = 1; i <= 20; i++ ) {
|
|
System.out.println(String.format("%2d", i) + ": " + term);
|
|
term = nextCalkinWilf(term);
|
|
}
|
|
System.out.println();
|
|
|
|
Rational rational = new Rational(83_116, 51_639);
|
|
System.out.println(" " + rational + " is the " + termIndex(rational) + "th term of the sequence.");
|
|
|
|
}
|
|
|
|
private static Rational nextCalkinWilf(Rational aTerm) {
|
|
Rational divisor = Rational.TWO.multiply(aTerm.floor()).add(Rational.ONE).subtract(aTerm);
|
|
return Rational.ONE.divide(divisor);
|
|
}
|
|
|
|
private static long termIndex(Rational aRational) {
|
|
long result = 0;
|
|
long binaryDigit = 1;
|
|
long power = 0;
|
|
for ( long term : continuedFraction(aRational) ) {
|
|
for ( long i = 0; i < term; power++, i++ ) {
|
|
result |= ( binaryDigit << power );
|
|
}
|
|
binaryDigit = ( binaryDigit == 0 ) ? 1 : 0;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
private static Deque<Long> continuedFraction(Rational aRational) {
|
|
long numerator = aRational.numerator();
|
|
long denominator = aRational.denominator();
|
|
Deque<Long> result = new ArrayDeque<Long>();
|
|
|
|
while ( numerator != 1 ) {
|
|
result.addLast(numerator / denominator);
|
|
long copyNumerator = numerator;
|
|
numerator = denominator;
|
|
denominator = copyNumerator % denominator;
|
|
}
|
|
|
|
if ( ! result.isEmpty() && result.size() % 2 == 0 ) {
|
|
final long back = result.removeLast();
|
|
result.addLast(back - 1);
|
|
result.addLast(1L);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
}
|
|
|
|
final class Rational {
|
|
|
|
public Rational(long aNumerator, long aDenominator) {
|
|
if ( aDenominator == 0 ) {
|
|
throw new ArithmeticException("Denominator cannot be zero");
|
|
}
|
|
if ( aNumerator == 0 ) {
|
|
aDenominator = 1;
|
|
}
|
|
if ( aDenominator < 0 ) {
|
|
numer = -aNumerator;
|
|
denom = -aDenominator;
|
|
} else {
|
|
numer = aNumerator;
|
|
denom = aDenominator;
|
|
}
|
|
final long gcd = gcd(numer, denom);
|
|
numer = numer / gcd;
|
|
denom = denom / gcd;
|
|
}
|
|
|
|
public Rational add(Rational aOther) {
|
|
return new Rational(numer * aOther.denom + aOther.numer * denom, denom * aOther.denom);
|
|
}
|
|
|
|
public Rational subtract(Rational aOther) {
|
|
return new Rational(numer * aOther.denom - aOther.numer * denom, denom * aOther.denom);
|
|
}
|
|
|
|
public Rational multiply(Rational aOther) {
|
|
return new Rational(numer * aOther.numer, denom * aOther.denom);
|
|
}
|
|
|
|
public Rational divide(Rational aOther) {
|
|
return new Rational(numer * aOther.denom, denom * aOther.numer);
|
|
}
|
|
|
|
public Rational floor() {
|
|
return new Rational(numer / denom, 1);
|
|
}
|
|
|
|
public long numerator() {
|
|
return numer;
|
|
}
|
|
|
|
public long denominator() {
|
|
return denom;
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
return numer + "/" + denom;
|
|
}
|
|
|
|
public static final Rational ONE = new Rational(1, 1);
|
|
public static final Rational TWO = new Rational(2, 1);
|
|
|
|
private long gcd(long aOne, long aTwo) {
|
|
if ( aTwo == 0 ) {
|
|
return aOne;
|
|
}
|
|
return gcd(aTwo, aOne % aTwo);
|
|
}
|
|
|
|
private long numer;
|
|
private long denom;
|
|
|
|
}
|