Menu
Featured / Mathématique / Par la communauté

Deviner le code d’un interphone grâce aux suites de De Bruijn

Quand je me balade à Lyon, je rêve de pouvoir ouvrir les portes de tous les immeubles. Ça peut paraître un peu con, mais j’adore visiter des halls d’entrée, découvrir des architectures. Une belle porte fermée, c’est comme une gourmandise inaccessible, je veux entrer et explorer.

Malheureusement, toutes les portes sont verrouillées par un digicode. Alors en googlant un peu, j’ai découvert 3 méthodes pour ouvrir des portes à code.

La moins légale : le pass universel

Posséder un pass Vigik. Les ouvriers EDF, les pompiers, les facteurs en ont un. Ils peuvent ouvrir une bonne partie des portes sans problème. Il y a quelques années, il était facile d’acheter un pass Vigik au marché noir ou sur le Dark Web.

Aujourd’hui, ces pass sont jetables, temporaires ou désactivables à distance, alors ça devient plus compliqué. Tant mieux d’un côté 🙂

Le petit boitier Vigik noir, en bas

 

La plus « James Bond » : l’analyse des touches

Soit vous mettez un peu de farine sur un digicode, vous soufflez pour l’estomper, et vous attendez que quelqu’un passe en tapant son code. Les touches sans farine sont celles des chiffres du code. Ouais, je sais, il faut de la farine.

Sinon, vous observez attentivement les touches du digicode. Vous pourriez y trouver des traces de crasses sur les touches fréquemment appuyées, ou des traces d’usure ENTRE les touches fréquemment appuyées (parce qu’on glisse nos doigts d’une touche à l’autre quand elles sont proches). J’essaie souvent cette méthode, mais sans succès pour l’instant.

La plus mathématique : la suite de De Bruijn

Quand rien ne marche, que la vie est une chienne, que tout fout le camp, heureusement, il reste les maths. Et la pizza.

J’ai donc raisonné autrement : puisque les digicodes me résistent, de combien de temps aurais-je besoin pour essayer toutes les combinaisons sur le clavier ? En partant du principe que le code que je recherche est composé de 4 chiffres, je devrais taper :

  • 0000
  • 0001
  • 0002
  • 9999

À un rythme de 1 code toutes les 2 secondes, il me faudrait environ 13 heures pour tout essayer. Hum… C’est bête, parce que dès les 2 premières tentatives, je perds un temps précieux. Je m’explique.

En essayant chaque combinaison bêtement, je tape 0000, puis 0001. Au final, en tapant seulement 00001, j’essaie bien ces deux premières combinaisons, mais en tapant sur 3 touches de moins.

Et si j’arrivais à trouver la combinaison de touches parfaite, pour essayer TOUS les nombres de 0000 à 9999, en un temps minimal ?

La suite de De Bruijn à la rescousse !

Né en 1918 et mort en 2012 (gg dude), Nicolaas Govert de Bruijn est un célèbre mathématicien. Il a beaucoup travaillé sur des problèmes de maths évidemment (théorie des graphes et assistance de preuves entre autres), mais aussi en neurologie.

Konrad Jacobs, Erlangen, Copyright is MFO
Mathematisches Forschungsinstitut Oberwolfach

Il est célèbre pour avoir théorisé les suites de De Bruijn. En langage mathématique, Wikipédia les définit comme suit :

Une suite de de Bruijn d’ordre n sur k symboles est un mot circulaire sur un alphabet A à k symboles qui contient toutes les suites de longueur n sur A une et une seule fois

Parlons plus simplement. Une suite de De Bruijn permet d’obtenir une suite de toutes les combinaisons possibles d’une série de chiffres, sans répéter 2 fois la même combinaison. C’est ce que je vous montrais toute à l’heure :

– Si je tape 0000, puis 0001 : je tape 2 combinaisons distinctes sur mon digicode. Ça marche, mais ce n’est pas optimal.

– Si je tape 00001 : je ne tape plus qu’une combinaison, qui contient les deux précédentes, sans répétition. Voila déjà une mini-suite de De Bruijn.

Reprenons la définition mathématique, pour ceux que ça intéresse

– Un alphabet (A), composé de (k) symboles. C’est à dire les symboles que nous voulons manipuler. Dans le cadre d’un digicode, l’alphabet à utiliser est l’ensemble des chiffres de 0 à 9 (A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, k = 10).

– Un ordre (n). C’est à dire la taille des combinaisons que l’on veut assembler avec notre alphabet. Les digicodes se composent généralement de 4 chiffres, donc l’ordre n=4.

En appliquant ensuite un algorithme de construction bien précis à vos paramètres de départ, vous obtiendrez une suite de combinaisons optimale.

Concrètement, en quoi ça m’aide à ouvrir une porte ?

Sans utiliser de suite de De Bruijn, en essayant toutes les combinaisons de votre digicode à 4 chiffres, vous allez devoir taper sur potentiellement 39 996 touches.

En optimisant votre recherche avec une suite de De Bruijn, vous n’aurez plus que k^n touches à taper dans le pire des cas (c’est à dire 9999, puisque c’est le dernier code qu’on essaie). Au final, vous taperez seulement sur 10^4 = 10000 touches. C’est 4 fois moins de travail !

Voila la série de chiffres à taper sur n’importe quel digicode pour ouvrir la porte :

0 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 8 0 0 0 9 0 0 1 1 0 0 1 2 0 0 1 3 0 0 1 4 0 0 1 5 0 0 1 6 0 0 1 7 0 0 1 8 0 0 1 9 0 0 2 1 0 0 2 2 0 0 2 3 0 0 2 4 0 0 2 5 0 0 2 6 0 0 2 7 0 0 2 8 0 0 2 9 0 0 3 1 0 0 3 2 0 0 3 3 0 0 3 4 0 0 3 5 0 0 3 6 0 0 3 7 0 0 3 8 0 0 3 9 0 0 4 1 0 0 4 2 0 0 4 3 0 0 4 4 0 0 4 5 0 0 4 6 0 0 4 7 0 0 4 8 0 0 4 9 0 0 5 1 0 0 5 2 0 0 5 3 0 0 5 4 0 0 5 5 0 0 5 6 0 0 5 7 0 0 5 8 0 0 5 9 0 0 6 1 0 0 6 2 0 0 6 3 0 0 6 4 0 0 6 5 0 0 6 6 0 0 6 7 0 0 6 8 0 0 6 9 0 0 7 1 0 0 7 2 0 0 7 3 0 0 7 4 0 0 7 5 0 0 7 6 0 0 7 7 0 0 7 8 0 0 7 9 0 0 8 1 0 0 8 2 0 0 8 3 0 0 8 4 0 0 8 5 0 0 8 6 0 0 8 7 0 0 8 8 0 0 8 9 0 0 9 1 0 0 9 2 0 0 9 3 0 0 9 4 0 0 9 5 0 0 9 6 0 0 9 7 0 0 9 8 0 0 9 9 0 1 0 1 0 2 0 1 0 3 0 1 0 4 0 1 0 5 0 1 0 6 0 1 0 7 0 1 0 8 0 1 0 9 0 1 1 1 0 1 1 2 0 1 1 3 0 1 1 4 0 1 1 5 0 1 1 6 0 1 1 7 0 1 1 8 0 1 1 9 0 1 2 1 0 1 2 2 0 1 2 3 0 1 2 4 0 1 2 5 0 1 2 6 0 1 2 7 0 1 2 8 0 1 2 9 0 1 3 1 0 1 3 2 0 1 3 3 0 1 3 4 0 1 3 5 0 1 3 6 0 1 3 7 0 1 3 8 0 1 3 9 0 1 4 1 0 1 4 2 0 1 4 3 0 1 4 4 0 1 4 5 0 1 4 6 0 1 4 7 0 1 4 8 0 1 4 9 0 1 5 1 0 1 5 2 0 1 5 3 0 1 5 4 0 1 5 5 0 1 5 6 0 1 5 7 0 1 5 8 0 1 5 9 0 1 6 1 0 1 6 2 0 1 6 3 0 1 6 4 0 1 6 5 0 1 6 6 0 1 6 7 0 1 6 8 0 1 6 9 0 1 7 1 0 1 7 2 0 1 7 3 0 1 7 4 0 1 7 5 0 1 7 6 0 1 7 7 0 1 7 8 0 1 7 9 0 1 8 1 0 1 8 2 0 1 8 3 0 1 8 4 0 1 8 5 0 1 8 6 0 1 8 7 0 1 8 8 0 1 8 9 0 1 9 1 0 1 9 2 0 1 9 3 0 1 9 4 0 1 9 5 0 1 9 6 0 1 9 7 0 1 9 8 0 1 9 9 0 2 0 2 0 3 0 2 0 4 0 2 0 5 0 2 0 6 0 2 0 7 0 2 0 8 0 2 0 9 0 2 1 1 0 2 1 2 0 2 1 3 0 2 1 4 0 2 1 5 0 2 1 6 0 2 1 7 0 2 1 8 0 2 1 9 0 2 2 1 0 2 2 2 0 2 2 3 0 2 2 4 0 2 2 5 0 2 2 6 0 2 2 7 0 2 2 8 0 2 2 9 0 2 3 1 0 2 3 2 0 2 3 3 0 2 3 4 0 2 3 5 0 2 3 6 0 2 3 7 0 2 3 8 0 2 3 9 0 2 4 1 0 2 4 2 0 2 4 3 0 2 4 4 0 2 4 5 0 2 4 6 0 2 4 7 0 2 4 8 0 2 4 9 0 2 5 1 0 2 5 2 0 2 5 3 0 2 5 4 0 2 5 5 0 2 5 6 0 2 5 7 0 2 5 8 0 2 5 9 0 2 6 1 0 2 6 2 0 2 6 3 0 2 6 4 0 2 6 5 0 2 6 6 0 2 6 7 0 2 6 8 0 2 6 9 0 2 7 1 0 2 7 2 0 2 7 3 0 2 7 4 0 2 7 5 0 2 7 6 0 2 7 7 0 2 7 8 0 2 7 9 0 2 8 1 0 2 8 2 0 2 8 3 0 2 8 4 0 2 8 5 0 2 8 6 0 2 8 7 0 2 8 8 0 2 8 9 0 2 9 1 0 2 9 2 0 2 9 3 0 2 9 4 0 2 9 5 0 2 9 6 0 2 9 7 0 2 9 8 0 2 9 9 0 3 0 3 0 4 0 3 0 5 0 3 0 6 0 3 0 7 0 3 0 8 0 3 0 9 0 3 1 1 0 3 1 2 0 3 1 3 0 3 1 4 0 3 1 5 0 3 1 6 0 3 1 7 0 3 1 8 0 3 1 9 0 3 2 1 0 3 2 2 0 3 2 3 0 3 2 4 0 3 2 5 0 3 2 6 0 3 2 7 0 3 2 8 0 3 2 9 0 3 3 1 0 3 3 2 0 3 3 3 0 3 3 4 0 3 3 5 0 3 3 6 0 3 3 7 0 3 3 8 0 3 3 9 0 3 4 1 0 3 4 2 0 3 4 3 0 3 4 4 0 3 4 5 0 3 4 6 0 3 4 7 0 3 4 8 0 3 4 9 0 3 5 1 0 3 5 2 0 3 5 3 0 3 5 4 0 3 5 5 0 3 5 6 0 3 5 7 0 3 5 8 0 3 5 9 0 3 6 1 0 3 6 2 0 3 6 3 0 3 6 4 0 3 6 5 0 3 6 6 0 3 6 7 0 3 6 8 0 3 6 9 0 3 7 1 0 3 7 2 0 3 7 3 0 3 7 4 0 3 7 5 0 3 7 6 0 3 7 7 0 3 7 8 0 3 7 9 0 3 8 1 0 3 8 2 0 3 8 3 0 3 8 4 0 3 8 5 0 3 8 6 0 3 8 7 0 3 8 8 0 3 8 9 0 3 9 1 0 3 9 2 0 3 9 3 0 3 9 4 0 3 9 5 0 3 9 6 0 3 9 7 0 3 9 8 0 3 9 9 0 4 0 4 0 5 0 4 0 6 0 4 0 7 0 4 0 8 0 4 0 9 0 4 1 1 0 4 1 2 0 4 1 3 0 4 1 4 0 4 1 5 0 4 1 6 0 4 1 7 0 4 1 8 0 4 1 9 0 4 2 1 0 4 2 2 0 4 2 3 0 4 2 4 0 4 2 5 0 4 2 6 0 4 2 7 0 4 2 8 0 4 2 9 0 4 3 1 0 4 3 2 0 4 3 3 0 4 3 4 0 4 3 5 0 4 3 6 0 4 3 7 0 4 3 8 0 4 3 9 0 4 4 1 0 4 4 2 0 4 4 3 0 4 4 4 0 4 4 5 0 4 4 6 0 4 4 7 0 4 4 8 0 4 4 9 0 4 5 1 0 4 5 2 0 4 5 3 0 4 5 4 0 4 5 5 0 4 5 6 0 4 5 7 0 4 5 8 0 4 5 9 0 4 6 1 0 4 6 2 0 4 6 3 0 4 6 4 0 4 6 5 0 4 6 6 0 4 6 7 0 4 6 8 0 4 6 9 0 4 7 1 0 4 7 2 0 4 7 3 0 4 7 4 0 4 7 5 0 4 7 6 0 4 7 7 0 4 7 8 0 4 7 9 0 4 8 1 0 4 8 2 0 4 8 3 0 4 8 4 0 4 8 5 0 4 8 6 0 4 8 7 0 4 8 8 0 4 8 9 0 4 9 1 0 4 9 2 0 4 9 3 0 4 9 4 0 4 9 5 0 4 9 6 0 4 9 7 0 4 9 8 0 4 9 9 0 5 0 5 0 6 0 5 0 7 0 5 0 8 0 5 0 9 0 5 1 1 0 5 1 2 0 5 1 3 0 5 1 4 0 5 1 5 0 5 1 6 0 5 1 7 0 5 1 8 0 5 1 9 0 5 2 1 0 5 2 2 0 5 2 3 0 5 2 4 0 5 2 5 0 5 2 6 0 5 2 7 0 5 2 8 0 5 2 9 0 5 3 1 0 5 3 2 0 5 3 3 0 5 3 4 0 5 3 5 0 5 3 6 0 5 3 7 0 5 3 8 0 5 3 9 0 5 4 1 0 5 4 2 0 5 4 3 0 5 4 4 0 5 4 5 0 5 4 6 0 5 4 7 0 5 4 8 0 5 4 9 0 5 5 1 0 5 5 2 0 5 5 3 0 5 5 4 0 5 5 5 0 5 5 6 0 5 5 7 0 5 5 8 0 5 5 9 0 5 6 1 0 5 6 2 0 5 6 3 0 5 6 4 0 5 6 5 0 5 6 6 0 5 6 7 0 5 6 8 0 5 6 9 0 5 7 1 0 5 7 2 0 5 7 3 0 5 7 4 0 5 7 5 0 5 7 6 0 5 7 7 0 5 7 8 0 5 7 9 0 5 8 1 0 5 8 2 0 5 8 3 0 5 8 4 0 5 8 5 0 5 8 6 0 5 8 7 0 5 8 8 0 5 8 9 0 5 9 1 0 5 9 2 0 5 9 3 0 5 9 4 0 5 9 5 0 5 9 6 0 5 9 7 0 5 9 8 0 5 9 9 0 6 0 6 0 7 0 6 0 8 0 6 0 9 0 6 1 1 0 6 1 2 0 6 1 3 0 6 1 4 0 6 1 5 0 6 1 6 0 6 1 7 0 6 1 8 0 6 1 9 0 6 2 1 0 6 2 2 0 6 2 3 0 6 2 4 0 6 2 5 0 6 2 6 0 6 2 7 0 6 2 8 0 6 2 9 0 6 3 1 0 6 3 2 0 6 3 3 0 6 3 4 0 6 3 5 0 6 3 6 0 6 3 7 0 6 3 8 0 6 3 9 0 6 4 1 0 6 4 2 0 6 4 3 0 6 4 4 0 6 4 5 0 6 4 6 0 6 4 7 0 6 4 8 0 6 4 9 0 6 5 1 0 6 5 2 0 6 5 3 0 6 5 4 0 6 5 5 0 6 5 6 0 6 5 7 0 6 5 8 0 6 5 9 0 6 6 1 0 6 6 2 0 6 6 3 0 6 6 4 0 6 6 5 0 6 6 6 0 6 6 7 0 6 6 8 0 6 6 9 0 6 7 1 0 6 7 2 0 6 7 3 0 6 7 4 0 6 7 5 0 6 7 6 0 6 7 7 0 6 7 8 0 6 7 9 0 6 8 1 0 6 8 2 0 6 8 3 0 6 8 4 0 6 8 5 0 6 8 6 0 6 8 7 0 6 8 8 0 6 8 9 0 6 9 1 0 6 9 2 0 6 9 3 0 6 9 4 0 6 9 5 0 6 9 6 0 6 9 7 0 6 9 8 0 6 9 9 0 7 0 7 0 8 0 7 0 9 0 7 1 1 0 7 1 2 0 7 1 3 0 7 1 4 0 7 1 5 0 7 1 6 0 7 1 7 0 7 1 8 0 7 1 9 0 7 2 1 0 7 2 2 0 7 2 3 0 7 2 4 0 7 2 5 0 7 2 6 0 7 2 7 0 7 2 8 0 7 2 9 0 7 3 1 0 7 3 2 0 7 3 3 0 7 3 4 0 7 3 5 0 7 3 6 0 7 3 7 0 7 3 8 0 7 3 9 0 7 4 1 0 7 4 2 0 7 4 3 0 7 4 4 0 7 4 5 0 7 4 6 0 7 4 7 0 7 4 8 0 7 4 9 0 7 5 1 0 7 5 2 0 7 5 3 0 7 5 4 0 7 5 5 0 7 5 6 0 7 5 7 0 7 5 8 0 7 5 9 0 7 6 1 0 7 6 2 0 7 6 3 0 7 6 4 0 7 6 5 0 7 6 6 0 7 6 7 0 7 6 8 0 7 6 9 0 7 7 1 0 7 7 2 0 7 7 3 0 7 7 4 0 7 7 5 0 7 7 6 0 7 7 7 0 7 7 8 0 7 7 9 0 7 8 1 0 7 8 2 0 7 8 3 0 7 8 4 0 7 8 5 0 7 8 6 0 7 8 7 0 7 8 8 0 7 8 9 0 7 9 1 0 7 9 2 0 7 9 3 0 7 9 4 0 7 9 5 0 7 9 6 0 7 9 7 0 7 9 8 0 7 9 9 0 8 0 8 0 9 0 8 1 1 0 8 1 2 0 8 1 3 0 8 1 4 0 8 1 5 0 8 1 6 0 8 1 7 0 8 1 8 0 8 1 9 0 8 2 1 0 8 2 2 0 8 2 3 0 8 2 4 0 8 2 5 0 8 2 6 0 8 2 7 0 8 2 8 0 8 2 9 0 8 3 1 0 8 3 2 0 8 3 3 0 8 3 4 0 8 3 5 0 8 3 6 0 8 3 7 0 8 3 8 0 8 3 9 0 8 4 1 0 8 4 2 0 8 4 3 0 8 4 4 0 8 4 5 0 8 4 6 0 8 4 7 0 8 4 8 0 8 4 9 0 8 5 1 0 8 5 2 0 8 5 3 0 8 5 4 0 8 5 5 0 8 5 6 0 8 5 7 0 8 5 8 0 8 5 9 0 8 6 1 0 8 6 2 0 8 6 3 0 8 6 4 0 8 6 5 0 8 6 6 0 8 6 7 0 8 6 8 0 8 6 9 0 8 7 1 0 8 7 2 0 8 7 3 0 8 7 4 0 8 7 5 0 8 7 6 0 8 7 7 0 8 7 8 0 8 7 9 0 8 8 1 0 8 8 2 0 8 8 3 0 8 8 4 0 8 8 5 0 8 8 6 0 8 8 7 0 8 8 8 0 8 8 9 0 8 9 1 0 8 9 2 0 8 9 3 0 8 9 4 0 8 9 5 0 8 9 6 0 8 9 7 0 8 9 8 0 8 9 9 0 9 0 9 1 1 0 9 1 2 0 9 1 3 0 9 1 4 0 9 1 5 0 9 1 6 0 9 1 7 0 9 1 8 0 9 1 9 0 9 2 1 0 9 2 2 0 9 2 3 0 9 2 4 0 9 2 5 0 9 2 6 0 9 2 7 0 9 2 8 0 9 2 9 0 9 3 1 0 9 3 2 0 9 3 3 0 9 3 4 0 9 3 5 0 9 3 6 0 9 3 7 0 9 3 8 0 9 3 9 0 9 4 1 0 9 4 2 0 9 4 3 0 9 4 4 0 9 4 5 0 9 4 6 0 9 4 7 0 9 4 8 0 9 4 9 0 9 5 1 0 9 5 2 0 9 5 3 0 9 5 4 0 9 5 5 0 9 5 6 0 9 5 7 0 9 5 8 0 9 5 9 0 9 6 1 0 9 6 2 0 9 6 3 0 9 6 4 0 9 6 5 0 9 6 6 0 9 6 7 0 9 6 8 0 9 6 9 0 9 7 1 0 9 7 2 0 9 7 3 0 9 7 4 0 9 7 5 0 9 7 6 0 9 7 7 0 9 7 8 0 9 7 9 0 9 8 1 0 9 8 2 0 9 8 3 0 9 8 4 0 9 8 5 0 9 8 6 0 9 8 7 0 9 8 8 0 9 8 9 0 9 9 1 0 9 9 2 0 9 9 3 0 9 9 4 0 9 9 5 0 9 9 6 0 9 9 7 0 9 9 8 0 9 9 9 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 1 6 1 1 1 7 1 1 1 8 1 1 1 9 1 1 2 2 1 1 2 3 1 1 2 4 1 1 2 5 1 1 2 6 1 1 2 7 1 1 2 8 1 1 2 9 1 1 3 2 1 1 3 3 1 1 3 4 1 1 3 5 1 1 3 6 1 1 3 7 1 1 3 8 1 1 3 9 1 1 4 2 1 1 4 3 1 1 4 4 1 1 4 5 1 1 4 6 1 1 4 7 1 1 4 8 1 1 4 9 1 1 5 2 1 1 5 3 1 1 5 4 1 1 5 5 1 1 5 6 1 1 5 7 1 1 5 8 1 1 5 9 1 1 6 2 1 1 6 3 1 1 6 4 1 1 6 5 1 1 6 6 1 1 6 7 1 1 6 8 1 1 6 9 1 1 7 2 1 1 7 3 1 1 7 4 1 1 7 5 1 1 7 6 1 1 7 7 1 1 7 8 1 1 7 9 1 1 8 2 1 1 8 3 1 1 8 4 1 1 8 5 1 1 8 6 1 1 8 7 1 1 8 8 1 1 8 9 1 1 9 2 1 1 9 3 1 1 9 4 1 1 9 5 1 1 9 6 1 1 9 7 1 1 9 8 1 1 9 9 1 2 1 2 1 3 1 2 1 4 1 2 1 5 1 2 1 6 1 2 1 7 1 2 1 8 1 2 1 9 1 2 2 2 1 2 2 3 1 2 2 4 1 2 2 5 1 2 2 6 1 2 2 7 1 2 2 8 1 2 2 9 1 2 3 2 1 2 3 3 1 2 3 4 1 2 3 5 1 2 3 6 1 2 3 7 1 2 3 8 1 2 3 9 1 2 4 2 1 2 4 3 1 2 4 4 1 2 4 5 1 2 4 6 1 2 4 7 1 2 4 8 1 2 4 9 1 2 5 2 1 2 5 3 1 2 5 4 1 2 5 5 1 2 5 6 1 2 5 7 1 2 5 8 1 2 5 9 1 2 6 2 1 2 6 3 1 2 6 4 1 2 6 5 1 2 6 6 1 2 6 7 1 2 6 8 1 2 6 9 1 2 7 2 1 2 7 3 1 2 7 4 1 2 7 5 1 2 7 6 1 2 7 7 1 2 7 8 1 2 7 9 1 2 8 2 1 2 8 3 1 2 8 4 1 2 8 5 1 2 8 6 1 2 8 7 1 2 8 8 1 2 8 9 1 2 9 2 1 2 9 3 1 2 9 4 1 2 9 5 1 2 9 6 1 2 9 7 1 2 9 8 1 2 9 9 1 3 1 3 1 4 1 3 1 5 1 3 1 6 1 3 1 7 1 3 1 8 1 3 1 9 1 3 2 2 1 3 2 3 1 3 2 4 1 3 2 5 1 3 2 6 1 3 2 7 1 3 2 8 1 3 2 9 1 3 3 2 1 3 3 3 1 3 3 4 1 3 3 5 1 3 3 6 1 3 3 7 1 3 3 8 1 3 3 9 1 3 4 2 1 3 4 3 1 3 4 4 1 3 4 5 1 3 4 6 1 3 4 7 1 3 4 8 1 3 4 9 1 3 5 2 1 3 5 3 1 3 5 4 1 3 5 5 1 3 5 6 1 3 5 7 1 3 5 8 1 3 5 9 1 3 6 2 1 3 6 3 1 3 6 4 1 3 6 5 1 3 6 6 1 3 6 7 1 3 6 8 1 3 6 9 1 3 7 2 1 3 7 3 1 3 7 4 1 3 7 5 1 3 7 6 1 3 7 7 1 3 7 8 1 3 7 9 1 3 8 2 1 3 8 3 1 3 8 4 1 3 8 5 1 3 8 6 1 3 8 7 1 3 8 8 1 3 8 9 1 3 9 2 1 3 9 3 1 3 9 4 1 3 9 5 1 3 9 6 1 3 9 7 1 3 9 8 1 3 9 9 1 4 1 4 1 5 1 4 1 6 1 4 1 7 1 4 1 8 1 4 1 9 1 4 2 2 1 4 2 3 1 4 2 4 1 4 2 5 1 4 2 6 1 4 2 7 1 4 2 8 1 4 2 9 1 4 3 2 1 4 3 3 1 4 3 4 1 4 3 5 1 4 3 6 1 4 3 7 1 4 3 8 1 4 3 9 1 4 4 2 1 4 4 3 1 4 4 4 1 4 4 5 1 4 4 6 1 4 4 7 1 4 4 8 1 4 4 9 1 4 5 2 1 4 5 3 1 4 5 4 1 4 5 5 1 4 5 6 1 4 5 7 1 4 5 8 1 4 5 9 1 4 6 2 1 4 6 3 1 4 6 4 1 4 6 5 1 4 6 6 1 4 6 7 1 4 6 8 1 4 6 9 1 4 7 2 1 4 7 3 1 4 7 4 1 4 7 5 1 4 7 6 1 4 7 7 1 4 7 8 1 4 7 9 1 4 8 2 1 4 8 3 1 4 8 4 1 4 8 5 1 4 8 6 1 4 8 7 1 4 8 8 1 4 8 9 1 4 9 2 1 4 9 3 1 4 9 4 1 4 9 5 1 4 9 6 1 4 9 7 1 4 9 8 1 4 9 9 1 5 1 5 1 6 1 5 1 7 1 5 1 8 1 5 1 9 1 5 2 2 1 5 2 3 1 5 2 4 1 5 2 5 1 5 2 6 1 5 2 7 1 5 2 8 1 5 2 9 1 5 3 2 1 5 3 3 1 5 3 4 1 5 3 5 1 5 3 6 1 5 3 7 1 5 3 8 1 5 3 9 1 5 4 2 1 5 4 3 1 5 4 4 1 5 4 5 1 5 4 6 1 5 4 7 1 5 4 8 1 5 4 9 1 5 5 2 1 5 5 3 1 5 5 4 1 5 5 5 1 5 5 6 1 5 5 7 1 5 5 8 1 5 5 9 1 5 6 2 1 5 6 3 1 5 6 4 1 5 6 5 1 5 6 6 1 5 6 7 1 5 6 8 1 5 6 9 1 5 7 2 1 5 7 3 1 5 7 4 1 5 7 5 1 5 7 6 1 5 7 7 1 5 7 8 1 5 7 9 1 5 8 2 1 5 8 3 1 5 8 4 1 5 8 5 1 5 8 6 1 5 8 7 1 5 8 8 1 5 8 9 1 5 9 2 1 5 9 3 1 5 9 4 1 5 9 5 1 5 9 6 1 5 9 7 1 5 9 8 1 5 9 9 1 6 1 6 1 7 1 6 1 8 1 6 1 9 1 6 2 2 1 6 2 3 1 6 2 4 1 6 2 5 1 6 2 6 1 6 2 7 1 6 2 8 1 6 2 9 1 6 3 2 1 6 3 3 1 6 3 4 1 6 3 5 1 6 3 6 1 6 3 7 1 6 3 8 1 6 3 9 1 6 4 2 1 6 4 3 1 6 4 4 1 6 4 5 1 6 4 6 1 6 4 7 1 6 4 8 1 6 4 9 1 6 5 2 1 6 5 3 1 6 5 4 1 6 5 5 1 6 5 6 1 6 5 7 1 6 5 8 1 6 5 9 1 6 6 2 1 6 6 3 1 6 6 4 1 6 6 5 1 6 6 6 1 6 6 7 1 6 6 8 1 6 6 9 1 6 7 2 1 6 7 3 1 6 7 4 1 6 7 5 1 6 7 6 1 6 7 7 1 6 7 8 1 6 7 9 1 6 8 2 1 6 8 3 1 6 8 4 1 6 8 5 1 6 8 6 1 6 8 7 1 6 8 8 1 6 8 9 1 6 9 2 1 6 9 3 1 6 9 4 1 6 9 5 1 6 9 6 1 6 9 7 1 6 9 8 1 6 9 9 1 7 1 7 1 8 1 7 1 9 1 7 2 2 1 7 2 3 1 7 2 4 1 7 2 5 1 7 2 6 1 7 2 7 1 7 2 8 1 7 2 9 1 7 3 2 1 7 3 3 1 7 3 4 1 7 3 5 1 7 3 6 1 7 3 7 1 7 3 8 1 7 3 9 1 7 4 2 1 7 4 3 1 7 4 4 1 7 4 5 1 7 4 6 1 7 4 7 1 7 4 8 1 7 4 9 1 7 5 2 1 7 5 3 1 7 5 4 1 7 5 5 1 7 5 6 1 7 5 7 1 7 5 8 1 7 5 9 1 7 6 2 1 7 6 3 1 7 6 4 1 7 6 5 1 7 6 6 1 7 6 7 1 7 6 8 1 7 6 9 1 7 7 2 1 7 7 3 1 7 7 4 1 7 7 5 1 7 7 6 1 7 7 7 1 7 7 8 1 7 7 9 1 7 8 2 1 7 8 3 1 7 8 4 1 7 8 5 1 7 8 6 1 7 8 7 1 7 8 8 1 7 8 9 1 7 9 2 1 7 9 3 1 7 9 4 1 7 9 5 1 7 9 6 1 7 9 7 1 7 9 8 1 7 9 9 1 8 1 8 1 9 1 8 2 2 1 8 2 3 1 8 2 4 1 8 2 5 1 8 2 6 1 8 2 7 1 8 2 8 1 8 2 9 1 8 3 2 1 8 3 3 1 8 3 4 1 8 3 5 1 8 3 6 1 8 3 7 1 8 3 8 1 8 3 9 1 8 4 2 1 8 4 3 1 8 4 4 1 8 4 5 1 8 4 6 1 8 4 7 1 8 4 8 1 8 4 9 1 8 5 2 1 8 5 3 1 8 5 4 1 8 5 5 1 8 5 6 1 8 5 7 1 8 5 8 1 8 5 9 1 8 6 2 1 8 6 3 1 8 6 4 1 8 6 5 1 8 6 6 1 8 6 7 1 8 6 8 1 8 6 9 1 8 7 2 1 8 7 3 1 8 7 4 1 8 7 5 1 8 7 6 1 8 7 7 1 8 7 8 1 8 7 9 1 8 8 2 1 8 8 3 1 8 8 4 1 8 8 5 1 8 8 6 1 8 8 7 1 8 8 8 1 8 8 9 1 8 9 2 1 8 9 3 1 8 9 4 1 8 9 5 1 8 9 6 1 8 9 7 1 8 9 8 1 8 9 9 1 9 1 9 2 2 1 9 2 3 1 9 2 4 1 9 2 5 1 9 2 6 1 9 2 7 1 9 2 8 1 9 2 9 1 9 3 2 1 9 3 3 1 9 3 4 1 9 3 5 1 9 3 6 1 9 3 7 1 9 3 8 1 9 3 9 1 9 4 2 1 9 4 3 1 9 4 4 1 9 4 5 1 9 4 6 1 9 4 7 1 9 4 8 1 9 4 9 1 9 5 2 1 9 5 3 1 9 5 4 1 9 5 5 1 9 5 6 1 9 5 7 1 9 5 8 1 9 5 9 1 9 6 2 1 9 6 3 1 9 6 4 1 9 6 5 1 9 6 6 1 9 6 7 1 9 6 8 1 9 6 9 1 9 7 2 1 9 7 3 1 9 7 4 1 9 7 5 1 9 7 6 1 9 7 7 1 9 7 8 1 9 7 9 1 9 8 2 1 9 8 3 1 9 8 4 1 9 8 5 1 9 8 6 1 9 8 7 1 9 8 8 1 9 8 9 1 9 9 2 1 9 9 3 1 9 9 4 1 9 9 5 1 9 9 6 1 9 9 7 1 9 9 8 1 9 9 9 2 2 2 2 3 2 2 2 4 2 2 2 5 2 2 2 6 2 2 2 7 2 2 2 8 2 2 2 9 2 2 3 3 2 2 3 4 2 2 3 5 2 2 3 6 2 2 3 7 2 2 3 8 2 2 3 9 2 2 4 3 2 2 4 4 2 2 4 5 2 2 4 6 2 2 4 7 2 2 4 8 2 2 4 9 2 2 5 3 2 2 5 4 2 2 5 5 2 2 5 6 2 2 5 7 2 2 5 8 2 2 5 9 2 2 6 3 2 2 6 4 2 2 6 5 2 2 6 6 2 2 6 7 2 2 6 8 2 2 6 9 2 2 7 3 2 2 7 4 2 2 7 5 2 2 7 6 2 2 7 7 2 2 7 8 2 2 7 9 2 2 8 3 2 2 8 4 2 2 8 5 2 2 8 6 2 2 8 7 2 2 8 8 2 2 8 9 2 2 9 3 2 2 9 4 2 2 9 5 2 2 9 6 2 2 9 7 2 2 9 8 2 2 9 9 2 3 2 3 2 4 2 3 2 5 2 3 2 6 2 3 2 7 2 3 2 8 2 3 2 9 2 3 3 3 2 3 3 4 2 3 3 5 2 3 3 6 2 3 3 7 2 3 3 8 2 3 3 9 2 3 4 3 2 3 4 4 2 3 4 5 2 3 4 6 2 3 4 7 2 3 4 8 2 3 4 9 2 3 5 3 2 3 5 4 2 3 5 5 2 3 5 6 2 3 5 7 2 3 5 8 2 3 5 9 2 3 6 3 2 3 6 4 2 3 6 5 2 3 6 6 2 3 6 7 2 3 6 8 2 3 6 9 2 3 7 3 2 3 7 4 2 3 7 5 2 3 7 6 2 3 7 7 2 3 7 8 2 3 7 9 2 3 8 3 2 3 8 4 2 3 8 5 2 3 8 6 2 3 8 7 2 3 8 8 2 3 8 9 2 3 9 3 2 3 9 4 2 3 9 5 2 3 9 6 2 3 9 7 2 3 9 8 2 3 9 9 2 4 2 4 2 5 2 4 2 6 2 4 2 7 2 4 2 8 2 4 2 9 2 4 3 3 2 4 3 4 2 4 3 5 2 4 3 6 2 4 3 7 2 4 3 8 2 4 3 9 2 4 4 3 2 4 4 4 2 4 4 5 2 4 4 6 2 4 4 7 2 4 4 8 2 4 4 9 2 4 5 3 2 4 5 4 2 4 5 5 2 4 5 6 2 4 5 7 2 4 5 8 2 4 5 9 2 4 6 3 2 4 6 4 2 4 6 5 2 4 6 6 2 4 6 7 2 4 6 8 2 4 6 9 2 4 7 3 2 4 7 4 2 4 7 5 2 4 7 6 2 4 7 7 2 4 7 8 2 4 7 9 2 4 8 3 2 4 8 4 2 4 8 5 2 4 8 6 2 4 8 7 2 4 8 8 2 4 8 9 2 4 9 3 2 4 9 4 2 4 9 5 2 4 9 6 2 4 9 7 2 4 9 8 2 4 9 9 2 5 2 5 2 6 2 5 2 7 2 5 2 8 2 5 2 9 2 5 3 3 2 5 3 4 2 5 3 5 2 5 3 6 2 5 3 7 2 5 3 8 2 5 3 9 2 5 4 3 2 5 4 4 2 5 4 5 2 5 4 6 2 5 4 7 2 5 4 8 2 5 4 9 2 5 5 3 2 5 5 4 2 5 5 5 2 5 5 6 2 5 5 7 2 5 5 8 2 5 5 9 2 5 6 3 2 5 6 4 2 5 6 5 2 5 6 6 2 5 6 7 2 5 6 8 2 5 6 9 2 5 7 3 2 5 7 4 2 5 7 5 2 5 7 6 2 5 7 7 2 5 7 8 2 5 7 9 2 5 8 3 2 5 8 4 2 5 8 5 2 5 8 6 2 5 8 7 2 5 8 8 2 5 8 9 2 5 9 3 2 5 9 4 2 5 9 5 2 5 9 6 2 5 9 7 2 5 9 8 2 5 9 9 2 6 2 6 2 7 2 6 2 8 2 6 2 9 2 6 3 3 2 6 3 4 2 6 3 5 2 6 3 6 2 6 3 7 2 6 3 8 2 6 3 9 2 6 4 3 2 6 4 4 2 6 4 5 2 6 4 6 2 6 4 7 2 6 4 8 2 6 4 9 2 6 5 3 2 6 5 4 2 6 5 5 2 6 5 6 2 6 5 7 2 6 5 8 2 6 5 9 2 6 6 3 2 6 6 4 2 6 6 5 2 6 6 6 2 6 6 7 2 6 6 8 2 6 6 9 2 6 7 3 2 6 7 4 2 6 7 5 2 6 7 6 2 6 7 7 2 6 7 8 2 6 7 9 2 6 8 3 2 6 8 4 2 6 8 5 2 6 8 6 2 6 8 7 2 6 8 8 2 6 8 9 2 6 9 3 2 6 9 4 2 6 9 5 2 6 9 6 2 6 9 7 2 6 9 8 2 6 9 9 2 7 2 7 2 8 2 7 2 9 2 7 3 3 2 7 3 4 2 7 3 5 2 7 3 6 2 7 3 7 2 7 3 8 2 7 3 9 2 7 4 3 2 7 4 4 2 7 4 5 2 7 4 6 2 7 4 7 2 7 4 8 2 7 4 9 2 7 5 3 2 7 5 4 2 7 5 5 2 7 5 6 2 7 5 7 2 7 5 8 2 7 5 9 2 7 6 3 2 7 6 4 2 7 6 5 2 7 6 6 2 7 6 7 2 7 6 8 2 7 6 9 2 7 7 3 2 7 7 4 2 7 7 5 2 7 7 6 2 7 7 7 2 7 7 8 2 7 7 9 2 7 8 3 2 7 8 4 2 7 8 5 2 7 8 6 2 7 8 7 2 7 8 8 2 7 8 9 2 7 9 3 2 7 9 4 2 7 9 5 2 7 9 6 2 7 9 7 2 7 9 8 2 7 9 9 2 8 2 8 2 9 2 8 3 3 2 8 3 4 2 8 3 5 2 8 3 6 2 8 3 7 2 8 3 8 2 8 3 9 2 8 4 3 2 8 4 4 2 8 4 5 2 8 4 6 2 8 4 7 2 8 4 8 2 8 4 9 2 8 5 3 2 8 5 4 2 8 5 5 2 8 5 6 2 8 5 7 2 8 5 8 2 8 5 9 2 8 6 3 2 8 6 4 2 8 6 5 2 8 6 6 2 8 6 7 2 8 6 8 2 8 6 9 2 8 7 3 2 8 7 4 2 8 7 5 2 8 7 6 2 8 7 7 2 8 7 8 2 8 7 9 2 8 8 3 2 8 8 4 2 8 8 5 2 8 8 6 2 8 8 7 2 8 8 8 2 8 8 9 2 8 9 3 2 8 9 4 2 8 9 5 2 8 9 6 2 8 9 7 2 8 9 8 2 8 9 9 2 9 2 9 3 3 2 9 3 4 2 9 3 5 2 9 3 6 2 9 3 7 2 9 3 8 2 9 3 9 2 9 4 3 2 9 4 4 2 9 4 5 2 9 4 6 2 9 4 7 2 9 4 8 2 9 4 9 2 9 5 3 2 9 5 4 2 9 5 5 2 9 5 6 2 9 5 7 2 9 5 8 2 9 5 9 2 9 6 3 2 9 6 4 2 9 6 5 2 9 6 6 2 9 6 7 2 9 6 8 2 9 6 9 2 9 7 3 2 9 7 4 2 9 7 5 2 9 7 6 2 9 7 7 2 9 7 8 2 9 7 9 2 9 8 3 2 9 8 4 2 9 8 5 2 9 8 6 2 9 8 7 2 9 8 8 2 9 8 9 2 9 9 3 2 9 9 4 2 9 9 5 2 9 9 6 2 9 9 7 2 9 9 8 2 9 9 9 3 3 3 3 4 3 3 3 5 3 3 3 6 3 3 3 7 3 3 3 8 3 3 3 9 3 3 4 4 3 3 4 5 3 3 4 6 3 3 4 7 3 3 4 8 3 3 4 9 3 3 5 4 3 3 5 5 3 3 5 6 3 3 5 7 3 3 5 8 3 3 5 9 3 3 6 4 3 3 6 5 3 3 6 6 3 3 6 7 3 3 6 8 3 3 6 9 3 3 7 4 3 3 7 5 3 3 7 6 3 3 7 7 3 3 7 8 3 3 7 9 3 3 8 4 3 3 8 5 3 3 8 6 3 3 8 7 3 3 8 8 3 3 8 9 3 3 9 4 3 3 9 5 3 3 9 6 3 3 9 7 3 3 9 8 3 3 9 9 3 4 3 4 3 5 3 4 3 6 3 4 3 7 3 4 3 8 3 4 3 9 3 4 4 4 3 4 4 5 3 4 4 6 3 4 4 7 3 4 4 8 3 4 4 9 3 4 5 4 3 4 5 5 3 4 5 6 3 4 5 7 3 4 5 8 3 4 5 9 3 4 6 4 3 4 6 5 3 4 6 6 3 4 6 7 3 4 6 8 3 4 6 9 3 4 7 4 3 4 7 5 3 4 7 6 3 4 7 7 3 4 7 8 3 4 7 9 3 4 8 4 3 4 8 5 3 4 8 6 3 4 8 7 3 4 8 8 3 4 8 9 3 4 9 4 3 4 9 5 3 4 9 6 3 4 9 7 3 4 9 8 3 4 9 9 3 5 3 5 3 6 3 5 3 7 3 5 3 8 3 5 3 9 3 5 4 4 3 5 4 5 3 5 4 6 3 5 4 7 3 5 4 8 3 5 4 9 3 5 5 4 3 5 5 5 3 5 5 6 3 5 5 7 3 5 5 8 3 5 5 9 3 5 6 4 3 5 6 5 3 5 6 6 3 5 6 7 3 5 6 8 3 5 6 9 3 5 7 4 3 5 7 5 3 5 7 6 3 5 7 7 3 5 7 8 3 5 7 9 3 5 8 4 3 5 8 5 3 5 8 6 3 5 8 7 3 5 8 8 3 5 8 9 3 5 9 4 3 5 9 5 3 5 9 6 3 5 9 7 3 5 9 8 3 5 9 9 3 6 3 6 3 7 3 6 3 8 3 6 3 9 3 6 4 4 3 6 4 5 3 6 4 6 3 6 4 7 3 6 4 8 3 6 4 9 3 6 5 4 3 6 5 5 3 6 5 6 3 6 5 7 3 6 5 8 3 6 5 9 3 6 6 4 3 6 6 5 3 6 6 6 3 6 6 7 3 6 6 8 3 6 6 9 3 6 7 4 3 6 7 5 3 6 7 6 3 6 7 7 3 6 7 8 3 6 7 9 3 6 8 4 3 6 8 5 3 6 8 6 3 6 8 7 3 6 8 8 3 6 8 9 3 6 9 4 3 6 9 5 3 6 9 6 3 6 9 7 3 6 9 8 3 6 9 9 3 7 3 7 3 8 3 7 3 9 3 7 4 4 3 7 4 5 3 7 4 6 3 7 4 7 3 7 4 8 3 7 4 9 3 7 5 4 3 7 5 5 3 7 5 6 3 7 5 7 3 7 5 8 3 7 5 9 3 7 6 4 3 7 6 5 3 7 6 6 3 7 6 7 3 7 6 8 3 7 6 9 3 7 7 4 3 7 7 5 3 7 7 6 3 7 7 7 3 7 7 8 3 7 7 9 3 7 8 4 3 7 8 5 3 7 8 6 3 7 8 7 3 7 8 8 3 7 8 9 3 7 9 4 3 7 9 5 3 7 9 6 3 7 9 7 3 7 9 8 3 7 9 9 3 8 3 8 3 9 3 8 4 4 3 8 4 5 3 8 4 6 3 8 4 7 3 8 4 8 3 8 4 9 3 8 5 4 3 8 5 5 3 8 5 6 3 8 5 7 3 8 5 8 3 8 5 9 3 8 6 4 3 8 6 5 3 8 6 6 3 8 6 7 3 8 6 8 3 8 6 9 3 8 7 4 3 8 7 5 3 8 7 6 3 8 7 7 3 8 7 8 3 8 7 9 3 8 8 4 3 8 8 5 3 8 8 6 3 8 8 7 3 8 8 8 3 8 8 9 3 8 9 4 3 8 9 5 3 8 9 6 3 8 9 7 3 8 9 8 3 8 9 9 3 9 3 9 4 4 3 9 4 5 3 9 4 6 3 9 4 7 3 9 4 8 3 9 4 9 3 9 5 4 3 9 5 5 3 9 5 6 3 9 5 7 3 9 5 8 3 9 5 9 3 9 6 4 3 9 6 5 3 9 6 6 3 9 6 7 3 9 6 8 3 9 6 9 3 9 7 4 3 9 7 5 3 9 7 6 3 9 7 7 3 9 7 8 3 9 7 9 3 9 8 4 3 9 8 5 3 9 8 6 3 9 8 7 3 9 8 8 3 9 8 9 3 9 9 4 3 9 9 5 3 9 9 6 3 9 9 7 3 9 9 8 3 9 9 9 4 4 4 4 5 4 4 4 6 4 4 4 7 4 4 4 8 4 4 4 9 4 4 5 5 4 4 5 6 4 4 5 7 4 4 5 8 4 4 5 9 4 4 6 5 4 4 6 6 4 4 6 7 4 4 6 8 4 4 6 9 4 4 7 5 4 4 7 6 4 4 7 7 4 4 7 8 4 4 7 9 4 4 8 5 4 4 8 6 4 4 8 7 4 4 8 8 4 4 8 9 4 4 9 5 4 4 9 6 4 4 9 7 4 4 9 8 4 4 9 9 4 5 4 5 4 6 4 5 4 7 4 5 4 8 4 5 4 9 4 5 5 5 4 5 5 6 4 5 5 7 4 5 5 8 4 5 5 9 4 5 6 5 4 5 6 6 4 5 6 7 4 5 6 8 4 5 6 9 4 5 7 5 4 5 7 6 4 5 7 7 4 5 7 8 4 5 7 9 4 5 8 5 4 5 8 6 4 5 8 7 4 5 8 8 4 5 8 9 4 5 9 5 4 5 9 6 4 5 9 7 4 5 9 8 4 5 9 9 4 6 4 6 4 7 4 6 4 8 4 6 4 9 4 6 5 5 4 6 5 6 4 6 5 7 4 6 5 8 4 6 5 9 4 6 6 5 4 6 6 6 4 6 6 7 4 6 6 8 4 6 6 9 4 6 7 5 4 6 7 6 4 6 7 7 4 6 7 8 4 6 7 9 4 6 8 5 4 6 8 6 4 6 8 7 4 6 8 8 4 6 8 9 4 6 9 5 4 6 9 6 4 6 9 7 4 6 9 8 4 6 9 9 4 7 4 7 4 8 4 7 4 9 4 7 5 5 4 7 5 6 4 7 5 7 4 7 5 8 4 7 5 9 4 7 6 5 4 7 6 6 4 7 6 7 4 7 6 8 4 7 6 9 4 7 7 5 4 7 7 6 4 7 7 7 4 7 7 8 4 7 7 9 4 7 8 5 4 7 8 6 4 7 8 7 4 7 8 8 4 7 8 9 4 7 9 5 4 7 9 6 4 7 9 7 4 7 9 8 4 7 9 9 4 8 4 8 4 9 4 8 5 5 4 8 5 6 4 8 5 7 4 8 5 8 4 8 5 9 4 8 6 5 4 8 6 6 4 8 6 7 4 8 6 8 4 8 6 9 4 8 7 5 4 8 7 6 4 8 7 7 4 8 7 8 4 8 7 9 4 8 8 5 4 8 8 6 4 8 8 7 4 8 8 8 4 8 8 9 4 8 9 5 4 8 9 6 4 8 9 7 4 8 9 8 4 8 9 9 4 9 4 9 5 5 4 9 5 6 4 9 5 7 4 9 5 8 4 9 5 9 4 9 6 5 4 9 6 6 4 9 6 7 4 9 6 8 4 9 6 9 4 9 7 5 4 9 7 6 4 9 7 7 4 9 7 8 4 9 7 9 4 9 8 5 4 9 8 6 4 9 8 7 4 9 8 8 4 9 8 9 4 9 9 5 4 9 9 6 4 9 9 7 4 9 9 8 4 9 9 9 5 5 5 5 6 5 5 5 7 5 5 5 8 5 5 5 9 5 5 6 6 5 5 6 7 5 5 6 8 5 5 6 9 5 5 7 6 5 5 7 7 5 5 7 8 5 5 7 9 5 5 8 6 5 5 8 7 5 5 8 8 5 5 8 9 5 5 9 6 5 5 9 7 5 5 9 8 5 5 9 9 5 6 5 6 5 7 5 6 5 8 5 6 5 9 5 6 6 6 5 6 6 7 5 6 6 8 5 6 6 9 5 6 7 6 5 6 7 7 5 6 7 8 5 6 7 9 5 6 8 6 5 6 8 7 5 6 8 8 5 6 8 9 5 6 9 6 5 6 9 7 5 6 9 8 5 6 9 9 5 7 5 7 5 8 5 7 5 9 5 7 6 6 5 7 6 7 5 7 6 8 5 7 6 9 5 7 7 6 5 7 7 7 5 7 7 8 5 7 7 9 5 7 8 6 5 7 8 7 5 7 8 8 5 7 8 9 5 7 9 6 5 7 9 7 5 7 9 8 5 7 9 9 5 8 5 8 5 9 5 8 6 6 5 8 6 7 5 8 6 8 5 8 6 9 5 8 7 6 5 8 7 7 5 8 7 8 5 8 7 9 5 8 8 6 5 8 8 7 5 8 8 8 5 8 8 9 5 8 9 6 5 8 9 7 5 8 9 8 5 8 9 9 5 9 5 9 6 6 5 9 6 7 5 9 6 8 5 9 6 9 5 9 7 6 5 9 7 7 5 9 7 8 5 9 7 9 5 9 8 6 5 9 8 7 5 9 8 8 5 9 8 9 5 9 9 6 5 9 9 7 5 9 9 8 5 9 9 9 6 6 6 6 7 6 6 6 8 6 6 6 9 6 6 7 7 6 6 7 8 6 6 7 9 6 6 8 7 6 6 8 8 6 6 8 9 6 6 9 7 6 6 9 8 6 6 9 9 6 7 6 7 6 8 6 7 6 9 6 7 7 7 6 7 7 8 6 7 7 9 6 7 8 7 6 7 8 8 6 7 8 9 6 7 9 7 6 7 9 8 6 7 9 9 6 8 6 8 6 9 6 8 7 7 6 8 7 8 6 8 7 9 6 8 8 7 6 8 8 8 6 8 8 9 6 8 9 7 6 8 9 8 6 8 9 9 6 9 6 9 7 7 6 9 7 8 6 9 7 9 6 9 8 7 6 9 8 8 6 9 8 9 6 9 9 7 6 9 9 8 6 9 9 9 7 7 7 7 8 7 7 7 9 7 7 8 8 7 7 8 9 7 7 9 8 7 7 9 9 7 8 7 8 7 9 7 8 8 8 7 8 8 9 7 8 9 8 7 8 9 9 7 9 7 9 8 8 7 9 8 9 7 9 9 8 7 9 9 9 8 8 8 8 9 8 8 9 9 8 9 8 9 9 9 9 0 0 0

Partons toujours du principe que vous mettez environ 2 secondes à taper 4 chiffres, vous mettrez seulement 3h30 à ouvrir votre porte si le code est le « pire code possible », c’est à dire 9999 (le dernier code essayé). Contre 13 heures toute à l’heure, presque 4 fois plus long.

La probabilité d’aller beaucoup plus vite ?

Dans les différents logements que j’ai habités, les codes ont toujours été inférieurs au nombre 3000. Si j’avais utilisé cette suite sur mes digicodes, j’aurais pu mettre entre 10 et 30 minutes pour ouvrir la porte. C’est long, mais pourquoi pas ?

Automatiser les tentatives ?

Ça pourrait être un projet passionnant : créer un petit boitier, à base d’Arduino et équipé de quelques servomoteurs, permettant de taper à notre place sur un digicode. Pas mal de difficultés à prendre en compte (adaptation universelle aux digicodes, précision, puissance de frappe). Mais pourquoi pas 😀

Pour en savoir plus sur les suites de de Bruijn

Un générateur de suites, très bien fait.
La page Wikipédia sur le sujet.
La page Wikipédia sur Nicolaas Govert de Bruijn.

24 Commentaires

  • Fred
    31 mai 2017 à 13 h 43 min

    Il serait utile de préciser que cela marche uniquement pour les systèmes ne nécessitant pas de valider le code à chaque fois.

    • Stéphane Paton
      1 juin 2017 à 14 h 17 min

      On en discutait sur Slack, et ça dépend beaucoup des villes et probablement de l’année de construction des logements. Dans mon cas, je n’ai jamais rencontré ce type de digicode.

  • Bryk
    31 mai 2017 à 14 h 03 min

    Ah! J’attendais ton article avec impatience, tu avais fait un bon teaser 🙂 , et j’ai adoré.
    Quel plaisir de trouver des codes, souvent on peut essayer le numéro du bâtiment avec le numéro de département. Je l’ai déjà vu plusieurs fois dans différents immeubles.
    Le système Vigik est cassable, mais demande pas mal d’effort.

    Alors, il reste ton idée d’Arduino, j’en ai un dans un tiroir qui ne sert pas! Je vais le dépoussiérer!

    Have Fun

    • Stéphane Paton
      1 juin 2017 à 14 h 18 min

      Hey Bryk,

      Tu me diras si tu arrives à quelque chose ! Merci pour ton commentaire en tous cas.

  • Yolo A
    31 mai 2017 à 14 h 43 min

    Super article ! Très bien vulgarisé comme d’habitude avec une touche d’humour très appréciable.
    Si j’avais su, j’aurais pu éviter de réveiller ma grand-mère à 3h du matin parce que je me trompais de « sens » dans le code (2556 au lieu de 6552…)

  • Mathieu GUINET
    31 mai 2017 à 14 h 48 min

    Mathématiquement très intéressant mais malheureusement inapplicable dans la réalité car les Digicode possède très souvent un code à 4 chiffres suivi d’un A / B.
    Dans ce cas, la suite de Bruijn ne marche pas ! Par contre j’ai déjà réussi à plusieurs reprises l’ouverture d’une porte grâce au touche usé ou salle !

    • Stéphane Paton
      1 juin 2017 à 14 h 22 min

      Les suites de De Bruijn fonctionnent avec n’importe quel alphabet. Si tu veux appliquer l’algo sur A = { 0,1,2,3,4,5,6,7,8,9,A,B }, tu peux. Voila d’ailleurs le résultat : https://pastebin.com/Ryp7UTmy

      • Renart sacripant
        1 octobre 2017 à 17 h 55 min

        Pour un code à 4 chiffres suivi d’un A / B les résultats de ce lien https://pastebin.com/Ryp7UTmy sont mauvais exemple 5827A n’y est pas

        merci pour votre article

        • Stéphane Paton
          3 octobre 2017 à 11 h 02 min

          Mince bien vu :-/ Le générateur que j’ai utilisé n’était sûrement pas terrible. Il faut que j’en trouve un mieux ! Merci pour la remarque !

          • Walegen
            16 février 2018 à 17 h 57 min

            Il manque 9000, 9900 et 9990 dans la série pour les codes de 4 chiffres. Il faut ajouter trois 0 à la fin de la liste pour qu’elle soit bonne.
            Il faut donc en moyenne 1h23min27,5s pour ouvrir une porte avec ce type de digicode.
            Sauf s’il y a un médecin ou tout autre personne recevant du public dans l’immeuble, à ce moment, c’est 2s le temps d’appuyer sur la sonnette. 😉

          • Stéphane Paton
            23 février 2018 à 14 h 16 min

            Merci beaucoup pour la correction ! 🙂

  • antonio de la vega
    31 mai 2017 à 15 h 07 min

    Génial et passionnant ! Si on voit quelqu’un taper frénétiquement sur un digicode pendant 30 minutes, on pourra dire : « salut Stephane »

    • Stéphane Paton
      1 juin 2017 à 14 h 22 min

      Merci Antonio ! 😀

    • Fayçal
      24 janvier 2018 à 16 h 29 min

      Si on voit quelqu’un entrain de surveiller pendant 30 min quelqu’un qui tape frénétiquement sur un digicode pendant 30 minutes, on pourra dire : “salut Antonio” , puis on profite de cette occasion pour saluer Stéphane .

  • Jacks
    31 mai 2017 à 15 h 24 min

    Ahahaha Je me demande si ce n’est pas cet algorithme qu’utilise les hackeurs lorsqu’ils connectent un petit machin dans les systèmes à code et après analyse ils retrouvent le code exacte…

    En tout cas, merçi parfait sujet.

    • Stéphane Paton
      1 juin 2017 à 14 h 23 min

      Jacks,

      Pourquoi pas ! Mais il existe des manières plus sophistiquées d’attaquer un système. L’idée derrière de Bruijn, c’est ce qu’on appelle de la brute-force : on n’a pas beaucoup d’ingéniosité, donc on essaie toutes les solutions jusqu’à trouver la bonne. 🙂

      Merci beaucoup pour ton commentaire.

  • Bastien O
    31 mai 2017 à 20 h 39 min

    Super intéressant, merci pour cet article !

  • Quentin Gcn
    31 mai 2017 à 23 h 41 min

    Oh un article sur un sujet mathématique ! Très bonne idée !!
    Je pense que je vais t’envoyer un petit truc qui va te plaire dans la semaine !

  • Philippe Peytroux
    1 juin 2017 à 11 h 17 min

    Je vois Monsieur Paton… vous passez votre temps à faire des recherches pour contrôler le monde, c’est ça ?
    On commence par le cerveau humain (manipulation) et on finit par les digicodes ?
    Haha, sincèrement, c’est super intéressant ! Et je ne savais pas quoi faire cette aprèm, donc…..

  • lara
    3 juin 2017 à 8 h 36 min

    Partisane du moindre effort… Personnellement, j’attends. De façon générale, si vous traînez dans le champ de vision d’un habitant dont l’immeuble requiert un code, il va le composer en cachant ce qu’il tape comme s’il était en caisse de supermarché avec une carte bleue. Le mieux est de ne pas être dans son champ direct, et si possible dans sa diagonale. De cette manière, vous allez le voir taper mais vous serez loin pour voir. Alors, j’enregistre le mouvement de son doigt, et à l’aide de la crasse, je reconstitue le tout (le mouvement ressemble un peu aux pass des téléphones modernes). Ca me prend disons 15 minutes au max (jusqu’à ce qu’une personne entre et se place à peu près comme je l’avais envisagé). Quand j’ai besoin d’entrer la nuit, l’attente est plus longue mais dans une grande ville, pas de problème, ça rentre et ça sort à toute heure.
    Puis, d’autres techniques encore, légales et rusées^^ quoi d’en pense Vigik, quand on veut entrer quelque part, on entre. Cordialement,

Laisser un commentaire