Algorithme de plus court chemin, algèbre min-plus et matrices d'adjacence

Je poste ici où j'en suis.

Trouver les décomposants de Goldbach, c'est équivalent à trouver les centres d'un graphe d'une forme particulière (triangulaire épointée), ce graphe a ses arêtes orientées, il est sans cycle, ses arêtes sont étiquetées par des valeurs positives. Ici, je colle la note explicative : lien (en) lien.

Au début, j'avais écrit une note en prose, là lien, pour montrer comment s'étaient agencées les idées, mais ça n'était pas assez désossé. C'est vrai qu'écrire dans la version désossée "découle des définitions", c'était culotté (Jean-Pierre Serre donne l'exemple dans sa conférence "How to write mathematics badly", le titre dit bien ce qu'il en est, c'est marrant quand il le raconte alors pourquoi pas) mais malvenu : il faut du culot pour penser qu'on pourrait..., et il faut être capable de se faire comprendre, c'est bien le moins ; si on n'est pas comprise, c'est qu'on a mal expliqué, peut-être, ou qu'on n'a pas encore suffisamment compris, pour bien expliquer. Pour tenter de mieux expliquer le "découle des définitions", j'ai écrit ça lien. Alors, le programme, à la fin, peut sembler complètement idiot : on prend deux nombres premiers, et au lieu de tester directement que leur somme vaut n, on teste que le max(2n-p-q,p+q) vaut n : si max(2n-p-q,p+q), c'est 2n-p-q et que 2n-p-q=n alors on a n=p+q, et si max(2n-p-q,p+q), c'est p+q alors on a aussi n=p+q, mais ce qui importe, c'est que le max en question correspond justement à l'excentricité du sommet dans le graphe triangulaire épointé. Je colle les petits graphes, jusqu'à 60 (ça tombe bien), lien ; après, on ne voit plus rien, les étiquettes des arêtes disparaissent, mais on a confiance en l'algorithme !

Enfin, cet après-midi, j'ai utilisé des matrices d'adjacence dans l'algèbre min-plus, parce qu'un calcul avec ces matrices permet aussi de trouver les excentricités, par un calcul de pivot (là, il faut que j'approfondisse, je ne sais pas encore tout à fait pourquoi ça marche ). Les premières matrices sont ici, et ce n'est pas trivial, le passage graphe-matrice d'adjacence, sauf si on utilise la numérotation des éléments des matrices par ligne et colonne car alors tout se simplifie : (i,j) est bêtement relié à (i,j+1) et (i+1,j).

Dernier truc franchement audacieux (pour ne pas dire gonflé) : si on "scale" les carrés géométriques, en se disant que le côté n'est pas de longueur n mais qu'il est de longueur 1, alors les chemins vers les nombres premiers décomposants sont toujours à distance 1/2 de la source, et on n'a qu'à se dire que le 1/2 en question, c'est celui de l'hypothèse de Riemann, et alors, ce serait fou, émouvant de simplicité, et fou...!