Conference rusure::math

Lynn,

	You will be greatly missed.

>Please keep in touch.

	Sure thing.

>Now, as my parting shot, the Yarbrough Memorial Puzzle: 
>Suppose you have a *large* sheet of quadrille paper (i.e. ruled into 1/4"
>squares); what is the smallest circle that can be drawn on that sheet so
>that at least 1,000,000 complete 1/4" squares are inside the circle? 

	Well, it's clear that the radius r lies in:
			[1000/pi^�, 2^�+1000/pi^�]	(*1/4", of course)
But after that the fun starts...

Best wishes to yourself and to Pat for the future.

Ever,
Andrew.

Lynn,
	Thanks for all you've contributed.


>Suppose you have a *large* sheet of quadrille paper (i.e. ruled into 1/4"
>squares); what is the smallest circle that can be drawn on that sheet so
>that at least 1,000,000 complete 1/4" squares are inside the circle? 

Assuming that the circle is centered at a '+' on the grid paper, then r� is
a prime number that is the sum of the squares of two numbers in only one way,
and those two numbers are (as one would guess, knowing Lynn) palindromes.

But what if the circle isn't necessarily at a '+' on the grid?

    I for one will miss you greatly, Lynn.  Any Will you be staying in the
    DC area, or moving elsewhere?
    
    --  Barry

I can be reached, for the indefinite future, at 
	Lynn Yarbrough 
	931 Park St. SE
	Vienna, VA 22180
	(703)938-4019

Of course, if & when we move again later (likely in a few years since DC is
an expensive place to retire) I will inform all I can manage to.

Thanks,

Lynn 

Assumptions:

    	. circle centered on "+"
	. solution for 1st quadrant is sufficient
	. "div" = division with truncation

Consider the radius of length R sweeping clockwise from the vertical.  As it
intersects each vertical quadrille line "Q", we'll determine how many squares
are completely covered in the column bordered on the right by Q.

At the intersection with the first line, the angle formed by R and the x-axis 
is

	1)  theta(1) = arccos(0.25 / R) 
	             = arccos(1 / 4R)

and the altitude ("opposite side") of the right triangle is
	
	2)  b(1) = sin(theta(1)) * R

How many blocks will be *completely* covered in the first column of squares 
(once the radius has swept through the whole quadrant)?  

	3)  blocks(1) = b(1) div 0.25
		      = int(4 * b(1))

Continuing the clockwise sweep, at the second quadrille line we find:

	4) theta(2) = arccos(0.5 / R)
		    = arccos(1 / 2R)

	5) b(2) = sin(theta(2)) * R

	6) blocks(2) = b(2) div 0.25
		     = int(4 * b(2))

So the total number of blocks is the series:

		 n
		----	
	7)      \
                /      int(4 * b(n))
		----
		i=1

But what's "n", i.e. how many vertical lines does R intersect in its sweep (at
least: how many which have at least one completely covered block to their
left)?  The answer is simply:

	8) blocks(1)

which we can visualize by pivotting the diagram around the 45-degree line.

So the series is

	        blocks(1)
		----	
	9)      \
                /      int(4 * b(n))
		----
		i=1

        where blocks(1) = int(4 * (sin(arccos(1/4R)) * R)) 

or
                blocks(1)
	        ----	
	10)     \
                /      int(4 * (sin(arccos(i/4R)) * R))
		----
		i=1

So... if this is right, then all we have to do is find the smallest R making
(10) equal to 250,000 (going back to the assumption that one quadrant
suffices).  It doesn't look easy, and I wonder if:

	a. I've overlooked an obvious simplification of the trig expressions,

    	b. there's some quick iterative method that will find the R for us.

		
						
							Mark

.5>Assumptions:
.5>    	. circle centered on "+"

	This may be an unsafe assumption.  The smallest circle that
	contains *one* square isn't centered at a '+'.  Nor is the circle
	for 2, 3, 5, 6, 7, 8, 9, or 10 squares.

		   +--+--+
		   |  |  |
		+--+--+--+
		|  |  |  |
		+--+--+--+
		   |  |  |
		*  +--+--+

	If the '*' is the origin, the 7 squares are enclosed by a circle
	with radius� = 65/18, centered at (11/6, 3/2).

.5> So... if this is right, then all we have to do is find the smallest R [...]

My approach was similar to Mark's (with the same dubious assumption).

The number of squares covered by a circle of radius R centered at the origin is:

	   int(R)
	    ----	
	    \
	4 * /    int( sqrt(R� - i�) )
	    ----
	    i=1

This does without the trigonometric functions.
The above is a function of R�, and R� is an integer.  While a closed-form
expression would be preferred, the above function is enough for a binary search
to easily find the smallest R� that encloses 10^6 squares.

BTW, the following adaptation of Newton's iterations calculates int(sqrt(x)):

int isqrt(int x) {
    int r, s = x/2;
    if (s == 0) return x;
    do { r = s; s = ((r+1) + (x-1)/(r+1))/2; } while (s != r);
    return r;
}