I was trying to prove the following:

  if  x%(x/2) != 0 or x%(x/2) == 0 

  then x%(x/y) != 0 or x%(x/y) == 0  such that y = [2,4)

So I am trying to figure out whether a number can have a factor in between its half and its fourth. I am trying to use it in a factoring algorithm.

  • $\begingroup$ I can't understand the function. Both antecedent and consequent are trivially true in classical logic, due to the law of excluded middle, as long as the quantities are actually defined (and in fact, even if they're undefined, depending on your definition of "equals" and "different"). So the claim is trivially true. $\endgroup$ – Yuval Filmus Jun 6 '14 at 0:46
  • $\begingroup$ @YuvalFilmus I see what you mean. I poorly stated what I was trying to say. What I am trying to see basically is what is the distance a number has to be from the half point to be a factor (n/2 to n/k). For example 99 has a factor at 99/3, but nothing from 2 to 3 (99/2 to 99/3). Is there a proof to figure out k. If I am able to do this then instead of trying n/2 to n/3 i can jump to n/3 and skip everything in between n/2 to n/3 $\endgroup$ – abden003 Jun 6 '14 at 17:54
  • $\begingroup$ A number $n$ has no factor strictly between $n/2$ and $n/3$, or strictly between $n/3$ and $n/4$, and so on. The reason is that if $n/k$ is a factor then $k$ must be an integer. $\endgroup$ – Yuval Filmus Jun 7 '14 at 0:38

If a number $n$ has a factor $m$ in the range $n/4 \leq m \leq n/2$, then the quotient $k = n/m$ satisfies $2 \leq k \leq 4$, that is, $k \in \{2,3,4\}$. This should give you a fast algorithm for determining whether such a factor $m$ exists.


Yuval Filmus' answer is better than this brute force attempt

Pseudo-code following:

Input: n (number to check if it has a factor in [n/4, n/2])

n1 = [n/4]
n2 = [n/2]

for k in n1..n2

     if ( n mod k === 0) return true

return false

Of course the previous algorithm will do what is asked in the question, however since a factor of a number (eg a prime) needs at most $\sqrt{n}$ it would not be very efficient

  • $\begingroup$ You can do much much better by considering $n/k$ instead of $k$. $\endgroup$ – Yuval Filmus Jun 6 '14 at 0:47
  • $\begingroup$ @YuvalFilmus, <del>how exactly is that?</del> seen your answer, yeap agree :) $\endgroup$ – Nikos M. Jun 6 '14 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.