Le PacBlog !

C'est l'anniversaire du PacBlog ! (en fait c'était il y a deux jours)

Pour ses deux ans, son "Blog Rank" est retombé à 2.

(C'est en gros un indicateur qui dit que quand il est proche de 0, le blog est à chier)

Voilà, pour ne pas s'arrêter sur ce caca d'anniversaire, je vais quand même ajouter un complément sans aucune valeur ajoutée sur l'article précédent.

Donc, pour garantir l'ordre sur le résultat d'un ORDER BY, définissez un champ fictif sur chacune des requêtes composant le UNION ALL :

SQL> SELECT *
  2  FROM (
  3     SELECT a.*, 1 o
  4     FROM paral1 a
  5     UNION ALL
  6     SELECT b.*, 2 o
  7     FROM paral2 b)
  8  ORDER BY o
  9  /

Ah là là, c'est pas ça qui va faire remonter mon BlogRank...

Ouais, on revient aux choses sérieuses : EULER CHALLENGE N°3 !

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

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

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

Ah, la décomposition en facteurs premiers... il n'y a pas grand chose de plus beau en ce monde !

1) La méthode brutale

Sous forme de questions successives :
Mon entier donné est-il divisible par un nombre entre 2 et lui-même ?
Ce diviseur est-il non divisible par un nombre entre 2 et lui-même (moins un) ?

=> Le plus grand de ceux-là, c'est le gagnant.

Allez :

SQL> WITH t AS (
  2  SELECT level n
  3  FROM DUAL
  4  CONNECT BY level <= round(sqrt(600851475143))
  5  )
  6  SELECT case max(n) when 1 then 600851475143 else max(n) end
  7  FROM t t1
  8  WHERE mod(600851475143, n) = 0
  9    AND NOT EXISTS (SELECT null
 10                    FROM t t2
 11                    WHERE mod(t1.n, t2.n) = 0
 12                      AND t2.n < round(sqrt(t1.n))
 13                      AND t2.n > 1
 14                      );

CASEMAX(N)WHEN1THEN600851475143ELSEMAX(N)END
--------------------------------------------
                                        6857

2) La méthode pas géniale mais très légèrement moins naze

Ce qui est bien avec les diviseurs, c'est qu'ils s'emboîtent :
Si :
a = b * q
Et
b = c * q2

Alors d'une part c est un diviseur de a :
a = (c * q2) * q
Avec c < b

D'autre part, si a n'est pas divisible par n < b, alors b ne l'est pas non plus (ni c d'ailleurs).

Donc pour limiter la complexité moyenne de la décomposition, on peut travailler itérativement sur le quotient.
La démarche :
- On prend n = 600851475143
- On cherche le premier diviseur de n entre 2 et racine carrée de n
- Dès qu'on trouve un diviseur p, il est premier par construction (sinon, un autre aurait été diviseur avant lui)

- On prend le quotient n1 = n / p
- On recherche le premier diviseur de n1 entre p et racine carrée de n1
- Dès qu'on trouve un diviseur p1, il est premier par construction (sinon, un autre aurait été diviseur avant lui)

... on itère jusqu'à ce que le diviseur à tester soit supérieur à la racine du quotient.

A la fin, le quotient qu'on n'a pas réussi à diviser est le plus grand facteur premier !

SQL> SELECT n, p, m, n / p
  2  FROM (
  3      SELECT 600851475143 n, 2 p, round(sqrt(13195)) m
  4      FROM DUAL
  5      ) t
  6  MODEL
  7  DIMENSION BY (0 l)
  8  MEASURES (n, p, m)
  9  RULES
 10  ITERATE(1000000) UNTIL (p[0] > m[0])
 11  (
 12      n[0] = CASE mod(n[0], p[0]) WHEN 0 THEN n[0] / p[0] ELSE n[0] END,
 13      p[0] = CASE mod(n[0], p[0]) WHEN 0 THEN p[0] ELSE p[0] + 1 END,
 14      m[0] = CASE mod(n[0], p[0]) WHEN 0 THEN round(sqrt(n[0] / p[0])) ELSE m[0] END
 15      );

         N          P          M        N/P
---------- ---------- ---------- ----------
  10086647       1471         83       6857

Tain, on dirait un exo de terminale...
Mais bon, j'ai vraiment pas trouvé plus joli pour chopper le plus grand facteur premier.

(Triste journée, en plus le temps est à chier...)

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 ?

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 !