Maths Olympiad Prep

Library / /692 of 860

Number theory Difficulty 5.4 AIME, harder Find the answer

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Answer: 1,2,3,41,2,3,4 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,224,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 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 n5,n!>Mn \geq 5, n!>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=nk1v_{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-2 k-1 powers of 2 are lost when going from (n+1)(n+1) ! to MM. Since M(n+1)M \mid(n+1) !, when n2k1k+1n3k+2n-2 k-1 \geq k+1 \Longleftrightarrow n \geq 3 k+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 3 k+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 3 k+2=11. We thus need only check values of nn between 5 and 10 : n=5:n!=120,M=60n=5: n!=120, M=60; n=6:n!=720,M=420n=6: n!=720, M=420 n=7:n!=5040,M=840n=7: n!=5040, M=840 n{8,9,10}:n!40320,M27720n \in\{8,9,10\}: n!\geq 40320, M \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. 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.