Day 2 Problem 2. Today has been a semi productive day and I am excited to get back to other reading as soon as Im done with this. The problem seems simple enough, and at the face of it, I can tell I can do a brute force and a recursion. Hmm. Although I am tempted to move straight to making a recursion code, I think Ill make the brute force one just for the heck of it. euler2.cpp

#include<iostream>
using namespace std;

int fiblast(int a[]);
int main()
{
        int s=2,k=0,a[3]={1,2,0};

while(k<4000000){
        if(k%2==0) s+=k;
        k=fiblast(a);
}
cout<<s<<endl;
return 0;
}

int fiblast(int a[]){
a[2]=a[0]+a[1];
a[0]=a[1];
a[1]=a[2];
return a[1];
}



Done. Now to think if a recursive solution can exist. Hmm. First, I cannot help but think how deplorably inefficient my earlier program is. Why the hell am I passing bulky arrays to a function which is going to be called many many times? I feel I can do a better job with three variables in the main function itself. Ok. Try 2 at brute force, basically the same algorithm but a better implementation.


#include<iostream>
using namespace std;

int main()
{
int a1=1,a2=2,a3=0;
while(a2<3009){
        if (a2 % 2==0)a3+=a2;
        a2=a1+a2;
        a1=a2-a1;
if(a2%2==0)cout<<"a2="<<a2<<endl;
}return 0;
}

Perfect. Well… in the sense of improvement, atleast. Now. Time to find a better solution. Hmm. After making some of the sequence, an obvious pattern is emerging. Starting from {2} ever {3^{rd}} number is even. This is so because the sum of odd and even is odd, and the sum of two odds is even. First let me just write the program, I will analyze the recursion itself later to see if there is a closed form, though I should expect one as it is a linear recursion

\displaystyle T_n=T_{n-1}+T_{n-2}

with {T_1 =1} and {T_2=2}

#include<iostream>
using namespace std;

int fib(int z);
int main(){
int s=0,k=0,l=1;
for(int i=2;k<4000000;i+=3)
{s+=k;k=fib(i);}
cout<<s<<endl;
return 0;}

int fib(int i){
if(i==1) return 1;
if(i==2) return 2;
return fib(i-1)+fib(i-2);
}

Well. That’s done.Though I am not sure yet if this is a better solution than the earlier one. I remember a recursive function creates a copy of itself and stores it in memory each time its called. Hmm. Ill make the comparision after I’m done with the closed form as it has begun to bug me and this has taken more time than I expected.

Note to self: Start Euler problems early morning before starting work.

The most efficient code for this problem would be to make the computer do just one computation by figuring out the closed form yourself.

im looking for a closed form for

\displaystyle  S=\sum_{k=1}^{T_{3k-1} < 4M} T_{3k-1} \ \ \ \ \ (1)

Where {T_k} is the k’th Fibbonaci number. {T_0=1}, {T_1=1} being the base cases.This sum should wait. Take the general sum S_n = T_0+ &T_1+ T_2 +\cdots + T_n
S_{n-1} =\qquad &T_0 + T_1+\cdots +T_{n-1}

On adding the above two equations, we get the recursion for the sums:

S_n+S_{n-1} &= T_0 + (T_2+T_3+\cdots + T_{n+1}) = S_{n+1} – T_1
S_n+S_{n-1} &= S_{n+1} – 1

So this is the recursion relation that needs to reduced to a close form. This is, as the Fibonaci terms, a second order recurrence. How should I have seen that earlier? Hmm. Ahh, of course, uptil now there is no reference to any particular sequence, so I can deduce that the sum of terms defined by a second order recurrence will have second order recursive defintions themselves.

My first attack would be to use generating functions:

\displaystyle  S(x) = \sum_{n=0}^\infty S_n x^n \ \ \ \ \ (2)

In some domain x where the power series is convergent.

S(x) &= S_0+S_1 x+\sum_{n=2}^\infty S_{n+1} x^n – \sum_{n=2}^\infty S_{n-1} x^n -\sum_{n=2}^\infty x^n
&= S_0+S_1 x+\frac{1}{x}\sum_{n=2}^\infty S_{n+1} x^{n+1} – x\sum_{n=2}^\infty S_{n-1} x^{n-1} -\sum_{n=2}^\infty x^n
&= S_0+S_1 x+\frac{1}{x}(S(x) – S_0 – S_1 x -S_2 x^2) – x(S(x) – S_0 ) -\frac{x^2}{1-x}

Using the values {S_0=1}, {S_1=2} and {S_2=4} the above reduces to

\displaystyle  S(x)=\frac{1}{(1-x)(1-x-x^2)} \ \ \ \ \ (3)

The amount of cancelling that took place to reduce to the simpler form from the formidable looking (9) suggests there could have been a simpler way. From the generating function of the fibbonaci sequence: G(x) &=\sum_{n=0}^\infty T_n x^n
&=\sum_{n=0}^\infty (S_n-S_{n-1}) x^n
&=S(x)-xS(x)

\displaystyle  S(x)=\frac{G(x)}{1-x} \ \ \ \ \ (4)

So, I could have got the generating function {S(x)} from direcly computing {G(x)}. Well, I’ve calculated {S(x)} so I verify that

\displaystyle  G(x)=\frac{1}{1-x-x^2} \ \ \ \ \ (5)

Now time to finally get the closed form from this generating function.

S(x) &=-\frac{1}{1-x}+\frac{x+2}{1-x-x^2}
&=-\frac{1}{1-x}+\frac{(x+2)}{\alpha-\beta}\left(\frac{1}{x-\alpha}-\frac{1}{x-\beta}\right) Now I think convergence issue has to be addressed, because the expansion of {1\over (x-\alpha)} would depend on the value of {\alpha}. If {\alpha} has a magnitude less than the max value of {x} then the power series would be in inverse powers of x. Ah, that is just silly of me! {x} is just a spectator in my scheme. I already know that {S(x)} has a power series expansion in powers of x not in inverse powers. So domain is the excluded interval {x\in (-\alpha,\alpha)}

\displaystyle  S(x) = (-1-x-x^2-x^3+\cdots) + \frac{(x+2)}{\beta-\alpha}\left( (\beta^{-1}-\alpha^{-1})s + (\beta^{-2}-\alpha^{-2})x^2 +\cdots	\right) \ \ \ \ \ (6)

\displaystyle  S_n = \frac{2}{\beta-\alpha}(\beta^{-n}-\alpha^{-n})+\frac{\beta^{-(n-1)}-\alpha^{-(n-1)}}{\beta-\alpha} \ \ \ \ \ (7)

But I just realize that all this is useless overworking in the face of the obvious solution staring at me now. The roots of the generating function for the fibbonaci sequence are {\alpha = -\frac{\sqrt{5}+1}{2}} and {\beta = \frac{\sqrt{5}11}{2}} and the from this, the closed form for the fibbonacis I get is

\displaystyle  T_n=\frac{1}{\sqrt{5}}\left( \frac{1}{\beta^{n+1}}-\frac{1}{\alpha^{n+1}} \right) \ \ \ \ \ (8)

I just need the sequence, {T_2+T_5+\cdots +T_n}

So this finally gives me

\displaystyle  S = \frac{1}{\sqrt{5}}\left( \frac{1-\beta^{-3k}}{\beta^3-1} -\frac{1-\alpha^{-3k}}{\alpha^3-1} \right) \ \ \ \ \ (9)

Now I need to find the {k^{th}} to truncate this summation at the limit, in this case 4 million. To take the general case where the limit is specified to be {L} the solution to {T_{3k-1}\leq L}

\displaystyle  k\leq \frac{\log\sqrt{5}L}{3 (\log\alpha -\log\beta) }\Rightarrow k=\lfloor \frac{\log \sqrt{5}L}{3 (\log\alpha -\log\beta) }\rfloor \ \ \ \ \ (10)

Finally, I’m done with the analysis. I plug in Eqn (23) into Eqn (22) and then translate the following formula to code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: