Maths Olympiad Prep

Library / /7 of 9

, 2019

Number theory Difficulty 5.6 AIME, harder Prove it United States

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

Solutions — 2

Solution 1

Solution:
Answer: 1,2,3,41,2,3,4

First, note that clearly there are no composite positive integers less than 2!2!, and no 33 consecutive composite positive integers less than 3!3!. The only composite integers less than 4!4! are
4,6,8,9,10,12,14,15,16,18,20,21,22 4,6,8,9,10,12,14,15,16,18,20,21,22
and it is easy to see that there are no 44 consecutive composite positive integers among them. Therefore, all n4n \leq 4 works.

Define M=lcm(1,2,,n+1)M=\operatorname{lcm}(1,2, \ldots, n+1). To see that there are no other such positive integers, we first show that for all n5n \geq 5, n!>Mn!>M. Let k=log2(n+1)k=\left\lfloor\log_{2}(n+1)\right\rfloor. Note that v2(M)=kv_{2}(M)=k, while
v2((n+1)!)=i=1kn+12ii=1k(n+12i1)=(n+1n+12k)k(n+12)k=nk1. 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 (nk1)k=n2k1(n-k-1)-k=n-2k-1 powers of 22 are lost when going from (n+1)!(n+1)! to MM. Since M(n+1)!M \mid (n+1)!, when n2k1k+1n3k+2n-2k-1 \geq k+1 \Longleftrightarrow n \geq 3k+2, we have
M(n+1)!2k+1(n+1)!2(n+1)<n! M \leq \frac{(n+1)!}{2^{k+1}} \leq \frac{(n+1)!}{2(n+1)}<n!
as desired. Since n2k1n \geq 2^{k}-1, we can rule out all kk such that 2k3k+32^{k} \geq 3k+3, which happens when k4k \geq 4 or n15n \geq 15. Moreover, when k=3k=3, we may also rule out all n3k+2=11n \geq 3k+2=11.

We thus need only check values of nn between 55 and 1010:

n=5n=5: n!=120n!=120, M=60M=60;

n=6n=6: n!=720n!=720, M=420M=420;

n=7n=7: n!=5040n!=5040, M=840M=840;

n{8,9,10}n \in \{8,9,10\}: n!40320n!\geq 40320, M27720M \leq 27720.

In all cases, n!>Mn!>M, as desired.

To finish, note that M2,M3,,M(n+1)M-2, M-3, \ldots, M-(n+1) are all composite (divisible by 2,3,,n+12,3, \ldots, n+1 respectively), which gives the desired nn consecutive numbers. Therefore, all integers n5n \geq 5 do not satisfy the problem condition, and we are done.

Solution 2

Solution:
Here is a different way to show that constructions exist for n5n \geq 5. Note that when n+1n+1 is not prime, the numbers n!2,n!3,,n!(n+1)n!-2, n!-3, \ldots, n!-(n+1) are all composite (the first n1n-1 are clearly composite, the last one is composite because n+1n!n+1 \mid n! and n!>2(n+1)n!>2(n+1)). Otherwise, if n=p1n=p-1 for prime p7p \geq 7, then the numbers (n1)!,(n1)!1,(n1)!2,,(n1)!(n1)(n-1)!,(n-1)!-1,(n-1)!-2, \ldots,(n-1)!-(n-1) are all composite (the first one and the last n2n-2 are clearly composite since (n1)!>2(n1)(n-1)!>2(n-1), the second one is composite since p(p2)!1=(n1)!1p \mid (p-2)!-1=(n-1)!-1 by Wilson's theorem).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.