HMMT-Feb 2019 team, Problem 4

Find all positive integers $n$ for which there do not exist $n$ consecutive composite positive integers less than $n$ !.

Solution: Solution 1. First, note that clearly there are no composite positive integers less than 2!, and no 3 consecutive composite positive integers less than 3 !. The only composite integers less than 4 ! are \[ 4,6,8,9,10,12,14,15,16,18,20,21,22 \] and it is easy to see that there are no 4 consecutive composite positive integers among them. Therefore, all $n \leq 4$ works. Define $M=\operatorname{lcm}(1,2, \ldots, n+1)$. To see that there are no other such positive integers, we first show that for all $n \geq 5, n !>M$. Let $k=\left\lfloor\log _{2}(n+1)\right\rfloor$. Note that $v_{2}(M)=k$, while $v_{2}((n+1) !)=\sum_{i=1}^{k}\left\lfloor\frac{n+1}{2^{i}}\right\rfloor \geq \sum_{i=1}^{k}\left(\frac{n+1}{2^{i}}-1\right)=\left(n+1-\frac{n+1}{2^{k}}\right)-k \geq(n+1-2)-k=n-k-1$. This means that at least $(n-k-1)-k=n-2 k-1$ powers of 2 are lost when going from $(n+1)$ ! to $M$. Since $M \mid(n+1)$ !, when $n-2 k-1 \geq k+1 \Longleftrightarrow n \geq 3 k+2$, we have \[ M \leq \frac{(n+1) !}{2^{k+1}} \leq \frac{(n+1) !}{2(n+1)}<n ! \] as desired. Since $n \geq 2^{k}-1$, we can rule out all $k$ such that $2^{k} \geq 3 k+3$, which happens when $k \geq 4$ or $n \geq 15$. Moreover, when $k=3$, we may also rule out all $n \geq 3 k+2=11$. We thus need only check values of $n$ between 5 and 10 : $n=5: n !=120, M=60$; $n=6: n !=720, M=420$; $n=7: n !=5040, M=840$; $n \in\{8,9,10\}: n ! \geq 40320, M \leq 27720$. In all cases, $n !>M$, as desired. To finish, note that $M-2, M-3, \ldots, M-(n+1)$ are all composite (divisible by $2,3, \ldots, n+1$ respectively), which gives the desired $n$ consecutive numbers. Therefore, all integers $n \geq 5$ do not satisfy the problem condition, and we are done. Solution 2. Here is a different way to show that constructions exist for $n \geq 5$. Note that when $n+1$ is not prime, the numbers $n !-2, n !-3, \ldots, n !-(n+1)$ are all composite (the first $n-1$ are clearly\\ composite, the last one is composite because $n+1 \mid n !$ and $n !>2(n+1))$. Otherwise, if $n=p-1$ for prime $p \geq 7$, then the numbers $(n-1) !,(n-1) !-1,(n-1) !-2, \ldots,(n-1) !-(n-1)$ are all composite (the first one and the last $n-2$ are clearly composite since $(n-1) !>2(n-1)$, the second one is composite since $p \mid(p-2) !-1=(n-1)$ ! -1 by Wilson's theorem $)$. $\fbox{1,2,3,4}$.

Answer: 1,2,3,4