I think DTs formula below isn't quite right; taking each clause as a 50:50 coin flip, the conjunctions are 1/8 true, and the disjunction only 1/4, while I'd expect 50%. Looking at the last couple of lines of MLBs listing of a+bsqrt2 in order, there seem to be 2 steps: add either -7+5sqrt2 or 3-2sqrt2 to the current number. Presumably, the good algorithm will have three or four candidate steps, to be tried in order, and the first step that keeps all the coordinates non-negative is accepted. Messy details to fill in: the rules for using the continued fraction expansion to create the step list, when to introduce new steps and discard old ones, and the appropriate generalization to 3D. Rich -----Original Message----- From: Marc LeBrun [mailto:mlb@fxpt.com] Sent: Monday, July 12, 2004 10:34 AM To: math-fun Subject: Re: [math-fun] perfect squares

=Dylan Thurston What's wrong with (p-r > 0 && q-s > 0 && (p-r)^2 < k*(q-s)^2) || (p-r < 0 && q-s < 0 && (p-r)^2 > k*(q-s)^2) ? [As before, x = sqrt(k)]

Nothing's wrong, but is there any "good" reason for why it's so complicated? By comparison, p/q < r/s is much simpler. The forms p+qx seem in some sense "morally equivalent" to p/q (for example they "induce" the reals similarly). Square testing, simple ordering, whatever: p+qx always seems to get "casey".

=Marc LeBrun Heck, I'd even pay $50 for an easy way to generate a+bx in increasing order for a,b >=0 (if you think you have one contact me to negotiate the definition of "easy"<;-).

=Dylan Thurston Err, it is easy once you have the continued fraction expansion, right? Is the issue getting the continued fraction expansion?

No, getting a CF is of course "solved". For example say k=2 so it's 1,2,2,2,... Maybe I've just been dense on seeing how to use that to nicely generate the a+bx. If you can tell me a truly easy way, then you've made an easy $50! "Easy" would be something like the so-called "BRM" raster line drawing algorithm, where you step directly to the next a,b without maintaining a whole bunch of state. (The best I've got so far maintains a sorted list of all a+bx with the same floor). Even funner would be directly computing the Nth a,b. Or, the number below some C+Dx. Here's the ordered forty-four k=2 pairs for a+bx < 10, then their a and b components: 0,0 1,0 0,1 2,0 1,1 0,2 3,0 2,1 1,2 4,0 0,3 3,1 2,2 5,0 1,3 4,1 0,4 3,2 6,0 2,3 5,1 1,4 4,2 7,0 0,5 3,3 6,1 2,4 5,2 8,0 1,5 4,3 7,1 0,6 3,4 6,2 9,0 2,5 5,3 8,1 1,6 4,4 7,2 0,7 0 1 0 2 1 0 3 2 1 4 0 3 2 5 1 4 0 3 6 2 5 1 4 7 0 3 6 2 5 8 1 4 7 0 3 6 9 2 5 8 1 4 7 0 0 0 1 0 1 2 0 1 2 0 3 1 2 0 3 1 4 2 0 3 1 4 2 0 5 3 1 4 2 0 5 3 1 6 4 2 0 5 3 1 6 4 2 7 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun