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>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 < 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>0, Y>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