A representation of odd numbers.

Question

The problem asks to prove: $$2\mathbb{Z}+1=\{x\in\mathbb{Z}\ |\ \exists\ n\in\mathbb{N}\ s.t. |x|=\frac{d(n^2)}{d(n)}\}.$$ where $d(n)$ is the function that counts the number of positive divisors of $n$.

I see that if the prime factorization of $n=p_1^{m_1}\dots p_k^{m_k}$, then $d(n)=\prod_{i=1}^k(m_i+1)$, therefore reduce the problem to $$2\mathbb{Z}+1=\{x\in\mathbb{Z}|\exists m_1,\dots,m_k\in\mathbb{N} , s.t. |x|=\prod_{i=1}^k\frac{2m_i+1}{m_i+1}\}.$$ But I have no idea how to proceed, please help.

Answer 1

If $$|x|=\prod_{i=1}^k\frac{2m_i+1}{m_i+1}\tag 1$$ then $$|x|\prod_{i=1}^k(m_i+1)=\prod_{i=1}^k(2m_i+1)\equiv 1\pmod 2$$ hence $x\not\equiv 0\pmod 2$ so that $x\equiv 1\pmod 2$, that's $x$ is odd.

Conversely, given $x$ an odd integer, we have to show that there exists $m_i\in\Bbb N$ satisfying $(1)$. Write $|x|=2^kq-1$ with $n\in\Bbb N$ and $2\nmid q$ and let $a=2^k-1$. If $m_i=(a|x|-1)/2^i$ then $m_i\in\Bbb N$ for $1\leq i\leq k$ and $$|x|=q\prod_{i=1}^k\frac{2m_i+1}{m_i+1}$$ and since $q<|x|$ and $q$ is odd, the assertion follows by induction on $q$.

---

I get the value $a=2^k-1$ in this manner.

Consider the recurrence $m_{i+1}=m_i/2$ and impose $2m_1+1=a|x|$ and $m_k+1=aq$ so that $$|x|=q\prod_{i=1}^k\frac{2m_i+1}{m_i+1}$$ Then $m_1=2^{k-1}m_k$ from which we get $$a=\frac{2^k-1}{2^kq-|x|}$$ Taking $q$ such that $|x|=2^kq-1$ gives $a=2^k-1$.

Answer 2

Below is a somewhat different approach.

---

First consider, for any integers $a,\,b$, we have $a=\frac ab\cdot b$. For $\frac ab$ to be of the form $\frac{2m+1}{m+1}$, we take $b=\frac{a+1}2$.

So we are led to consider the sequence $$a_0(a)=a,a_1(a)=\frac{a_0(a)+1}2,\cdots,a_{n+1}(a)=\frac{a_n(a)+1}2,\cdots.$$

Now an easy induction shows that $a_n(a)=\frac{a+1+2+\cdots+2^{n-1}}{2^n}=\frac{a+2^n-1}{2^n}$. Hence, if $a$ is divisible by $2^n-1$, say $a=(2^n-1)k$, then $a_n(a)=(2^n-1)\frac{k+1}{2^n}$.

Then, for any odd number $a$, we have $$a=\frac{(2^n-1)a}{2^n-1}=X\cdot\frac{a_n}{2^n-1},$$ where $X=\prod_{i=0}^{n-1}\frac{a_i}{a_{i+1}}$, $a_i=a_i((2^n-1)a)$, and the previous discussion shows that $\frac{a_n}{2^n-1}=\frac{a+1}{2^n}$

We can choose $n$ to be the greatest $\ell$ such that $2^\ell$ divides $a+1$. Then $\frac{a+1}{2^n}$ is an odd integer, and we have reduced from $a$ to a smaller odd number $\frac{a+1}{2^n}$, so an induction concludes the proof.

Also, observe that if $a_n$ is an integer, then so is $a_{n-1}=2a_n-1$. This justifies that $X$ is really of the form we want.

---

This is a rewrite of the previous version, and appears more intuitive I hope.