mirror of
https://bitbucket.org/Mattrixwv/projecteulerlua.git
synced 2025-12-06 09:33:58 -05:00
84 lines
2.7 KiB
Lua
84 lines
2.7 KiB
Lua
--ProjectEuler/lua/Problem14.lua
|
|
--Matthew Ellison
|
|
-- Created: 02-07-19
|
|
--Modified: 06-19-20
|
|
--[[
|
|
The following iterative sequence is defined for the set of positive integers:
|
|
n → n/2 (n is even)
|
|
n → 3n + 1 (n is odd)
|
|
Which starting number, under one million, produces the longest chain?
|
|
]]
|
|
--All of my requires, unless otherwise listed, can be found at https://bitbucket.org/Mattrixwv/luaClasses
|
|
--[[
|
|
Copyright (C) 2020 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/>.
|
|
]]
|
|
|
|
|
|
require "Stopwatch"
|
|
|
|
|
|
local timer = Stopwatch:create();
|
|
timer:start();
|
|
|
|
TOP_NUM = 1000000 --The largest number that you will check against the chain
|
|
|
|
--This function returns a table of numbers created by the chain
|
|
local function getChain(startNum)
|
|
--Put the starting number in the list
|
|
local chain = {};
|
|
chain[#chain+1] = startNum;
|
|
|
|
--Starting with the current number perform the correct opperations on the numbers until that number reaches 1
|
|
while(startNum > 1) do
|
|
--Determine if the number is odd or even and perform the correct operations and add the new number to the list
|
|
if((startNum % 2) == 0) then
|
|
startNum = startNum / 2;
|
|
else
|
|
startNum = (3 * startNum) + 1;
|
|
end
|
|
--Add the new number to the chain
|
|
chain[#chain+1] = startNum;
|
|
end
|
|
|
|
--Return the list
|
|
return chain;
|
|
end
|
|
|
|
--Setup your variables
|
|
local largestChain = {};
|
|
|
|
--Start at 1 and run up to TOP_NUM checking how long the chain is when started with each number
|
|
for startingNumber=1,TOP_NUM do
|
|
local currentChain = getChain(startingNumber);
|
|
--If the new chain is longer than the current longest chain replace it
|
|
if(#currentChain > #largestChain) then
|
|
for location=1,#currentChain do
|
|
largestChain[location] = currentChain[location];
|
|
end
|
|
end
|
|
end
|
|
|
|
timer:stop();
|
|
|
|
--Print the results
|
|
print("The longest chain with a starting number < " .. TOP_NUM .. " starts with " .. largestChain[1] .. " with a length of " .. #largestChain);
|
|
print("It took " .. timer:getSeconds() .. " seconds to run this algorithm")
|
|
|
|
--[[Results:
|
|
The longest chain with a starting number < 1000000 starts with 837799 with a length of 525
|
|
It took 13.704 seconds to run this algorithm
|
|
]]
|