Euler challenge 2

Salut les gars, moi c'est Robert, et je n'aime pas les mouches.

(Il me fallait une phrase d'intro, j'ai pas trouvé mieux...)

Bon aujourd'hui, c'est le deuxième exo de l'Euler challenge !

 http://projecteuler.net/index.php?section=problems

DISCLAIMER :

J'ai la flemme de m'inscrire sur le site, donc je ne prendrais même pas la peine de vérifier mes résultats

  By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

1) La méthode brutale

Il y a quelques temps, je découvrais la clause MODEL qui permet de faire de l'itératif à partir de 10g... et donc facilement des suites récurrentes.

Donc du coup, c'est tout simple :

SQL> SELECT sum(u)
  2  FROM (
  3       SELECT n, u
  4       FROM (
  5         SELECT 0 n, 0 U FROM DUAL
  6         UNION ALL SELECT 1 n, 1 U FROM DUAL
  7         ) t
  8       MODEL
  9        dimension by (n)
 10        measures (u)
 11        rules upsert
 12        iterate(33)
 13        (u[2+iteration_number] = u[1+iteration_number] + u[iteration_number])
 14  )
 15  WHERE mod(u, 2) = 0
 16  /

    SUM(U)
----------
  4613732

Passionnant, n'est ce pas... allez, on va rigoler un peu plus !

2) La méthode mathématique

Bon, faire la somme de trucs qui sont déjà définis en se sommant les uns les autres, ça sent l'astuce à plein nez, non ?

(J'ai toujours fait les maths à l'intuition, ce qui explique surement mon destin pitoyable...)

Première remarque :

Un+2 = Un+1 + Un

Pour que Un+2 soit pair, il faut que Un+1 et Un soient soit tous les deux pairs, soit tous les deux impairs.

Mais s'ils sont tous les deux pairs, tous les autres termes le sont... et ce n'est pas le cas.

Bref, regardez bien les termes de la suite :

0 1 1 2 3 5 8 13 21 34 ...

Un terme sur 3 est pair, et bien sûr il est la somme des deux termes impairs précédents.

=> Si on s'arrête au bon endroit, la somme des termes pairs est égale à la somme des termes impairs !

La proposition formelle P(p) :

Quel que soit p, somme(U3i, 0<= i <= p) = somme(Ui impairs, 0<=i<=3p)

La preuve :

P(0) vraie, disons-le (ça c'est de l'argument !)

Supposons p(n) vraie, qu'en est-il de p(n+1) ?

somme(U3i, 0<= i <= n+1) = somme(U3i, 0<= i <= n)  + U3(n+1)

                                                 = somme(U3i, 0<= i <= n)  + U3n+1 + U3n+2

                                                 = somme(Ui impairs, 0<= i <= 3n)  + U3n+1 + U3n+2

                                                 = somme(Ui impairs, 0<= i <= 3(n+1))

Ca, c'est fait... 

somme(U3i, 0<= i <= n) = somme(Ui, 0<= i <= 3n) / 2

Il ne reste plus qu'à calculer la "série" de Fibonacci !

Pour cela, deuxième remarque :

quand on somme des termes qui justement se définissent comme la somme des deux précédents, on doit avoir des chances de retomber sur un de ces termes, non ?

Fibo	0	1	1	2	3	5	8	13	21
Série	0	1	2	4	7	12	20	33	54

Ben on retombe pas tout à fait dessus, mais à un près...

Somme(Ui, 0<=i<=n) = Un+2 - 1

(La démo par récurrence est triviale, vous la ferez vous-même !)

Et du coup, le résultat (en utilisant la forme analytique de Fibonacci) : 

somme(U3i, 0<= i <= n) = (U3n+2 - 1) / 2 = ((((1 + sqrt(5)) / 2) ^ (3n+2) - ((1 - sqrt(5)) / 2) ^ (3n+2)) / sqrt(5) - 1) / 2

(Ok, c'est illisible...)

SQL> SELECT ((power((1+sqrt(5))/2, 35) - power((1-sqrt(5))/2, 35)) / sqrt(5) - 1) / 2 res
  2  FROM dual
  3  /

       RES
----------
   4613732

Bon ok, le U33, je l'ai cherché à tâtons et c'est laid, mais bon !