AIME I 2015 #14:Area under a function

(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?

• note that you can compute the integral in term of $n$ – Elaqqad Apr 16 '15 at 22:46
• – Cyclohexanol. Apr 16 '15 at 22:50

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}{}$ 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.

$$\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)$$

• 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. – Prasun Biswas Apr 16 '15 at 23:04

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}$$

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