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
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!
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
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
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.
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
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.
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
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 
Edit: 20 is the number of times iterated before stopping by the way…
2 Likes
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
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
@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
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
I know what recursion is and I use it, I just didn’t use it when I was making the Fibonacci sequence.
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
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
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.
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
This is true if you do the summation of values outside of the tail-recursive function. However if your function looked like this:
function f(a, b, maxValue, acc)
local c = a + b
if c >= maxValue then
return acc
elseif c % 2 == 0 then
acc = acc + c
end
return f(b, c, maxValue, acc)
end
then you can run f(0, 1, 4000000, 0) and get the correct value of 4613732 without ever calculating the same term twice, and without storing a term in memory longer than it used
1 Like
You don’t need recursion or loops to solve a Fibonacci sequence. It can be done in O(1) (aka constant) time. No need for a cache either. This function uses the “golden ratio” phi:
local sqrt5 = 2.2360679775 -- avoid recalculating it every time
local function fibonacci(n)
return math.round(1.618033988749895 ^ n / sqrt5)
end
Note: math.round() is new in Luau
The problem isn’t calculating the nth term, it’s summing terms on a conditional basis. Because of this, a tail-recursive solution means that you’re never re-calculating fibonacci(n) with the same value twice, and in my implementation you are using a computationally cheaper method to calculate terms
1 Like