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

    Thanks for reading :D


  • 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

  • @Validark I jump to a recursive method too often, thanks.

Looks like your connection to Scripting Helpers was lost, please wait while we try to reconnect.