[Non-Roblox Question] Lua Fibonacci Sequence Problem Off By 2

Help and Feedback Scripting Support
#1

Disclaimer: This question is not specific to roblox scripting, but is for learning lua. Continue to read if you’d still like to help.

There’s a coding problem on this website [link above as well], and here it is:

"Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms."

Me and my friend have been trying to solve this problem for the 30 minutes - 1 hour, and we finally (thought) we got the solution! But as it turns out, it’s off by 2 digits?? I’m surprised it’d be off by that little. Is there some little thing that we did wrong?

Here’s the code (grandSum is our answer):

local grandSum = 0

local a = 1
local b = 2
local c = 0

local switch = false

while c < 4000000 do
    if switch == false then
        c = a + b
        switch = true
        if c % 2 == 0 and c <= 4000000 then
            grandSum = grandSum + c
            print("C: " .. c)
        end
    end

    if switch == true then
        a = b
        b = c
        c = a + b
        if c % 2 == 0 and c <= 4000000 then
            grandSum = grandSum + c
            print("C: " .. c)
            print("grandSum: " .. grandSum)
        end
    end
end

So the correct answer it says is 4613732. However, we got 4613730… odd.

I know this isn’t directly roblox related, but since it’s all a part of learning lua/roblox lua, I thought I could post here.

Thanks!

1 Like
#2

If you comment your code it would help a lot. As it stands I don’t understand at all the purpose of the switch conditional for one thing

2 Likes
#3

The purpose of the switch is to make sure the variable doesn’t overlap with the previous number.
With the switch, it would be a+b=c then switch a=b b=c then add again. So basically the switch makes the c=b then makes b=a. If you did it without it would add up to the same sum each time.

Hopefully, that makes sense.

#4

I’m not entirely certain, but I think the issue is that you are counting with your c variable. However, since your program starts with the first three members of the sequence in memory the 2 assigned to the variable b is never counted. This would explain why your calculated value is 2 below the correct answer.

1 Like
#5

Ah, you know what you are probably right. Each undefined numeral variable is automatically one so I believe a fix would be to reassign the variable B to one. Let me check it out.

EDIT: I just realized that it should be b=1; a=0; that way it starts from the beginning.

Further edit and solution:
It worked!

image
image1777×1287 167 KB

Because we are taking the modulus of 2 we would not get the odd numbers.

Solution change ‘a’ to zero ‘b’ to one. This will cause the script to build from the ground up because you are already starting as ‘2’ you skip two numbers.

1 Like
#8

Looks like the original problem has already been solved, which is that you’re not counting the second term in the Fibonacci sequence because of how a and b are set at 1 and 2.

Here’s another way to look at the problem using recursion, which I hope you might find interesting. It also includes an optimization technique. Let me know if you have any questions about it.

local memoization_table = {[0]=0, [1]=1}  -- 0 and 1 are base cases

function fibonacci(n)
	if memoization_table[n] then	-- Instead of re-calculating fib(n), use memoized value. Optimization technique
		return memoization_table[n]
	end
	
	local value = fibonacci(n-1) + fibonacci(n-2)
	memoization_table[n] = value
	
	return value
end


local n = 0
local sum = 0 
while true do
	n+=1
	local val = fibonacci(n)
	
	if val>4000000 then
		break
	end
	
	if val%2==0 then
		sum+=val
	end
end

print(sum)
3 Likes
#9

Your script is nice and makes sense but you need to add something where ‘n+=1’ is or else it will error out. Maybe its because I am using a Lua script executor because I can’t access studio right now. But as for optimization MJT did a great job doing just that. If you increase the max number to < inf or just add a ridiculously long exponent the system calculates the solutions almost instantaneously. I found this other Lua script that did the exact same thing but the only difference was it took 257 seconds to calculate 20,000 different results.

#10

Cool thanks! The n+=1 part is pretty new and specific to roblox’s luau.
If you’re interested about the optimization, check out dynamic programming. It sacrifices memory for saving up on computation; and is good for certain algorithms which might want to recompute certain parts. I think it’s pretty cool.

1 Like
#11

Oh cool, I did not know about that function my executor probably needs a update.

Yeah, dynamic programming is really interesting and fun. The website stated above has a ton of practice questions you can apply your dynamic programming skills to.

#12

I did some experimenting of my own and managed to get the same answer.

local n1 = 1
local n2 = 2
local n3 = 0
local sum = n2

local i = 0
while n3 <= 4000000 do
  i = i + 1
  n3 = n1 + n2
  n1 = n2
  n2 = n3
  if i%3 == 0 then
    sum = sum + n3
  end
end

print(sum)

This loop “skips” the first two terns, and every three terms after that, an even number shows up in the sequence, therefore I do (Term# - 2)%3 aka i%3 to determine if n3 is an even number, and add it to the final sum.

1 Like
#13

So I found this post, got bored and made this…

local function fib(amnt)
    local t = {1,1}
    local current = 1
    local previous = 1
    -- 1,2,3,5,8,13,21,34... etc  var 1 + var 2 = var  var 2 + var 3 = var 4
    for i = 1,amnt,1 do
        local tblLength = #t
        local newNum = t[tblLength-1]+t[tblLength]
        print(newNum)
        table.insert(t,newNum)
    end
end
fib(20)

it works :smiley:

Edit: 20 is the number of times iterated before stopping by the way…

2 Likes
#14

Your code is skipping the first two terms because you are not starting with the right values.

Usually the first value in the sequence would be 0, and the second would be 1. You are using 1 as the first and 2 as the second. Every other number in the sequence is the sum of the previous two numbers. This can be computed recursively as well.

local function fib(n)
	if (n == 0 or n == 1) then
		return n
	else
		return fib(n - 1) + fib(n - 2)
	end
end

[edit] looks like other people replied with this function too, and included dynamic programming as well.

local memory = {
	[0] = 0,
	[1] = 1
}
local function fib(n)
	if (memory[n]) then
		return memory[n]
	else
		local result = fib(n - 1) + fib(n - 2)
		memory[n] = result
		return result
	end
end
2 Likes
#16

Ah, thanks everyone for the responses! I enjoy seeing the different ways you all approach coding - it makes me think of what a creative craft it is, that has much potential to grow.

@SilvRHat That is interesting, thanks for sharing! I haven’t explored recursion yet, and I’ve only been programming for about 3 months now, but It’s something I’m looking to understand! So thanks for the share with that.

@AbiZinho Nice, that’s an interesting way to approach it!

@greatneil80 Haha I feel you - them bored days lol. But that’s really cool, that’s a unique way of doing it. I was thinking of using a table myself, but we found a somewhat more simple way. Thanks for sharing!

@Blokav Ah I see - that helped clarify what the others were babbling about haha. And nice script, it looks good!

@alksjdfl Ah interesting. I’m not sure if I was calling the function correctly (I did fibonacci(1) when I called it), but it didn’t seem to work. Thanks for sharing though!

You all have a great rest of your week and weekend!

1 Like
#17

@SilvRHat
@AbiZinho
@greatneil80
@Blokav
@alksjdfl

You guys all look like you’re interested in this problem, so here’s an interesting video which explains the issues with the typical recursive solution, and teachers a better way of doing it

2 Likes
#18

slightly off topic, but those operators are in Luau only (roblox’s new version of lua). you can’t find them in normal lua. you can find a list of all of these changes here: Compatibility - Luau

1 Like
#20

I know what recursion is and I use it, I just didn’t use it when I was making the Fibonacci sequence.

#21

I never said you don’t use recursion, I’m just sharing an interesting video on the subject. There really was nothing there for you to take personally

1 Like
#22

Tail recursion is usually an optimization recognized by the compiler. Idk (since lua is interpreted) if this would actually apply to Lua. Something to check out.

In this case, I’d also say the dynamic programming approach I outlined is more efficient (especially in this context) or equally efficient. This is because, if we have a memoized value already computed we return that instead of having more recursive calls. And the tail recursion optimization is good handling the stack, but we still handle computation on each recursive call. Since we call fibonacci(n) on multiple numbers in this problem, we’re not recomputing values between each call with DP as we would with tail recursion.

But this is a good optimization for eliminating stack overflow issues, and is a good alternative if you don’t have the memory to spare for DP.

2 Likes
#23

Yeah, I’m pretty sure the LuaU interpreter would be able to catch something like this, but it’s a good idea to learn and utilise tools like tail recursion as compilers/interpreters may miss optimisations in more complex projects.

Regarding your optimisation, since n is always increasing the script never actually runs fibonacci(n) with the same value of n twice. Therefore the memoization_table is never actually indexed for a result. If you plan on running fibonacci() to solve other problems in the same runtime then a cache table like yours would be useful, but in this specific example you’re simply spending computation and memory without any actual use of the optimisation.

One more bit of code review advice, your while loop should be checking the val > 4000000 in the while {condition} do section. If you’re worried about val’s scope bleeding out to the top-level script then you could consider putting the entire calculation code into its own function.

#24

Just real quick, remember:
f(n+1) = f(n) + f(n-1)
f(n+2) = f(n+1) + f(n) = 2f(n) + f(n-1)

If we call f(3), f(1) is called twice.
Both DP and tail recursion are going to solve this problem of recomputing f(n) multiples times for f(n+1), f(n+2), and so on. They just do so in different ways.

But since we are continuously incrementing n, its nice having that cache table. If we calculate f(7), store that, then increment n and call f(8), we’re going to look up the values f(6) and f(7) in our table and return those immediately. And we never re-compute f(n) on any calls. With tail recursion you’ll only never re-compute f(n) on recursive calls. Lets say we compute f(7) with tail recursion. It’ll run maybe even faster than if we did with DP because the stack is taken care of. Super useful and a good practice. But then we increment n, and run f(8). We never stored f(7) or f(6), so now we’ll have to recompute those.

1 Like