%ProjectEuler/Octave/Problem16.m
%Matthew Ellison
% Created: 
%Modified: 03-28-19
%What is the sum of the digits of the number 2^1000?
%{
	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 your variables
numberToPower = 2;
POWER = 1000;
nums = [1];
carry = 0;
currentPower = 0;

%Start the timer
startTime = clock();

%Loop until you reach the correct power to raise the number to
while(currentPower < POWER)
	counter = 1;
	%Loop through every element in the list and multiply by 2
	while(counter <= size(nums)(2))
		nums(counter) = (nums(counter) * numberToPower) + carry;
		carry = 0;
		%If one of the elements is >= 10 you need to carry to the next element
		if(nums(counter) >= 10)
			nums(counter) -= 10;
			++carry;
		end
		++counter;
	end
	%If you have something to carry after everything has been multiplied you need to add a new column
	if(carry > 0)
		nums(end + 1) = carry;
		carry = 0;
	end
	++currentPower;
end

%Stop the timer
endTime = clock();

%Print the results
nums = fliplr(nums);	%Flip the results so it is easier to move to a string
counter = 1;
number = [''];
while(counter <= size(nums)(2))
	number(counter) = num2str(nums(counter));	%Convert each number to a character
	++counter;
end

%Print the results
printf("2^1000 = %s\n", number)
printf("The sum of the digits is: %d\n", sum(nums))
printf("It took %f seconds to run this algorithm\n", etime(endTime, startTime))

%Cleanup your variables
clear numberToPower;
clear POWER;
clear nums;
clear carry;
clear currentPower;
clear counter;
clear startTime;
clear endTime;
clear number;
clear ans;

%{
Results:
2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
The sum of the digits is: 1366
It took 3.203796 seconds to run this algorithm
%}