# Product of odd evil numbers over the product of odd odious numbers

im working on a problem where im confronted with this fraction $\frac{3 \cdot 5\cdot9\cdot15\cdot17\cdot23\cdot27\cdot29 ...}{1\cdot7\cdot11\cdot13\cdot19\cdot21\cdot25\cdot31 ...}$ . I found that the product in the numerator is the product over all odd evil numbers and the product in the denominator is the product over all odd odious numbers. Im especially interested in the sequence $\frac{3}{1}=3$ , $\frac{3\cdot5}{1\cdot7}=\frac{15}{7}$ , $\frac{3\cdot5\cdot9\cdot15}{1\cdot7\cdot11\cdot13}=\frac{2025}{1001}$ , ... where $2^n$ factors are put together. Its easy to see that this series converges monotonically decreasing to 2 but i have no idea how to proof that. Can somebody help me ?

Note: an odious number is a nonnegative integer which has an odd number of $1$s in its binary expansion. An evil number is one which has an even number of $1$s.

Edit: Because some people are a bit suspicious about odious and evil numbers i want to give an alternative formulation of my problem. Consider the following recursive function: $f(n)=(-1)\cdot f(l)$ where $n=2^k+l$ and $l>0$ is the unique representation of n as the maximal power of 2 with a remainder $0\le l \lt 2^k$ and $f(1)=(-1)^k$ where $n=2^k$ which is defined on non negative odd integers. Im looking for the value of the product $\lim_{N->\infty}\prod_{n=1}^{2^N}{(2\cdot n-1)^{-f(n)}}$ . This is the way i came to this fraction given above.

Edit2: I think i found another representation without a proof that these are equal

$\frac{3 \cdot 5\cdot9\cdot15\cdot17\cdot23\cdot27\cdot29 ...}{1\cdot7\cdot11\cdot13\cdot19\cdot21\cdot25\cdot31 ...}=(1+\frac{2}{1})\cdot(1-\frac{2}{7})\cdot(1-\frac{2}{11})\cdot(1+\frac{2}{13})\cdot(1-\frac{2}{19})\cdot(1+\frac{2}{21})\cdot(1+\frac{2}{25})\cdot(1-\frac{2}{31})...$

It seems to me that the rule of building this product is $\prod_{n=1}^{\infty}{(1+\frac{(-1)^{m_n}\cdot2}{o_n})}$ where $m_n$ is the n-th element of the Thue–Morse sequence and $o_n$ is the n-th element of the odd odious number sequence. Maybe this looks familiar to somebody

• What is an evil/odious number ??? – Nicolas FRANCOIS Aug 12 '18 at 16:46
• Without a clear definition of the product series, this problem simply cannot be solved and should be closed. – David G. Stork Aug 12 '18 at 17:10
• An odious number is a nonnegative number that has an odd number of 1s in its binary expansion. The first few odious numbers are therefore 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, $\cdots$. I guess evils are those that have even number of 1s – ab123 Aug 12 '18 at 17:11
• According to Wikipedia John Horton Conway called the numbers "odious"( for "odd") and "evil" (for "even"). – saulspatz Aug 12 '18 at 17:33
• A little computer experimentation suggests that if w define $s_k = 0$ if $2k-1$ is evil and $s_k=1$ if $2k-1$ is odious, $k=1,2,3.\dots$ then we get the complement of the Thue-Morse sequence that is $0$ when Thue-Morse has $1$ and vice-versa. I don't have time to try to prove this now, and I don't know if it helps to solve the problem. – saulspatz Aug 12 '18 at 18:12

## 2 Answers

This follows easily from corollary 2.4(b) of "More Infinite Products: Thue-Morse and the Gamma function" (arXiv:1709.03398) by Jean-Paul Allouche, Samin Riasat, and Jeffrey Shallit. The statement there is

$$\prod_{n \ge 0} \left( {4n+1 \over 4n+3} \right)^{(-1)^{t_n}} = {1 \over 2}$$

where $t_n$ is the Thue-Morse sequence, i. e. $t_n$ is the sum of the bits of the binary expansion of $n$. Your desired result follows by taking the reciprocal of both sides to get

$$\prod_{n \ge 0} \left( {4n+3 \over 4n+1} \right)^{(-1)^{t_n}} = 2$$

and some rewriting on the left-hand side to get a product over odd numbers.

• I didn't even realize that you'd posted this. Some time ago, I started writing an answer explaining why I thought that Shallit's earlier paper was relevant, though I couldn't solve the problem, but as I was typing I started chipping away at it, until I solved it. Now I see that sometime during that process, you posted a solution. Sigh. – saulspatz Aug 13 '18 at 15:08

I haven't solved this in detail, but I'm sure I know how to go about it. There are some facts about evil and odious numbers that I have found experimentally by computer. Once these are verified, they will give a complete solution.

Look at "On Infinite Products Associated with Sums of Digits," by J.O. Shallit. For $k\geq2$ a positive integer, the author defines $s_k(n)$ to be the sum of the digits of the nonnegative integer $n$ when written in base $k$. Theorem $3$ in the paper is

Let $k$ be an even positive integer and let $m_i, n_i$ be such that $2i\leq m_i,n_i<2(i+1),$ and $s_k(m_i)\equiv0\pmod2$ and $s_k(n_i)\equiv1\pmod2.$ Then $$\prod_{i=0}^{\infty}{1+m_i\over 1+n_i}={\sqrt{k}\over k}$$

If we let $k=2,$ and let $m_i$ and $n_i$ be the evil and odious integers, respectively, this gives $$\prod_{i=0}^{\infty}{1+m_i\over 1+n_i}={1\over \sqrt2} \tag{1}$$

I haven't proved that the growth conditions are satisfied, just verified them numerically for $0\leq i<2^{20},$ but I would expect that it isn't very hard to do this, using the Thue-Morse sequence.

Notice that if instead of running over the evil and odious numbers, $m_i$ and $n_i$ ran over the even evil and odious numbers, we would have the reciprocal the product we want. Therefore, let us divide the product in $(1)$ by $$\prod_{i=0}^{\infty}{1+m_i'\over 1+n_i'}\tag{2}$$ where $m_i',n_i'$ run over the odd evil and odious numbers, respectively. Say $m_i'=2c_i+1, n_i'=2d_i'+1,$ so that $${1+m_i'\over1+n_i'}={1+c_i\over1+d_i}\tag{3}$$

The $c_i$ are precisely the odious integers, and the $d_i$ are precisely the even integers, so that the product in $(2)$ is the reciprocal of the product in $(1)$ or $1/\sqrt2,$ and $(1)$ divided $(2)$ is $1/2,$ which is just what we want. That the $c_i$ and $d_i$ are as claimed follows from the fact that $2n+1\mapsto n$ is a bijection from the odd positive integers onto to nonnegative integers, and the recurrence $t_{2n+1}=1-t_n$ for the Thue-Morse sequence.

I'll leave the growth conditions for you to verify.

I should mention that in the proof of Theorem $1$, Shallit appeals to Prouhet's solution of the Prouhet-Tarry-Escott problem, which apparently depends on the Thue-Morse sequence.