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