//============================================================================== // RationalsNtoQ.java //============================================================================== package tribble.math.misc; import java.lang.Exception; import java.lang.Integer; import java.lang.Long; import java.lang.NumberFormatException; import java.lang.String; import java.lang.System; import java.math.BigInteger; /******************************************************************************* * A mathematical mapping of the naturals (N) to the rationals (Q). * *

* Sequence S(n) is defined as: * 

*    S(0) =    0
*    S(2n) =   S(n)+1, for n > 0
*    S(2n+1) = 1/S(n)+1 = 1/S(2n)
* *

* Sequence S(n) maps every natural number to every rational number. * In other words, S(n) is a bijection between all * n > 0 in N * to all r = p/q * in Q. * * *

* A partial list of S(n):
* *     0. 0/1 = 0 *    20. 7/3     *    40. 10/3     *    60. 13/5     *    80. 13/3
*     1. 1/1 = 1 *    21. 3/7     *    41. 3/10     *    61. 5/13     *    81. 3/13
*     2. 2/1 = 2 *    22. 7/4     *    42. 10/7     *    62. 13/8     *    82. 13/10
*     3. 1/2     *    23. 4/7     *    43. 7/10     *    63. 8/13     *    83. 10/13
*     4. 3/1 = 3 *    24. 7/2     *    44. 11/4     *    64. 7/1  = 7 *    84. 17/7
*     5. 1/3     *    25. 2/7     *    45. 4/11     *    65. 1/7      *    85. 7/17
*     6. 3/2     *    26. 7/5     *    46. 11/7     *    66. 7/6      *    86. 17/10
*     7. 2/3     *    27. 5/7     *    47. 7/11     *    67. 6/7      *    87. 10/17
*     8. 4/1 = 4 *    28. 8/3     *    48. 9/2      *    68. 11/5     *    88. 15/4
*     9. 1/4     *    29. 3/8     *    49. 2/9      *    69. 5/11     *    89. 4/15
*    10. 4/3     *    30. 8/5     *    50. 9/7      *    70. 11/6     *    90. 15/11
*    11. 3/4     *    31. 5/8     *    51. 7/9      *    71. 6/11     *    91. 11/15
*    12. 5/2     *    32. 6/1 = 6 *    52. 12/5     *    72. 13/4     *    92. 18/7
*    13. 2/5     *    33. 1/6     *    53. 5/12     *    73. 4/13     *    93. 7/18
*    14. 5/3     *    34. 6/5     *    54. 12/7     *    74. 13/9     *    94. 18/11
*    15. 3/5     *    35. 5/6     *    55. 7/12     *    75. 9/13     *    95. 11/18
*    16. 5/1 = 5 *    36. 9/4     *    56. 11/3     *    76. 14/5     *    96. 11/2
*    17. 1/5     *    37. 4/9     *    57. 3/11     *    77. 5/14     *    97. 2/11
*    18. 5/4     *    38. 9/5     *    58. 11/8     *    78. 14/9     *    98. 11/9
*    19. 4/5     *    39. 5/9     *    59. 8/11     *    79. 9/14     *    99. 9/11
* * * *

* Some relations derived for S(n):
* *    r1. S(n) for even n > 1 * = S(n/2)+1.
*    r2. S(n) for odd  n > 1 * = 1/S(n−1).
*    r3. S(2k) * = k+1, for k >= 0.
*    r4. S(n) = p/q, * p > q for all even n > 0.
*    r5. S(n) = p/q, * p < q for all odd n.
* * * *

* Some inverse relations for S(n):
* *    i1. * S−1(0) = 0.
*    i2. * S−1(1) * = S−1(p/p) = 1, * for p > 0.
*    i3. * S−1(p) * = S−1(p/1) * = 2p−1, for p > 0.
*    i4. * S−1(p/q) * = 2S−1(p/q −1), * if p > q.
*    i5. * S−1(p/q) * = S−1(q/p) + 1, * if p < q.
* * * *

* Acknowledgments *

* This program was taken from a sequence that was re-discovered independently * by David R. Tribble circa Oct 2006.
* See also: *

* * *

*

*
Source code:
*
Available at: * http://david.tribble.com/src/java/tribble/math/misc/RationalsNtoQ.java *
*
Documentation:
*
Available at: * http://david.tribble.com/docs/tribble/math/misc/RationalsNtoQ.html *
*
* * * @version $Revision: 1.1 $ $Date: 2010/06/05 22:40:59 $ * @since 2010-06-05 * @author David R. Tribble (david@tribble.com) *
* Copyright ©2010 by David R. Tribble, all rights reserved.
* Permission is granted to any person or entity except those designated by * by the United States Department of State as a terrorist, or terrorist * government or agency, to use and distribute this source code provided * that the original copyright notice remains present and unaltered. */ public class RationalsNtoQ { static final String REV = "@(#)tribble/math/misc/RationalsNtoQ.java $Revision: 1.1 $ $Date: 2010/06/05 22:40:59 $\n"; // ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ // Static variables private static boolean verbose = false; // ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ // Static methods /*************************************************************************** * Use a mathematical sequence mapping the naturals (N) to the * rationals (Q) to print a mapping for a single natural, or a mapping * for a single rational, or to print an entire subsequence of rationals. * *

* Usage *

* java RationalsNtoQ [-v] p/q
* java RationalsNtoQ [-v] p / q
* java RationalsNtoQ [-v] n
* java RationalsNtoQ * [-v] n1 [n2] * *

* Specifying a single natural (unsigned integer) n produces the * rational mapping of S(n). * *

* Specifying a single rational p/q as two unsigned integers * separated by a fraction slash (/) produces the natural mapping of * S−1(p/q). * The rational can also be specified as three separate arguments: * p, '/', and q. * *

* Specifying two naturals n1 and n2 * produces the rational mapping subsequence of S(n1) * through S(n2). * *

* The -v (verbose) option causes the intermediate sequence values * to be printed as the final sequence value is calculated. * * @since 1.1, 2010-06-05 */ public static void main(String[] args) throws Exception { try { BigInteger a1; BigInteger a2; int i = 0; // Parse the command line options if (args.length >= i+1 && args[i].equals("-v")) { i++; verbose = true; } // Parse the command line args if (args.length >= i+3 && args[i+1].equals("/")) { // Parse rational: 'p' '/' 'q' a1 = new BigInteger(args[i+0]); if (a1.compareTo(BigInteger.ZERO) < 0) throw new NumberFormatException(); a2 = new BigInteger(args[i+2]); if (a2.compareTo(BigInteger.ZERO) <= 0) throw new NumberFormatException(); mapQtoN(a1, a2); } else if (args.length >= i+2) { // Parse range: 'n1' 'n2' a1 = new BigInteger(args[i+0]); if (a1.compareTo(BigInteger.ZERO) < 0) throw new NumberFormatException(); a2 = new BigInteger(args[i+1]); if (a2.compareTo(BigInteger.ZERO) < 0) throw new NumberFormatException(); listNtoQ(a1, a2); } else if (args.length >= i+1) { int p; p = args[i].indexOf('/'); if (p > 0) { // Parse rational: 'p/q' a1 = new BigInteger(args[i].substring(0, p)); if (a1.compareTo(BigInteger.ZERO) < 0) throw new NumberFormatException(); a2 = new BigInteger(args[i].substring(p+1)); if (a2.compareTo(BigInteger.ZERO) <= 0) throw new NumberFormatException(); mapQtoN(a1, a2); } else { // Parse natural: 'n' a1 = new BigInteger(args[i]); if (a1.compareTo(BigInteger.ZERO) < 0) throw new NumberFormatException(); mapNtoQ(a1); } } else { // Display a program usage message System.out.println("Mathematical mapping of the naturals (N) " + "to the rationals (Q)."); System.out.println(); System.out.println("usage: java " + RationalsNtoQ.class.getName() + " [-v] n"); System.out.println("usage: java " + RationalsNtoQ.class.getName() + " [-v] n1 n2"); System.out.println("usage: java " + RationalsNtoQ.class.getName() + " [-v] p/q"); System.out.println("usage: java " + RationalsNtoQ.class.getName() + " [-v] p / q"); System.out.println(); System.out.println("Options:"); System.out.println(" -v Verbose output"); System.out.println(); System.out.println("Specifying a single natural (unsigned " + "integer) 'n' produces the rational mapping"); System.out.println("of S(n)."); System.out.println(); System.out.println("Specifying a single rational 'p/q' as two " + "unsigned integers separated by a"); System.out.println("fraction slash ('/') produces the natural " + "mapping of iS(p/q). The rational can"); System.out.println("also be specified as three separate " + "arguments: 'p', '/', and 'q'."); System.out.println(); System.out.println("Specifying two naturals 'n1' and 'n2' " + "produces the rational mapping subsequence"); System.out.println("of S(n1) through S(n2)."); System.out.println(); System.out.println("The '-v' (verbose) option causes the " + "intermediate sequence values to be printed"); System.out.println("as the final sequence value is " + "calculated."); // Punt System.exit(255); } } catch (NumberFormatException ex) { System.out.println("*** Bad number format"); throw ex; } } /*************************************************************************** * Print the rational S(n) = p/q that a given natural * n maps to. * * @param n * A natural (positive integer). * * @since 1.1, 2010-06-05 */ private static void mapNtoQ(BigInteger n) throws Exception { BigInteger[] r; // Print n System.out.print("N: "); System.out.println(n.toString()); // Print p/q = S(n) r = seq(n); System.out.print("Q: "); System.out.print(r[0].toString()); System.out.print(" / "); System.out.println(r[1].toString()); } /*************************************************************************** * Print the sequence of rationals S(n1) to * S(n2). * * @param n1 * A natural (positive integer). * * @param n2 * A natural (positive integer). * * @since 1.1, 2010-06-05 */ private static void listNtoQ(BigInteger n1, BigInteger n2) throws Exception { // Print n1 and n2 System.out.print("N1: "); System.out.println(n1.toString()); System.out.print("N2: "); System.out.println(n2.toString()); // Print S(n1) to S(n2) while (n1.compareTo(n2) <= 0) { BigInteger[] r; // Print ni System.out.print("S("); System.out.print(n1.toString()); System.out.print(") = "); // Print S(ni) r = seq(n1); System.out.print(r[0].toString()); if (r[1] != BigInteger.ONE && r[1].compareTo(BigInteger.ONE) != 0) { System.out.print("/"); System.out.print(r[1].toString()); } System.out.println(); // Increment n1 n1 = n1.add(BigInteger.ONE); } } /*************************************************************************** * Print the natural n = * S−1(p/q) that a given * rational p/q maps to. * * @param p * A natural, the numerator p of the rational. * * @param q * A natural, the denominator q of the rational. * * @since 1.1, 2010-06-05 */ private static void mapQtoN(BigInteger p, BigInteger q) throws Exception { BigInteger n; // Print p/q System.out.print("Q: "); System.out.print(p.toString()); System.out.print(" / "); System.out.print(q.toString()); System.out.println(); // Print n = iS(p/q) n = invseq(p, q); System.out.print("N: "); System.out.println(n.toString()); } /*************************************************************************** * Find the rational S(n) = p/q * that a given natural n maps to. * * @param n * A natural (positive integer). * * @return * An array r containing a rational p/q, where * r[0] = p, and * r[1] = q. * * @since 1.1, 2010-06-05 */ public static BigInteger[] seq(BigInteger n) { BigInteger[] r; if (n.compareTo(BigInteger.ZERO) == 0) { // n = 0: S(0) = 0/1 = 0 r = new BigInteger[2]; r[0] = BigInteger.ZERO; r[1] = BigInteger.ONE; } else if (n.compareTo(BigInteger.ONE) == 0) { // n = 1: S(1) = 1/1 = 1 r = new BigInteger[2]; r[0] = BigInteger.ONE; r[1] = BigInteger.ONE; } else if (n.getLowestSetBit() == 0) { BigInteger tmp; // n is odd: S(n odd) = S(2k+1) = 1/(S(k)+1) = 1/S(n-1) r = seq(n.subtract(BigInteger.ONE)); tmp = r[0]; r[0] = r[1]; r[1] = tmp; } else { // n is even: S(n even) = S(2k) = S(k)+1 = S(n/2)+1 r = seq(n.shiftRight(1)); r[0] = r[0].add(r[1]); } if (verbose) System.out.println(" S(" + n.toString() + "): " + r[0].toString() + "/" + r[1].toString()); return (r); } /*************************************************************************** * Find the natural n = * S−1(p/q) that a given * rational p/q maps to. * * @param p * A natural, the numerator p of the rational. * * @param q * A natural, the denominator q of the rational. * * @since 1.1, 2010-06-05 */ public static BigInteger invseq(BigInteger p, BigInteger q) { BigInteger n; if (p.compareTo(BigInteger.ZERO) == 0) { // iS(0) = 0 n = BigInteger.ZERO; } else if (p.compareTo(q) == 0) { // iS(1) = 1 n = BigInteger.ONE; } else if (p.compareTo(q) < 0) { // p < q: iS(p/q) = iS(q/p) + 1 n = invseq(q, p).add(BigInteger.ONE); } else // (p > q) { // p > q: iS(p/q) = 2 iS(p/q - 1) = 2 iS((p-q)/q) n = invseq(p.subtract(q), q).shiftLeft(1); } if (verbose) System.out.println(" iS(" + p.toString() + "/" + q.toString() + "): " + n.toString()); return n; } } // End RationalsNtoQ.java