Out of memory Problem [Problem 2 , Project Euler (Sum of even Fibonacci numbers)]

%When i tried x=597455000 it straightly said, out of memory problem.
%How can i fix this problem ?
%Give me some advices

function y=shadowofeuler(x)
m(1)=1;
m(2)=1;
i=3;
while(x>=i)
 m(i)= m(i-1)+m(i-2); 
 i=i+1;
end
n=m(3:3:end);
y=sum(n(find(n<x)));
end

Answer 1

[John D'Errico]

Note that IF you are really trying to solve PE #2 (it has been a moderately long time since I was actively solving PE problems on a daily basis) then you are doing something wildly wrong. PE #2 only assks for the sum of Fibonacci numbers that do not exceed 4e6.

Instead, it looks like you are trying to solve a Cody problem, this one, in fact:

https://www.mathworks.com/matlabcentral/cody/problems/232

Note that it does NOT ask you to solve for the sum of the first 597455000 fibonacci numbers. It asks you to solve for the sum of even Fibonacci numbers that do not exceed that value. There is an immense difference!

See that your while loop is running like this:

while(x>=i)

WRONG! Think carefully about what the correct test would be. I won't do your Cody problem for you, as that teaches you nothing. Sorry.

The Fibonacci number with index as large as 597455000, thus F_597455000, would be a number with a vast number of decimal digits. (Do I really need to compute it, or even to compute the log of that number?) While that sum would be technically possible to accomplish, that is NOT what was asked. Anyway, as part of a PE problem, they would always ask you to compute that result modulo some large integer anyway.

So what you need to do is first, NOT compute and save the numbers, as that is inefficient. Just save the sum of the numbers that are even. In fact, it might even be there are easier ways to answer that problem, however, they may not all be the most code efficient ways for a top Cody score. I'd need to look to see if I wrote code for that Cody problem. While I may have done so, Cody has moved by leaps and bounds since I was actively solving Cody problems too. Drat. Now you have me wondering what I did there, or if not, maybe I want to go play Cody for a bit... Grant would want me to do so.

First, just for kicks, how many decimal digits does F_597455000 have?

We can just use the Binet formula here, then taking the log, base 10. Even simpler, we need only the bigger term in that formula.

https://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

Thus we can use

F_n = (1+ sqrt(5))^n / 2^n/ sqrt(5)

APPROXIMATELY so. This term completely dominates the smaller one for even reasonably small values of n. Then

log10(F_n) = (log10(1 + sqrt(5)) - log10(2))*n - log10(sqrt(5))

In MATLAB, we see that

n = 597455000;
(log10(1 + sqrt(5)) - log10(2))*n - log10(sqrt(5))
ans =
          124860710.256066

So that Fibonacci number would have almost 125 MILLION decimal digits. This is not what was requested. As I said, a HUGE difference.

Anyway, If I REALLY wanted to compute the sum of the even Fibonacci numbers, I would probably use a cute little trick, and completely avoid a loop at all. And that is something I will not say any more about, as I hope others might be willing to take that as a challenge. Thus, what is the sum of the Fibonacci numbers that are divisible by 3, up to index 1000, all done without a loop? Note that the 1000'th Fibonacci number is itself huge.

fibonacci(1000)
ans =
    43466557686937456435688527675040625802564660517371780402481729089536
555417949051890403879840079255169295922593080322634775209689623239873322
471161642996440906533187938298969649928516003704476137795166849228875   

I'll add the answer if anyone wants to know it, though I won't pose my solution. Here is the modulus of that sum by my computations, modulo 1e9.

mod(S,1e9)
ans =
563887875

Since each term must be divisible by 3, so must be the sum.

mod(S,3)
ans =
    0

Answer 2

[James Tursa]

Don't store all of the numbers as you go and then add them up at the end. Only keep a few numbers in memory at one time and do the summing as part of your looping.

[Syed Shahed]

How do i do that? @James

[James Tursa]

E.g. the basic structure of the loop would be

m1 = 1;
m2 = 1;
while( some condition of your choosing )
    m3 = m1 + m2; % the new number
    % do something with the new number m3
    % e.g., maybe you add m3 into your total sum if it meets a condition
    m1 = m2; % shift m2 into m1
    m2 = m3; % shift m3 into m2
end

The loop can go on for quite some time (basically until double precision limit is reached), and there are only three terms in memory at once.

Answer 3

[Osahon Usuanlele]

def fibs(num):
	arr = [1,1]
	count = 1
	while count < num - 1:
		arr.append(arr[len(arr)-1] + arr[len(arr)-2])
		count+=1
		arr.pop(0)
	print(arr)
fibs(1000)