Collatz Conjecture function in Lua.

• I just decided to post this after watching this numberphile video. I thought I might as well make it in Lua. Mainly to see how efficient I could get my solution. And I'm posting this here so maybe you guys can make it faster!

Basically, how the conjecture goes is like this:

• If the number is even, divide by two.
• Else, multiply by 3 and add 1.

And the problem is finding out if any numbers exist, that you can start with and not eventually get to 1. My function returns how many rounds of this conjecture it would take before the number returns to one. (Whether there exists a number that doesn't eventually get to one is still unsolved.)

Here's what I started with:

local function CollatzConjecture(num, val)
val = val or 0
if(num==1)then
return val
elseif(num%2==0)then
return CollatzConjecture(num/2, val+1)
else
return CollatzConjecture((3*num+1)/2, val+2)
end
end

You'll notice I take a short cut they talk about in the video, where when the number is odd and you do 3x+1, you can divide by 2 to skip another round in the function, therefore increasing efficiency. Just make sure you add two to the steps if you do this :3

That's the old code, which is 20% slower than this code:

local function CollatzConjecture(num, val)
val = val or 0
return num==1 and val or num%2==0 and CollatzConjecture(num/2, val+1) or CollatzConjecture((3*num+1)/2, val+2)
end

Bit long, but it gets the job done.

Here's the code I used to calculate which was faster:

local function CollatzConjecture(num, val)
val = val or 0
return num==1 and val or num%2==0 and CollatzConjecture(num/2, val+1) or CollatzConjecture((3*num+1)/2, val+2)
end

local start = tick()
for i = 1,100000 do
CollatzConjecture(i)
end

print("Time took =", tick()-start)

And the same thing with the other. Method one printed Time took = 10.206101894379, while method two printed: Time took = 8.2290716171265

Obviously if you try this your computer might be faster/slower than mine, but if you think you have a better method that would be cool to see :3

• This post is deleted!

• Here is a much faster version.

local function CollatzConjecture(Int)
-- Given an integer, return the number of steps to get to 1
local Count = 0

repeat
if Int % 2 == 0 then
Int = 0.5 * Int
Count = Count + 1
else
Int = 1.5 * Int + 0.5
Count = Count + 2
end
until Int == 1

return Count
end