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 \$N\$, find the sum of the even-valued terms.Input Format:First line contains \$T\$ that denotes the number of test  cases. This is followed by \$T\$ lines, each containing an integer, \$N\$.Output Format:Print the required answer for each test case.Constraints:\$1 \le T \le 10^{5}\$  \$10 \le N \le 4 \times 10^{16}\$#include <iostream>int main () {    int nCases;    std::cin >> nCases;    for (int i = 0; i < nCases; i++) {        unsigned long back = 1;        unsigned long front = 2;        unsigned long total = front;        unsigned long maxNumber;        std::cin >> maxNumber;        while (true) {            unsigned long frontPrime = front;            front = (3 * front) + (2 * back);            back = (2 * frontPrime) + back;            if (front > maxNumber) {                break;            } else {                total += front;            }        }        std::cout << total << '\n';    }    return 0;}Commented and formatted:#include <iostream>int main () {    int nCases;    std::cin >> nCases;    for (int i = 0; i < nCases; i++) {        unsigned long back  = 1; // First number of the sequence        unsigned long front = 2; // Second number of the sequence        unsigned long total = front; // Since out of the 2, only front is even        unsigned long maxNumber;        std::cin >> maxNumber;        // Keep on getting the even numbers until the number becomes        // greater than the max        while (true) {            unsigned long frontPrime = front; // Need to store its original value for use later            // We know that every 3rd number is even:            // 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...            // o, o, e, o, o, e,  o,  o,  e,  o,  o,   e...            // Since an odd plus an odd has to equal an even,            // but an even and an odd is always odd.            //            // So using f(n+2) = f(n+1)        + f(n)            //                 = f(n) + f(n-1) + f(n)            //                 = 2f(n) + f(n-1)            //            // and      f(n+3) = f(n+2)               + f(n+1)            //                 = f(n+1)        + f(n) + f(n) + f(n-1)            //                 = f(n) + f(n-1) + f(n) + f(n) + f(n-1)            //                 = 3f(n) + 2f(n-1)            //            // Where n = front, and n-1 = back,            // we can save from iterating more than once.            // n+2 is 3 spaces ahead of n-1, and n+3 is 3 spaces ahead of n,            // thus we go to each even only and save a modulo check.            front = (3 * front) + (2 * back);            back  = (2 * frontPrime) + back;            if (front > maxNumber) {                break;            } else {                total += front;            }        }        std::cout << total << '\n';    }    return 0;}I was wondering if there is anything I could do to improve the efficiency, both processor- and memory-wise, size (of the code itself not the comments), or general style.I am also curious as to whether or not there would be a better way to do my algorithm so as not to store frontPrime.
Project Euler #2: Even Fibonacci numbers
c++;beginner;algorithm;programming challenge
I see a number of things that may help you improve your code.Make it clear when loops endThe code currently uses while (true) but it doesn't really loop infinitely.  It's better, generally, to have the loop exit condition explicitly stated.  For example we could rewrite your main loop as:unsigned long total = 0;while (front <= maxNumber) {    total += front;    unsigned long frontPrime = front;    front = (3 * front) + (2 * back);    back = (2 * frontPrime) + back;}Analyze the mathematicsYour mathematical analysis is correct as far as it goes, but there's a bit easier way to do it.  A bit more algebra will convince you that the series looks like this:$$a_0 = 0$$$$a_1 = 2$$$$a_n = 4a_{n-1} + a_{n-2}$$Derivation of this sequenceThe Fibonacci numbers are defined as:$$F_0 = 0$$$$F_1 = 1$$$$F_n = F_{n-1} + F_{n-2}$$As you've already noted, the sum of two odd number is even, and the sum of an odd and even number is odd. For the Fibonacci sequence, this means that the sequence of \$O\$ (odd) and \$E\$ (even) looks like this:$$E, O, O, E, O, O, E, ...$$In other words, every third term is even.  This gets us to the fact that \$a_n = F_{3n}\$. From this observation, we have this:$$a_n = F_{3n}$$$$a_{n-1} = F_{3(n-1)} = F_{3n-3}$$$$a_{n-2} = F_{3(n-2)} = F_{3n-6}$$$$a_n = F_{3n-1} + F_{3n-2}$$Using the definition of the Fibonacci sequence, and expanding the terms on the right, this becomes:$$a_n = F_{3n-2} + F_{3n-3} + F_{3n-3} + F_{3n-4}$$Substituting \$a\$ terms for \$F\$ terms, we have:$$a_n = F_{3n-2} + 2a_{n-1} + F_{3n-4}$$Expanding the \$F\$ terms on the right again using the definition of the Fibonacci sequence yields:$$a_n = F_{3n-3} + F_{3n-4} + 2a_{n-1} + F_{3n-5} + F_{3n-6}$$Again, substitute \$a\$ terms for \$F\$ terms:$$a_n = a_{n-1} + F_{3n-4} + 2a_{n-1} + F_{3n-5} + a_{n-2}$$Doing one last substitution and rearranging terms, we get:$$a_n = 4a_{n-1} + a_{n-2}$$Code implementationThat means that the outer loop could instead be written like this:unsigned long back = 0;unsigned long front = 2;unsigned long current=0;unsigned long total = front;unsigned long maxNumber;std::cin >> maxNumber;while (front <= maxNumber) {    total += current;    current = 4*front + back;    back = front;    front = current;}std::cout << total << '\n';In this scheme \$a_{n-2}\$ is named back and \$a_{n-1}\$ is named front.  Naturally, \$a_n\$ is named current.Don't recompute valuesThe sequence is the same every time, so it really doesn't make much sense to recompute values every time.  Better would be to compute them once and save them in a std::vector or std::array. Even better is to compute the values once at compile time.  Given the input range, there are less than 30 terms, which is a very modest storage requirement.Omit return 0When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.  Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments:  I didn't know that. or That's bad advice!  My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard.  For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;All versions of both standards since then (C99 and C++98) have maintained the same idea.  We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function.  Reasons against omitting seem to boil down to it looks weird.  If, like me, you're curious about the rationale for the change to the C standard read this question.  Also note that in the early 1990s this was considered sloppy practice because it was undefined behavior (although widely supported) at the time.  So I advocate omitting it; others disagree (often vehemently!)  In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.