Skip to content

Instantly share code, notes, and snippets.

@johncip
Last active February 17, 2016 06:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save johncip/90ffe2370e505fb939b3 to your computer and use it in GitHub Desktop.
Save johncip/90ffe2370e505fb939b3 to your computer and use it in GitHub Desktop.
Count on Cantor
/*
* 264 - Count on Cantor
*
* Given an input value N, print the Nth term in Cantor's enumeration.
*
* There may be a simpler closed form of this. However, what strikes me as
* possible right now is: we figure out what diagonal n is on, which gives us
* the beginning of that diagonal (1/2, 3/1, 1/4, 5/1, etc.). Then, we adjust
* the numerator and denominator based on the distance from the first term in
* the diagonal and the direction it takes (up-right for odd, down-left for
* even).
*
* To figure out which diagonal it is on, we could precompute the triangular
* numbers, but the triangular number function (over the reals) has an inverse.
* We can just use that and take the ceiling.
*
*/
import java.util.Scanner;
public class Main {
/**
* Entry point. For each input number n, prints the nth term in Cantor's
* sequence.
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String fmt = "TERM %d is %s\n";
while (in.hasNextInt()) {
long n = in.nextInt();
System.out.format(fmt, n, cantorTerm(n));
}
in.close();
}
/**
* Returns which diagonal n is on.
*
* It is the ceiling of the inverse triangular number function.
*/
static long diagonal(long n) {
double it = (-1 + Math.sqrt(1 + 8 * n)) / 2.0;
return (long) Math.ceil(it);
}
/**
* Returns the distance along the diagonal.
*
* It is the difference between n and (one plus the next smallest triangular
* number).
*/
static long distance(long n) {
long diag = diagonal(n);
long start = 1 + (diag * (diag - 1)) / 2;
return n - start;
}
/**
* Returns the nth term in Cantor's sequence.
*/
static String cantorTerm(long n) {
long inv = diagonal(n);
long dist = distance(n);
long den, num;
if (inv % 2 == 0) {
// even rows: numerators start small
num = 1 + dist;
den = inv - dist;
} else {
// odd rows: numerators start big
num = inv - dist;
den = 1 + dist;
}
return num + "/" + den;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment