Find all positive integers $m, n$ satisfying $n!+2^{n-1}=2^m$.
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 $2^m=2^{n-1}+n!>2^{n-1},$ and so $m \geq n$. Hence, $v_2(n!)=v_2(2^m-2^{n-1})=n-1,$ that is $s_2(n)=1,$ hence $n=2^k$ for some $k \geq 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 \geq 128$. Observe that $n!=2^{n-1}(2^{m-n+1}-1),$ hence $3 \mid 2^m-1$, which implies that $m$ is even. Let $m=2k$, and apply the LTE to obtain that $v_3(k)+1=v_3(n!),$ that is $v_3(m-n+1)=v_3(n!)-1$. Let $t$ be such that $3^t <n<3^{t+1}$. Note that, by Legendre's formula, $\displaystyle v_3(n!)=\lfloor \dfrac{n}{3} \rfloor +\ldots+\lfloor \dfrac{n}{3^t} \rfloor>n(\dfrac{1}{3}+\ldots+(\dfrac{1}{3})^t)-t>\dfrac{3^t-1}{2}-t>\dfrac{n-3}{6}-\log_3(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 $3^{122/12}>3^{10}>128,$ and if it holds for $n$ then for $n+1$ we have to prove that $n+1<n \cdot 3^{1/12},$ which is true as $3^{1/12} \sim 1.09$ and $n \geq 128$). Hence, $v_3(m-n+1)>n/12,$ which in turn implies that $m-n+1>3^{n/12},$ therefore $n!=2^{n-1}(2^{m-n+1}-1)>2^{3^{n/12}}$ Now, we may obtain a contradiction by proving the following Claim. Claim 2: For all $n \geq 128$, $2^{3^{n/12}} \geq n!$ holds true. Proof: For $n=128$, we need to prove that $2^{3^{128/12}} \geq 128!$. It is well known that $n! \leq (\dfrac{n}{2})^n$ for all $n$ (provable by induction). Hence, $128! \leq 64^{128}=2^{768}$ and $2^{3^{128/12}}>2^{3^{10}}>2^{768},$ and so we are done $\blacksquare$ Now, back to the problem, we are left to examine $n \in \{8,16,32,64 \}$. If $n=8$, from $v_3(m-n+1)=v_3(n!)-1$, we obtain $v_3(m-7)=2,$ hence $m \geq 16$. However, $2^m=n!+2^{n-1}=8!+2^7 \leq 4^8+2^8=2^{16}+2^8<2^{17}$, hence $m=16$. However, in this case we must have $8!=2^{16}-2^7=511 \cdot 2^7,$ which is not the case as $3 \nmid 511$. 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!!