//============================================================================== // MapNtoQ.java //============================================================================== package tribble.math.misc; // System imports import java.lang.Exception; import java.lang.Integer; import java.lang.Long; import java.lang.String; import java.lang.System; /******************************************************************************* * Generates a sequence of rational numbers. * 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.
* * * * * @version $Revision: 1.1 $ $Date: 2006/04/06 00:42:16 $ * @since 2006-04-05 * @author David R. Tribble * (david@tribble.com) */ public class MapNtoQ { static final String REV = "@(#)tribble/math/misc/MapNtoQ.java $Revision: 1.1 $ $Date: 2006/04/06 00:42:16 $\n"; /*************************************************************************** * Generate a sequence of S(n) numbers. * *

* Usage *

* java MapNtoQ [[first_n] last_n] * * @since 1.1, 2006-04-05 */ public static void main(String[] args) throws Exception { long first = 0; long last = 32*1024; // Parse args if (args.length > 0) last = Long.parseLong(args[0]); if (args.length > 1) { first = last; last = Long.parseLong(args[1]); } if (first < 0) first = 0; // Generate a S(n) sequence for (long n = first; n <= last; n++) { int[] r; r = seq(n); System.out.println(n + ". " + ratioToString(r) + " = S(" + invseq(r) + ")"); } } static int[] seq(long n) { int[] r; if (n <= 1) { // S(1) = 1/1 = 1 r = new int[2]; r[0] = (n < 1 ? 0 : 1); r[1] = 1; } else if ((n & 1) == 0) { // S(n even) = S(2k) = S(k)+1 = S(n/2)+1 r = seq(n/2); r[0] = r[0] + r[1]; r[1] = r[1]; } else { int tmp; // S(n odd) = S(2k+1) = 1/(S(k)+1) = 1/S(n-1) r = seq(n-1); tmp = r[0]; r[0] = r[1]; r[1] = tmp; } return (r); } static long invseq(int[] r) { if (r[0] == 0) return 0; else if (r[0] == r[1]) return (1); else if (r[0] < r[1]) { int[] a; // invS(p/q) = invS(q/p)+1, for p < q a = new int[2]; a[0] = r[1]; a[1] = r[0]; return (invseq(a) + 1); } else // (r[0] > r[1]) { int[] a; // invS(p/q) = 2 invS(p/q-1), for p > q a = new int[2]; a[0] = r[0] - r[1]; a[1] = r[1]; return (2 * invseq(a)); } } static String ratioToString(int[] r) { if (r[1] == 1) return (r[0] + ""); else return (r[0] + "/" + r[1]); } } // End MapNtoQ.java