Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re^4: Closest factor less than sqrt(N) [proof]

by sleepingsquirrel (Hermit)
on Feb 21, 2005 at 00:13 UTC ( #432917=note: print w/ replies, xml ) Need Help??


in reply to Re^3: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root

Here's an informal proof of our conjecture "The factor of N closest to sqrt(N) is less than sqrt(N)".

  1. Let M be the positive square root of N. (M*M = N, M>0)
  2. 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. (M-1 < 2*M-M))
  3. 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)
  4. Take a pair of numbers whose product is N. Call the smaller (M-X) and the larger (M+Y). (i.e. X>0, Y>0)
  5. So, (M-X) * (M+Y) = N
  6. Multiplying out, M^2 + M*(Y-X) - X*Y = N
  7. But M^2 = N (by definition)
  8. Substituting: N + M*(Y-X) - X*Y = N
  9. Subtracting N: M*(Y-X) - X*Y = 0
  10. Since X and Y are positive (by definition, step 4), the term -X*Y is negative
  11. If -X*Y is negative, the only way for the entire sum to equal 0 is if the term M*(Y-X) is positive
  12. But M is positive (step 1), so (Y-X) must also be positive, which means that Y is greater than X.
  13. Finally, if Y is greater than X, the smaller factor, (M-X) is closer to M than (M+Y), so you can limit your factor search to numbers less than sqrt(N).


-- All code is 100% tested and functional unless otherwise noted.


Comment on Re^4: Closest factor less than sqrt(N) [proof]
Replies are listed 'Best First'.
Re^5: Closest factor less than sqrt(N) [proof]
by hv (Parson) on Feb 21, 2005 at 09:45 UTC

    Here's an easier way: take n = m^2, and a factor greater than the square root m + d, then the other factor is:

    m^2/(m + d) = m - dm/(m + d) = m - d + d^2/(m + d)
    Now d^2/(m + d) is greater than zero, so the cofactor is greater than m - d and hence closer to the square root.

    Hugo

Re^5: Closest factor less than sqrt(N) [proof]
by BrowserUk (Pope) on Feb 21, 2005 at 00:52 UTC

    sleepingsquirrel++

    Makes sense to me--but then my version did (to me) too :)

    Who'd've thunk it--even informality is relative :)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://432917]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (10)
As of 2015-07-29 11:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (263 votes), past polls