[math-fun] An alternative way to count the rationals?
JZucker> Well, the Calkin-Wilf tree is still the best, of course. Thank you, Joshua! I had somehow lived in total ignorance of Newman's amazing, useful, and tiny invention: NestList[1/(2*Floor[#] - # + 1) &, 0, 69] 1 1 3 2 1 4 3 5 2 5 3 1 5 4 7 {0, 1, -, 2, -, -, -, 3, -, -, -, -, -, -, -, 4, -, -, -, -, 2 3 2 3 4 3 5 2 5 3 4 5 4 7 3 3 8 5 7 2 7 5 8 3 7 4 1 6 5 9 4 11 -, -, -, -, -, -, -, -, -, -, -, 5, -, -, -, -, --, --, 8 5 7 2 7 5 8 3 7 4 5 6 5 9 4 11 7 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 --, --, --, --, --, --, --, --, -, -, -, -, --, --, --, 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 13 8 11 3 10 7 11 4 9 5 1 7 6 11 5 --, --, --, --, --, --, --, -, -, -, 6, -, -, --, --, --, ...} 8 11 3 10 7 11 4 9 5 6 7 6 11 5 14 (http://oeis.org/A002487). Julian derived the reverse sequence: NestList[2*Ceiling[1/#] - 1 - 1/# &, 14/9, 9] 14 5 11 6 7 1 5 9 4 {--, --, --, --, -, -, 6, -, -, -} 9 14 5 11 6 7 6 5 9 and found the waiting time from 355/113 to 0 was 67107848. I.e., intermediate swell was >>355. But the real surprise came with plotting the forward sequence starting with Sqrt[-1] in a neighborhood of the origin--the Ford Pinto circles <http:gosper.org/fordpinto.png>! (Complete with some particulate emissions.) (Using Mma's convention: Floor[z]==Floor[Re[z]]+I*Floor[Im[z]].) The reverse sequence plots the left half (mirror image). --rwg rwg> Duh, the original argument was < -1, so the z/(z-1) transformation gives a single, convergent series: 10 3 1/12 1/12 13 1 5 2 3 5 sqrt(6) 17 23 hyper_2f1(--, --, -, --------) = --------------------- 24 24 6 2 2 1/6 17 23 3125 Duh, all you need is z<1/2.
Thank you, Joshua! I had somehow lived in total ignorance of Newman's amazing, useful, and tiny invention: NestList[1/(2*Floor[#] - # + 1) &, 0, 69]
--Golly, this is amazing. http://oeis.org/A002487 explains, the sequence there is a(0,1,2,3,...) = 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8... Rewriting the recurrence I find a(n+2) = 2*a(n+1)*Floor(a(n)/a(n+1)) + a(n+1) - a(n) for example 7 = 2*4*Floor(5/4) + 4 - 5 = 8+4-5 and 8 = 2*3*Floor(7/3) + 3 - 7 = 12+3-7. They give another recurrence a(2*n) = a(n); a(2*n+1) = a(n)+a(n+1). OEIS claims that L.Carlitz 1964 showed a(n+1) = number of odd binomial(n-k,k) with 0<=k<n/2, but this is just false. Trying to rediscover what the hell this actually should have said, I compute Pascal triangle mod 2: 1 11 101 1111 10001 110011 1010101 11111111 and as Javier Torres pointed out the sums of 45 degree upward-right diagonals are 1,1,2,1,3,2,3,1... so that a(n+1) = sum( binomial(n-k, k) mod 2, k=0..floor(n/2) ) Which shows the following interesting massive bug in MAPLE 9: f := (n) -> sum( binomial(n-k, k) mod 2, k=0..floor(n/2) ); f(34); 9227465 Say WHAT??!! Hence 0 <= a(n) <= (n+1)/2 and it is never 0 after the start.
OEIS claims also a(n+1) = number of ways of writing n as a sum of powers of 2, each power being used at most twice (the number of hyperbinary representations of n) [Carlitz; Lind] If so, it seems to me this yields a fast algorithm for evaluating a(n), "fast" meaning in O(log(n)) steps: You keep incrementing k, the maximum power of 2, each time keeping track of the #reps of m=(n modulo 2^(k+1)) and of m+2^(k+1). That's only two counts to keep track of. This algorithm enables us to say what is the nth rational number in O(log(n)) steps. Question: is there any fast way to go in the other direction: given a rational, what is its position in the order?
On Sun, Nov 6, 2011 at 6:28 PM, Warren Smith <warren.wds@gmail.com> wrote:
Question: is there any fast way to go in the other direction: given a rational, what is its position in the order?
Yes, Euclidean algorithm gets you the result in a short time as well. The quotients you encounter there tell you how many times you have to take the left or right branch as you're navigating the tree, i.e., the binary representation of your position in the order. I think my favorite discovery that results from all this is the inverse function of the number of hyperbinary representations: that is, it gives a fast way to determine all EulerPhi[1000] even numbers that have 1000 hyperbinary representations. (Of course there are then infinitely many odd numbers that also have the same 1000 representations, because a(2n+1) = a(n).) I have a paper (coauthored by one of my now eighth-grade tutors and myself, based on some of our work and in collaboration with Brent Yorgey of http://mathlesstraveled.com/2009/10/18/the-hyperbinary-sequence-and-the-calk... ... we plan to submit to Math Horizons, I think, since there's not much original in it other than the method of presentation. Most of what's in it can be found in Brent's series of posts on hyperbinary. --Joshua Zucker
On Sun, Nov 6, 2011 at 4:30 PM, Bill Gosper <billgosper@gmail.com> wrote:
JZucker>
Well, the Calkin-Wilf tree is still the best, of course.
Thank you, Joshua! I had somehow lived in total ignorance of Newman's amazing, useful, and tiny invention: NestList[1/(2*Floor[#] - # + 1) &, 0, 69]
1 1 3 2 1 4 3 5 2 5 3 1 5 4 7 {0, 1, -, 2, -, -, -, 3, -, -, -, -, -, -, -, 4, -, -, -, -, 2 3 2 3 4 3 5 2 5 3 4 5 4 7 3
3 8 5 7 2 7 5 8 3 7 4 1 6 5 9 4 11 -, -, -, -, -, -, -, -, -, -, -, 5, -, -, -, -, --, --, 8 5 7 2 7 5 8 3 7 4 5 6 5 9 4 11 7
7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 --, --, --, --, --, --, --, --, -, -, -, -, --, --, --, 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13
13 8 11 3 10 7 11 4 9 5 1 7 6 11 5 --, --, --, --, --, --, --, -, -, -, 6, -, -, --, --, --, ...} 8 11 3 10 7 11 4 9 5 6 7 6 11 5 14
(http://oeis.org/A002487). Julian derived the reverse sequence: NestList[2*Ceiling[1/#] - 1 - 1/# &, 14/9, 9]
14 5 11 6 7 1 5 9 4 {--, --, --, --, -, -, 6, -, -, -} 9 14 5 11 6 7 6 5 9
and found the waiting time from 355/113 to 0 was 67107848. I.e., intermediate swell was >>355.
Following Josh's pointer http://mathlesstraveled.com/2009/10/18/the-hyperbinary-sequence-and-the-calk... In[1]:= alf[1] = 1; alf[x_ /; x < 1] := 2*alf[x/(1 - x)]; alf[x_] := 1 + 2*alf[x - 1] In[2]:= Timing[alf[355/113]] Out[2]= {0.000129, 67107847} As Yorgey says: Sweet. --rwg
But the real surprise came with plotting the forward sequence starting with Sqrt[-1] in a neighborhood of the origin--the Ford Pinto circles <http:gosper.org/fordpinto.png>! (Complete with some particulate emissions.) (Using Mma's convention: Floor[z]==Floor[Re[z]]+I*Floor[Im[z]].) The reverse sequence plots the left half (mirror image). --rwg rwg>
Duh, the original argument was < -1, so the z/(z-1) transformation gives a single, convergent series:
10 3 1/12 1/12 13 1 5 2 3 5 sqrt(6) 17 23 hyper_2f1(--, --, -, --------) = --------------------- 24 24 6 2 2 1/6 17 23 3125
Duh, all you need is z<1/2.
The explanation at http://mathlesstraveled.com/2009/10/18/the-hyperbinary-sequence-and-the-calk... of the "Calkin-Wilf [rooted binary] tree" makes it clear that this remarkable ordering of the rationals is simply from left to right within each level of the tree in a "raster scan." The root of the tree is 1/1 and the left child of a/b is a/(a+b) and the right child is (b+a)/b. That makes it easy to find the Nth rational number because we know the tree has 2^k nodes at level=k>=0 so we can in O(logN) steps walk down the tree to the right place. The "right place" is at level k where N is a (k+1)-bit positive integer and in the (N-2^k)th location (first location is "0") within that level. This is a simpler O(logN)-step algorithm than I described before: You simply walk k steps down the tree going right (1) or left (0) according to the bits in N's binary expansion (most-significant first) except that you ignore THE most significant bit of N since it always is 1. (Sorry to be playing catch-up here...) Now, let me return to the problem I had posed last post of answering the reverse problem -- given a rational number a/b, what is its number N? The tree-parent of a/b [assumed reduced so GCD(a,b)=1] is: a/(b-a) if b>a (a-b)/b if a>b has no parent (it is the tree-root) if a=b. This allows us also to walk UP the tree. So given a/b we reduce it using Euclidean GCD algorithm, then walk up the tree to the root. As we walk, each step we know whether that was a left-child (0) or right-child (1). These bits tell us the binary representation of N as described above. This algorithm runs in O(1+log(a+b)) steps. We now can do such fine things as compare two rationals a/b and c/d to decide which comes first in order, in O(1+log(a+b+c+d)) steps. As I noted before, the amazing sequence http://oeis.org/A002487 a(0,1,2,3,...) = 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8... which generates the nonnegative rationals 0/1, 1/1, 1/2, 2/1, 1/3, 3/2,... in Calkin-Wilf order obeys the non-Fibonacci recurrence a(n+2) = 2*a(n+1)*Floor(a(n)/a(n+1)) + a(n+1) - a(n) which trivially allows us to walk the rationals 1 step at a time in the forward direction. It also allows us to walk in the decreasing-n (backward) direction 1 step at a time in O(1) operations per step, although realizing that, is a bit trickier. [An "operation" x+y, x-y, or floor(x/y) is assumed to be O(1) "steps" in our model of computation...] Wikipedia https://secure.wikimedia.org/wikipedia/en/wiki/Stern–Brocot_tree says the "Stern Brocot" tree is related to the Calkin-Wilf tree by a bit-reversal permutation and explains the connection between the SB tree and the continued fraction expansion of a rational number. It also points out the SB tree is a valid binary search tree with the rational numbers (according to the usual real-number ordering)! https://secure.wikimedia.org/wikipedia/en/wiki/Calkin–Wilf_tree The "Minkowski question mark" function is a continuous analogue of the discrete Stern-Brocot tree which works with the real numbers instead of the integers... https://secure.wikimedia.org/wikipedia/en/wiki/Minkowski%27s_question_mark_f... http://mathworld.wolfram.com/MinkowskisQuestionMarkFunction.html And what, I wonder, is the fourier series expansion of ?(x)-x ? quite amazing stuff... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
The amazing integer sequence http://oeis.org/A002487 a(0,1,2,3,...) = 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8... which generates the nonnegative rationals 0/1, 1/1, 1/2, 2/1, 1/3, 3/2,... in Calkin-Wilf order via the recurrence a(n+2) = 2*a(n+1)*Floor(a(n)/a(n+1)) + a(n+1) - a(n) -- that sequence of rationals can be viewed as a pseudo-random number generator for the probability distribution ProbDensity(x) = 1/2 if 0<x<1, but = 1/(2*x*x) if x>1 here: http://mathworld.wolfram.com/UniformRatioDistribution.html But unlike the usual pseudo-random generators with finite period, this has infinite period. If only the rationals lying in (0,1) are taken, which is every other rational starting at 1/2 (i.e. discard the rationals>1), then we get a uniform01 pseudorandom number generator which only generates rationals, generates them all, and has "infinite period." You could combine it with finite-period pseudo-random generators to get a more-random infinite-period uniform01 generator. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On Sun, Nov 6, 2011 at 11:29 PM, Bill Gosper <billgosper@gmail.com> wrote:
On Sun, Nov 6, 2011 at 4:30 PM, Bill Gosper <billgosper@gmail.com> wrote:
JZucker>
Well, the Calkin-Wilf tree is still the best, of course.
Thank you, Joshua! I had somehow lived in total ignorance of Newman's amazing, useful, and tiny invention: NestList[1/(2*Floor[#] - # + 1) &, 0, 69]
1 1 3 2 1 4 3 5 2 5 3 1 5 4 7 {0, 1, -, 2, -, -, -, 3, -, -, -, -, -, -, -, 4, -, -, -, -, 2 3 2 3 4 3 5 2 5 3 4 5 4 7 3
3 8 5 7 2 7 5 8 3 7 4 1 6 5 9 4 11 -, -, -, -, -, -, -, -, -, -, -, 5, -, -, -, -, --, --, 8 5 7 2 7 5 8 3 7 4 5 6 5 9 4 11 7
7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 --, --, --, --, --, --, --, --, -, -, -, -, --, --, --, 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13
13 8 11 3 10 7 11 4 9 5 1 7 6 11 5 --, --, --, --, --, --, --, -, -, -, 6, -, -, --, --, --, ...} 8 11 3 10 7 11 4 9 5 6 7 6 11 5 14
(http://oeis.org/A002487). Julian derived the reverse sequence: NestList[2*Ceiling[1/#] - 1 - 1/# &, 14/9, 9]
14 5 11 6 7 1 5 9 4 {--, --, --, --, -, -, 6, -, -, -} 9 14 5 11 6 7 6 5 9
and found the waiting time from 355/113 to 0 was 67107848. I.e., intermediate swell was >>355.
Following Josh's pointer
http://mathlesstraveled.com/2009/10/18/the-hyperbinary-sequence-and-the-calk...
In[1]:= alf[1] = 1; alf[x_ /; x < 1] := 2*alf[x/(1 - x)]; alf[x_] := 1 + 2*alf[x - 1]
In[2]:= Timing[alf[355/113]]
Out[2]= {0.000129, 67107847}
As Yorgey says: Sweet. --rwg
Well, semisweet. This recursion mimics the subtractive Euclid process, with time proportional to the sum of the CF terms of x. Theoretically, the expected value of a CF term is infinite(!), so this is poor form. Practically, the length in bits of the answer will be > Sum(CF terms), so if you hit a huge term, you're screwed anyway. Nevertheless, even further speedup of alf is possible by rewriting it to take its argument as a continued fraction. Neil, by examining the binary values of alf, quickly produced a very fast version closely resembling this nonworking one, which he gave me by accident: FromDigits[Rest[Reverse[ Flatten[Table[Mod[i, 2], {i, 1, Length[#]}, {n, #[[i]]}]]]] &@ContinuedFraction[x],2] About 20 hrs later, I finally managed to debug an optimization of alf: ecf[{}] = 0; ecf[{L___, a_, 1}] = ecf[{L, a + 1}]; ecf[{0, 0, L___}] := ecf[{L}]; ecf[{x_}] := 2^x - 1; ecf[L_List] := 2^L[[1]]*(1 + 2^L[[2]]*ecf[Drop[L, 2]]) - 1 E.g., In[77]:= ecf[{3, 7, 16}] Out[77]= 67107847 Both this and Neil's (good one) are equivalent to the formula alf(x) = waiting time from 1= -1 + 2^L1 (1 + 2^L2 (-1 + ... (-1 + 2^Ln)))), n odd, -1 + 2^L1 (1 + 2^L2 (-1 + ... (1 + 2^(-1 + Ln)))), n even, where CF(x) = {L1,...Ln}. (I.e., decrement the last term if there are evenly many.) I guess people already knew this. --rwg But the real surprise came with plotting the forward sequence
starting with Sqrt[-1] in a neighborhood of the origin--the Ford Pinto circles <http:gosper.org/fordpinto.png>! (Complete with some particulate emissions.) (Using Mma's convention: Floor[z]==Floor[Re[z]]+I*Floor[Im[z]].) The reverse sequence plots the left half (mirror image). --rwg rwg>
At least one Yahoo user couldn't access this image. Try this?: http://gosper.org/fordpinto.png --rwg
This reminded me of a slightly related puzzle: Figure out the value of a Legendre symbol, using the continued fraction of the 'numerator' & 'denominator'. There must be some relationship, since the iteration for CF and Legendre symbol are so similar. Rich ----- Quoting Bill Gosper <billgosper@gmail.com>: <massively clipped>
Both this and Neil's (good one) are equivalent to the formula alf(x) = waiting time from 1= -1 + 2^L1 (1 + 2^L2 (-1 + ... (-1 + 2^Ln)))), n odd,
-1 + 2^L1 (1 + 2^L2 (-1 + ... (1 + 2^(-1 + Ln)))), n even,
where CF(x) = {L1,...Ln}.
BG>quickly produced a very fast version closely resembling this nonworking one, which he gave me by accident: Here's what I should have sent Bill: alf=FromDigits[ ReplacePart[ Reverse[Flatten[ Table[Mod[i, 2], {i, 1, Length[#1]}, {n, #1[[i]]}]]], 1 -> 1], 2] & --Neil On Thu, Nov 10, 2011 at 6:58 PM, Bill Gosper <billgosper@gmail.com> wrote:
On Sun, Nov 6, 2011 at 11:29 PM, Bill Gosper <billgosper@gmail.com> wrote:
On Sun, Nov 6, 2011 at 4:30 PM, Bill Gosper <billgosper@gmail.com> wrote:
JZucker>
Well, the Calkin-Wilf tree is still the best, of course.
Thank you, Joshua! I had somehow lived in total ignorance of Newman's amazing, useful, and tiny invention: NestList[1/(2*Floor[#] - # + 1) &, 0, 69]
1 1 3 2 1 4 3 5 2 5 3 1 5 4 7 {0, 1, -, 2, -, -, -, 3, -, -, -, -, -, -, -, 4, -, -, -, -, 2 3 2 3 4 3 5 2 5 3 4 5 4 7 3
3 8 5 7 2 7 5 8 3 7 4 1 6 5 9 4 11 -, -, -, -, -, -, -, -, -, -, -, 5, -, -, -, -, --, --, 8 5 7 2 7 5 8 3 7 4 5 6 5 9 4 11 7
7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 --, --, --, --, --, --, --, --, -, -, -, -, --, --, --, 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13
13 8 11 3 10 7 11 4 9 5 1 7 6 11 5 --, --, --, --, --, --, --, -, -, -, 6, -, -, --, --, --, ...} 8 11 3 10 7 11 4 9 5 6 7 6 11 5 14
(http://oeis.org/A002487). Julian derived the reverse sequence: NestList[2*Ceiling[1/#] - 1 - 1/# &, 14/9, 9]
14 5 11 6 7 1 5 9 4 {--, --, --, --, -, -, 6, -, -, -} 9 14 5 11 6 7 6 5 9
and found the waiting time from 355/113 to 0 was 67107848. I.e., intermediate swell was >>355.
Following Josh's pointer
http://mathlesstraveled.com/2009/10/18/the-hyperbinary-sequence-and-the-calk...
In[1]:= alf[1] = 1; alf[x_ /; x < 1] := 2*alf[x/(1 - x)]; alf[x_] := 1 + 2*alf[x - 1]
In[2]:= Timing[alf[355/113]]
Out[2]= {0.000129, 67107847}
As Yorgey says: Sweet. --rwg
Well, semisweet. This recursion mimics the subtractive Euclid process, with time proportional to the sum of the CF terms of x. Theoretically, the expected value of a CF term is infinite(!), so this is poor form. Practically, the length in bits of the answer will be > Sum(CF terms), so if you hit a huge term, you're screwed anyway. Nevertheless, even further speedup of alf is possible by rewriting it to take its argument as a continued fraction. Neil, by examining the binary values of alf, quickly produced a very fast version closely resembling this nonworking one, which he gave me by accident:
FromDigits[Rest[Reverse[ Flatten[Table[Mod[i, 2], {i, 1, Length[#]}, {n, #[[i]]}]]]] &@ContinuedFraction[x],2]
About 20 hrs later, I finally managed to debug an optimization of alf: ecf[{}] = 0; ecf[{L___, a_, 1}] = ecf[{L, a + 1}]; ecf[{0, 0, L___}] := ecf[{L}]; ecf[{x_}] := 2^x - 1; ecf[L_List] := 2^L[[1]]*(1 + 2^L[[2]]*ecf[Drop[L, 2]]) - 1
E.g., In[77]:= ecf[{3, 7, 16}] Out[77]= 67107847
Both this and Neil's (good one) are equivalent to the formula alf(x) = waiting time from 1= -1 + 2^L1 (1 + 2^L2 (-1 + ... (-1 + 2^Ln)))), n odd,
-1 + 2^L1 (1 + 2^L2 (-1 + ... (1 + 2^(-1 + Ln)))), n even,
where CF(x) = {L1,...Ln}. (I.e., decrement the last term if there are evenly many.) I guess people already knew this. --rwg
But the real surprise came with plotting the forward sequence
starting with Sqrt[-1] in a neighborhood of the origin--the Ford Pinto circles <http:gosper.org/fordpinto.png>! (Complete with some particulate emissions.) (Using Mma's convention: Floor[z]==Floor[Re[z]]+I*Floor[Im[z]].) The reverse sequence plots the left half (mirror image). --rwg rwg>
At least one Yahoo user couldn't access this image. Try this?: http://gosper.org/fordpinto.png --rwg
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thank you, Joshua! I had somehow lived in total ignorance of Newman's amazing, useful, and tiny invention: NestList[1/(2*Floor[#] - # + 1)&, 0, 69]
For obvious (intuitive) reasons, this function avoids near-integers like the plague! (very evident if you plot the successive compositions and notice the banding) One question I haven't attempted to answer is the following: Given f(x) = 1/(2*floor(x) - x + 1) r(n) = (f^n)(0) ;; f^n = n compositions of f is there a "closed form", or way to recognize in constant time which values of n satisfy r(n+1) = 1/r(n) ? Let's call the values r(n),r(n+1) "reciprocal pairs" which satisfy the above. Obviously, reciprocal pairs are at n={2, 5, 11, 23, ...}. Let's say the (n>=0)th reciprocal pair is rp(n). It seems that rp(n) = (2n+1)/2 holds (but I have no proof!). In light of this, it might simply be more interesting to just look at the values of n satisfying the equation above. Here is a Common Lisp program (well, program and terminal output) to calculate the values (not very efficiently) of n where reciprocal pairs are located. <<<BEGIN PROGRAM>>> CL-USER> (declaim (optimize speed (safety 0) (debug 0))) NIL CL-USER> (defun f (x) (declare (type ratio x)) (/ (+ (* 2 (floor x)) (- x) 1))) F CL-USER> (defun find-reciprocal-pairs (max-n) (declare (type fixnum max-n)) (loop :for n :from 1 :to max-n :for rn := (f 0) :then rn+1 :for rn+1 := (f rn) :when (= rn+1 (/ rn)) :collect n)) FIND-RECIPROCAL-PAIRS CL-USER> (progn (compile 'f) (compile 'find-reciprocal-pairs) t) T CL-USER> (time (find-reciprocal-pairs (expt 10 9))) Timing the evaluation of (FIND-RECIPROCAL-PAIRS (EXPT 10 9)) User time = 0:10:12.881 System time = 0.124 Elapsed time = 0:10:17.654 Allocation = 59557713860 bytes 0 Page faults (2 5 11 23 47 95 191 383 767 1535 3071 6143 12287 24575 49151 98303 196607 393215 786431 1572863 3145727 6291455 12582911 25165823 50331647 100663295 201326591 402653183 805306367) <<<END PROGRAM>>> Perhaps it'd be interesting to look at the number of pairs below N... <<<BEGIN PROGRAM>>> CL-USER> (defun count-reciprocal-pairs-below (n) (length (find-reciprocal-pairs (1- n)))) COUNT-RECIPROCAL-PAIRS-BELOW CL-USER> (compile 'count-reciprocal-pairs-below) COUNT-RECIPROCAL-PAIRS-BELOW NIL NIL CL-USER> (dotimes (n 10 nil) (format t "Reciprocal pairs below 10^~A == ~A~%" n (count-reciprocal-pairs-below (expt 10 n)))) Reciprocal pairs below 10^0 == 0 Reciprocal pairs below 10^1 == 2 Reciprocal pairs below 10^2 == 6 Reciprocal pairs below 10^3 == 9 Reciprocal pairs below 10^4 == 12 Reciprocal pairs below 10^5 == 16 Reciprocal pairs below 10^6 == 19 Reciprocal pairs below 10^7 == 22 Reciprocal pairs below 10^8 == 25 Reciprocal pairs below 10^9 == 29 <<<END PROGRAM>>> I'd conjecture then that the number of them grows log-linearly (which sort of makes sense, as we might look at the function f as a breadth-first search on the rationals, so as the height increases linearly, the number to check increases exponentially). Anyway, I need to get back to work now, so my little mindless ramble is over. Take care! Robert Smith On 11/6/2011 5:30 PM, Bill Gosper wrote:
JZucker>
Well, the Calkin-Wilf tree is still the best, of course.
Thank you, Joshua! I had somehow lived in total ignorance of Newman's amazing, useful, and tiny invention: NestList[1/(2*Floor[#] - # + 1)&, 0, 69]
1 1 3 2 1 4 3 5 2 5 3 1 5 4 7 {0, 1, -, 2, -, -, -, 3, -, -, -, -, -, -, -, 4, -, -, -, -, 2 3 2 3 4 3 5 2 5 3 4 5 4 7 3
3 8 5 7 2 7 5 8 3 7 4 1 6 5 9 4 11 -, -, -, -, -, -, -, -, -, -, -, 5, -, -, -, -, --, --, 8 5 7 2 7 5 8 3 7 4 5 6 5 9 4 11 7
7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 --, --, --, --, --, --, --, --, -, -, -, -, --, --, --, 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13
13 8 11 3 10 7 11 4 9 5 1 7 6 11 5 --, --, --, --, --, --, --, -, -, -, 6, -, -, --, --, --, ...} 8 11 3 10 7 11 4 9 5 6 7 6 11 5 14
(http://oeis.org/A002487). Julian derived the reverse sequence: NestList[2*Ceiling[1/#] - 1 - 1/#&, 14/9, 9]
14 5 11 6 7 1 5 9 4 {--, --, --, --, -, -, 6, -, -, -} 9 14 5 11 6 7 6 5 9
and found the waiting time from 355/113 to 0 was 67107848. I.e., intermediate swell was>>355. But the real surprise came with plotting the forward sequence starting with Sqrt[-1] in a neighborhood of the origin--the Ford Pinto circles<http:gosper.org/fordpinto.png>! (Complete with some particulate emissions.) (Using Mma's convention: Floor[z]==Floor[Re[z]]+I*Floor[Im[z]].) The reverse sequence plots the left half (mirror image). --rwg rwg>
Duh, the original argument was< -1, so the z/(z-1) transformation gives a single, convergent series:
10 3 1/12 1/12 13 1 5 2 3 5 sqrt(6) 17 23 hyper_2f1(--, --, -, --------) = --------------------- 24 24 6 2 2 1/6 17 23 3125
Duh, all you need is z<1/2. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Bill Gosper -
Joshua Zucker -
Neil Bickford -
rcs＠xmission.com -
Robert Smith -
Warren Smith