# Thread: Functions

1. ## Functions

Let $d:\mathbb{N}\rightarrow\mathbb{N}$ where$d(n)$ is the number of natural divisors of $n$. Prove that for all $n$, $d(2^{n-1})=n$. (I formulated this conjecture myself. So, if it's nonsensical let me know.)

Induction:

Base: let $n=1$. Then $d(2^{1-1})=1$.

Now assume for some $k\in\mathbb{N}$, $d(2^{k-1})=k$. Then the number of natural divisors of $2^{k-1}$ can be listed as follows:
$2^0,2^1,2^2,...,2^{k-1}$. Multiplying each divisor by 2 gives the list $2^1,2^2,..,2^{k-1},2^{(k+1)-1}$. But these are the divisors of $2^{(k+1)-1}$ without​ $1$. Thus $d(2^{(k+1)-1})=d(2^{k-1})+1=k+1$ as desired.
Therefore by the principle of induction, $d(2^{k-1})=k$.

2. ## Re: Functions

Originally Posted by VonNemo19
Let $d:\mathbb{N}\rightarrow\mathbb{N}$ where$d(n)$ is the number of natural divisors of $n$. Prove that for all $n$, $d(2^{n-1})=n$. (I formulated this conjecture myself. So, if it's nonsensical let me know.)
It is far from nonsensical! In fact it is well known.
If ${\large n=2^{p}\cdot3^{q}\cdot5^{r}\cdot7^{s}\cdot11^{t}}$ then $d(n)=(p+1)\cdot(q+1)\cdot(r+1)\cdot(s+1)\cdot(t+1 ).$