Two integers 



N


{\displaystyle N}

 and 



M


{\displaystyle M}

 are said to be amicable pairs if 



N
≠
M


{\displaystyle N\neq M}

 and the sum of the proper divisors of 



N


{\displaystyle N}

 (




s
u
m

(

p
r
o
p
D
i
v
s

(
N
)
)


{\displaystyle \mathrm {sum} (\mathrm {propDivs} (N))}

) 



=
M


{\displaystyle =M}

 as well as 




s
u
m

(

p
r
o
p
D
i
v
s

(
M
)
)
=
N


{\displaystyle \mathrm {sum} (\mathrm {propDivs} (M))=N}

.



Example

1184 and 1210 are an amicable pair, with proper divisors:

   1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592   and 
   1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605   respectively.


Task

Calculate and show here the Amicable pairs below 20,000; (there are eight).



Related tasks
 Proper divisors
 Abundant, deficient and perfect number classifications
 Aliquot sequence classifications and its amicable classification. 


 
#include <vector>
#include <unordered_map>
#include <iostream>
 
int main() {
    std::vector<int> alreadyDiscovered;
    std::unordered_map<int, int> divsumMap; 
    int count = 0;
 
    for (int N = 1; N <= 20000; ++N)
    {      
        int divSumN = 0;
 
        for (int i = 1; i <= N / 2; ++i)
        {
            if (fmod(N, i) == 0)
            {
                divSumN += i;
            }
        }
 
        // populate map of integers to the sum of their proper divisors
        if (divSumN != 1) // do not include primes
            divsumMap[N] = divSumN;
 
        for (std::unordered_map<int, int>::iterator it = divsumMap.begin(); it != divsumMap.end(); ++it)
        {
            int M = it->first;
            int divSumM = it->second;
            int divSumN = divsumMap[N];
 
            if (N != M && divSumM == N && divSumN == M)
            {
                // do not print duplicate pairs
                if (std::find(alreadyDiscovered.begin(), alreadyDiscovered.end(), N) != alreadyDiscovered.end())
                    break;
 
                std::cout << "[" << M << ", " << N << "]" << std::endl;
 
                alreadyDiscovered.push_back(M);
                alreadyDiscovered.push_back(N);
                count++;
            }
        }
    }
 
    std::cout << count << " amicable pairs discovered" << std::endl;
}
 