Problem 3

For any positive integer

n

, let

d(n)

denote the number of positive divisors of

n

(including

1

and

n

itself). Determine all positive integers

k

such that

\frac{d(n^2)}{d(n)}=k

for some

n

Step 5 of 6: Factor the quotient

Previous step Next step

In plain words

The quotient telescopes into admissible factors.

\frac{k}{y}=\prod_{j=0}^{t-1}\frac{2^{j+1}x+1}{2^j x+1}

Detailed analysis

Each factor on the right has the form $(2a+1)/(a+1)$ , with $a=2^j x$ . By induction, $y$ is also a product of factors of this form, so $k=y(k/y)$ has the required representation.