Rosales-Garcia
dans Arithmétique
Bonjour,
Sauf erreur,
1) $93930$ ($62\times1515$) est le plus petit multiple strictement positif de $1515$ qui soit une combinaison linéaire à coefficients entiers et positifs de $1789$ et $2018$.
2) $104535$ ($69\times1515$) est le "deuxième" plus petit multiple strictement positif de $1515$ qui soit une combinaison linéaire à coefficients entiers et positifs de $1789$ et $2018$. Par "deuxième", j'entends qu'il en existe un et un seul autre qui soit plus petit que lui.
3) $187860$ ($124\times1515$) est le "troisième" plus petit multiple strictement positif de $1515$ qui soit une combinaison linéaire à coefficients entiers et positifs de $1789$ et $2018$. Par "troisième", j'entends qu'il en existe deux et deux autres seulement qui soient plus petit que lui.
Etc.
J'aimerais juste savoir si la formule de Rosales-Garcia évoquée dans un autre fil permet ce genre de calculs.
Merci d'avance.
Sauf erreur,
1) $93930$ ($62\times1515$) est le plus petit multiple strictement positif de $1515$ qui soit une combinaison linéaire à coefficients entiers et positifs de $1789$ et $2018$.
2) $104535$ ($69\times1515$) est le "deuxième" plus petit multiple strictement positif de $1515$ qui soit une combinaison linéaire à coefficients entiers et positifs de $1789$ et $2018$. Par "deuxième", j'entends qu'il en existe un et un seul autre qui soit plus petit que lui.
3) $187860$ ($124\times1515$) est le "troisième" plus petit multiple strictement positif de $1515$ qui soit une combinaison linéaire à coefficients entiers et positifs de $1789$ et $2018$. Par "troisième", j'entends qu'il en existe deux et deux autres seulement qui soient plus petit que lui.
Etc.
J'aimerais juste savoir si la formule de Rosales-Garcia évoquée dans un autre fil permet ce genre de calculs.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Claude Quitté, auquel je renouvelle mes remerciements, m'a transmis le livre en pdf, mais en Anglais, j'ai assez vite renoncé à vouloir décortiquer à la fois la démarche mathématique et la traduction, 2 exercices qui ne me sont familiers ni l'un ni l'autre. Lui devrait pouvoir te dire si ce point a été abordé, il a l'air d'avoir beaucoup travaillé sur les semis groupes.
Je vais essayer de voir de mon coté s'il n'y pas déjà plus ou moins une réponse dans tout ce qui a été écrit sur les 2 fils précédents.
Dois-je comprendre que tu as encore un truc pour en plus déterminer la suite des multiples qui sont combinaisons linéaires à coefficients positifs?
Si oui, tu vas nous donner du sacré boulot, déjà que je ne n'ai toujours pas compris ta méthode dans le fil précédent !
Al-Kashi
Al-Kashi
Pas beaucoup de temps. Je confirme juste ton 1. (et donc, je ne réponds pas ni à ton 2. ni à ton 3.). Un AUTRE algorithme (je profite du fait que $a \wedge b = 1$), qui donne le même résultat. Remarque : je n'ai pas vu chez Rosales-Garcia, de méthode (algorithme) de détermination du multiplicateur minimal. Ce n'est pas l'objet de leur ouvrage.
Ah bon ?!? (A propos de Rosales-Garcia.)
J'avais lu dans un de tes messages : "Il a fallu attendre 2004 pour que Rosales et Garcia obtiennent une formule algébrique (symétrique), en fonction de $n_{1}$, $n_{2}$, $n_{3}$, $c_{1}$, $c_{2}$, $c_{3}$ (les $c_{i}$ sont les multiplicateurs minimaux)".
J'ai dû à ce moment-là faire un lien inapproprié entre Rosales-Garcia et multiplicateurs minimaux.
@ Al-Kashi :
C'est ça, un "truc"...
Des petits conflits entre passionnés, c'est fréquent. Bon, j'arrête mon char psy, voire curé!
Je planche sur le même problème que Gil, problème d'ailleurs suggéré par Claude (si j'ai bien lu) à savoir:
$p, q, r$ naturels étant donnés, tout de même supposés étrangers dans leur ensemble et $p\notin <q,r>$,
donner un algorithme qui fournit la liste croissante des naturels $k$ tels que $kp$ n'appartient pas à $<q,r> $.
Par complémentaire, on trouvera la liste de Gil.
J'ai donné un algorithme qui, je croyais, résolvait la question et je me suis planté, bien que me restreignant au cas $q\wedge r=1$.
Dans l'exemple proposé par Gil, je pense qu'il fonctionne vu que $1515, 1789, 2018 $ sont deux à deux étrangers:
(l'absence d'os, enfin j'espère, provient de ce que, pour tout $0<k<1789$, $1515\times k \neq 0$ mod $1789$ et mod $2018$).
Soient
$A^+$ la liste croissante des naturels $k<1789$ tels que $1515\times k \in <1789,2018>$,
$A^-$ la liste croissante des naturels $k<1789$ tels que $1515\times k \in <1789,2018>^c$ et
$1515:=2018j-1789i$ où $0<j<1789$.
Alors
$0\in A^+$,
$1515\in A^-$, et
pour tout $0<k<1788$,
$k$ et $k+1$ sont dans la même liste SSI $( (k+1)i)_r- (ki)_r$ et $( (k+1)j)_q- (kj)_q$ ont le même signe.
A suivre
Amicalement
Paul
Si on veut se donner une idée précise des 0 modulo c positifs, c'est à dire ax+by = kc, avec x et y > 0, on peut se ramener à un tableau d'additions modulo c, ce que j'ai expliqué dans ma méthode " Frobénius 3 " .
Dans le repère orthonormé, sur l'axe Ox, on place les multiples croissants de " a " et sur l'axe 0y ceux de " b ". Tout point à coordonnées entières (x,y) a pour valeur ax + by, auquel on peut donner la valeur [c].
J'ai expliqué pourquoi les " c" plus petites valeurs modulo " c" étaient groupées près de (00) dans un rectangle tronqué par un autre rectangle. Cette figure est un motif de tapisserie qui se répète infiniment dans le plan, et quand on a affaire à cette situation, il existe un couple de vecteurs non colinéaires qui dessinent les limites de ce motif (leur produit vectoriel vaut "c" dans notre problème). Les 2 vecteurs en question sont précisément celui qui donne le plus petit multiple de c: V0 et l'un des 2 vecteurs qui découpent le rectangle V1 = Vymin ou Vxmin. Or ce sont des vecteurs de recopie, c'est à dire que toute valeur valeur modulo c est déduite d'une seule (x,y) au départ par l'opération :
(x,y) + k V0 + j V1, k et j entiers relatifs.
Il en est de même des "c" zéros [c], dont le plus petit est en (0,0), ils se trouvent dans le carré qui s'étend de (0;0) à (c-1, c-1). ils sont distribués régulièrement dans une trame au pas des vecteurs V0 et V1.
Al-Kashi
La formule de Rosales-Garcia qui donne le nombre de Frobenius du semi-groupe $n_1\N + n_2\N + n_3\N$ (dans le contexte fourni par ces auteurs) utilise les multiplicateurs minimaux $c_1, c_2, c_3$ de ...etc... Ceci ne signifie pas qu'ils étudient le problème de la détermination des $c_i$. Ce n'est pas leur affaire, du moins dans le papier que j'ai pointé. Et je n'ai rien vu dans leur ouvrage qui concerne la détermination de ce multiplicateur minimal (quand je dis que je n'ai rien vu, c'est que je n'ai rien vu, j'ai pu louper quelque chose dans les 190 pages).
Quand je t'ai dit hier que je ne répondais pas à tes deux questions 2. et 3. c'est tout simplement que je n'avais pas les moyens d'y répondre. Et pas trop de temps. Il se trouve que j'ai eu un peu de temps ce jour. J'ai fait quoi ? J'ai pris mon algorithme certifié dont j'ai parlé dans l'autre fil et j'ai apporté une mise à jour infime de manière à ce qu'il puisse calculer le deuxième, le troisième ...etc.. selon les termes de ton premier post.
Cela a été très vite, je t'assure. Le seul problème a été l'organisation : ne pas se mélanger les pinceaux dans les divers programmes, trouver un nom à la nouvelle fonction. J'ai beaucoup hésité sur le fait de mettre un s ou pas à Multiplier et finalement, je n'en ai pas mis. Note : donner des noms (les plus pertinents possibles) aux fonctions, aux variables ..etc.. est une activité compliquée en programmation (cf Programming Proverbs de Henry Ledgard).
Voilà en ce qui concerne les 3 premiers : je trouve comme toi 62, 69 et 124. Ils sont accompagnés d'un certificat $(u,v)$. Note que ce que tu vises, en un certain sens c'est le semi-groupe $c\N \cap (a\N + b\N)$ avec ici $a \wedge b = 1$ J'espère que tu comprends un peu près les résultats d'exécution ci-dessus.
En obtenir $10^3 = 1000$ au lieu de 3 n'est qu'une question de temps Ma foi, vouloir déterminer le semi-groupe $c\N \cap (a\N + b\N)$ (avec $a \wedge b = 1$) est un joli problème. C'est un semi-groupe de type fini (engendré par un nombre fini de générateurs). Joli problème mais je n'ai pas le temps.
Bon courage à toi.
V0 = 43x+4y.........V1 = -24x+33y......avec x = 2018 et y = 1789.
V0 = 62 ( * 1515) le plus petit.
V1 = 7 (mais avec un x négatif, donc ne convient pas)
V0+V1 = 19x+37y = 69 convient
2V0 = 124 convient (puisque V0 convient)
2V0 + V1 = 62x+41y = 131
3V1+2V0 = 14x+103y = 145.
etc......
Un grand merci d'avoir encore une fois consacré de ton temps à une de mes questions.
@ nodgim :
OK, je vois que ta méthode fonctionne aussi.
Al-Kashi