# Iterative Floors and Ceilings

$\left\lfloor\dfrac{2016}{\left\lfloor\dfrac{2016}{k}\right\rfloor}\right\rfloor=k\quad;\qquad \left\lceil\dfrac{2016}{\left\lceil\dfrac{2016}{k}\right\rceil}\right\rceil=k$

An integer $k$ with $1\le k\le 2016$ is called $2016-$awesome, if it satisfies the two equations above.

Question: Find the number of $2016-$awesome numbers.

• You could ask for the number of solutions that are not factors of 2016 instead. Mar 28 '16 at 11:02
• A shame it isn't an infinite progression of floors and ceilings... Mar 28 '16 at 11:19

To make things more general (and make certain relationships clearer), replace $$2016$$ with $$N$$. There exists some non-negative $$q,r$$ such that $$N = qk +r$$ and $$r < k$$ (i.e., $$q$$ is the quotient and $$r$$ is the remainder when dividing $$N$$ by $$k$$). Note that also $$N = (q+1)k - (k-r)$$.

If $$r = 0$$ then $$k\mid N$$ and obviously $$k$$ is awesome. Now assume $$r \ne 0$$. Then $$\left\lfloor\frac{N}k\right\rfloor = q, \left\lceil\frac{N}k\right\rceil = q+ 1\\\left\lfloor\frac{N}q\right\rfloor = k + \left\lfloor\frac{r}q\right\rfloor , \left\lceil\frac{N}{q+1}\right\rceil = k - \left\lfloor\frac{k-r}{q+1}\right\rfloor$$ So for $$k$$ to be awesome, we must have $$r < q$$ and $$k - r \le q$$

To answer ghosts_in_the_code's comment, if $$k\le\sqrt{N}$$, then $$q \ge\sqrt{N}$$, and $$r < k \le q$$ while $$k - r \le k \le q$$. So every $$k \le\sqrt{N}$$ is automatically awesome.

Adding the two inequalities together gives $$k < 2q$$ and therefore $$k^2 < 2kq = 2(N - r) < 2N$$. Therefore the only awesome $$k > \sqrt{2N}$$ are the divisors of $$N$$. So, the place to search is only the stretch $$\sqrt{N} < k <\sqrt{2N}$$. For $$N = 2016$$ this is from $$45$$ to $$63$$. Everything below $$45$$ is automatically awesome, everything above $$63$$ is awesome only if it divides $$2016$$.

So we have three groups:

Divisors of 2016:

1,2,3,4,6,7,8,9,12,14,16,18,21,24,28,32,36,42,48,56,63,72,84,96,112,126,144,168,224,252,288,336,504,672,1008,2016 (36 total)

Less than or equal to $$\sqrt{2016}$$ (excluding the divisors):

5,10,11,13,15,17,19,20,22,23,25,26,27,29,30,31,33,34,35,37,38,39,40,41,43,44 (26 total)

Super awesome:

45,46,50,51,54 (5 total)

for

67 awesome numbers in all.

Since there was no tag, I took the liberty of determining the solution through Java code.

public class FloorsCeilings {

public static void main(String[] args) {
int count = 0;
for (double i = 1; i<=2016; i=i+1) {
if (Math.ceil(2016/Math.ceil(2016/i)) == i &&
Math.floor(2016/Math.floor(2016/i)) == i) {
System.out.println(i);
count++;
}
}
System.out.println("Count="+count);
}

}


This gives us the solution that there are

67 numbers which are $2016-*awesome*$. These numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 50, 51, 54, 56, 63, 72, 84, 96, 112, 126, 144, 168, 224, 252, 288, 336, 504, 672, 1008, 2016.

If someone can provide an elegant solution that does not brute force it, I will be the first to upvote. :)

• The first thing I can notice is that all numbers below the square root of 2016 are awesome numbers. Idk if there is any specific reason for this or not. Mar 28 '16 at 11:08