Page History: Project Euler Comes to Azeroth

Compare Page Revisions

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Current 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

« Older Revision - Back to Page History - Newer Revision »

Page Revision: 2008/04/30 08:57

Intro

I joked with my friend Dustin about creating solutions to the Project Euler problems using LUA (and running them in WoW). Here's where I'll post those solutions as I finish them.

I'll try to generalize my solutions where I see fit. For example, I added a parameter to Problem 1 to set the upper limit of 1000, but I did not parameterize the 3 and 5, etc.

Problem 1

The sum of a series from 1..n = n*(n+1)/2. So, when stepping by something other than one, you would just need to multiply the series by that step value (n+1, though, becomes the ceiling(upperLimit / factor)).

function ProjectEuler:OnEnable()
    ProjectEuler:Problem001(1000)
end
function ProjectEuler:Problem001(upperLimit)
        self:Print("Sum of all numbers less than " 
            .. upperLimit .. " that are divisible by 3 or 5")
        
        local f = function(factor)
            local n = math.ceil(upperLimit / factor)
            return n * (n-1) * factor / 2
        end
    
        local result = f(3) + f(5) - f(15)

        self:Print(result)
end

Problem 2

I'm cheating a little bit here and capitalizing on the fact that every 3rd item in this Fibonacci sequence is even. f() is the sequence generator.

function ProjectEuler:Problem002(upperLimit)
	self:Print("Sum of all even numbers less than " .. upperLimit .. " in Fibonacci Sequence")
	
	local result, x1, x2 = 0, 1, 2
	
	local f = function(t1, t2)
		return t2, t1+t2
	end
	

	while x2 < upperLimit
	do
		self:Print("adding "..x2)
		result = result + x2
		x1,x2 = f(f(f(x1,x2)))
	end
	
	self:Print(result)
end

Problem 3

Iterate from 2 <= n <= composite / n. Reset iterator after each factor is found (in case the composite has multiple prime factors that are the same). If n becomes greater than (composite / n), then stop, and what's left will be the final prime factor.

function ProjectEuler:Problem003(composite)
	self:Print("Largest prime factor of "..composite)

	local n = 2
	
	while n < (composite / n)
	do
		if composite % n == 0 then
			composite = composite / n
			self:Print("prime factor="..n); 
			n = 1 -- reset N to ensure primes (i.e., 2x2x3x5x5 = 300)
		end
		n=n+1
	end
	
	self:Print("The largest is: "..composite)
end

Problem 4

I don't feel like this is a necessarily elegant solution... Maybe the challenge is in the palindrome logic? I just don't like converting to string and then reversing. Also, the search range of 900-999 was just a SWAG, but it worked.

function ProjectEuler:Problem004()

	local reverse = function(a)
		local result = 0
		while a > 0
		do
			result = result * 10 + mod(a,10)
			a = floor(a/10)
		end
		
		return result
	end
	
	for n=999,900,-1
	do
		for m=n,900,-1
		do
			local x = n*m
			if x == reverse(x) then
				self:Print("Palindrome: "..x)
				return
			end
		end
	end
end

Problem 5

f() is called recursively to prime factorize each of the numbers to 20. My brute force method of generating the LCM first divides out any common prime factors (between the 1..20 series and the accumulated LCM) and then multiplies by the iteration number (1-20).

function ProjectEuler:Problem005()
	
	local result = 1
	local f = function(x)
		for i = 2, x
		do
			if x % i == 0 then
				return i, x / i
			end
		end
		
		return 1, x
	end
	
	for n = 20, 3, -1
	do
		local z = n
		while z > 1
		do
			pf, z = f(z)
			if pf == 1 then break end
			if result % pf == 0 then result = result / pf end
		end
		result = result * n
	end
	
	self:Print(result)

end