Possible mis-interpretation in Project Euler #21

235 Views Asked by At

Here is the problem statement for Problem 21 of Project Euler.

Let $d(n)$ be defined as the sum of proper divisors of $n$ (numbers less than $n$ which divide evenly into $n$).

If $d(a) = b$ and $d(b) = a$, where $a ≠ b$, then $a$ and $b$ are an amicable pair and each of $a$ and $b$ are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore $d(220) = 284$. The proper divisors of 284 are 1, 2, 4, 71 and 142; so $d(284) = 220$.

Evaluate the sum of all the amicable numbers under 10000.

My question is this: Suppose there are only three numbers $a, b$ and $c$ which have the same sum of divisors. Clearly there will be three amicable pairs, $(a,b), (b,c)$ and $(c,a)$.

Will my answer be $a+b+c$ or $(a+b)+(b+c)+(c+a)$ as being the sum of amicable pairs?

Or does the question ask us to find only pairs, in which case, the above triplet of $ a,b,c$ will not be a part of the sum.

If we consider all counting numbers including and below 10 in light of the amicable pair sum problem, below is the breakup by number.

  1. $d(x)=n$ : (list of x with d(x)=n) sum_=sum of all x in list if more than one element exists in list.

  2. $d(x)=1 : (2,3,5,7)$ sum1=2+3+5+7=17

  3. $d(x)=2 : (4)$ solitary member, hence not added sum3=0
  4. $d(x)=3 : (9)$ solitary member, hence not added sum4=0
  5. $d(x)=6 : (6)$ solitary member, hence not added sum6=0
  6. $d(x)=7 : (8)$ solitary member, hence not added sum7=0
  7. $d(x)=8 : (10)$ solitary member, hence not added sum8=0

Is the sum in this case (for all natural numbers including and upto 10) $0$ or $17$?

2

There are 2 best solutions below

1
On BEST ANSWER

$(a,b)$ being an amicable pair, does not mean that $a$ and $b$ have the same sum of their divisors, but rather that the sum of the divisors of $a$ is $b$ and the sum of the divisors in $b$ is $a$. So having three numbers with the same sum of their divisors doesn't matter to this problem.

0
On

Every prime $p$ has $d(p)=1$.

$d(18)=d(51)=d(91)=21$

$d(32)=d(125)=d(161)=d(209)=d(221)=31$

I'm not sure whether these sets have a name. Except for the primes, the set of numbers with any given factor sum will be finite; the largest possible member of the set $\{x\}$ with $d(x)=n$ would be the square of $n-1$, if that is a prime.

Luckily for the real problem statement, there are no amicable pairs that cross over the $10000$ threshold, or $100000$, but a couple of pairs straddle the $1000000$ mark. Amicable numbers below $100000$ are as follows:

$$ \begin{array}{c|c} Lower & Upper & \text{Cumulative sum} \\\hline 220 & 284 & 504 \\ \hline 1184 & 1210 & 2898 \\ \hline 2620 & 2924 & 8442 \\ \hline 5020 & 5564 & 19026 \\ \hline 6232 & 6368 & 31626 \\ \hline 10744 & 10856 & 53226 \\ \hline 12285 & 14595 & 80106 \\ \hline 17296 & 18416 & 115818 \\ \hline 63020 & 76084 & 254922 \\ \hline 66928 & 66992 & 388842 \\ \hline 67095 & 71145 & 527082 \\ \hline 69615 & 87633 & 684330 \\ \hline 79750 & 88730 & 852810 \\ \end{array} $$