function [] = Problem21()
%ProjectEuler/Octave/Problem21.m
%Matthew Ellison
% Created: 03-19-19
%Modified: 03-28-19
%Evaluate the sum of all the amicable numbers under 10000
%{
	Copyright (C) 2019  Matthew Ellison

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
%}


%Setup the varibles
LIMIT = 10000;	%The top number that will be evaluated
divisorSum = [];	%Holds the sum of the factors of the subscript number

%Start the timer
startTime = clock();

%Generate the factors of all the numbers < 10000, get their sum, and add it to the list
for cnt = 1 : LIMIT
	divisors = getDivisors(cnt);	%Get all the divisors of a number
	if(size(divisors)(2) > 1)
		divisors(end) = [];	%Remove the last entry because it will be the number itself
	end
	divisorSum(end + 1) = sum(divisors);	%Add the sum of the divisors to the vector
end
%Check every sum of divisors in the list for a matching sum
amicable = [];
for cnt = 1 : size(divisorSum)(2)
	sumOfDivisors = divisorSum(cnt);
	%If the sum is greater than the number of divisors then it is impossible to be amicable. Skip the number and continue
	if(sumOfDivisors >= size(divisorSum)(2))
		continue;
	%We know that divisorSum[cnt] == sum, do if divisorSum[sum] == cnt we have found an amicable number
	elseif(divisorSum(sumOfDivisors) == cnt)
		%A number can't be amicable with itself, so skip those numbers
		if(sumOfDivisors == cnt)
			continue;
		end
		amicable(end + 1) = cnt;
	end
end

%Stop the timer
endTime = clock();

%Sort the vector for neatness
sort(amicable);

%Print the results
printf("All amicable numbers less than %d are\n", LIMIT)
%Print the list of amicable numbers
for location = 1: size(amicable)(2)
	printf("%d\n", amicable(location))
end
printf("The sum of all of these amicable numbers is %d\n", sum(amicable))
printf("It took %f seconds to run this algorithm\n", etime(endTime, startTime))

end	%Problem21()

function [divisors] = getDivisors(goalNumber)
	divisors = [];
	%Start by checking that the number is positive
	if(goalNumber <= 0)
		return;
	%If the number is 1 return just itself
	elseif(goalNumber == 1)
		divisors(end + 1) = 1;
		return;
	%Otherwise add 1 and itself to the list
	else
		divisors(end + 1) = 1;
		divisors(end + 1) = goalNumber;
	end

	%Start at 3 and loop through all numbers < sqrt(goalNumber) looking for a number that divides it evenly
	topPossibleDivisor = ceil(sqrt(goalNumber));
	for possibleDivisor = 2 : topPossibleDivisor
		%If you find one add it and the number it creates to the list
		if(mod(goalNumber, possibleDivisor) == 0)
			divisors(end + 1) = possibleDivisor;
			%Account for the possibility sqrt(goalNumber) being a divisor
			if(possibleDivisor != topPossibleDivisor)
				divisors(end + 1) = goalNumber / possibleDivisor;
			end
		end
	end

	%Sort the list before returning for neatness
	divisors = sort(divisors);
end

%{
Results:
All amicable numbers less than 10000 are
220
284
1184
1210
2620
2924
5020
5564
6232
6368
The sum of all of these amicable numbers is 31626
It took 5.650108 seconds to run this algorithm
%}