Overblog
Suivre ce blog
Administration Créer mon blog
20 juin 2011 1 20 /06 /juin /2011 13:43

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
 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...)

 

Published by Pacman - dans Journal intime
commenter cet article
19 mai 2011 4 19 /05 /mai /2011 20:02

Cher journal intime,

 

Un jour, j'ai commencé à te raconter mes fantasmes arithmétiques.

Et ce jour là, l'ami Keeh les a sur-alimentés avec son lien vers le Euler Project :

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

 

Donc voilà, à partir d'aujourd'hui et autant que faire se peut, nous allons résoudre des défis de ce projet en SQL.

(Et si possible, avec du pur calcul)

 

Et puis tiens, je vais en faire un sur deux en allemand (l'anglais on me force à en faire au boulot, j'en vomis...)

 

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

Published by Pacman - dans Journal intime
commenter cet article
14 avril 2011 4 14 /04 /avril /2011 15:13

Cher journal intime,

 

Je dois te faire un terrible aveux :

J'ai commencé à te tromper avec un autre média d'exhibitionnisme mental :

http://twitter.com/indexffs

 

Eh oui, avec toi, c'est toujours pleins d'attentions, du temps, de l'argent...

 

... alors que Twitter, c'est à la pulsion, du jet instantanné !

 

Plus concrètement, sur le PacTwitt, ce sont des liens vers des sites qui documentent des fonctionnalités que je trouve sympa, ou juste un petit commentaire sur des sujets pour lesquels je n'ai ni le temps, ni la patience pour en faire un vrai article.

 

L'autre différence, c'est que contrairement au PacBlog, le PacTwitt n'est pas obligatoire inutile !

Published by Pacman - dans Journal intime
commenter cet article
15 octobre 2010 5 15 /10 /octobre /2010 13:22

Cher journal intime,

 

Comme tu le sais déjà, Z/Zn est un anneau, quoi qu'il arrive.
Mais qu'est ce qui peut assurer l'inversibilité de chacun de ses éléments ?
Je veux essayer de répondre, sans utiliser les théorèmes d'intellos autistes que je ne comprends pas !


1) Si n n'est pas premier, c'est vite réglé :


On peut trouver p > 1 qui divise n...
... et tu fais comment maintenant pour trouver des candidats à :
p * q = s * n + 1 ???
(Oui, on reconnaît l'identité de bezout... comme quoi ce n'est pas idiot)

 

Partons de p.
p = n * 0 + p, et p > 1

 

Ensuite, on colle successivement (itérativement) des p :
p + p = 0 * n + 2p, et 2p > 1 bien sûr

 

On continue à coller des morceaux jusqu'à ce qu'à atteindre n (puisque p divise n)
p * q = n + 0

 

En collant le suivant, on revient au début et ça boucle !
p * (q+1) = n + p

 

Donc le plus petit reste qu'on peut obtenir en multipliant p par quelque chose et divisant par n... c'est p > 1 !

 

Donc, si n est non premier, il existe au moins un élément de Z/Zn* non inversibe.

 

2) Si n est premier :

 

Prenons un p quelconque entre 2 et n - 1, et cherchons si on lui trouve un inverse dans Z/Zn.
Pour cela, regardons juste ce qu'il se passe quand on tente de le multiplier par chacun des éléments :

r = 0 * p mod n
r = 1 * p mod n
r = 2 * p mod n
...
r = n-1 * p mod n

 

Sur un exemple, p = 7, n = 11

 

i 0 1 2 3 4 5 6 7 8 9 10
p * i 0 7 14 21 28 35 42 49 56 63 70
r 0 7

3

10 6 2 9 5 1 8 4

 

 

(Ho, ça m'a bien fait réviser mes tables de 7 et de 11 !)

 

=> Si on trouve un inverse, c'est bien parce que l'opération * p réalise une permutation de Z/Zn !
(En clair, si en itérant 11 fois, je trouve 11 résultats différents entre 0 et 10, je vais forcément tomber une fois sur le gros lot...)

 

Ca se montre et s'explique aisément :
Si jamais on trouvait deux fois le même résultat, pour deux multiplicateurs différents q' > q, on sait que la différence aurait un reste nul par la division par n :
p * q' - p * q = k n
p * (q' - q) = k n

 

Et comme q' - q est compris entre 1 et n-1, on aurait :
- soit q' - q = 1 et donc p = k n : ouh là, pas possible
- soit q' - q > 1 et là on a trouvé un diviseur à n qui est premier : pas possible non plus !

 

C'est donc impossible, et on retrouve en fait sur la fameuse boucle qu'on avait eu plus haut : si on retombe deux fois sur le même reste, c'est qu'on est en train de boucler... et donc on a du passer par zéro.

 

Donc, si n est premier, tout p de Z/Zn* est inversible.

 

3) Allez, pour ne pas piéger les petits jeunes de terminale qui doivent vraiment démontrer le truc au bac, on va quand même rappeler la démonstration instantannée par l'identité de bezout.

 

Soit n entier strictement supérieur à 0.
Z/Zn est un corps si et seulement :
Pour tout p différent de 0 appartenant à Z/Zn, il existe q appartenant Z/Zn tel que p * q = 1 (multiplication dans Z/Zn)
<=> il existe k entier naturel tel que :
p * q = k * n + 1
p * q + (-k) * n + 1

 

Z/Zn est un corps si et seulement si quelque soit p dans [1,n-1], p et n sont premiers entre eux.
... ce qui veut exactement dire que n est premier !


 

Published by Pacman - dans Journal intime
commenter cet article
8 octobre 2010 5 08 /10 /octobre /2010 18:23

Cher journal intime,

Ces jours-ci, une terrible phrase me hante :
"Z/Zn est un corps, si et seulement si n est premier"

Plus que la réponse basique "parce que Bezout", je voudrais saisir l'essence même de l'inversibilité de ces éléments.
C'est mon prochain objectif dans la vie.

Mais en attendant, le Pacblog inaugure ses nouvelles couleurs.
J'en ai profité également pour écrire mon premier pense bête PL / SQL.

... avec une astuce lamentable pour faire du syntax-highlight :
- J'écris le code sous TOAD qui me fait la coloration syntaxique
- Je le colle dans Word qui garde la mise en forme
- Je sauvegarde en HTML
- Je copie / colle le source du HTML sur le PacBlog...

(Oui, c'est honteux)




Published by Pacman - dans Journal intime
commenter cet article
9 janvier 2010 6 09 /01 /janvier /2010 11:55
Cher journal intime,

Depuis maintenant trois semaines, j'ai rejoint le côté obscur de l'informatique, qui n'est presque plus de l'informatique d'ailleurs... et je m'éloigne du monde d'Oracle après presque 2 ans d'acharnement.

Par la même, c'est également mon lointain rêve de devenir un jour DBA qui perd de sa consistence...

Cela dit, je ne lacherai pas l'affaire si facilement !

C'est donc le moment de faire la liste des bonnes résolutions pour 2010 :

- S'efforcer de poster une fois toutes les deux semaines
- Lire plus de docs Oracle, et plus de Asktom !
- Créer des pages pour expliquer / décrire les concepts Oracle afin de pouvoir y faire référence
- Vaincre Dark Sidious, et dominer l'empire à sa place.

Ah oui au passage : Bonne année !
Published by Pacman - dans Journal intime
commenter cet article
13 août 2009 4 13 /08 /août /2009 22:57

Je suis sur que pour les quelques personnes qui ont lu un des articles, une insulte a du leur venir spontannément à l'esprit :
Mais pourquoi les titres sont toujours en anglais, alors que le contenu est rédigé dans un français puisé des campagnes profondes ?

A vrai dire, je voulais vraiment écrire intégralement en anglais, mais je me suis aperçu que ma réserve de motivation ne suffirait pas à la fois pour me pencher sérieusement sur une problématique, et me cogner la tête contre les murs pour l'écrire dans une autre langue...

Mais je vais me reprendre.
Et pour faire crédible, je vais me fixer des objectifs :
- Un article en allemand au moins d'ici la fin du mois
- Un article en anglais au moins d'ici la mi-septembre
- D'ici la fin de l'année, j'apprends le japonais, et j'écris un article !
(faut peut être que je m'y mette tout de suite, en fait...)

Published by Pacman - dans Journal intime
commenter cet article
18 juillet 2009 6 18 /07 /juillet /2009 16:01
Voilà voilà, j'ai toujours rêvé d'avoir un journal intime, et de le laisser traîner un peu partout pour que tout le monde puisse le lire.
C'est bien à ça que ça sert, un blog ?
J'ai enfin fait le pas. Je suis tellement heureux que je vais m'ouvrir une bière (et changer de caleçon éventuellement).

Bref plus sérieusement, j'ai vu qu'un collègue de forum avait créé un blog pour y poster des petits tours de magie en SQL...

Donc ici, à part mes élucubrations et les expressions de mes perversions les plus étranges, on va parler d'Oracle et de SQL.
Published by Pacman - dans Journal intime
commenter cet article