1
$\begingroup$

I am looking for the full solution for $a$ to the floor function equation where $\left\lfloor{\frac{N}{a}}\right\rfloor = \left\lfloor{\frac{N}{p}}\right\rfloor - a$. I have tried the quadratic solution when dropping the floor functions and this does identify most of the solutions for $a$. However there are a few more solutions that are not identified by this method. The conditions are $p > 1$ (actually $p$ is prime), $N \ge {p}^{2}$, $a > 0$, and $N, a, p \in \mathbb{Q}$, and $1 \le a \le N$.

Also I am using Mathematica and it does handle equations with floor functions when using Solve or Reduce. For example Mathematica does not solve $\left\lfloor{a}\right\rfloor = 0$ where the solution is $0 \le a < 1$.

$\endgroup$
0
$\begingroup$

Clearly, $a$ must be a positive integer. Let $q=\lfloor \frac Np\rfloor$. Note that $q\ge p$. We have $\frac Na\le \lfloor \frac Na\rfloor<\frac Na+1$, hence necessarily $$N\le q a -a^2<N+a$$ so that $a$ must be between (inclusively) the roots $\frac {q\pm\sqrt{q^2-4N}}2$ of $x^2-q a+N$, and strictly not between the roots $\frac{q-1\pm\sqrt{(q-1)^2-4N}}2 $ of $x^2-(q-1)x+N$. Thus $$ \left\lceil\tfrac {q-\sqrt{q^2-4N}}2\right\rceil\le a\le \left\lceil\tfrac{q-1-\sqrt{(q-1)^2-4N}}2\right\rceil-1\text{ or } \left\lfloor\tfrac{q-1+\sqrt{(q-1)^2-4N}}2\right\rfloor +1\le a\le \left\lfloor\tfrac {q+\sqrt{q^2-4N}}2\right\rfloor$$

Note that it is possible that $q^2<4N$, in which case the first quadratic has no real roots - and the original problem has no solutions. On the other hand, if $(q-1)^2<4N$ that's fine and there simply is no restriction imposed by the second quadratic, i.e., $$ \left\lceil\tfrac {q-\sqrt{q^2-4N}}2\right\rceil\le a\le \left\lfloor\tfrac {q+\sqrt{q^2-4N}}2\right\rfloor\qquad\text{ if }(q-1)^2<4N.$$

$\endgroup$
  • $\begingroup$ Using the case where $p = 11$ and $N = 500$ the last formula gives $20 \le a \le 25$, while the full solution is $18 \le a \le 28$. I also duplicated the above derivation using the two end points of $\left\lfloor{N/a}\right\rfloor$. So why are we missing these other solutions? $\endgroup$ – Lorenz H Menke Aug 14 '16 at 23:19
  • $\begingroup$ I would fix the third sentence to read: We have $\left\lfloor{N/a}\right\rfloor = N/a - \alpha$ where $0 \le \alpha < 1$, hence necessarily ... $\endgroup$ – Lorenz H Menke Aug 16 '16 at 1:27
0
$\begingroup$

Clearly, $a$ must be a positive integer. Let $q = \left\lfloor \frac{N}{p}\right\rfloor$. Note that $q \ge p$. We have $\frac{N}{a} - 1 < \left\lfloor \frac{N}{a}\right\rfloor \le \frac{N}{a}$, hence necessarily $$N - a < q a - a^2 \le N $$ so that $a$ must be strictly not between the roots $\frac {q + 1 \pm \sqrt{\left({q + 1}\right)^{2} - 4\, N}}{2}$ of $a^2 - \left({q + 1}\right) a + N$, and be between (inclusively) the roots $\frac{q \pm \sqrt{{q}^{2} - 4\, N}}{2}$ of $a^2 - q\, a + N$. Thus \begin{equation*} 0 < a \le \left\lfloor{\frac{1}{2} \left({q - \sqrt{{q}^{2} - 4\, N}}\right)}\right\rfloor \quad \text{or} \quad a \ge \left\lceil{\frac{1}{2} \left({q + \sqrt{{q}^{2} - 4\, N}}\right)}\right\rceil \quad \text{if} \quad N < \frac{{q}^{2}}{4} \end{equation*} and \begin{equation*} a > 0 \quad \text{if} \quad N \ge \frac{{q}^{2}}{4}. \end{equation*} On the other hand, if $N < \left({q + 1}\right)^{2}/4$ that's fine and there simply is no restriction imposed, i.e., \begin{equation*} \left\lceil{\frac{1}{2} \left({q + 1 - \sqrt{\left({q + 1}\right)^{2} - 4\, N}}\right)}\right\rceil \le a \le \left\lfloor{\frac{1}{2} \left({q + 1 + \sqrt{\left({q + 1}\right)^{2} - 4\, N}}\right)}\right\rfloor \quad \text{if} \quad N < \frac{\left({q + 1}\right)^{2}}{4}. \end{equation*} For example, when $p = 11$ and $N = 500$ then $500 < 529$ and $18 \le a \le 28$.

$\endgroup$

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.