12
$\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$
11
  • 4
    $\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
    Commented Jun 18, 2015 at 15:21
  • 1
    $\begingroup$ @wythagoras yes. I have corrected. $\endgroup$ Commented Jun 18, 2015 at 15:23
  • 3
    $\begingroup$ 71 is prime, so $1+\frac{1}{71}$ is a possible value. $\endgroup$
    – wythagoras
    Commented Jun 18, 2015 at 15:26
  • 1
    $\begingroup$ @wythagoras I have mentioned the major issue of my proof as "Problem" $\endgroup$ Commented Jun 18, 2015 at 15:30
  • 1
    $\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$ Commented Jun 18, 2015 at 15:32

4 Answers 4

11
$\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$
3
$\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$
2
$\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$
1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .