Properties of Prime number less than or equal to $n$ For $n \geq 3$,let $\tau_n$ denotes the set of all primes less than or equal to $n$ and $l_A = \sum_{p \in A}p^k$ for some $k \in \mathbb N$, where $A \subseteq \tau_n$. Do there exist $A_1, A_2 \subseteq \tau_n$ with $l_{A_1}$ and $l_{A_2}$ are sum of prime powers of $A_1$ and $A_2$, respectively satisfy the following:

*

*$l_{A_1}$ and $l_{A_2}$ are atmost $n$;


*$A_1\cap A_2 = \varnothing$;


*$p \in \tau_n \setminus A_1$, we have $l_{A_1} + p > n;$


*$p \in \tau_n \setminus A_2$, we have $l_{A_2} + p > n$.
I have tried to solve this but at the end of the proof, I stuck.
For $3 \leq n \leq 9$ and $i \in \{1, 2\}$, consider $l_{A_i}$ is the sum of all primes belongs $A_i$  and for $n = 10$, $l_{A_1} = 2^2 + 5$ and $l_{A_2} = 3 + 7$, we can see below
$$n =  3, A_1 = \{2\}, A_2 = \{3\}; $$
$$n =5, 6, A_1 = \{2, 3\}, A_2 = \{5\};$$
$$n =7, A_1 = \{2, 5\}, A_2 = \{7\};$$
$$n =8, A_1 = \{3, 5\}, A_2 = \{7\};$$
$$n =9, A_1 = \{2, 7\}, A_2 = \{3, 5\};$$
$$n =10, A_1 = \{2, 5\}, A_2 = \{3, 7\}.$$
Now we assume that $n \geq 11$ and first suppose that $n = p$ for some prime $p$. Consider $A_1 = \{ p\}$ and $l_{A_1} = p$. Further, we construct $A_2$ and $l_{A_2}$ which satisfy the given condition with $A_1$. In view Theorem $1$ (see https://arxiv.org/pdf/0907.5232.pdf), choose $p_1$ is the second largest element in $\tau_{n}$ and it lies between $\lfloor \frac{p}{2} \rfloor$ and $p - 1$. Again choose $p_2$ is the largest element in $\tau_{n_2}$, where $n_1 = n$ and $n_2= n_1 - p_1$. Continue this process, we get  $p_{i}$ is the largest element in $\tau_{n_i}$, where $n_i = n_{i -1} - p_{i - 1}$. Note that $p_{i} + p_{i - 1} \leq n_{i -1}$ gives $p_{i} + p_{i - 1} + \cdots + p_1 \leq n$. After finite number of steps this process will terminate and we get $n_{k + 1} \in \{0, 1\}$ and $T_2 = \{p_k, p_{k - 1}, \ldots, p_1\}$ as cardinality of $\tau_n$ is finite, otherwise there exists $p_{k+1} \leq n_k - p_k$. For any $p' \in \tau_n \setminus T_2$, we have $p' \geq n_i$ for some $i$, where $2 \leq i \leq k+1$. Consequently, we get $p' + p_{i-1} + p_{i-2} + \cdots + p_1 > n$ and then we consider $l_{A_2} = \sum_{j = 1}^{k}p_j$. Also, $A_1 \cap A_2 = \varnothing$. Thus. the result holds whenever $n$ is prime. In a similar way, one can prove the result whenever $n$ is of the form  $p + 1$ and $p+2$ for some prime $p$.
Now we assume that $n$ is not of the form $p$ or $p + 1$, where $p$ is a prime. We prove the result by induction on $n$ and suppose that the result is true for all $k$ less than or equal to $n - 1$.  By  Theorem 1 (see https://arxiv.org/pdf/0907.5232.pdf), choose $p_1$ and $q_1$ be the largest and second largest elements in $\tau_n$. Note that $2 \leq n-p_1 < n-q_1 < n$. By induction hypothesis, there exists $A_1', A_2' \subseteq \tau_{n-q_1}$, $l_{A_1'}$ and $l_{A_2'}$ satisfy the given conditions. Consider $A_1 = A_1' \cup \{p_1\}, l_{A_1}= l_{A_1'} + p_1$ and $A_2 = A_2' \cup \{q_1\}, l_{A_2}= l_{A_2'} + q_1$.  Clearly, $A_1 \cap A_2 = \varnothing$. Further, let $p' \in \tau_n \setminus A_1$. By (iii), $l_{A_1'} + p' > n - q_1$ give $l_{A_1'} + p_1 + p' >l_{A_1'} + q_1 + p' > n$. This implies that $l_{A_1} +p' > n$. If $p' \in \pi_n \setminus A_2$, then $l_{A_2'} + p' > n - q_1$ wo obtain $l_{A_1} +p' > n$. Since $l_{A_2'} \leq n-q_1 < \lfloor \frac{n}{2} \rfloor$ gives $l_{A_2} \leq n$.
Further, I am stuck here, how to prove $l_{A_1}$ is at most $n$.
I am so thankful to you for any kind of help.
 A: This looks like a very challenging problem because you will always have a lot of small primes that are not in one of the sets. Specifically, the prime number 2 can be in at most one of $A_1$ or $A_2$, meaning that (without loss of generality) $2\notin A_1$ so your restrictions in $l_{A_1}$ mean that $l_{A_1}\leq n$ but $l_{A_1}+2 > n$. This means you need $l_{A_1}\in \{n,n-1\}$. Can you choose primes from the set to reach exactly one of these two numbers? And having done so, the same problem holds for $A_2$. Have you tried looking at variants of Goldbach's conjecture?
This issue is probably why your inductive proof is hard to finish. Suppose that (in your notation) the inductive case for $A_1',A_2'\subseteq \tau_{n-q_1}$, we have that $l_{A_1'}\geq n-q_1-1$ (without loss of generality, this holds by the reasoning above, since we can choose $A_1'$ to be the set that does not contain $2$). Then if you set $A_1=A_1'\cup\{p_1\}$, since $p_1 > q_1$ (and since they are both primes, $p_1\geq q_1+2$), you have $l_{A_1} \geq n -q_1-1 + p_1 \geq n+1$.
You could try adding the larger prime to the set with a smaller sum. What I mean is, assume that $l_{A_1'}\leq l_{A_2'}$. Then set $A_1=A_1'\cup\{p_1\}$ and $A_2=A_2'\cup\{q_1\}$. But this doesn't solve the problem: it could be that $2\notin A_1'$ and $2\notin A_2'$, meaning that $l_{A_1'} \geq n-q_1-1$, giving the same problem.
More generally, consider the smallest prime $p$ such that $p\leq p_1-q_1$ and $p\notin A_1'$. This provides a lower bound on $l_{A_1'}$, since we need $l_{A_1'}+p > n-q_1$. Then if $A_1=A_1'\cup\{p_1\}$, we have
$$l_{A_1}=l_{A_1'}+p_1 > n -q_1- p + p_1\geq n$$
and so the set $A_1$ will not work. If you want your inductive proof to work, you would need to show that you can choose one of the sets such that it contains all primes $p\leq p_1-q_1$, which seems quite difficult!
One thing to try could be using your technique of selecting the largest prime not exceeding the bound, but do both sets at once. That is, build the sets $A_1$ and $A_2$ one prime at a time, such that if the current values of the sums satisfy $l_{A_1}\leq l_{A_2}\leq n$, then choose the largest prime $p$ such that $p\leq n - l_{A_1}$, and add $p$ to $A_1$ (if $l_{A_2}\leq l_{A_1}$, add $p$ to $A_2$).
The problem with this approach (and your original approach) is to ensure that  you don't select a prime "too early" in some sense. That is, if you end up with $n-l_{A_1} = 5$ but you've already put $2$, $3$, and $5$ into $A_2$, then the proof fails. You would need to show that there is always some prime $p\leq n- l_{A_{\{1,2\}}}$ that hasn't been selected yet.
