Last active
February 17, 2016 06:02
-
-
Save johncip/90ffe2370e505fb939b3 to your computer and use it in GitHub Desktop.
Count on Cantor
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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