note sleepingsquirrel Here's an informal proof of our conjecture "The factor of N closest to sqrt(N) is less than sqrt(N)". <ol> <li>Let M be the positive square root of N. (<tt>M*M = N, M&gt;0</tt>) </li> <li>The closest factor to M is bewteen 1 and 2*M. (i.e. 1 is closer to M than any number greater than twice M. <tt>(M-1 &lt; 2*M-M)</tt>)</li> <li>For every pair of numbers whose product is N, one of the pair will be greater than M and the other less than M. (the product of two numbers greater than M is greater than N, and the product of two numbers less than M would be less than N) </li> <li>Take a pair of numbers whose product is N. Call the smaller (<tt>M-X</tt>) and the larger (<tt>M+Y</tt>). (i.e. <tt>X&gt;0, Y&gt;0</tt>) </li> <li>So, <tt>(M-X) * (M+Y) = N</tt></li> <li>Multiplying out, <tt>M^2 + M*(Y-X) - X*Y = N</tt></li> <li>But <tt>M^2 = N</tt> (by definition)</li> <li>Substituting: <tt>N + M*(Y-X) - X*Y = N </tt></li> <li>Subtracting N: <tt>M*(Y-X) - X*Y = 0</tt></li> <li>Since X and Y are positive (by definition, step 4), the term <tt>-X*Y</tt> is negative</li> <li>If <tt>-X*Y</tt> is negative, the only way for the entire sum to equal 0 is if the term <tt>M*(Y-X)</tt> is positive</li> <li>But M is positive (step 1), so <tt>(Y-X)</tt> must also be positive, which means that Y is greater than X.</li> <li>Finally, if Y is greater than X, the smaller factor, <tt>(M-X)</tt> is closer to M than <tt>(M+Y)</tt>, so you can limit your factor search to numbers less than sqrt(N).</li> </ol> <!-- Node text goes above. Div tags should contain sig only --> <div class="pmsig"><div class="pmsig-309610"> <p><hr>-- All code is 100% tested and functional unless otherwise noted. </div></div> 432558 432812