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

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?

• Can you point me towards a formula which defines what $c_n$ in the multiplied series is given arbitrary $a_n$ and $b_n$? Usually, I see the multiplication of series as a power series thing. – Zemyla Feb 2 '20 at 18:38
• @Zemyla: $a_i^sb_j^s=(a_ib_j)^s$, so $c_n=a_ib_j$ for some $i,j$. The question is equivalent to asking: is it possible to find $(a_n)$, $(b_n)$ such that every composite number $c$ has exactly one factorization of the form $c=a_ib_j$, while prime numbers (and $1$) have no factorizations of that form? – Greg Martin Feb 2 '20 at 20:48
• Using @GregMartin 's characterization of the problem, we can rewrite further: write $X = \mathbb{N}^\infty$ to denote the set of all eventually-zero sequences of natural numbers (where we include $0$). Can we find $A, B \subset X$ such that $A + B = X \backslash (\{e_i\} \cup \{(0)\})$, where $e_i$ is the sequence with $1$ in the $i$th position and $0$ everywhere else, and where we think of the sum as a multiset (in other words, so there is no repetition)? – user44191 Feb 2 '20 at 21:41

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$$

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.

• What about 6? Am I missing something? – Wlod AA Feb 2 '20 at 21:08
• @KonstantinosGaitanas, actually, $\ 2^n\cdot 4\,=\,2^{n+2}.$ – Wlod AA Feb 2 '20 at 23:15
• Just add all numbers $2p$ to $(b_n)$ where $p$ is an arbitrary odd prime. Right? – user6976 Feb 3 '20 at 2:23

$$\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 and $$b_1.

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\}.$$

• The illustration strongly suggests $A = \{2^i\}, B = \{4\} \cup \{2p\} \cup C$, where $C$ is the set of odd numbers with at least 2 (not necessarily distinct) prime factors. – user44191 Feb 3 '20 at 3:57
• Even more simply: $A=\{2^i\}$, $B=\{2p\} \cup \{\text{odd composite numbers}\}$. Then the proof is simple: any composite number $c$ is of the form $2^n x$, where $x$ is odd. If $x$ is prime, we choose $a=2^{n-1}$, $b=2x$; if $x$ is composite, we choose $a=2^n$, $b=x$, and in either case $c=ab$. – Matt F. Feb 3 '20 at 8:39