For any positive integer $n$, consider its binary representation. Denote by $f(n)$ the number we get after removing all the $0$'s in its binary representation, and $g(n)$ the number of $1$'s in the binary representation. For example, $f(19) = 7$ and $g(19) = 3.$ Find all positive integers $n$ that satisfy $$n = f(n)^{g(n)}.$$ Proposed by usjl
Problem
Source: 2024 Taiwan TST Round 2 Independent Study 2-N
Tags: Taiwan, number theory
Tintarn
28.03.2024 19:52
Of course if $g(n)=k$, then $f(n)=2^k-1$ so we are really asked to find all $k \ge 1$ such that $(2^k-1)^k$ has exactly $k$ ones in binary expansion.
Here $k=1$ yields the solution $n=1$ and $k=2$ yields the solution $n=9$.
If $k$ is odd, then $(2^k-1)^k \equiv -1 \pmod{2^k}$ ends in $k$ binary ones and hence has more than $k$ binary ones in total, unless $k=1$.
Now assume that $k \ge 4$ is even. We will exhibit two blocks of ones both of length almost $k$, which will clearly suffice to obtain a contradiction.
The first block is at the very beginning: Note that $(2^k-1)^k$ is less than $2^{k^2}$ and the difference
\[2^{k^2}-(2^k-1)^k=2^{k^2}\left(1-\left(1-\frac{1}{2^k}\right)^k\right) \le 2^{k^2} \cdot \frac{k}{2^k}=k \cdot 2^{k^2-k}\]by Bernoulli. Hence, there are at least $k-\log_2(k)$ binary ones at the beginning.
On the other hand, consider the last $2k$ binary digits. These are equal to those of $4^k-k2^k+1$. This means that the first $k-\log_2(k)$ digits of this block will again be binary ones.
In total, we have at least $2k-2\log_2(k)+1$ binary ones which is more than $k$ for $k \ge 4$.
In fact, extending this argument to the odd blocks, one can get that of the $k^2$ binary digits of $(2^k-1)^k$ at least $\gg \frac{k^2}{\log k}$ are ones, and by a similar reasoning for the even blocks, the same holds for the zeroes.
Of course we would expect that for large $k$, roughly half of the digits are ones and the other half zeroes.
sami1618
18.08.2024 19:03
It is sufficient to find all $k$ for which $s_2((2^k-1)^k)=k$. The values of $k=1$ and $k=2$ give valid solution $n=1$ and $n=9$ so now assume $k\geq 3$. We have that $$(2^k-1)^k=\sum_{i=0}^{k} (-1)^{k-i} \binom{k}{i} 2^{ki}$$Notice it is very easy to establish the bound $\binom{k}{i}<2^{k-1}$ for all $i$. For example at $k=4$ this binomial evaluates to $$\underbrace{0001|0\texttt{-}100}|\underbrace{0110|0\text{-}100}|0001_2$$Where the bars separate the blocks of $k$ and the negatives have not yet been computed (forgive the notation). After computation we get $$0000|1100|0101|1100|0001_2$$Notice that we can compute the stuff in each under brace separately. It is sufficient to show that the stuff under each underbrace has at least two ones after subtraction (If $k$ is odd then we pair up all the blocks and if $k$ is even we have one remaining as above). It is sufficient then to show that if $n$ is a multiple of $2^{k}$ and if $m$ is smaller than $2^{k-1}$ then $n-m$ has at least two binary ones which is trivial.
Toll
19.08.2024 14:30
in this solution, let $log = log_2$ observe that if $n=2^k$ for some $k$ we need $f(n)^{g(n)} = n = 1^k = 1$ as only solution, so now suppose $n$ is not a power of $2$ Note that now we are given the amount of digits of $n$ in base $2$ as $\lceil log(n) \rceil$, also note that $f(n) = 2^k-1$ for some $k$ and we have $k+g(n) = \lceil log(n) \rceil$, we replace $g(n)$ by $l$ and hence we have $k+l = \lceil log(n) \rceil$, which gives us $k+l > log(n)$, now we can assume $(2^k-1)^l = n$ which gives us $k+l > l\cdot log(2^k-1)$, hence $\frac kl + 1 > log(2^k-1)$ which finally gives us $\frac{log(2^k)}{l}+1 > log(2^k-1)$ which holds for $l=0,1$ always trivially, and for $l=2$ this fails for $k \geq 7$, and for bigger values of $l$, it fails earlier, but now we may note that with $l=0$ we have $n=1$ again as the only solution, for $l=1$ we have $f(n) = n$ where $f(n)$ removes one zero from the binary representation of $n$, which yields no solution, hence we have our bound and must simply check all cases up to $n= 128$ (you can fasten this bash by looking at the bound for bigger values of n and dismissing some of those), but even so, there are only $128$ cases left which is doable by hand and not interesting, the only other solution is $n=9$ which clearly works