Pell.java


Below is the syntax highlighted version of Pell.java from §5.5 Intractability.


/******************************************************************************
 *  Compilation:  javac Cube.java
 *  Execution:    java Cube
 *  
 *  Searches for an integer solution to x^2 - cy^2 = 1
 *  It is known that for any positive integer c that is not itself
 *  a perfect square, there are infinitely many integral solutions (x, y).
 *
 *
 *  % java Pell 59
 *  x = 530, y = 69
 *
 *  % java Pell 60
 *  x = 31, y = 4
 *
 *  % java Pell 61
 *  x = 1766319049, y = 226153980
 *
 *  % java Pell 62
 *  x = 63, y = 8
 *
 *  % java Pell 63
 *  x = 8, y = 1
 *
 *  % java Pell 64
 *  [ infinite loop ]
 *
 ******************************************************************************/

public class Pell { 

    public static void main(String[] args) { 
        long c = Long.parseLong(args[0]);

        boolean done = false;
        long x = 1;
        long y = 1;
        while (!done) {
            long diff = x*x - c*y*y;
            if      (diff == 1) done = true;
            else if (diff >  1) y++;
            else                x++;
        }
        StdOut.println("x = "+ x + ", y = " + y);
    }

}


Copyright © 2000–2017, Robert Sedgewick and Kevin Wayne.
Last updated: Fri Oct 20 14:12:12 EDT 2017.