11
$\begingroup$

Let $d_1, d_2, \cdots d_k$ be all the factors of a positive integer '$n$' including $1$ and $n$. Suppose $d_1 + d_2 + d_3+\cdots+d_k = 72$. Then find the value of $\frac{1}{d_1}+\frac{1}{d_2}+\cdots + \frac{1}{d_k}$.

Attempt: Consider, $d_1, d_2, \cdots d_k$ are the factors of $n$ ascending order. Then

$d_1d_k=n$, $d_2d_{k-1}=n$, $\cdots$, $d_kd_{1}=n$ ............... (1)

Assume, $\frac{1}{d_1}+\frac{1}{d_2}+\cdots + \frac{1}{d_k}=P$ Then $\frac{n}{d_1}+\frac{n}{d_2}+\cdots + \frac{n}{d_k}=nP$ i.e $d_k+d_{k-1}+\cdots +d_2+d_1=nP$ (using 1) i.e $72=nP$, or $P=72/n$.

Problem: I have considered that number of divisors of $n$ are even as every divisor $d$ of $n$ has a twin divisor $n/d$. But it is not true if $n$ is a perfect square i.e $n=d^2$ as in this case $n$ has odd number of divisors (for example, $4=2^2$, $4$ has three divisors $1,2 ~\&~ 4$).

$\endgroup$
  • 3
    $\begingroup$ Shouldn't that read $\frac{1}{d_1}+\frac{1}{d_2}+\cdots + \frac{1}{d_k}$ instead of $\frac{1}{d_1}+\frac{1}{d_1}+\cdots + \frac{1}{d_1}$? If not, how many $\frac{1}{d_1}$ are there? $\endgroup$ – wythagoras Jun 18 '15 at 15:21
  • $\begingroup$ @wythagoras yes. I have corrected. $\endgroup$ – user1942348 Jun 18 '15 at 15:23
  • 2
    $\begingroup$ 71 is prime, so $1+\frac{1}{71}$ is a possible value. $\endgroup$ – wythagoras Jun 18 '15 at 15:26
  • $\begingroup$ @wythagoras I have mentioned the major issue of my proof as "Problem" $\endgroup$ – user1942348 Jun 18 '15 at 15:30
  • $\begingroup$ Your argument still works fine in the case where $n$ is a perfect square - in that case, the middle divisor $d_m$ won't have any 'partner', but you have $d_m=\frac{n}{d_m}$ so it is (in effect) its own partner. $\endgroup$ – Steven Stadnicki Jun 18 '15 at 15:32
10
$\begingroup$

Your argument is fine and squares are not a problem. You are not pairing up the divisors, you are just reordering them. Let's walk through your calculation with $n=9$, where the sum of divisors is $1+3+9=13$. We then are asking what the value of $\frac 11 + \frac 13 + \frac 19=S$ is. We multiply by $9$ and get $9S=9+3+1=13, S=\frac{13}9$. The term $3$ does not cause a problem.

$\endgroup$
2
$\begingroup$

Generally the sum of the reciprocals of the divisors of $n$ is equal to $\frac{\sigma(n)}{n}$ where $\sigma$ is the sum of divisors function. This quantity is sometimes referred to as the abundancy ratio or abundancy index of $n$. It can be used to tell whether $n$ is abundant, deficient, or perfect.

$\endgroup$
1
$\begingroup$

Your answer still correct if $n$ is a perfect square since it only has one positive root, so for the term $\frac{n}{d_{root}} = d_{root}$ you get exactly what you need.

$\endgroup$
0
$\begingroup$

Let $p,q,r$ be prime.

$n=p$: $\sum d =1+p$, thus $p=71$, which is indeed prime.

$n=p^k$: $\sum d =1+p+p^2+\ldots+p^n$, thus $p(p^{k-1}+\ldots+p+1)=71$, which is not possible since $p, p+1 >1$ and 71 is prime.

$n=pq$: $\sum d =1+p+q+pq$, thus $(p+1)(q+1)=72$.

  • $p=2$ gives $q=23$. $n=46$
  • $p=3$ gives $q=17$. $n=51$
  • $p=5$ gives $q=11$. $n=55$
  • $p=7$ gives nothing.

$n=p^2q$: $\sum d =1+p+p^2+q+pq+p^2q$, thus $(p^2+p+1)(q+1)=72$.

  • $p=2$ gives nothing.
  • $p=3$ gives nothing.
  • $p=5$ gives nothing.

$n=p^kq^l$, $k,l\geq2$: $\sigma_1(n)\geq(p^2+p+1)(q^2+q+1)\geq7\cdot13>72$.

If $n=pqr$, $\sigma_1(n)\geq\sigma_1(30)\geq72$, with first inequality equality iff $n=30$.

So the values of $n$ for this holds are exactly:

$$n=30, 46, 51, 55, 71$$

And this gives the values for $P$ as:

$$\frac{12}{5}, \frac{36}{23}, \frac{24}{17}, \frac{72}{55}, \frac{72}{71}$$

This shows that it could be bruteforced in a reasonable time (a quarter) but of course your argument is much more elegant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.