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?

  • $\begingroup$ 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. $\endgroup$ – Zemyla Feb 2 '20 at 18:38
  • 3
    $\begingroup$ @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? $\endgroup$ – Greg Martin Feb 2 '20 at 20:48
  • $\begingroup$ 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)? $\endgroup$ – 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.

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

  • $\begingroup$ 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. $\endgroup$ – user44191 Feb 3 '20 at 3:57
  • $\begingroup$ 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$. $\endgroup$ – Matt F. Feb 3 '20 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.