Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

tribble.math.misc
Class RationalsNtoQ

java.lang.Object
  extended by tribble.math.misc.RationalsNtoQ

public class RationalsNtoQ
extends java.lang.Object

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

Since:
2010-06-05
Version:
$Revision: 1.1 $ $Date: 2010/06/05 22:40:59 $
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.

Constructor Summary
RationalsNtoQ()
           
 
Method Summary
static java.math.BigInteger invseq(java.math.BigInteger p, java.math.BigInteger q)
          Find the natural n = S−1(p/q) that a given rational p/q maps to.
static void main(java.lang.String[] args)
          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.
static java.math.BigInteger[] seq(java.math.BigInteger n)
          Find the rational S(n) = p/q that a given natural n maps to.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

RationalsNtoQ

public RationalsNtoQ()
Method Detail

main

public static void main(java.lang.String[] args)
                 throws java.lang.Exception
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.

Throws:
java.lang.Exception
Since:
1.1, 2010-06-05

seq

public static java.math.BigInteger[] seq(java.math.BigInteger n)
Find the rational S(n) = p/q that a given natural n maps to.

Parameters:
n - A natural (positive integer).
Returns:
An array r containing a rational p/q, where r[0] = p, and r[1] = q.
Since:
1.1, 2010-06-05

invseq

public static java.math.BigInteger invseq(java.math.BigInteger p,
                                          java.math.BigInteger q)
Find the natural n = S−1(p/q) that a given rational p/q maps to.

Parameters:
p - A natural, the numerator p of the rational.
q - A natural, the denominator q of the rational.
Since:
1.1, 2010-06-05
Overview  Package   Class  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD