|
|
Here is an interesting sequence I discovered the other day:
S(0) = 0.
S(2n) = n+1, for n > 0.
S(2n+1) = 1/S(2n).
Or, equivalently:
S(0) = 0.
S(n even) = n/2 + 1, for n > 0.
S(n odd) = 1/S(n-1).
The interesting thing about this sequence is that it maps the
naturals to the rationals. In other words, it is a bijection
S(n in N) <-> p/q in Q, from all the naturals n in N to all the
rationals p/q in Q.
It is similar to Cantor's diagonal mapping of the rationals, but
is simpler because it maps each natural to a unique rational p/q,
where p and q are relatively prime, i.e., there are no duplicate
rationals (such as 2/4, 3/6, 4/8, etc.) produced by the mapping.
Cantor's denumeration of the rationals proceeds in an orderly
diagonal fashion, as shown in this image:
http://david.tribble.com/img/MapNtoQ1.png
Sequence S(n) proceeds in a less obvious fashion, as shown here:
http://david.tribble.com/img/MapNtoQ.png
The progression is symmetric about the p=q axis, because each
odd term S(2n+1) is the inverse of the preceding even term S(2n).
This image shows the progression of only the odd terms:
http://david.tribble.com/img/MapNtoQ2.png
The inverse mapping is:
invS(0) = 0.
invS(1) = invS(p/p) = 1.
invS(p) = invS(p/1) = 2^(p-1).
invS(p/q) = 2 invS(p/q - 1), for p > q.
invS(p/q) = 1 + invS(q/p), for p < q.
The inverse function handles rationals in non-reduced form
(e.g., 2/4, 12/18, 15/25, etc.), mapping them to their equivalent
reduced form (p/q, where p and q are relatively prime). This works
because evaluating invS(pk/qk) winds up with a term of invS(k/k)
in the recursive evaluation, which is simply 1.
The inverse function makes it apparent that every rational of
the form p/1 (i.e., every natural) is mapped to each natural
that is a power of 2, i.e., p = S(2^(p-1)).
The first 100 terms of S(n):
0. 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
Though I discovered this little sequence independently, I was
most certainly not the first to find it, since it's such a
simple sequence. A brief Google search turned up these links,
showing that Kepler played with a similar sequence, treating
it as a binary tree and attempting to relate it to the cosmic
harmonies:
http://ndirty.cute.fi/~karttu/Kepler/a086592.htm
http://www.research.att.com/~njas/sequences/?q=id:A020651
http://www.research.att.com/~njas/sequences/?q=id:A020650
http://www.research.att.com/~njas/sequences/?q=id:A086592
I wrote a little Java program to generate the sequence:
http://david.tribble.com/src/java/tribble/math/misc/MapNtoQ.java
-drt
|
|
