Find all positive integers m,n satisfying n!+2n−1=2m.
Problem
Source: 2023 Singapore MO Round 2 Senior Q4
Tags: factorial, number theory
24.06.2023 12:37
Not the most effective solution, but I think it works. Note that 2m=2n−1+n!>2n−1, and so m≥n. Hence, v2(n!)=v2(2m−2n−1)=n−1, that is s2(n)=1, hence n=2k for some k≥0. If n=1 we obviously have the solution m=1. If n=2, we obviously have the solution m=2, while if n=4 we obviously have the solution m=5. Assume firstly that n≥128. Observe that n!=2n−1(2m−n+1−1), hence 3∣2m−1, which implies that m is even. Let m=2k, and apply the LTE to obtain that v3(k)+1=v3(n!), that is v3(m−n+1)=v3(n!)−1. Let t be such that 3t<n<3t+1. Note that, by Legendre's formula, v3(n!)=⌊n3⌋+…+⌊n3t⌋>n(13+…+(13)t)−t>3t−12−t>n−36−log3(n)>n/12, with the last inequality being true as it is equivalent to 3(n−6)/12>n, which can be proved inductively (for n=128 we have 3122/12>310>128, and if it holds for n then for n+1 we have to prove that n+1<n⋅31/12, which is true as 31/12∼1.09 and n≥128). Hence, v3(m−n+1)>n/12, which in turn implies that m−n+1>3n/12, therefore n!=2n−1(2m−n+1−1)>23n/12 Now, we may obtain a contradiction by proving the following Claim. Claim 2: For all n≥128, 23n/12≥n! holds true. Proof: For n=128, we need to prove that 23128/12≥128!. It is well known that n!≤(n2)n for all n (provable by induction). Hence, 128!≤64128=2768 and 23128/12>2310>2768, and so we are done ◼ Now, back to the problem, we are left to examine n∈{8,16,32,64}. If n=8, from v3(m−n+1)=v3(n!)−1, we obtain v3(m−7)=2, hence m≥16. However, 2m=n!+2n−1=8!+27≤48+28=216+28<217, hence m=16. However, in this case we must have 8!=216−27=511⋅27, which is not the case as 3∤. If n=16, from v_3(m-n+1)=v_3(n!)-1, we obtain v_3(m-15)=6, hence m \geq 3^6+15=744. However, 2^m=n!+2^{n-1}=16!+2^{15} \leq 2^{24}+2^{15}<2^{25}, a contradiction. If n=32, from v_3(m-n+1)=v_3(n!)-1, we obtain v_3(m-31)=14, hence m \geq 3^{14}+31. However, 2^m=n!+2^{n-1}=32!+2^{31} \leq 2^{80}+2^{31} <2^{81}, a contradiction. If n=64, from v_3(m-n+1)=v_3(n!)-1, we obtain v_3(m-63)=29, hence m \geq 3^{29}+63. However, 2^m=n!+2^{n-1}=64!+2^{63} \leq 2^{192}+2^{63}<2^{193}, a contradiction. To sum up, the only solutions are (m,n)=(1,1), (m,n)=(2,2) and (m,n)=(5,4)$. (thanks @below!)
24.06.2023 13:56
Of course, (1,1) works as well.
24.06.2023 14:38
Using Legendre's formula we have v_2(n!)=n-s_p(n) If n is'nt power of 2 We have m=n-s_p(n) So 2^m<2^{n-1}+n! \rightarrow n=2^k Consider A={m|m=4k+3;m\le 2^k} , we have |A|=\dfrac{2^k}{4} If k\ge 3 we have v_2(n!+2^{n-1})=n so m=n \rightarrow n!=2^{n-1} \rightarrow n=1 False \rightarrow k=1 or k=2 From this we have (m,n)=(2,2);(5;4);(1;1)
12.06.2024 07:34
The above post is wrong. After deducing that n is a power of 2, letting n!=2^{n-1}a, where a is odd, it happens that a\equiv 3 mod 4. This is because the post fails to account for contribution to a from even non-powers of 2. I outline the correct approach here: Insted of considering a mod 4, we show that a\equiv3 mod 8 for all n=2^k for k\ge3. We proceed with induction. The base case k=3 is easily computable. To go from k to k+1, we can reach all even numbers in the range [1,2^{k+1}] by multiplying all numbers in the range [1,2^k] by 2. This keeps a constant as this factor is absorbed into the 2^{n-1} term in 2^{n-1}a. Then we add all the odd numbers, which mod 8 is just 1,3,5,7 repeated. As 8\mid 2^{k+1}, it follows that this is equivalent to multiplying by 1. Therefore a is unchanged and remains 3. It follows that m\le n+1. Simple bounding gives n\le4.
12.06.2024 19:48
13.06.2024 05:35
Obviously m \geq n. Claim: n > v_2(n!) Proof: v_2(n!) = \sum\limits_{i=1}^{\infty} \lfloor \frac{n}{2^i} \rfloor \leq \sum\limits_{i=1}^{\infty} \frac{n}{2^i} = n \cdot \sum\limits_{i=1}^{\infty} \frac{1}{2^i} = n but, \exists k such that \lfloor \frac{n}{2^{n_0}} \rfloor = 0 \forall n_0 \geq k. So, n > v_2(n!) If v_2(n!) < n - 1 \Longrightarrow \frac{n!}{2^{v_2(n!)}} + 2^{n-v_2(n!)-1} = 2^{m - v_2(n!)} but LHS is odd and RHS is even. ABS! Then, v_2(n!) = n - 1 \bullet n = 1 \Longrightarrow (m, n) = (1, 1) \bullet n > 1
Thus, n \in \{ 2, 4\} after checking we have (m, n) = (2, 2); (5, 4) \boxed{\therefore (m, n) = (1, 1); (2, 2); (5, 4)}
13.06.2024 09:18
Marcos_Vinicius wrote: Obviously m \geq n. Claim: n > v_2(n!) Proof: v_2(n!) = \sum\limits_{i=1}^{\infty} \lfloor \frac{n}{2^i} \rfloor \leq \sum\limits_{i=1}^{\infty} \frac{n}{2^i} = n \cdot \sum\limits_{i=1}^{\infty} \frac{1}{2^i} = n but, \exists k such that \lfloor \frac{n}{2^{n_0}} \rfloor = 0 \forall n_0 \geq k. So, n > v_2(n!) If v_2(n!) < n - 1 \Longrightarrow \frac{n!}{v_2(n!)} + 2^{n-v_2(n!)-1} = 2^{m - v_2(n!)} but LHS is odd and RHS is even. ABS! Then, v_2(n!) = n - 1 \bullet n = 1 \Longrightarrow (m, n) = (1, 1) \bullet n > 1
Thus, n \in \{ 2, 4\} after checking we have (m, n) = (2, 2); (5, 4) \boxed{\therefore (m, n) = (1, 1); (2, 2); (5, 4)} Please ,note that v_2(n!)<n-1 is not true for all n\geq 6. try n=2^r ,where r is a positive integers. But the idea is definitely good. Also, a small fix that you have written \frac{n!}{v_2(n!)} which is a small mistake you did, it should be \frac{n!}{2^{v_2(n!)}}.
13.06.2024 18:13
oh, thanks for correction
13.06.2024 18:42
Firstly we are getting that m = n or m>n If we take two cases C - 1 m=n n! + 2^(n-1) = 2^n => n! = 2^n-1 It would satisfy iff n has only 1 or 2 as its factor since RHS is always a power of 2 So n = 1 or 2 (1,1) , (2,2) C - 2 m>n n! = 2^(n-1){2^(m-n+1) - 1} now we can generalize that [n/2] + [n/4] + [n/8] + ..... must be equal to 2^(n-1) since the second part is always odd Now this would satisfy iff n belongs to the set of 2^k Now if we take k greater 2 then we see that after taking some few cases that there is no such n possible for k greater than 2 So, n=4 and by putting it we would get m = 5 I am extremely sorry as I wasn't able to explain some things like why n belongs to 2^k and why n can't be greater than 4 elaborately as don't know how to use But I can say that after taking some special cases and doing some specific generalization that is what I did Sorry!!