Is it possible to multiply two series to get as a result all composite numbers?

Question

I was toying with the following problem:
Is it possible to find two infinite integer sequences $(a_n), (b_n)>0$ such that $\sum_{n=1}^{\infty}\frac{1}{(a_n)^s}\cdot \sum_{n=1}^{\infty}\frac{1}{(b_n)^s}=\sum_{n=1}^{\infty}\frac{1}{(c_n)^s}$ for every $s>1$? Here $c_n$ denotes the $n$-th composite number.
I can show that without loss of generality, $1\in a_n$ and for every $x$ with $\Omega(x)=2, x\in (b_n)$ but this did not help much.

Can someone provide an answer to this problem?

Answer 1

This is the answer of Greg Martin, with the correction of Mark Sapir, and details added.

Write $\Omega(n)$ for the number of prime factors of $n$ (counted with multiplicity), and $\Omega_{\operatorname{odd}}(n)$ for the number of odd prime factors of $n$ (counted with multiplicity), so $\Omega(n) = \Omega_{\operatorname{odd}}(n) + v_2(n)$ (where $v_2$ is the valuation at $2$).

Example. Let $A = \{1,2,4,8,\ldots\} = 2^{\mathbf Z_{\geq 0}}$, and let $$B = \{n\ |\ \Omega(n) = 2\} \cup \{n \text{ odd}\ |\ \Omega(n) \geq 3\}.$$ For $n \in \mathbf Z_{>0}$, the number of representations $n = a \cdot b$ with $a \in A$ and $b \in B$ is $1$ if $n$ is composite, and $0$ otherwise.

Proof. Given $n \in \mathbf{Z}_{>0}$ composite (i.e. $\Omega(n) \geq 2$), define $k \in \mathbf Z_{\geq 0}$ as follows:

1. If $\Omega_{\operatorname{odd}}(n) \geq 2$, set $k = v_2(n)$.
2. If $\Omega_{\operatorname{odd}}(n) = 1$, set $k = v_2(n) - 1$.
3. If $\Omega_{\operatorname{odd}}(n) = 0$, set $k = v_2(n) - 2$.

In cases 2 and 3, note that $k \geq 0$ since $\Omega(n) \geq 2$. Then set $a = 2^k$ and $b = \tfrac{n}{a}$. Then $n = a \cdot b$, and clearly $a \in A$. We also have $b \in B$:

1. In case 1 above, $b$ is odd with $\Omega(b) \geq 2$;
2. In case 2 above, $b$ is even with $\Omega(b) = 2$;
3. In case 3 above, $b = 4$.

This shows existence of the desired decomposition. For uniqueness, assume $n = a \cdot b$ with $a \in A$ and $b \in B$. Let $m = v_2(n)$. Then $\Omega_{\operatorname{odd}}(b) = \Omega_{\operatorname{odd}}(n)$, so

1. If $\Omega_{\operatorname{odd}}(n) \geq 2$, then $\Omega_{\operatorname{odd}}(b) \geq 2$, which by definition of $B$ forces $b$ odd, hence $a = 2^m$.
2. If $\Omega_{\operatorname{odd}}(n) = 1$, then $\Omega_{\operatorname{odd}}(b) = 1$, which by definition of $B$ forces $b$ even and $\Omega(b) = 2$, hence $a = 2^{m-1}$.
3. If $\Omega_{\operatorname{odd}}(n) = 0$, then $\Omega_{\operatorname{odd}}(b) = 0$, which by definition of $B$ forces $b = 4$, hence $a = 2^{m-2}$.

This shows that $(a,b)$ must be as constructed above. Finally, since all elements of $B$ are composite, any integer of the form $n = a \cdot b$ with $a \in A$ and $b \in B$ is composite. $\square$

Answer 2

One way of doing this is by taking $(a_n)=(1,2,4,8,16,\dots)$ and by taking $(b_n)=(4, 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, \dots)$ to consist of $4$ together with the sequence of odd composite numbers. EDIT: as Wlod AA points out, one should also include $2p$ in the $b$ sequences for all odd primes $p$.

This solution can be modified by replacing the special prime $2$ with any other prime; it might well be possible to replace $\{2\}$ with a larger set of primes and generalize the construction.

Answer 3

$\newcommand\N{\mathbb N}$ Define the nondecreasing sequences $(A_n)_{n\in\N}$ and $(B_n)_{n\in\N}$ of subsets of $\N=\{1,2,\dots\}$ recursively as follows: $$A_1:=\{1\},\quad B_1:=\{4\};$$ for $n\ge2$, $$ (A_n,B_n):=\left\{ \begin{aligned} (A_{n-1},B_{n-1})&\text{ if }c_n\in A_{n-1}B_{n-1},\\ (A_{n-1},B_{n-1}\cup\{c_n\})&\text{ if }c_n\notin \N B_{n-1},\\ (A_{n-1}\cup\{a^*_n\},B_{n-1})&\text{ if }c_n\in\N B_{n-1}\setminus A_{n-1}B_{n-1}\\ &\text{ and }a^*_n>\max A_{n-1}, \\ (A_{n-1},B_{n-1}\cup\{c_n\})&\text{ if }c_n\in\N B_{n-1}\setminus A_{n-1}B_{n-1}\\ &\text{ and }a^*_n\le\max A_{n-1}, \end{aligned} \right. $$ where $$a^*_n:=\min(\N\cap(c_n/B_{n-1})).$$

Let now $$A:=\{a_1,a_2,\dots\}:=\bigcup_{n\in\N}A_n,\quad B:=\{b_1,b_2,\dots\}:=\bigcup_{n\in\N}B_n,$$ where $a_1<a_2<\cdots$ and $b_1<b_2<\cdots$.

Then the product of $A$ and $B$ equals $C:=\{c_1,c_2,\dots\}$, where $A,B,C$ are considered multisets. That is, for each $c\in C$ there is a unique pair $(a,b)\in A\times B$ such that $c=ab$.

The identity in question now follows.

---

For an illustration, note that, in particular, $$A_{50}=\{1, 2, 4, 8, 16\},$$ $$B_{50}=\{4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 27, 33, 34, 35, 38, 39, 45, 46, \ 49, 51, 55, 57, 58, 62, 63, 65, 69\}.$$