Project Euler - Problema 2: Números de Fibonacci pares

Letra del problema

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.

Soluciones

Método 1 - Verificar paridad para cada $F_x$

Un numero $x$ es par si es divisible por 2, esto es decir que $x$ es múltiplo de 2. Más formalmente:

$$x \ \text{es par} \ \iff \ \exists\,c\in\mathbb{Z} \ : \ x = c \cdot 2$$

Por esto, $\frac x2 = c$ con resto 0, lo cual puede verificarse mediante aritmética modular: $x \bmod 2 = 0$

Sea $F_x$ la sucesión de Fibonacci, esta es generada por la recurrencia:

$$\left\{\begin{aligned} & F_{0} = 0 \\ & F_{1} = 1 \\ & F_{x} = F_{x-1}+F_{x-2} \end{aligned}\right.$$

Esta recurrencia se puede implementar naturalmente de manera recursiva, aunque resulte ineficiente. Normalmente las condiciones iniciales elegidas son $(0, 1)$, o $(1, 1)$ pero esto no cambia el resultado para el problema en cuestión donde solo interesa sumar términos pares de la sucesión.

Entonces una solución posible es sumar cada $F_x$ tal que $F_x \leq n$ y $F_x \bmod 2 = 0$.

\begin{algorithm}\caption{}\begin{algorithmic}
  \FUNCTION{pe2}{$n$}
    \STATE $i := 0$
    \STATE $x := 0$
    \STATE $r := 0$
    \WHILE{$x \leq n$}
      \IF{$x \; mod \; 2 = 0$}
      \STATE $r := r + x$
      \ENDIF
      \STATE $i := i + 1$
      \STATE $x := $ \CALL{fib}{$i$}
    \ENDWHILE
    \RETURN $r$
  \ENDFUNCTION
  \STATE
  \FUNCTION{fib}{$x$}
    \IF{$x = 0$}
      \RETURN $0$
    \ENDIF
    \IF{$x = 1$}
    \RETURN $1$
    \ENDIF
    \RETURN \CALL{fib}{$x-1$} $ + $ \CALL{fib}{$x-2$}
  \ENDFUNCTION
\end{algorithmic}\end{algorithm}

Complejidad
Sea $x(n)$ la función inversa de $F_x=n$, esta retorna en que posición de la sucesión se encuentra el valor $n$:

$$x(n) = \left \lfloor \log_\phi (n \,\sqrt{5}+\frac{1}{2}) \right \rfloor \in O(\log(n))$$

El ciclo while en $\text{PE2}(n)$ se ejecuta una cantidad de veces no mayor a $O(\log(n))$. Por otro lado, $\text{FIB}(x) \in O(2^n)$.

Por lo tanto, $\text{PE2}(n) \in O(2^n \log(n))$.

Método 2 - Generar $F_x$ verificando paridad de términos

Es natural implementar $F_x$ recursivamente, porque de acuerdo al paso recursivo cada término depende de los dos términos anteriores en la sucesión:

$$F_{x} = F_{x-1} + F_{x-2}$$

Si la recurrencia se cumple para $x$, entonces también se cumple para $x+2$. Luego:

$$F_{x+2} = F_{x+1} + F_{x}$$

Esta observación permite generar la sucesión “hacia adelante”, sin tener que ir “hacia atras”, y se puede implementar por recursión de cola o de manera iterativa.

La versión iterativa de $\text{FIB}$:

\begin{algorithm}\begin{algorithmic}
  \FUNCTION{fib}{$x$}
    \STATE $a := 0$
    \STATE $b := 1$
    \FOR{$j := 0$ \TO $x-1$}
      \STATE $t := a + b$
      \STATE $a := b$
      \STATE $b := t$
    \ENDFOR
    \RETURN $b$
  \ENDFUNCTION
\end{algorithmic}\end{algorithm}

Con dos variables es suficiente para guardar los dos últimos valores generados, y con estos generar el siguiente.

Esta versión de $\text{FIB}(x)$, además de ser más eficiente, se puede adaptar fácilmente para resolver el problema en cuestión donde hay que sumar cada $F_x$ tal que $F_x \leq n$ y $F_x \bmod 2 = 0$ , y no es necesario usar una función auxiliar para calcular $F_x$.

\begin{algorithm}\caption{}\begin{algorithmic}
  \FUNCTION{pe2}{$n$}
    \STATE $a := 0$
    \STATE $b := 1$
    \STATE $r := 0$
    \WHILE{$b \leq n$}
      \IF{$x \; mod \; 2 = 0$}
        \STATE $r := r + b$
      \ENDIF
      \STATE $t := a + b$
      \STATE $a := b$
      \STATE $b := t$
    \ENDWHILE
    \RETURN $r$
  \ENDFUNCTION
\end{algorithmic}\end{algorithm}

Complejidad
Sea $x(n)$ la función inversa de $F_x=n$, esta retorna en que posición de la sucesión se encuentra el valor $n$:

$$x(n)=\left \lfloor \log_\phi (n \,\sqrt{5}+\frac{1}{2}) \right \rfloor \ \in \ O(\log(n))$$

El ciclo while en $\text{PE2}(n)$ se ejecuta una cantidad de veces no mayor a $O(\log(n))$.

Por lo tanto, $\text{PE2}(n) \in O(\log(n))$.

Método 3 - Generar términos pares de $F_x$

Observando los términos de $F_x$ comenzando desde $(1, 1)$:

$$1,\ 1,\ \color{red}{2},\ 3,\ 5,\ \color{red}{8},\ 13,\ 21,\ \color{red}{34},\ 55,\ 89,\ ...$$

Se puede notar que cualquier término par siempre se encuentra en una posición que es múltiplo de 3.

Mantener tres variables para guardar los tres últimos valores generados de $F_x$ sirve para evitar tener que verificar la paridad de cada termino, ya que en toda iteración el tercer término generado es siempre par.

\begin{algorithm}\caption{}\begin{algorithmic}
 \FUNCTION{pe2}{$n$}
   \STATE $a := 1$
   \STATE $b := 1$
   \STATE $c := 2$
   \STATE $r := 0$
   \WHILE{$c \leq n$}
     \STATE $r := r + c$
     \STATE $a := b + c$
     \STATE $b := a + c$
     \STATE $c := a + b$
   \ENDWHILE
   \RETURN $r$
 \ENDFUNCTION
\end{algorithmic}\end{algorithm}

Complejidad
$\text{PE2}(n) \in O(\log(n))$.

Método 4 - Suma de pares en forma cerrada

Partiendo de la suma de $F_x$:

$$\sum_{i=1}^{x}F_i=F(x+2)-1 \label{eq4.1}\tag{4.1}$$

Reagrupando los términos de \ref{eq4.1}:

$$\begin{align*} \sum_{i=1}^{x}F_i &= 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + ...\\ &= (1+1) + 2 + (3+5) + 8 + (13+21) + 34 + ...\\ &= 2 + 2 + 8 + 8 + 34 + 34 + ...\\ &= 2\,2 + 2\,8 + 2\,34 + ...\\ &= 2\,(2 + 8 + 34 + ...) \end{align*}$$

\begin{algorithm}\caption{}\begin{algorithmic}
 \STATE $\phi = (1 + \sqrt{5})/2$
 \STATE
 \FUNCTION{pe2}{$n$}
   \STATE $x := \log_\phi(n \times \sqrt{5} + 0.5)$
   \STATE $x := $ \CALL{nearestMultOf3}{$x$}
   \RETURN $($\CALL{fib}{$x+2$} $-1)/2$
   \ENDFUNCTION
   \STATE
   \FUNCTION{fib}{$x$}
     \RETURN $(\phi^x -(1-\phi)^x)/\sqrt{5}$
   \ENDFUNCTION
   \STATE
   \FUNCTION{nearestMultOf3}{$x$}
     \RETURN $3 \times (x/3)$
   \ENDFUNCTION
\end{algorithmic}\end{algorithm}