Permutations and Combinations - divisors of a number Question:
A number $n$ is given as $2^{31}3^{19}$. Find the number of divisors of $n^2$ which are less than $n$ and not a divisor of $n$.
Well the total number of divisors of a number is given by adding one to the power and multiplying them. Not sure how I would proceed for this question however. Any hint?
 A: Hint: The exponent of 2 or 3 (or both) in the divisors of $n^2$ which do not divide $n$ must be greater than 31 and 19, respectively.
A: you want the divisors $d$ of $2^{62}3^{38}$ that are smaller than $2^{31}3^{19}$ and satisfy one of those properties (at most can be met at a time)
$2^{32}$ divides $d$.
$3^{19}$ divides $d$.
For the first notice you want $2d$ to be a divisor of $2^{31}3^{19}$ that is smaller than $3^{19}$.  So classify according to the exponent of $3$ in the factorization of $d$.
Let $d=2^j3^k$. Then $2d=2^{j+1}3^k$. so you want $j+1\leq 31$ so that $2^{j+1}\leq3^{19-k}$. How many $j$ are there for a given $k$?. Take log on both sides and you want $(j+1)\log(2)\leq(19-k)\log3\iff j\leq \frac{\log(3)(19-k)}{\log(2)}-1$
You just have to be carefull this number does not exceed $31$, but it doesn't.
Thus what you want is $\sum\limits_{k=0}^{18}\lfloor\frac{\log(3)(19-k)}{\log(2)}-1\rfloor$.
You have to do the same thing for the second case (but you have to be carefull because when $k$ is $0$ it is possible the bound will exceed $19$, so you need to do a little careful casework.
