1
$\begingroup$

(This isn't the exact wording of the problem on the AIME)

Find the number of $n,2\le n \le 1000$ such that $$\int_1^n x \lfloor \sqrt x \rfloor dx\in \Bbb Z$$

During the test, I noticed that for some values, for example, $2^2\le n \lt 3^2$, all values satisfied the condition, while for some values, eg $3^2\le n\lt4^2$, only half of the values satisfied the equation. I wasn't sure how to find all n, and as I did not have much time, I couldn't check all values of $n$. How would one approach this problem?

$\endgroup$
3
$\begingroup$

For any positive integer $n$, let $p = \lfloor \sqrt{n} \rfloor$.

To simplify derivation, we will treat all integrals involved as Riemann Stieltjes integral. This will allow us to integrate functions with jump discontinuities (e.g $\lfloor \sqrt{x}\rfloor$ ) by part.

Change variable to $u = \sqrt{x}$, we have:

$$\begin{align} \int_1^n x\lfloor\sqrt{x}\rfloor dx &= \frac12 \int_{1^-}^{\sqrt{n}^{+}} \lfloor u \rfloor du^4 = \frac12\left\{ \left[\lfloor u\rfloor u^4\right]_{1^-}^{\sqrt{n}^+} - \int_{1^-}^{\sqrt{n}^+} u^4 d\lfloor u \rfloor\right\}\\ &= \frac12\left( p n^2 - \sum_{k=1}^p k^4\right) = \frac12\left( p n^2 - \frac15 B_5(p+1)\right)\tag{*1} \end{align} $$ where $$B_5(x) = \frac16 (x-1)x(2x-1)(3x(x-1)-1)$$ is the Bernoulli polynomial of order $5$. We don't really need this explicit form of $B_5(x)$. What we need is following:

$$\sum_{k=1}^p k^4 \equiv \begin{cases} 1, &\text{ if } p \equiv 1, 2 \pmod 4\\ 0, &\text{ if } p \equiv 0, 3 \pmod 4 \end{cases}\tag{*2} $$ For the last expression of $(*1)$, notice

  • there is a single factor $\frac12$ outside the bracket.
  • what inside the bracket is an integer.

This means the integral at hand is an integer if and only if the bracket in the last expression of $(*1)$ is even. Using $(*2)$, we find this will happen when and only when one of the following three conditions are satisfied.

  1. $p \equiv 0 \pmod 4$, $p^2 \le n < (p+1)^2$
  2. $p \equiv 1 \pmod 4$, $p^2 \le n < (p+1)^2$, $n$ odd.
  3. $p \equiv 3 \pmod 4$, $p^2 \le n < (p+1)^2$, $n$ even.

This leads to totally $483$ solutions for the problem.

$$ \begin{array}{r|r:l} \verb/solu#/ & p & 2 \le n \le 1000\\ \hline 1 & 1 & 3\\ 4 & 3 & 10,12,14\\ 13 & 4 & 16,17,18,19,20,21,22,23,24\\ 19 & 5 & 25,27,29,31,33,35\\ 26 & 7 & 50,52,54,56,58,60,62\\ 43 & 8 & 64,65,\ldots,79,80\\ 53 & 9 & 81,83,85,87,89,91,93,95,97,99\\ 64 & 11 & 122,124,\ldots,140,142\\ 89 & 12 & 144,145,\ldots,167,168\\ 103 & 13 & 169,171,\ldots,193,195\\ 118 & 15 & 226,228,\ldots,252,254\\ 151 & 16 & 256,257,\ldots,287,288\\ 169 & 17 & 289,291,\ldots,321,323\\ 188 & 19 & 362,364,\ldots,396,398\\ 229 & 20 & 400,401,\ldots,439,440\\ 251 & 21 & 441,443,\ldots,481,483\\ 274 & 23 & 530,532,\ldots,572,574\\ 323 & 24 & 576,577,\ldots,623,624\\ 349 & 25 & 625,627,\ldots,673,675\\ 376 & 27 & 730,732,\ldots,780,782\\ 433 & 28 & 784,785,\ldots,839,840\\ 463 & 29 & 841,843,\ldots,897,899\\ 483 & 31 & 962,964,\ldots,998,1000\\ \end{array} $$

Notes

  • $\color{blue}{[1]}$ Above analysis implies none of the $n$ with $2^2 \le n < 3^2$ satisfies the condition. This is different from what you claim in the question. I've verified by hand and by wolfram alpha that your claim is invalid.
$\endgroup$
3
$\begingroup$

$$\lfloor\sqrt x\rfloor=\begin{cases}1,~x\in[1,4)\\ 2,~x\in[4,9)\\ 3,~x\in[9,16)\\ \vdots\\ 31,~x\in[961,1000]\end{cases}$$

Use this to rewrite the integral as,

$$I=\left(\sum_{i=1}^{p-1}\int\limits_{i^2}^{(i+1)^2}ix\,\mathrm dx\right)+\int\limits_{p^2}^npx\,\mathrm dx$$

where $p\in\Bbb{Z}$ such that $p^2\leq n\leq (p+1)^2$

$$I=\sum_{i=1}^{p-1}\left(\frac{i}{2}(4i^3+6i^2+4i+1)\right)+\frac{p}{2}(n^2-p^4)$$

$\endgroup$
  • $\begingroup$ I'm not sure if this will result in a nice simplification or not, but you can try to examine it and take it further. $\endgroup$ – Prasun Biswas Apr 16 '15 at 23:04
1
$\begingroup$

Let $k$ be the greatest integer $k$ such that $k^2\leq n$ henece: $$\int_1^n x \lfloor \sqrt x \rfloor dx=\sum_{i=1}^{k-1}i\int_{i^2}^{(i+1)^2}xdx+k\int_{k^2}^nxdx=\sum_{i=1}^{k-1}i\frac{(i+1)^4-i^4}{2}+\frac{k(n^2-k^4)}{2} $$

$\endgroup$
  • $\begingroup$ That's what I was thinking of too! But I don't think it'll be $(2i+1)$. $\endgroup$ – Prasun Biswas Apr 16 '15 at 23:00
  • $\begingroup$ Because, on evaluation of that part, it's like $(i+1)^4-i^4$ and not $(i+1)^2-i^2$ $\endgroup$ – Prasun Biswas Apr 16 '15 at 23:01
  • $\begingroup$ I'm talking about the integral under summation. $\endgroup$ – Prasun Biswas Apr 16 '15 at 23:02
  • $\begingroup$ wolframalpha.com/input/… $\endgroup$ – Elaqqad Apr 16 '15 at 23:13

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.