Let $S$ be a set of positive integers, such that $n \in S$ if and only if $$\sum_{d|n,d<n,d \in S} d \le n$$Find all positive integers $n=2^k \cdot p$ where $k$ is a non-negative integer and $p$ is an odd prime, such that $$\sum_{d|n,d<n,d \in S} d = n$$
Problem
Source: 2019 China TST Test 3 P2
Tags: Divisors, number theory
23.03.2019 23:13
The answer seems to be all Mersenne primes(?) Claim 1: $p^k \in S$ for any prime $p$. Proof: First note $1 \in S,$ then $p \in S$, and induct on the exponent. Claim 2: Let $k_0$ satisfy $2^{k_0} - 1 <p \le 2^{k_0+1}-1$. Then $2^kp \not \in S \iff k_0 | k-1$ and $k-1 \ne 0$. Proof: Write $k = sk_0 + r$ where $0 \le r < k_0$ and induct on $s$, using a size argument. The conclusion is that equality is reached iff $k=k_0, p=2^{k_0+1}-1$.
24.03.2019 00:01
@above I think you made a slight mistake in the case where $p$ is a Mersenne prime The answer is whenever $p = 2^{x+1} - 1$ (a Mersenne prime) for some $x > 1$ and $k = c(x+1) - 1$ for some $c \in \mathbb{N}.$ Notice that it's clear that $2^k \in S$ for all nonnegative $k$. Now, let's fix a random prime $p$. which is in the interval $(2^x - 1, 2^{x+1} - 1]$ for some $x > 0.$ Then note that $p, 2p, \cdots, 2^{x-1}p \in S$ clearly. If $p \neq 2^{x+1} - 1$, then $2^x p \notin S.$ Then, we have that since $(2^x + 1) (p) > 2^{2x} -1$ but is $< 2^{2x+1} - 1,$ we know that $2^{x+1}p, 2^{x+2} p, \cdots, 2^{2x-1}p$ are all in $S$, but $2^{2x} p$ is not. Continuing in this manner and noting that $(2^{kx} + 2^{(k-1)x} + \cdots + 2^x + 1)(p) \in (2^{(k+1)x} - 1, 2^{(k+2)x}-1),$ we can inductively obtain that $2^xp, 2^{2x}p, 2^{3x}p, \cdots$ are exactly the numbers of the form $2^kp$ which are not in $S.$ It's now immediate that there are no solutions in this case. Now, we only have to deal with the case where $p = 2^{x+1} - 1,$ i.e., $p$ is a Mersenne prime. Then, notice that $p, 2p, \cdots, 2^xp \in S.$ However, then we have $2^{x+1}p \notin S,$ and so hence $2^{x+2}p, 2^{x+3}p, \cdots, 2^{2x+1}p \in S.$ But then, $2^{2x+2}p \notin S,$ and so continuing in this fashion and using the identity $(1 + 2^{x+1} + \cdots + 2^{r(x+1)})(2^{x+1} - 1) = 2^{(r+1)(x+1)} - 1 = 1 + 2 + \cdots + 2^{rx + r + x},$ we obtain that all equality cases are when $p = 2^{x+1} - 1$ and $k = c(x+1) - 1.$
25.03.2019 05:53
It is clear $2^n \in S$, and notice: if $p\geq 2^{k+1}-1$, then divisors of $p2^k$ are all in $S$. Two things are worth to be considered: (1) $p, 2p, \cdots, p2^l \in S$, $p2^{l+1} \notin S$; (2) $2^l-1\leq p\leq 2^{l+1}-1$. We consider (2): if $2^l-1\leq p< 2^{l+1}-1$, we can find $p, 2p, \cdots, p2^{l-1} \in S$, $p2^{l} \notin S$, and $p2^{l+1}, p2^{l+2}, \cdots, p2^{2l-1} \in S$, $p2^{2l} \notin S$. We claim: $p2^{l}, p2^{2l}, \cdots, p2^{[\frac{k-1}{l}]l} \notin S$, and other divisors of $p2^k$ are all in $S$. Then, $$2^{k+1}=p+p\frac{2^{(s+1)l}-2^l}{2^l-1},$$$sl\leq k-1$, $(s+1)l\geq k$. If $2^l-1< p< 2^{l+1}-1$, then $(s+1)l<k+1$, $(s+1)l=k$, it follows that $$p=\frac{(2^l-1)(2^{k+1}-1)}{2^k-1}.$$Since $gcd(2^k-1, 2^{k+1}-1)=1$, we have $2^k-1\mid 2^l-1$, then $l\geq k$. $p, 2p, \cdots, p2^{k-1} \in S$. We can get: $p=2^{k+1}-1$ or $p=2^l-1$, where $l\mid k+1$.
11.05.2020 12:53
Nice problem! Here's my solution: Let $a=\lfloor \log_2(p+1) \rfloor-1$, and note that since $p \geq 3$, so $a \in \mathbb{N}$. Let $$f(n)=\left(\sum_{d \mid n,d<n,d \in S} d \right)- n$$so the given condition is $n \in S \Leftrightarrow f(n) \leq 0$. Also, we get $f(n) \leq \sigma(n)-2n$, where $\sigma(n)$ is the sum of all positive divisors of $n$. Then we have $$f(2^m) \leq \sigma(2^m)-2^{m+1}=-1 \Rightarrow 2^m \in S \quad \forall m \geq 0$$Then $1 \in S$, and so $f(p)=1-2p<0$, i.e. $p \in S$. Now, using $2^{a+1}-1 \leq p \leq 2(2^{a+1}-1)$, we have the following key claim- CLAIM For $r \in \mathbb{N}$, we have $2^rp \not \in S$ if and only if $a+1 \mid r$. (Proof) Write $r=x(a+1)-y$ where $0 \leq y \leq a$ and $x \in \mathbb{N}$. We proceed by induction on $x \geq 1$. For $x=1$ and $y>0$, we have $r \leq a$, which gives $$f(2^rp) \leq \sigma(2^rp)-2^{r+1}p=2^{r+1}-p-1 \leq 2^{a+1}-(p+1) \leq 0$$so $2^rp \in S$ for $r \leq a$. Then, $x=1$ and $y=0$ gives $$f(2^rp)=f(2^{a+1}p)=\sigma(2^{a+1}p)-2^{a+2}p=2^{a+2}-(p+1)>0$$which means that $2^{a+1}p \not \in S$. This proves the base case. Now suppose the result is true for some $x$, and let $r=(x+1)(a+1)-y$. First suppose $y>0$, so that $r \leq (x+1)(a+1)-1$. Then, with the help of the inductive hypothesis, we get that \begin{align*} f(2^rp) &\leq \sigma(2^rp)-2^{r+1}p-(2^{a+1}p+2^{2(a+1)}p+ \dots +2^{x(a+1)}p) \\ &=2^{r+1}-1-p-\frac{2^{a+1}(2^{x(a+1)}-1)p}{2^{a+1}-1} \\ & \leq (2^{(x+1)(a+1)}-1)-\frac{(2^{(x+1)(a+1)}-1)p}{2^{a+1}-1} \\ &=(2^{(x+1)(a+1)}-1) \left(1-\frac{p}{2^{a+1}-1} \right) \leq 0 \\ \end{align*}So $2^rp \in S$ when $y>0$. Finally, if $y=0$, then the previous fact and the inductive hypothesis together imply that \begin{align*} f(2^rp) &=\sigma(2^rp)-2^{(r+1)p}-(2^{a+1}p+2^{2(a+1)}p+ \dots +2^{x(a+1)}p) \\ &=2^{r+1}-1-p-\frac{2^{a+1}(2^{x(a+1)}-1)p}{2^{a+1}-1} \\ &=(2^{r+1}-1)-\frac{(2^{(x+1)(a+1)}-1)p}{2^{a+1}-1} \\& \geq (2^{(x+1)(a+1)+1}-1)-2(2^{(x+1)(a+1)}-1)=1 \\ \end{align*}Thus, $2^{(x+1)(a+1)}p \not \in S$, completing the induction step. $\Box$ Return to the problem at hand. The problem asks us to find all $k$ and $p$ so that $f(2^kp)=0$. This means that equality must hold at all $\leq$ signs in the proof of the Lemma above. But the last equality holds only if $p=2^{a+1}-1$ (in the proof of both base case and the inductive step). Also, the second equality (in both proofs) holds when $y=1$, i.e. $r+1=x(a+1)$ for some positive integer $x$. Since the first equality (in both proofs) trivially holds by our Lemma, we have that all solutions are of the form $k=x(a+1)-1$ and $p=2^{a+1}-1$ for $a,x \in \mathbb{N}$. $\blacksquare$
08.01.2022 23:45
Fix $p$. Choose the least $t \in \mathbb Z_{\ge 0}$ such that $2^{t+1} > p+1$. Let $X = \{2^k \cdot p : k \in \mathbb Z_{\ge 0}\}$ and $Y \subseteq X$ for which problem condition is true. Claim: The set $X \setminus S$ is precisely $\{2^{kt} \cdot p : k \in \mathbb Z_{>0} \}$. Proof: Suppose $X = \{2^{k_1} \cdot p, 2^{k_2} \cdot p,\ldots\}$. We will show $k_i = i \cdot t$ using strong induction on $i$. Note that $$\sigma(2^k \cdot p) = p \cdot 2^{k+1} + (2^{k+1} - (p+1))$$So $k_1 = t$ just follows by definition of $t$. Now assume $k_i = i \cdot t ~ \forall ~ 1 \le i \le m$ and we want $k_{m+1} = t(m+1)$. Observe $k_{m+1} \in \mathbb Z_{\ge 0}$ is the least satisfying \begin{align*} 2^{k_{m+1}} + 1 > (p+1) + \sum_{i=1}^m 2^{k_i} \cdot p = (p+1) + p \cdot \sum_{i=1}^m 2^{k_i} & \\ \iff 2^{k_{m+1} + 1 - mt} > \frac{p+1}{2^{mt}} + p \left(\sum_{i=1}^m \frac{1}{2^{t(m-i)}} \right) & \qquad \qquad (1) \end{align*}As $2^t \le p+1$, thus \begin{align*} \text{LHS} \ge \frac{p+1}{(p+1)^m} + p \left( \sum_{i=1}^m \frac{1}{(p+1)^{m-i}} \right) = p+1 \ge 2^t \qquad \qquad (2) \end{align*}which implies $k_m > t(m+1) - 1$. Now as $2^{t+1} \ge p+3$, so letting $2^t = z \ge \frac{p+3}{2}$ we have \begin{align*} \text{LHS} &< \frac{p+1}{z^m} + p \left( \sum_{j=0}^{\infty} \frac{1}{z^j} \right) = \frac{p+1}{z^m} + p \left( \frac{1}{1 - \frac{1}{z}} \right) \le \frac{p+1}{z^m} + p \cdot \frac{p+3}{p+1} < 1 + (p+2) \le 2^{t+1} \end{align*}Note second last inequality doesn't hold for $m=1$, but that case is easy. It follows that $k_m \le t(m+1)$, so we conclude that $k_{m+1} = t(m+1)$, proving our claim. $\square$ Look at $(1),(2)$ again. Note that $y$ is precisely the set of $k_{m+1} \in [tm, t(m+1))$ for which equality in $(1)$ holds. If we focus on $(2)$ again, we obtain this happens iff $2^t = p+1$ and $k_{m+1} = t(m+1) - 1$. Thus we have our solution set! $\blacksquare$