Hocus Pocus

Bonjour à toutes et à tous,
Aujourd'hui, j'ai le plaisir de vous proposer ci-dessous un amusant petit tour de magie. Seulement, pour cela, j'aurai besoin de votre contribution. Soyez rassuré$\cdot$e$\cdot$s, c'est à la portée de tout$\cdot$e arithméticien$\cdot$ne.
Alors, si cela vous intéresse...commençons sans plus tarder ! (en laissant tomber l'écriture inclusive qui me dérange moi-même.)

$\fbox{I}$ : [size=medium] Choix de a,b,c. [/size]
Pour commencer, je vais vous demander de choisir trois entiers premiers entre eux deux à deux, dont l'un sera compris entre $70$ et $79$, un autre entre $80$ et $89$ et le troisième entre $90$ et $99$. Nous les appellerons $a$, $b$ et $c$, mais libre à vous de choisir lequel vous appellerez $a$, lequel vous appellerez $b$ et lequel vous appellerez $c$.
(Prenez note quelque part de ces trois valeurs, à moins que vous n'ayez une bonne mémoire !)

$\fbox{II}$ : [size=medium] Détermination de p,q. [/size]
Maintenant que $a,b,c$ sont déterminés, je vais vous demander de résoudre l'équation diophantienne $ax+by=c$ comme vous le voulez, mais de façon à ce que le résultat obtenu soit de la forme suivante :
Pour un certain entier $p$ tel que $0<p<b$, un certain entier $q$ tel que $0<q<a$, et $n\in \mathbb{Z}$,
$$x=-bn-p \qquad \text{et} \qquad y=an+q$$
Une fois que cela sera fait, prenez tout simplement note de la valeur trouvée pour $p$ et pour $q$.

$\fbox{III}$ :[size=medium] Détermination de X,Y et apparition soudaine de k. [/size]
Ici, deux options conduisant au même résultat se présentent à vous :

Option 1 : Vous êtes en mesure d'utiliser un tableur.
Dans ce cas, posez (en remplaçant évidemment $a,b,p,q$ par leur valeur numérique) :
$y_1=\dfrac{(a-q)x-q}{a}$

$y_2=\dfrac{(b-p)x-p}{b}$
puis demandez à votre tableur d'afficher simultanément les valeurs en écriture décimale de $y_1$ et $y_2$, pour $x\in \mathbb{N^*}$.

Option 2 : Vous n'êtes pas en mesure d'utiliser un tableur.
Dans ce cas, saisissez à cette adresse {https://wolframalpha.com} la commande suivante (merci le copier/coller) :
Table{x, N[((a-q)*x-q)/a], N[((b-p)*x-p)/b]} for x from 1 to 50
(en remplaçant évidemment $a,b,p,q$ par leur valeur numérique).

Dans les deux cas, vous devriez vous retrouver devant un tableau qui ressemble à ceci (dans cet exemple, $a=71$, $b=96$, $c=83$) :

$$\begin{array}{|c|c|c|}
\hline
x & y_1 & y_2 \\
\hline
1 & 0.746479 & 0.770833 \\
\hline
2 & 1.61972 & 1.65625 \\
\hline
3 & 2.49296 & 2.54167 \\
\hline
4 & 3.3662 & 3.42708 \\
\hline
5 & 4.23944 & 4.3125 \\
\hline
6 & 5.11268 & 5.19792 \\
\hline
7 & 5.98592 & 6.08333 \\
\hline
\end{array}$$
Vous y voyez que, pour $1 \leq x \leq 6$, aucun intervalle des réels $[y_1, y_2]$ ne comporte d'entier positif.
En revanche, pour $x=7$, l'intervalle des réels $[5.98592; 6.08333]$ comporte un (plus petit) entier positif, à savoir l'entier positif $6$.
Dans cet exemple, posons alors $X=7$ et $Y=6$.

Dans votre propre tableau, je vous invite à chercher pareillement votre $X$ et votre $Y$. (Je rappelle si nécessaire que $0$ est un entier positif.)
Remarque importante : Si jamais votre tableur, dont je ne connais pas les performances, vient à afficher une valeur entière, je ne peux que vous conseiller de procéder à une vérification afin de vous assurer que cette valeur entière n'est pas le résultat d'un arrondi vers le haut ou vers le bas effectué par la machine, car cela fausserait les résultats.

Vous avez trouvé vos $X$ et $Y$ ?
Bien !
Alors, posez enfin : $X+1=k$.

Et voilà !!!

$\fbox{IV}$ : [size=medium] Et voilà, quoi ? [/size]
Et voilà ! :
Quels que soient les entiers $a,b,c$ initialement choisis par vous, il se fait que votre entier
$$
\begin{array}{|c|}
\hline
k \\
\hline
\end{array}$$
est tel que $kc$ (tiens, revoilà $c$ !) est le plus petit multiple strictement positif de $c$ exprimable sous la forme d'une combinaison linéaire, à coefficients entiers strictement positifs, de $a$ et $b$. Dit autrement, il vous sera impossible d'exprimer un multiple strictement positif de $c$ strictement inférieur à $kc$ comme la somme d'un multiple strictement positif de $a$ et d'un multiple strictement positif de $b$.

C'est magique, comme moyen de déterminer $k$ ! non ?


$\fbox{V}$ : [size=medium] Remarques. [/size]
Remarque 1 :
Plus précisément, vous avez :
$$ \fbox{kc=ma+nb},
$$ où :
$m$ $(\in \mathbb{N^*})$ $=-p+(b-p)X-(b)Y$.
$n$ $(\in \mathbb{N^*})$ $=+q-(a-q)X+(a)Y$.

Remarque 2 :
Au moment de choisir $a,b,c$, j'aurais pu vous donner beaucoup plus de liberté en vous proposant de choisir trois entiers naturels premiers entre eux deux à deux tels que l'on n'ait pas l'égalité :
(le plus grand des trois) = (un multiple strictement positif du plus petit) + (un multiple strictement positif de celui qui n'est ni le plus grand ni le plus petit).
Si je ne l'ai pas fait, c'est afin que ce tour conserve son caractère ludique, en rendant faciles tant le choix des nombres que la détermination de $k$ ainsi que la preuve que le résultat est bien le bon.
[Ajout du 20/01/2021 : On trouvera ici http://www.les-mathematiques.net/phorum/read.php?5,2128624,2167980#msg-2167980 trois méthodes faciles pour s'aider dans le choix de $a,b,c$.]

[Ce mercredi 13 janvier 2021 à 10h00, je remplace au paragraphe précédent l'expression "infiniment plus de liberté" par l'expression "beaucoup plus de liberté" car, si ces deux expressions peuvent s'employer indistinctement dans le langage courant, en revanche en mathématiques ce n'est pas le cas. Possédant des capacités de calcul limitées, les tableurs finiront tôt ou tard par procéder à des arrondis si on choisit $a,b,c$ trop grands pour eux. Or, j'en ai déjà parlé au point $\fbox{III}$, les arrondis sont nos ennemis. En d'autres mots, ici, si le choix de $a,b,c$ peut être "grand", il n'est pas "infiniment grand".]

Mille mercis à celles et ceux qui auront bien voulu jouer un petit moment avec moi.
(Je prie pour que ce message ne soit pas déplacé dans la rubrique "Shtam".)
«1

Réponses

  • AD,

    Merci d'avoir agrandi les deux fractions en utilisant l'option \dfrac{}{} que je ne connaissais pas. Comme cela, c'est plus lisible, en effet.

    J'ai remarqué, entre autres modifications, que tu avais ajouté...une virgule, presqu'en fin de message. Quel souci de la précision !
    Moi, je ne l'aurais pas mise (d'ailleurs je ne l'ai pas mise :-)) mais au moins, comme ça, j'ai le sentiment que quelqu'un a lu mon message en entier. Encore merci à toi.
  • Sneg
    Je t'ai aussi indiqué une manière plus "classique" d'encadrer une expression à l'aide de la commande \fbox{...} ;-)
    AD
  • Oui, j'ai remarqué aussi !
    Grand merci, AD.
  • Bonjour.

    Désolé, je viens seulement de voir ce fil (que je m'étais moralement engagé à venir voir) et il a fallu aller bien bas dans le forum pour le trouver.

    Concernant l'exercice, je coince au niveau de la détermination de a, b et c, j'ai choisi $a= 71$, $b=83$ et $c=97$ (ils sont premiers, donc premiers entre-eux) et il m'est très difficile de trouver $(x,y)$ strictement positifs tels que $ax+by=c$.

    Comment fais-tu, sneg ?

    A bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • Bonjour, Dreamer, et merci d'intervenir.

    Comment faire pour trouver $x, y$ tels que $71x+83y=97$ ?

    Comme je l'ai noté dans le message initial, il s'agit d'une équation diophantienne. Elle se résout donc comme toute équation diophantienne de cette forme.

    Si tu es aussi pris par le temps que je peux l'être, alors saisis tout simplement dans Wolfram Alpha la commande suivante (sans les guillemets) :
    "solve 71x+83y=97 for x and y integers"

    La solution apparaîtra presqu'instantanément :
    $x=-83n-15$ et $y=71n+14$ $(n \in \mathbb{Z})$,
    dont la forme est conforme à ce que je demandais dans le message initial :
    $x=-bn-p$ et $y=an+q$, avec $0<p<b$ et $0<q<a$.

    Encore merci.
  • Désolé, j'avais pris le caractère positif de $x$ et $y$ de manière stricte, sans avoir regardé plus loin.

    Ok pour la suite.
    Ça ne me semble pas particulièrement magique mais c'est sympa.

    A bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • C’est vrai, Dreamer, que ce petit « tour de magie » ne peut s’apprécier que si l’on a déjà cherché à calculer $k$ sans recourir à la programmation informatique.

    Ici, rien qu’en saisissant dans un logiciel de mathématiques les deux commandes suivantes... :

    1) solve ax+by=c for x and y integers
    et
    2) Table{x, N[((a-q)*x-q)/a], N[((b-p)*x-p)/b]} for x from 1 to 100 (ou plus de 100)

    ... il s’affiche un tableau de valeurs numériques où le $k$ recherché apparaît tout seul, dans toute sa splendeur.
    (En fait, ce qui apparaît c’est $X$. Mais comme $k=X+1$, ça revient au même.)

    Aussi longtemps que l’on n’a pas démêlé le pourquoi du comment de cette méthode de calcul de $k$, cela reste magique, non ? :-)
  • Bonjour

    Sans Wolfram, et si vous tendez la joue, vous aurez un petit Bézout.
    La méthode est simplement l'algorithme d'Euclide étendu.

    83 = 71 * 1 + 12
    71 = 12 * 5 + 11
    12 = 11 * 1 + 1
    11 = 1 * 11 + 0

    Donc déjà, on sait que le pgcd de 71 et 83 est 1 (quel scoop.). Et on étend le processus.

    12 = 83 * 1 - 71 * 1
    11 = 71 * 1 - 12 * 5 = 71 * 1 - (83 * 1 - 71 * 1) * 5 = 83 * (-5) + 71 * 6
    1 = 12 * 1 - 11 * 1 = (83 * 1 - 71 * 1) * 1 - (83 * (-5) + 71 * 6) * 1 = 83 * 6 + 71 * (-7)

    On a le pgcd en fonction des 2 entiers de départ. Pour faire apparaître 97, on peut multiplier froidement les 2 membres par 97. Ou alors, on bidouille les coefficients trouvés. On réussira toujours puisque la formule obtenue permet d'avoir une résolution de 1.

    1 = 83 * 6 + 71 * (-7)
    84 = 83 * 7 + 71 * (-7)
    96 = 83 * 8 + 71 * (-8)
    97 = 83 * 14 + 71 * (-15)

    J'ai passé sous silence le ppcm 83*71=5893 qui permet de trouver d'autres couples tout aussi valides.
  • Salut, si le topic revient il se dévoile un peu seul. Juste à Sneg comme avis: je ne questionne la beauté mais quand tu mets les bornes sur $p$ et $q$ ça semble restrictif sur les choix $a,b,c$. Il doit y avoir quelque chose qui marche sans ces bornes.
  • Attention, PetitLutinMalicieux !
    Le but du jeu n'est pas de trouver $m,n \in \mathbb{Z}$ tels que $ma+nb=c$.
    Ce qu'il s'agit de faire, c'est trouver le plus petit entier strictement positif $k$ tel que $kc=ma+nb$, avec $m,n$ entiers strictement positifs aussi.

    Tonm, si j'ai imposé ces conditions sur $a,b,c$, c'est pour, à ma façon, coller à la théorie des semigroupes numériques 3-engendrés de Rosales & Garcia-Sanchez...même si je crains que claude quitté, infiniment meilleur connaisseur que moi, n'approuve pas du tout mon approche !
    (Je sais, je suis incorrigible.)
  • Sneg a écrit:
    Le but du jeu n'est pas de trouver $m,n \in \mathbb{Z}$ tels que ma+nb=c.
    Oui. Tu dis ça, mais c'est ce que tu as demandé à Wolfram Alpha.
    Je me mettais juste à la place de l'internaute moyen, qui voulait savoir comment Wolfram Alpha avait fait. Et comment on peut faire soi-même, à la main.
  • C’est d’accord, PetitLutinMalicieux.
    Merci de t’intéresser à ce fil.
  • Je n'avais pas fait le tour de magie. Maintenant, je viens de le faire. Et je suis frustré. Cela ne marche pas du tout. Et je ne sais pas d'où vient la faute. Je donne mes valeurs.
    a=79
    b=96
    c=83
    83=96*56-79*67
    n=-1$\in \mathbb{Z}$ (à propos, il y a 2 "n" dans ton sujet)
    x=56=-96*(-1)-40
    y=-67=79*(-1)+12
    p=40 (0<p<96)
    q=12 (0<q<79)
    X=2
    Y=1
    k=3
    m=-24
    n=-43
    ma+nb=-24*79+-43*96=-6024
    kc=3*83=249
    :-S
    Qu'est-ce que j'ai fait de mal ?
    :-(
  • Oui, aprés réflexion tu peux supposer que si $k\neq 1$ pas de solutions positives à $ax+by=c$, alors n'importe quel solution à $ax+by=c$ aura la forme $x=-nb-p$ et $y=na+q$ avec $0<p<b$ et $0<q<a$
    pour un certain entier $n$.

    Cordialement.
  • Tonm,
    je découvre à l'instant ton message et à priori je ne suis pas vraiment d'accord avec toi.

    PetitLutinMalicieux,
    Je suis désolée que tu sois frustré.
    Reprenons ensemble, comme dans le message initial, le chemin qui mène à $k$ :

    $\fbox{I}$ : [size=medium] Choix de a,b,c. [/size]
    Tu as choisi $a=79$, $b=96$ et $c=83$. C'est parfait.

    $\fbox{II}$ : [size=medium] Détermination de p,q. [/size]
    La solution de l'équation diophantienne $79x+96y=83$ sous la forme que j'ai demandée est la suivante :
    $$x=-96n-67 \qquad \text{et} \qquad y=79n+56$$
    (Oui, il y a deux $n$, mais c'est la même variable.)

    Donc, $p=67$ et $q=56$. C'est là, ton erreur. Allons jusqu'au bout avec les bonnes valeurs :

    $\fbox{III}$ :[size=medium] Détermination de X,Y et apparition soudaine de k. [/size]
    A partir de $a=79$, $b=96$, $p=67$ $q=56$, le tableau que tu dois obtenir avec ton propre tableur ou avec la commande suivante à saisir sur Wolfram Alpha (sans les guillemets) :
    "Table{x, N[((79-56)*x-56)/79], N[((96-67)*x-67)/96]} for x from 1 to 50"
    ressemble à celui-ci :

    $$\begin{array}{|c|c|c|}
    \hline
    x & y_1 & y_2 \\
    \hline
    1 & -0,41\cdots & -0,39\cdots \\
    \hline
    2 & -0,12\cdots & -0,09\cdots \\
    \hline
    3 & 0,16\cdots & 0,20\cdots \\
    \hline
    4 & 0,45\cdots & 0,51\cdots \\
    \hline
    5 & 0,74\cdots & 0,81\cdots \\
    \hline
    6 & 1,03\cdots & 1,11\cdots \\
    \hline
    7 & 1,32\cdots & 1,41\cdots \\
    \hline
    8 & 1,62\cdots & 1,71\cdots \\
    \hline
    9 & 1,91\cdots & 2,02\cdots \\
    \end{array}$$

    Tu y vois que, pour $1 \leq x \leq 8$, aucun intervalle des réels $[y_1, y_2]$ ne comporte d'entier positif.
    En revanche, pour $x=9$, l'intervalle des réels $[1,91\cdots ; 2,02\cdots ]$ comporte un (plus petit) entier positif, à savoir l'entier positif $2$.
    Posons alors $X=9$ et $Y=2$.

    Pose enfin : $X+1=9+1=10=k$. Et voilà ! Tu as trouvé $k$.

    Et avec les formules données dans le message initial, tu trouves aussi $m$ et $n$ :
    $m$ $(\in \mathbb{N^*})$ $=-p+(b-p)X-(b)Y=-67+(96-67)9-(96)2=2$.
    $n$ $(\in \mathbb{N^*})$ $=+q-(a-q)X+(a)Y=56-(79-56)9+(79)2=7$.
    (Il y a un moyen plus expéditif que ces deux formules rébarbatives pour calculer $m$ et $n$, mais c'est mon petit secret.)

    Ainsi, tu as finalement :
    $$ \fbox{$10\times83=2\times79+7\times96$}$$
    avec $10, 2, 7$ qui sont bien des entiers strictement positifs, et avec $10$ qui est minimal.

    Maintenant, tu vas me demander de prouver que c'est la bonne solution.
    C'est le point épineux du problème. Car pour prouver que c'est la bonne solution, je dois dévoiler mon tour de magie. Et cela, il n'en est pas question ! :-)
    Donc, Je dois te demander de vérifier par toi-même. Pardonne-moi.
  • Oui pas d'accord ou pas clair ou...
    Ça devra parvenir (correctement).
  • Ahhhhhh. Mais je comprends tout. Il est important de dire, dans l'énoncé, que "n" ne doit pas être fixé, contrairement à p et q.

    Merci pour l'explication.
  • Bonjour, je met ce lien parceque ça répond à l'idée de mon avant dernier message sur la forme des solutions quand $k$ est différent de 1,

    https://en.m.wikipedia.org/wiki/Bézout's_identity

    C'est la même chose avec $ax+by=1$ ou $ax+by=c$ on part de $by_0=c\pmod{a}$ avec $0<y_0=q<a$
    Comme $c$ est positive et $x<0$, $x=-q$ avec $0<q<b$ tu devra finir l'idée.

    Si $k=1$ les solutions ne peuvent être représenter par
    $x=-nb-p$, $y=na+q$ avec les bornes vue que l'un au moins $ (x \text{ ou } y ) $ est négatif. Même ici il y a un lien

    http://www.les-mathematiques.net/phorum/read.php?5,2109576,2109700#msg-2109700

    Enfin si on est là, $ax+by=c$, $ a,b,c$ entiers non nuls, et $pgcd(a,b)=1$, le $k$ minimal tel que $ax+by=kc$, $x,y>0$ est le plus petit $k\ge 1$ vérifiant

    $kc-(b[ky_0 \pmod{a}]) \ge 0$ où $by_0 =c \pmod{a}$,

    Vous remarquez qu'à chaque incrément de $k$ on fait une division en calculant $ ky_0 \pmod{a}$
    pareil pour le jeu de Sneg.

    Bonne année.
  • J'ai fait un essai avec 71 x + 83 y = 97 z

    Je cherche d'abord classiquement 71 x - 83 y = 1 puis, en multipliant par 97 j'obtiens : 71( -15 + 83 k ) + 83 ( 14 - 71 k ) = 97

    On introduit le facteur j : 71 ( -15j + 83k) + 83 ( 14j - 71 k) = 97 j

    Il faut -15 j + 83 k > 0 et 14 j - 71 k > 0

    Une remise en forme : 83 / 15 > j / k >71 / 14 ou 5 + 8/15 > j / k > 5 + 1/14

    Je cherche un j min : 5+1/2 convient ( 5 + 1/1 trop grand). D'où j = 11 et k = 2

    71 * 1 + 83 * 12 = 11 * 97.
  • Tonm et nodgim,

    Vous êtes les deux seules personnes au monde à me proposer une méthode manuelle pour déterminer $k$. Je vous en remercie infiniment, même si pour le moment je ne les comprends pas encore.

    Cela dit, reste-t-elle utilisable avec des nombres plus grands comme par exemple a=33587, b=30013 et c=10000, voire des nombres dépassant le million ?

    La méthode que je propose dans ce fil a pour intérêt (?) que l’on ne doit rien calculer du tout. On recueille juste les résultats d’une équation diophantienne calculés par un logiciel puis, à partir de ces solutions, on se contente de regarder un tableau affiché par un tableur. On peut faire ça allongé dans son canapé préféré. Le seul danger, car $k$ peut être loin dans le tableau, c’est le risque d’assoupissement.

    Cela dit, on me dira que si on ne veut vraiment rien calculer du tout, la solution est la programmation informatique. Mais cela ne m’aurait pas permis de vous présenter ma méthode de calcul sous la forme d’un tour de magie.

    Encore mille mercis !
    Et bonne année 2021 !
  • 33587 * 25 + 30013 * 25 = 159 * 10000

    Sauf erreur.

    L'arithmétique existait avant les logiciels.
  • Mais, nodgim !! Pourquoi ne m’as-tu jamais parlé de ta méthode ?!
    À l’époque où nous communiquions à propos du nombre de Frobenius, tu ne me parlais jamais que de «vecteurs de recopie» (auxquels je ne comprenais rien, pardonne-moi).
    Mais ce n’est pas grave ! Comme ça, j’ai mis au point ma propre méthode de calcul.
    Tout est bien qui finit bien. :-)
  • Note personnelle :
    Le cas amusant a=impair, b=a+1, c=a+2.
    Démontrer que k=(a+1)/2.
  • Sneg, si tu connais l'anglais je t'invite à lire ça https://hal.inria.fr/hal-01337295
    Et les débuts http://www.les-mathematiques.net/phorum/read.php?5,1188697,1199371
    Bonne année.
  • @ Sneg : Je confirme ce (a+1)/2, avec la même méthode employée pour calculer les cas proposés précédemment.
  • Merci pour les liens, Tonm. C’est très gentil.

    Nodgim, après mes examens je reviendrai sur ta méthode.
  • Bonjour Sneg. En ce début d'année 2021, je me suis dit que c'était l'occasion pour moi de faire un tour de magie. C'est vraiment un tour de magie car je ne sais pas comment cela marche pour la bonne raison que je viens juste de découvrir le truc. J'ai seulement compris comment faire le tour en louchant sur une toute petite partie d'un exposé de Rosales et de l'un de ses papiers in https://cmup.fc.up.pt/cmup/ASA/numsgps_meeting/slides/rosales-2.pdf http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6CC24007F6B17875BA75F94436062565?doi=10.1.1.145.9528&rep=rep1&type=pdf

    Mais il va falloir que tu t'accroches. Peut-être que mon machin est un peu trop compliqué et risque de faire flop.

    $\bullet$ 1. D'abord, il faut que je te présente rapidement l'arbre de Stern-Brocot. C'est un arbre dans lequel poussent toutes les fractions positives. Un dessin extrait d'une note à la fin. On part de $0 = {a \over b} = {0 \over 1}$, $\infty = {c \over d} = {1 \over 0}$ et on fait une ``addition de cancre'' ${a \over b} \oplus {c \over d} = {a + c \over b + d} =_{\rm ici} {1 \over 1}$. Que l'on met au milieu (dans une ligne en dessous) et on recommence. C'est le premier dessin que tu vois.

    Ensuite, tu fais un peu de ménage pour obtenir l'arbre en dessous avec des branches rouges et des feuilles qui sont des fractions. On ne met ni $0 = {0 \over 1}$ ni $\infty = {1 \over 0}$ dans l'arbre (mais on ne les oublie pas car c'est eux qui ont engendré le binz). On a donc un arbre binaire avec $1 = {1 \over 1}$ comme racine. Binaire car il y a 2 branches en dessous de chaque feuille, branches que l'on schématise par $G$ et $D$, $G$ pour gauche, $D$ pour droite.

    Si tu prends un mot en les symboles $G, D$, par exemple le mot $m = DDGG$ et que tu suis les directions en partant de la racine 1, tu tombes sur une feuille qui est une fraction, ici dans l'exemple, $7/3$. Et ce qui est déjà magique, c'est que tu obtiens tous les rationnels (les fractions) positifs une et une seule fois. Je veux dire que partant d'une fraction, tu peux reconstituer le chemin qui part de la racine et qui conduit au rationnel en question.

    Un peu magique, non ? Mais ce n'est pas de cette magie dont je veux te parler. Bien entendu, il y a belle lurette que j'ai programmé tout cela et je ressors la chose à l'occasion.
    [color=#000000]> m := D * D * G * G ;
    > WordToRational(m) ;
    7/3
    [/color]
    
    Au cas où tu saurais ce qu'est une matrice $2 \times 2$, tu peux regarder les quelques lignes ci-dessous, sinon passe au point 2 (tu connais le conte de Raymond Queneau, Les 3 alertes petits pois ? http://ecole.donazaharre.free.fr/Document/Primaire/NosTextes/2009/HistoiresEmbranchements/Histoire_Queneau.pdf). Une manière d'obtenir la fraction consiste à remplacer dans le mot $m$ les symboles $G,D$ par les deux matrices ci-dessous et à faire le produit
    $$
    D \leftrightarrow \left[\matrix {1 & 0\cr 1 & 1\cr}\right] \qquad
    G \leftrightarrow \left[\matrix {1 & 1\cr 0 & 1\cr}\right] \qquad
    \text{produit dans le mot } m = \left[\matrix {\alpha & \beta\cr \gamma & \delta \cr}\right] \qquad \text{feuille } =
    {\text{somme ligne basse} \over \text{somme ligne haute}} = {\gamma + \delta \over \alpha + \beta}
    $$
    [color=#000000]> mD ;
    [1 0]
    [1 1]
    > mG ;
    [1 1]
    [0 1]
    > mD * mD * mG * mG ;
    [1 2]
    [2 5]
    [/color]
    
    Ici la feuille fraction est ${2 + 5 \over 1 + 2} = {7 \over 3}$

    $\bullet$ 2. J'en viens à tes affaires, si, si. Il se trouve que ce avec toi tu t'amuses i.e. faire rentrer un entier $c$ dans $a\N + b\N$ en le multipliant par le plus petit entier $k \ge 1$ possible, cela porte un nom.

    Je te présente maintenant ce que Rosales (et les autres) nomme le semi-groupe quotient de $\langle a, b \rangle =_{\rm def} a\N + b\N$ par un entier $c \ge 1$. C'est par définition l'ensemble des entiers $k$ qui font rentrer $c$ dans $\langle a, b \rangle$. De manière formelle (à gauche, c'est la notation utilisée par Rosales)
    $$
    S := \langle a, b \rangle/c = \{ k \in \N \mid kc \in \langle a, b\rangle \}
    $$Une fois que $a,b,c$ sont fixés, ce $S$ c'est un semi-groupe i.e. $S$ contient $0$ et si $k_1, k_2 \in S$ alors $k_1 + k_2 \in S$.

    On va prendre $a,b \ge 2$ avec $a \wedge b = 1$ et $c \ge 1$. Et tu sais à quoi s'amusent les auteurs ? Ils déterminent un système de générateurs de $S$ grâce à l'arbre de Stern-Brocot. Dingue, non ?

    $\bullet$ 3. Mais nous autres, enfin surtout toi, tu veux juste le plus petit élément $\ge 1$ de $S$ i.e. le plus petit $k \ge 1$ qui fait rentrer $c$ dans $a\N + b\N$. Je te raconte comment cela se passe sur un exemple.

    D'abord, je fais tourner mes vieilles affaires des années passées
    [color=#000000]> a := 11  ; b := 15 ; c := 13 ;
    > k, alpha, beta := MultiplicateurMinimal(c, a,b) ;
    > k ;
    2
    > alpha ;
    1
    > beta ;
    1
    > k*c eq alpha*a + beta*b ;
    true
    [/color]
    
    Tu vois $a = 11$, $b = 15$, $c = 13$. Et on a trouvé $k = 2$ : $2 \times 13 = 1 \times 11 + 1 \times 15$.

    $\bullet$ 4 Maintenant, c'est NOUVEAU et le tour de magie (de Rosales) commence vraiment ici. Tu cherches une relation de Bezout sur $a,b$ avec $u,v \ge 1$
    $$
    ub - va = 1 \qquad \text{donc} \qquad {b \over v} - {a \over u} = {1 \over uv}
    $$
    [color=#000000]> a := 11  ; b := 15 ;
    > // 1 = u*b - v*a 
    > u, v := Bezout(a,b) ;
    > u, v ;
    3 4
    > u*b - v*a ;
    1
    [/color]
    
    Ensuite débarque $c$ que l'on veut faire rentrer dans $a\N + b\N$. On regarde les deux fractions suivantes dans l'arbre de Stern-Brocot.
    $$
    {a \over cu} \quad<\quad {b \over cv}
    $$
    [color=#000000]> a / (c*u) ;
    11/39
    > P1 := RationalToWord(a/(c*u)) ;
    > P1 ;
    G^3 * D * G * D^4
    > b / (c*v) ;
    15/52
    > P2 := RationalToWord(b/(c*v)) ;
    > P2 ;
    G^3 * D^2 * G^6
    [/color]
    
    Regarder signifie déterminer le chemin, suite de symboles $G,D$, qui vient de la racine. On les voit ci-dessus. Je les recopie :
    $$
    P_1 = GGGDGDDDD, \qquad \qquad P_2 = GGGDDGGGGGG
    $$
    Ces deux mots possèdent un plus grand préfixe commun (préfixe :: en partant de la gauche). Que je note $P$ ci-dessous :
    [color=#000000]> P := Prefix(P1,P2) ;
    > P ;
    G^3 * D
    [/color]
    
    Et le miracle vient maintenant. Ce préfixe est un chemin donc détermine une fraction notée $r$, que je fais afficher sous la forme $r = <d,n>$ avec la signification $r = n/d$ ($n$ numérateur et $d$ pour dénominateur). Et la magie, c'est que le numérateur de la fraction correspondant au chemin préfixe $P$ de $P_1, P2_2$, c'est $k$. Le $k$ que tu cherches dans ce fil !!
    [color=#000000]> r := WordToPoint(P)  ;
    > r ;
    <7, 2>
    > r[2] eq k ;
    true
    [/color]
    
    Bon, j'en conviens, c'est peut-être beaucoup pour un début d'année.115312
  • Bonsoir, claude quitté,

    Un tout grand merci d'intervenir pour proposer toi aussi un tour de magie. :-) (Une nouvelle épidémie ?)
    Comme je l'ai écrit plus haut dans ce fil, j'ai bien peur que tu n'aies pas trop apprécié le mien, qui jette aux orties la théorie officielle.
    Mais c'est pour s'amuser !!

    De mon côté, je m'efforcerai sans faute de savourer ton tour dès que j'en aurai le temps, car j'ai commencé aujourd'hui même ma session d'examens et ne suis pas trop en condition pour me concentrer sur de nouvelles idées.

    Mais je reviendrai, sois-en sûr.
    A bientôt !
    Bonne année 2021 !
  • @ Claude Quitté: c'est bien entendu de cette façon que je trouve les solutions à ce problème. En revanche, j'utilise aussi les fractions continues, qui sont assez indissociables de l'arbre Stern-Brocot. Ce sont des outils bizarres mais très efficaces.
  • Rebonjour Sneg,
    Ok, tu n'as pas le temps. Souhaitons que tu reviennes plus tard. Attention, ce qui suit va être violent de ma part. Je conteste des phrases de ta part du style ``Vous êtes les deux seules personnes au monde à me proposer une méthode manuelle pour déterminer $k$'' ou bien ``Cela dit, on me dira que si on ne veut vraiment rien calculer du tout, la solution est la programmation informatique''. D'ailleurs, cette dernière phrase ne veut rien dire du tout.

    On a l'impression que le mot ``programmation informatique'' est un truc magique qui va tout résoudre. Mais en faisant quoi ?

    D'abord, je fournis de nouveau la spécification du problème. Soient $a, b \in \N^*$ avec $\gcd(a,b) = 1$ et $c \in \N^*$. Déterminer le plus petit $k \ge 1$ tel que $kc \in a\N + b\N$ i.e. $kc = ua + vb$ avec $u,v$ entiers $\ge 0$.

    Ta méthode, vos méthodes ? Je demande à voir. De manière précise. Je te raconte ce qui s'est passé de mon côté. Comme la théorie des semi-groupes numériques intervient dans des histoires de courbes monomiales affines, j'ai eu besoin de résoudre le problème ci-dessus, résoudre au sens ``écrire un algorithme qui''. C'était grosso-modo il y a 4-5 ans. Cet algorithme était inefficace (pour des grands entiers), je le savais mais cela suffisait à mes besoins dans mes affaires de courbes monomiales.

    J'ai remis cela en 2019 en écrivant un algorithme bien plus efficace mais toujours incrémental (méthode modulaire + essais successifs). Mais je savais bien que ce n'était pas une bonne méthode.

    Et voilà que 2021 arrive (bonne année), découvrant que les professionnels (Rosales, Garcia-Sanchez et les autres) ont bien avancé la chose. Mots-clefs (en anglais) : Bezout sequences, Stern-Brocot tree, quotient of semi-group by a positive integer, proportionally modular diophantine inequality, proportionally modular numerical semigroups ...etc...

    C'est d'une efficacité extraordinaire. Regarde la taille de $a,b$, de $c$ qui est volontairement petit et le temps de calcul.
    [color=#000000]> repeat a := Random(10^50,10^70) ;  b := Random(10^50,10^70) ; until Gcd(a,b) eq 1 ;
    > c := Random(10^2,10^3) ;
    > a ;
    440873662298863921176812501693448530804046869520423716362875483538673
    > b ;
    5294089434848330362467784207519840730936345994943003310688725232287019
    > c ;
    440
    > time k, u, v := MinimalMultiplier2021(c, a,b) ;
    Time: 0.030
    > k ;
    121314005735273191448883228158394085179272098314210313883899791764968
    > u ;
    13
    > v ;
    9
    > k*c eq u*a + v*b ;
    true
    [/color]
    
    Je prends maintenant mon vieux machin de 2019 que je jugeais efficace à l'époque. Pas question de le faire tourner avec $a,b$ trop gros. Je me calme en prenant $a, b$ bien plus petits. Regarde le temps de calcul de la méthode 2021 (implémentée hier) et celui de la méthode 2019. Tu comprends maintenant que ``programmation informatique'', cela ne veut absolument rien dire.
    [color=#000000]> repeat a := Random(10^6,10^8) ;  b := Random(10^6,10^9) ; until Gcd(a,b) eq 1 ;
    > c := Random(10^2,10^3) ;
    > a ;
    83422945
    > b ;
    980575204
    > c ;
    680
    > time k1, u1, v1 := MinimalMultiplier2021(c, a,b) ;
    Time: 0.000
    > k1 ;
    7700835
    > u1 ;
    4
    > v1 ;
    5
    > time k2, u2, v2 := MinimalMultiplier2019(c, a,b) ;
    Time: 14.760
    > [k1, u1, v1] eq [k2, u2, v2] ;
    true
    [/color]
    
  • Hello,

    Oubli et/ou maladresse de ma part dans mon premier post hier. J'ai pointé sur des transparents d'un exposé de Rosales (Porto 2008) sans me rendre compte qu'il y avait un exposé précédent. Normal, je découvrais le truc. Je répare en pointant sur l'exposé 1 in https://cmup.fc.up.pt/cmup/ASA/numsgps_meeting/slides/rosales-1.pdf.

    Le problème comme souvent est de rentrer dans le binz. Ce n'était pas facile en commençant par l'exposé 2 !

    Note : les auteurs ont trouvé un filon. Et quand on trouve un filon, c'est bien (sic) de l'exploiter https://cmup.fc.up.pt/cmup/ASA/numsgps_meeting/slides/robles-perez.pdf

    En résumé : maintenant, on dispose de plusieurs mots-clés, ce qui facilite la recherche sur le web.
  • Pour commencer, claude quitté, un tout grand merci pour les liens vers lesquels tu me diriges, même si je ne comprends pas encore très bien vers où on va (c'est assez habituel, chez moi).

    Petit retour en arrière.
    Si tu regardes les dates, tu verras que ce fil n'a suscité la réaction de personne pendant plus d'un mois. j'étais déçue. Pour lancer une discussion sur le sujet (le calcul de $k$), j'espérais l'intervention d'au moins deux personnes, nodgim et toi. Nodgim a fini par venir, mais pas toi. Les deux phrases à moi que tu contestes dans ton avant-dernier message, ... j'avoue que je les ai un peu écrites pour te faire réagir (en supposant que tu les lises). Pardonne-moi. Je ne le ferai plus.

    Pourquoi chez moi cette obsession pour $k$ ?
    Un jour, nodgim m'a fait connaître l'existence du "problème des pièces de monnaie" (avec 3 pièces), sans m'en donner la solution. C'était une énigme qu'il posait.
    J'ai cherché une solution générale et, un peu avec son aide, j'en ai trouvé une ... qui passe obligatoirement par le calcul de $k$. Ne trouvant nulle part dans les livres le moyen de calculer ce $k$, n'obtenant pas non plus de réponse sur ce forum, il a bien fallu que je me débrouille toute seule. Et j'ai fini par trouver la méthode qui fait l'objet de ce fil et dont tu sembles douter, au point que j'imagine que tu n'as pas dû la tester. Perte de temps pour trop peu de résultats face à ta méthode, sans doute.
    J'ai moi-même bien conscience des limites de ma méthode. Pour qu'on lui trouve un quelconque intérêt, il faudrait qu'elle affiche elle aussi la valeur de $k$ en une fraction de secondes, quels que soient les nombres $a,b,c$ du départ. Et cela ne serait possible que si elle était transcrite en langage informatique. C'est la raison pour laquelle j'ai pris le parti de ne la présenter que sous la forme d'un petit divertissement ... qui ne divertira sans doute jamais personne d'autre que moi.

    Tu sembles t'émerveiller de voir apparaître $k$ au détour d'un chemin à travers des fractions. (Je n'ai pas encore tout compris, pardon.)
    De mon côté, trouver $k$ revient à tracer deux droites sécantes, mais quasiment confondues, dans un repère orthonormé et à déterminer le point le plus proche de l'origine du repère, qui soit compris entre les deux droites et dont les coordonnées soient entières et positives.
    Deux visions différentes du même problème.

    J'imagine que pour toi, tout cela est très sérieux, alors que je semble simplement "jouer". C'est vrai, mais même quand je m'amuse à jouer, je le fais avec le plus grand sérieux.

    A bientôt !
  • Par la programmation informatique, le point $\fbox{III}$ du message initial s’effectue en une fraction de secondes.
    Est-il possible de régler le point $\fbox{II}$ par la programmation informatique également ?
    Merci d’avance.
  • @ Sneg : ta 1ère évocation de lien entre le problème que tu présentes ici : trouver x, y tel que ax + by = zc avec z min et le problème que j'avais proposé antérieurement : trouver l'entier max qu'on ne peut pas écrire comme somme de ax + by + cz, m'avait laissé perplexe, je n'avais pas réagi, pensant avoir mal compris.

    Le fait que tu reviennes sur le sujet plus nettement me fait maintenant réagir :quel lien entre les 2 problèmes ? Dans le 1er, on cherche ax + by - cz = 0 avec z min. Dans le second, on cherche le nombre max dans l'expression ax + by + cz. As tu trouvé une relation directe entre z et ce nombre max ?
  • [color=#000000]SnegMethod := function(c, a,b)
      assert Gcd(a,b) eq 1   and  c in [1..a*b] ;
      q := (Modinv(b,a)*c) mod a ;
      p := ExactQuotient(b*q - c, a) ;
      assert c eq b*q - a*p  and p in [1..b-1]  and	q in [1..a-1] ;
      for x := 1 to Min(a,b) do
        y1 := ((a-q)*x - q) / a ;
        y2 := ((b-p)*x - p) / b ;
        assert y1 lt y2 ;
        if Ceiling(y1) le Floor(y2) then
          X := x ;
          Y := Ceiling(y1) ;
          assert Y	eq Floor(y2) ;  // je n'en sais rien
          return X, Y ;
        end if ;
      end for ;
      error "Impossibile : que passa ?" ;
    end function ;
    [/color]
    
    Un exemple : mon ancienne mauvaise ``méthode'' (sic) incrémentale puis celle de Sneg (tout aussi incrémentale).
    [color=#000000]
    > repeat a := Random(10^7,10^8) ;  b := Random(10^7,10^8) ; until Gcd(a,b) eq 1 ;
    > c := Random(10,10^2) ;
    > a ;
    34960174
    > b ;
    76465565
    > c ;
    80
    > time k, u, v := MinimalMultiplier2019(c, a,b) ;
    Time: 7.010
    > k ;
    4096650
    > time X, Y := SnegMethod(c, a, b) ;
    Time: 11.970
    > k eq X+1 ;
    true
    [/color]
    
  • Nodgim,
    je viens de voir ton message. J'y répondrai au plus vite. A bientôt.

    Claude quitté,
    k eq X+1
    true
    Est-ce que cela veut bien dire ce que je pense ?

    Pardon pour mon style télégraphique.
  • Nodgim,

    En effet, pour moi, la recherche du nombre de Frobenius de l'ensemble $\{a, b, c\}$ passe par la détermination de $k$, $m$ et $n$ dans l'égalité $ma+nb=kc$, avec $k$ entier strictement positif minimum et $m,n \in \mathbb{N}$.

    Le fait que "mes" $m,n$ puissent être nuls (jamais ensemble) semble me mettre en désaccord avec la théorie des semi-groupes numériques (dont le problème de Frobenius fait partie) de Rosales & Garcia-Sanchez, où $m$ et $n$ sont strictement positifs (pour ce que j'en sais). Donc, je préfère ne pas aborder ici ces cas-là.

    Pour les mêmes raisons, je ne parlerai pas non plus des cas où l'égalité suivante est vérifiée :
    (Le plus grand des trois nombres) = (M $\times$ le plus petit nombre) + ( N $\times$ le nombre qui n'est ni le plus grand ni le plus petit),
    avec $M,N$ des entiers strictement positifs.

    Il reste alors les cas que j'ai abordés dans ce fil et qui semblent être en accord avec la théorie de Rosales & Garcia-Sanchez : ceux où $a,b,c$ sont trois entiers strictement positifs distincts, premiers entre eux deux à deux et tels que l'on n'ait pas l'égalité :
    (Le plus grand des trois nombres) = (M $\times$ le plus petit nombre) + ( N $\times$ le nombre qui n'est ni le plus grand ni le plus petit),

    Dans ces derniers cas, le lien entre $k$ et le nombre de Frobenius de l'ensemble $\{a, b, c\}$ est le suivant :
    $\fbox{1}$ Dans l'égalité $ma+nb=kc$, la détermination de $k$ (minimal) entraîne la détermination de $m$ et $n$.

    $\fbox{2}$ Connaissant $m$ et $n$, je peux résoudre l'équation diophantienne $nx+my=c$ qui possède toujours au moins deux solutions strictement positives $(X, Y)$ et $(X', Y')$ telles que $aX \equiv bY \pmod{c}$ et $aX' \equiv bY' \pmod{c}$. Claude quitté a démontré ici : http://www.les-mathematiques.net/phorum/read.php?5,2083604,2095540#msg-2095540 l'existence de ces deux solutions. (Dans l'ensemble de ce genre de solutions, le tout c'est de trouver les deux bonnes. C'est heureusement plus facile qu'on ne croit.)

    $\fbox{3}$ Connaissant $a,b,c$, $m$ et $n$ ainsi que $(X, Y)$ et $(X', Y')$, il me devient possible de calculer le nombre de Frobenius de l'ensemble $\{a, b, c\}$ au moyen d'un calcul ne reprenant rien d'autre que ces différentes valeurs.

    Par exemple, si $a=2021$, $b=1517$, $c=899$ :
    On calcule par "Hocus Pocus" que $k=77$, $m=32$ et $n=3$.
    Ensuite, on sélectionne, parmi dix solutions possibles, les deux solutions adéquates $(X, Y)$ et $(X', Y')$ de l'équation diophantienne $nx+my=c$, à savoir $(\underline{33}, 25)$ et $(1, \underline{28})$.
    Le nombre de Frobenius de l'ensemble $a=2021$, $b=1517$, $c=899$ est alors le plus élevé des deux suivants :
    1) $(\underline{33}-1)a+(n-1)b-c=66807$
    ou
    2) $(m-1)a+(\underline{28}-1)b-c=102711$
    C'est-à-dire $102711$.

    (Nodgim, tu connais ça.)
  • Sneg,

    Une première question à propos de complexité. Quel est, en fonction de $k$, le nombre d'exécutions de (la boucle de) l'étape III (celle dont tu dis, je te cite, que ``par la programmation informatique, elle s'effectue en une fraction de seconde'') ? I.e. celle où l'on risque de s'endormir sur le canapé ?

    Nogdim.

    J'ai fourni des mots clefs dans un post (en ce qui concerne la recherche de $k$, cf plus bas). Je crois que tu disposes du livre de Rosales & Garcia-Sanchez, Numerical Semigroups, 2009 (je t'ai procuré le pdf il me semble, vrai, faux ?).

    La détermination pertinente du plus petit $k \ge 1$ tel que $kc \in \N a + \N b$ a été réalisée par l'équipe portugaise dans les années 2008.

    Elle fait l'objet des deux chapitres chap 4 : Proportionnally modular numerical semigroups, chap 5 : The quotient of a numerical semigroup by a positive integer. Ce n'est pas si facile de rentrer dedans et il faut compter, si on ne se décourage pas, plusieurs semaines pour parvenir à ses fins.115570
  • Claude quitté,
    La boucle s'effectue $k-1$ fois.
    Tout dépendra donc de la vitesse d'exécution de l'ordinateur. Plus $k$ sera grand, plus la réponse se fera attendre, évidemment.

    Un jour, dans mon canapé, la recherche visuelle de $x$ dans le tableau dont je parle au point $\fbox{III}$ du message initial m'a pris entre une et deux heures. Cet $x$ valait environ $10000$. Les joies du confinement.

    Avec le petit programme de onze lignes que j'ai écrit l'autre jour, le résultat s'est affiché bien plus rapidement. Je n'ai pas chronométré, mais ça se compte en poignées de secondes à peine. Aucun rapport avec mon expérience dans le canapé.
    En plus, la calculatrice sur laquelle j'ai écrit mon petit programme date d'après le mode d'emploi de 1997 et ne peut sans doute pas rivaliser de vitesse avec les ordinateurs actuels.

    Quand j'écris que "l'on ne doit rien calculer du tout", je veux dire que l'on peut se contenter de regarder ce qui s'affiche sous nos yeux. Passivement. Et (très) patiemment.
  • @ Claude Quitté : oui, tu m'avais bien fait passer le pdf du livre R&G, mais je ne l'ai regardé qu'en diagonale, il y a bien trop d'anglicismes dans ce livre, plus encore que dans le dernier Goncourt. Quand tu écris qu'il faut plusieurs semaines ( je n'en doute pas un seul instant ) pour comprendre leur théorie qui pourra donner la solution du plus petit k de a n + b m = k c, alors que de mon coté je sais le faire tout seul.....Cela dit, le livre donne accès à des généralités pour résoudre des problèmes bien plus complexes.

    @ Sneg: j'ai compris. Dans ta méthode, le calcul de k est un intermédiaire pour le calcul du nombre de Frobénius. Je sais que la recherche du nombre de F est plus complexe que celle de k, et c'est logique puisqu'il n'y a que 2 variables pour chercher k ,et 3 pour chercher F. Je me souviens vaguement maintenant de ta méthode curieuse qui consiste à calculer d'abord (m,n) puis (x,y) de mx + ny = c. Je n'ai pas trop envie de replonger dans le calcul de F. pour tenter de comprendre comment tu t'y prends, mais si tu justifies ta méthode, tout est OK.
  • Bonjour Sneg (et Nogdim)

    $\bullet$ 1. Voilà une réponse précise : $k-1$ itérations pour déterminer $k$. Depuis le début, je m'en étais rendu compte et comme je disposais d'une ``méthode'' (une très mauvaise méthode) de complexité analogue ($k$ itérations), je n'étais pas intervenu.

    Ce qui est curieux dans tes posts, c'est l'alternance de faits précis rédigés avec le plus grand soin et de choses floues (voir plus loin).

    La formule que tu donnes pour le nombre de Frobenius de $a\N + b\N + c\N$ (dans un contexte ad-hoc) est ce que l'on appelle la forme asymétrique. Aux notations près (et à une permutation près de ``ton dictionnaire'') c'est celle qui figure au début de la remark 13 après le corollary 12 du papier de 2004 (Rosales, Garcia-Sanchez, toujours les mêmes) in http://hera.ugr.es/doi/15773139.pdf

    J'ai donc envie de dire ``bravo''. Et je le dis : BRAVO. En passant : tu m'attribues une preuve de je-ne-sais-trop-quoi mais je n'y suis pour rien. J'ai simplement appliqué les résultats de Rosales-Garcia (et je me souviens que cela n'a pas été simple de te faire passer l'information, j'ai dû m'y reprendre à plusieurs fois).

    Il y a une formule symétrique pour le nombre de Frobenius sur laquelle cela serait une bonne chose de revenir, cf le point 4,

    $\bullet$ 2 Chose floue : ce qui concerne l'informatique. Par exemple ``fraction de seconde'', cela n'a aucun sens. Ce qui compte, dans les temps de calcul que j'ai mentionnés, c'est la comparaison entre les diverses méthodes. Pas les temps de calcul en absolu. En ce qui concerne l'efficacité, tu as tendance à croire à la magie de la ``transcription informatique'' (je reprends tes termes). Non : ce qui compte, c'est la complexité.

    Bien sûr qu'un tableur réalise des calculs. Des choses totalement obscures dans le point III de ton premier post : écriture décimale, valeur numérique, intervalle des réels. Je pense que tu ignores ce qui concerne le calcul en ``flottants''. Il est préférable d'éviter d'en parler (précision, je ne l'utilise pas de calcul flottant).

    $\bullet$ 3. Domaine de validité en ce qui concerne la détermination du plus petit $k \ge 1$ tel que $kc \in \N a + \N b$. Chez moi (pour ma mauvaise méthose) : $a \wedge b = 1$ et $c \ge 1$, rien de plus. Ma méthode est bourrin(e) mais sans mystère. Elle est tellement bourrine et mauvaise que j'ai presque honte de parler de ``méthode''.

    Chez toi, ce n'est pas clair. I.e. dans tes points I, II de ton premier post, il y a un sacré flou sur le choix de $a,b,c$. Il faut des contraintes pour disposer de $p,q$ dans les intervalles que tu cites et pouvoir avoir $c = -ap + bq$. Tu te doutes que si je dis cela, il a une raison.

    Bref : selon toi, que doivent vérifier $a,b,c$ de manière précise pour pouvoir réaliser ton étape II ? Note : comme j'ai programmé toutes tes affaires, ``il a bien fallu que j'y passe''.

    $\bullet$ 4. Formule symétrique pour le nombre de Frobenius de $n_1\N + n_2\N + n_3\N$ (je reprends les notations de Rosales-Garcia) : il s'agit de la proposition 15 dans le papier cité qui ne fait intervenir que $n_1, n_2, n_3, c_1, c_2, c_3$ : $c_1$ c'est le plus petit entier $\ge 1$ tel que $c_1n_1 \in n_2\N + n_3\N$. Idem pour $c_2, c_3$.

    Elle nécessite un certain contexte rappelé à plusieurs reprises dans le papier. Mais, à ma grande surprise, j'ai pu vérifier, de manière expérimentale, qu'elle était valide pour TOUT semi-groupe $n_1\N + n_2\N + n_3\N$ 3-engendré (on peut par exemple avoir $n_3 = n_2$ !). Cela mériterait d'être approfondi.

    Nogdim (et Sneg)

    $\bullet$ 5. Je ne sais pas ce que tu veux dire ``je sais faire tout seul'' i.e. déterminer le plus petit $k \ge 1$ tel que $kc \in \N a + \N b$. Quel est le contexte ? Quelle est la complexité de ta méthode ?

    Remarque : il n'y a pas (enfin, c'était le cas en 2008) de formule pour $k$ en fonction de $a,b,c$. C'est un problème ouvert, cf page 6 du deuxième exposé de Rosales aux journées de Porto in https://cmup.fc.up.pt/cmup/ASA/numsgps_meeting/slides/rosales-2.pdf. La seule manière de déterminer $k$ ``en général'' réside donc dans un algorithme. Mais un algorithme, cela deande autant de précision q'une preuve : il doit être prouvé, en principe, sa complexité doit être analysée ...etc...

    Pourrais tu nous exposer cela avec la plus grande précision ? Je sais c'est du boulot et je comprendrais que tu dises ``non, trop de travail''. De mon côté, je peux montrer ma mauvaise méthode (dont j'ai presque honte) : je l'ai déjà fait avec vous il y a 2 ou 3 ans (toi + Sneg, elle n'avait pas ce pseudo à cette époque). Et à cette époque, tout le monde s'en fichait et il y avait trop de bruits sur le fil.

    J'en redonne un petit coup. Rappel : il y a de la ``science mathématique'' chez Rosales-Garcia, c'est cela le plus important (Stern-Brocot et compagnie). Et en prime, un bonus : c'est efficace !! Bref, que du bonheur avec leurs trouvailles.
    [color=#000000]> repeat a := Random(10^7,10^8) ;  b := Random(10^7,10^8) ; until Gcd(a,b) eq 1 ;
    > c := Random(10,10^2) ;
    > a ;
    93976760
    > b ;
    40519791
    > c ;
    34
    > time k1, u1, v1 := MinimalMultiplier2021(c, a,b) ; // la méthode efficace de l'équipe Portugaise.
    Time: 0.000
    > k1 ;
    18587146
    > time X, Y := SnegMethod(c, a, b) ;
    Time: 52.540
    > k1 eq X+1 ;
    true
    > time k, u, v := MinimalMultiplier2019(c, a,b) ; // ma très mauvaise méthode
    Time: 31.600
    > [k,u,v] eq [k1,u1,v1] ;
    true
    [/color]
    
    Rappel : ce qui compte, ce n'est pas les temps de calcul en absolu mais les rapports, la comparaison entre eux.

    $\bullet$ 6. Un pointeur sur le colloque ``Iberian Meeting on Numerical Semigroups-Porto 2008'' https://cmup.fc.up.pt/cmup/ASA/numsgps_meeting/schedule_slides.html. En passant : est ce que vous avez une idée du nombre de personnes dans l'équipe ? Saviez vous qu'ils travaillent dans ce domaine depuis plus de 20 ans ? Avec vous une idée de ce qu'ils ont réalisé dans le logiciel GAP ? ...etc...

    Précision : ce n'est pas ma spécialité, je ne suis qu'un amateur dans ce domaine. Je veux juste comprendre le B.A.BA.

    $\bullet$ 7. En 2021, nous sommes résignés à nous ``promener'' avec un masque que l'on doit avoir toujours sur soi. Mais pourquoi ne pas avoir toujours sur soi un arbre de Stern-Brocot ? C'est ce que je racontais à mes étudiant(e)s il y a bien longtemps. J'en attache un petit avec une migration douce.

    Ce n'est pas encore trop tard : bonne année 2021 à vous deux et bonne suite.
  • @ Claude Quitté :

    Non, k peut être trouvé par une voie directe.

    Je remets ici ce que j'avais écrit plus haut :

    "J'ai fait un essai avec 71 x + 83 y = 97 z

    Je cherche d'abord classiquement 71 x - 83 y = 1 puis, en multipliant par 97 j'obtiens : 71( -15 + 83 k ) + 83 ( 14 - 71 k ) = 97

    On introduit le facteur j : 71 ( -15j + 83k) + 83 ( 14j - 71 k) = 97 j

    Il faut -15 j + 83 k > 0 et 14 j - 71 k > 0

    Une remise en forme : 83 / 15 > j / k >71 / 14 ou 5 + 8/15 > j / k > 5 + 1/14

    Je cherche un j min : 5+1/2 convient ( 5 + 1/1 trop grand). D'où j = 11 et k = 2

    71 * 1 + 83 * 12 = 11 * 97. "


    Auquel j'ajoute une précision :

    Dans la recherche de " j min " tel que 83 / 15 > j / k >71 / 14, il suffit de chercher le développement en fractions continues de 83/15 et 71/14. La divergence détermine la fraction commune j / k qui est la fraction recherchée.

    83/15 : ( 5,1, 1, 7)
    71/14 : ( 5,14 )

    Le commun est (5,1) on choisit (5,1+1) = (5,2) = 11 / 2.
  • Claude quitté,

    Il m'est très agréable de lire que tu retrouves pour ainsi dire à l'identique un de mes (petits) résultats mathématiques dans un ouvrage pointu d'arithmétique.
    Au point qu'il m'importe peu que ma méthode pour calculer $k$ transcrite en langage informatique soit la plus lente.
    Pardon, si tu trouves que je n'ai aucune ambition mathématique.

    Cela dit, tu reproches à certains de mes passages d'être "flous".
    Cela m'étonne parce que j'ai exprès accompagné mon texte d'un exemple censé être explicatif. Quelques explications supplémentaires :
    "L'écriture décimale" (d'un quotient) t'est inconnue ? $\dfrac{7}{3}=2,333...$
    "Valeur numérique" : Si, par exemple, au début du tour "Hocus Pocus" tu as choisi les nombres $a=71$ et $b=83$, alors la valeur numérique de $a$ et $b$ dans la suite du texte sera respectivement $71$ et $83$.
    "L'intervalle des réels" $[m,n]$, c'est l'ensemble des nombres réels compris entre deux valeurs réelles $m$ et $n$ appartenant elles-mêmes à l'ensemble.
    J'ai du mal à croire que tu ne comprennes pas.

    Enfin, pour ce qui est du choix de $a,b,c$, je pensais avoir été suffisamment claire au point $\fbox{V}$ du message initial, Remarque 2.
    Si tu choisis trois nombres $a,b,c$ tels que je les définis là, tu auras $p$ et $q$ tels que je les souhaite.
    Là aussi, j'ai du mal à croire que tu le contestes.
    Mais, prudence !
    Je t'écoute.
  • $\def\lr{\leftrightarrow}$Nogdim
    J'ai vu ton post. Il a fallu que je fasse un (petit) effort pour comprendre. Par exemple, en ce qui concerne la dernière phrase ``Le commun est $(5,1)$, on choisit $(5, 1+1)$'', je ne trouve pas que cela soit limpide-limpide. Mais j'ai compris quand même (via les mots de Stern-Brocot).

    Je vais me permettre de réécrire certaines choses de manière numérico-symbolique afin de me faciliter la tâche si jamais un jour je relis cela (?). J'ai changé tes notations car ton $k$ ne correspond pas au $k$ dont parle Sneg depuis le début du fil.

    Contexte : $a, b$ des entiers $\ge 2$ premiers entre eux, $c$ un entier $\ge 1$. Objectif : détermination du plus petit $k \ge 1$ tel que $kc \in \N a + \N b$ ainsi qu'une écriture (non unique si on ne normalise pas) $kc = Ua + Vb$ avec $U,V$ entiers $\ge 0$.

    $\bullet$ D'abord, de nouveau, les affaires de Rosales and co (j'ai fourni des références dans d'autres posts et j'en redonne une ici). Soient $u,v \ge 1$ tels que $\fbox{$ub - va = 1$}$. Si $k/d$ est le rationnel $>0$, ancêtre commun du couple $(a/cu, b/cv)$ de rationnels $>0$, alors $k$ est le plus petit entier $\ge 1$ tel que $kc \in \N a + \N b$. Et on a :
    $$
    kc = Ua + Vb \qquad U = -kcv + db \ge 0, \qquad V = kcu - da \ge 0
    $$Ancêtre commun est à prendre au sens de l'arbre de Stern-Brocot.

    $\bullet$ Tes affaires dans le cas $a = 71$, $b = 83$, $c = 97$. Tu écris avec des entiers $\alpha, \beta \ge 0$
    $$
    \fbox {$c = -\alpha a + \beta b$}, \qquad \alpha = 15, \quad \beta = 14
    $$puis tu détermines le développement en fractions continues (je mets l'équivalent en mots de Stern-Brocot) :
    $$
    {b \over \alpha} = {83 \over 15} \lr (5, 1, 1, 7) = (q_1, q_2, q_3, q_4) =_{\rm def} q_1 + {1 \over q_2 + {1 \over {q_3 + {1 \over q_4}}}} \lr
    D^{q_1} G^{q_2} D^{q_3} G^{q_4 -1} =_{\rm ici} D^5GDG^6
    $$Et
    $$
    {a \over \beta} = {71 \over 14} \lr (5, 14) = (q'_1, q'_2) =_{\rm def} q'_1 + {1 \over q'_2} \lr
    D^{q'_1} G^{q'_2-1} =_{\rm ici} D^5G^{13}
    $$Le préfixe commun (gauche) des deux mots en $D,G$ vi-dessus est $D^5 G^1 \lr 5 + {1 \over 1 + 1} = {11 \over 2}$. Ce $11 \over 2$ est l'ancêtre commun du couple $(a/\beta, b/\alpha)$. Ici, on a donc $k = 11$, $d = 2$ et
    $$
    kc = (-k\alpha + db) a + (k\beta -da)b, \qquad \text{i.e. ici} \qquad 11 \times 97 = 1 \times 71 + 12 \times 83
    $$Note 1 : j'ai utilisé la correspondance entre mots de Stern-Brocot et réduites, cf l'attachement qui vient de mon brouillon. Attention au dernier terme de la réduite et à l'exposant du dernier symbole du mot. Il y a une différence d'une unité et j'ai essayé de le montrer en rouge.

    Note 2 : une référence (parmi d'autres, hormis mes propres affaires) pour le calcul de l'ancêtre commun. M. BULLEJOS AND J. C. ROSALES, PROPORTIONALLY MODULAR DIOPHANTINE INEQUALITIES AND THE STERN-BROCOT TREE (section 5) in http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=E82755517AE98CA83E5F5D0B3B13F1D3?doi=10.1.1.145.9528&rep=rep1&type=pdf

    Note 3 : il y a une forte analogie entre les deux méthodes : $cv$ versus $\alpha$, $cu$ versus $\beta$ . Mais les objets intervenant chez nogdim sont bien plus petits. Cela vient du fait que l'on part d'une écriture $c = -\alpha a + \beta b$ et non pas de l'écriture $1 = ub - va$ multipliée par $c$. Je me comprends.

    Bref, bravo pour nogdim.

    Sneg,

    Pour l'instant, je ne t'ai pas répondu comme tu vois. Je ne sais pas si je le ferais. Pour au moins deux raisons. La première : cela me demande beaucoup trop de temps, cf par exemple la réponse à nogdim.

    La deuxième raison est que nous n'avons pas les mêmes objectifs. De mon côté, j'ai besoin de preuves, de justifications ...etc... y compris pour les algorithmes. Je n'ai certes fourni aucune justification de mes dires mais j'ai fourni des références très précises. Où sont vos justifications ? Certes, tu ne souhaitais pas en fournir ``car tu voulais faire un tout de magie'' ou quelque chose comme cela.

    Et je ne sais pas si lire/consulter les mathématiques des autres vous intéresse vraiment. C'est souvent compliqué mais de mon côté ``je me sens obligé'' de le faire. Certes, c'est mon problème.

    Je ne suis même pas persuadé que ce post vous concerne vraiment et ``vous soit utile'' (rappel : en égoïste que je suis, je l'ai écrit pour mézigue).

    Juste une petite chose. Tu devrais éviter ce genre de phrase ``Pardon, si tu trouves que je n'ai aucune ambition mathématique'' qui n'a rien à voir avec la choucroute. Ai je mentionné quoi que ce soit qui ressemble à cela ?

    PS : hier, j'ai attaché un pdf mais je me suis trompé en attachant tout mon BROUILLON ! Je voulais juste attacher la dernière page avec l'arbre de Stern-Brocot. Surtout, ne pas essayer de lire ce brouillon qui m'est destiné (c'est marqué au début : assemblage de notes hétéroclites ayant servi ....etc..). Vous pouvez cependant jeter un oeil pour voir ce qu'est un algorithme accompagné d'une preuve.

    Bref, je te répondrais peut-être mais plus tard (je n'ose pas te dire combien de temps il me faut pour étudier le plus soigneusement vos méthodes, confronter les points de vue ... composer un post ...etc.. ).115678
  • $\def\Z{\mathbb Z}\def\Q{\mathbb Q}\def\R{\mathbb R}$Sneg (suite)

    Je viens de lire une partie de ta réponse. J'en attache un extrait (premier attachement). Sincèrement, je pense que ce type de réponse de ta part est à éviter si tu souhaites échanger.

    Ce morceau de réponse pourrait donner l'impression que tu expliques au blaireau que je suis ce qu'est un intervalle de $\R$. Or, il se trouve que je connais 2 ou 3 petites choses de base en mathématiques, en particulier ce qu'est un intervalle de $\R$.

    Je ne suis pas persuadé que tu saches ce qu'est le calcul flottant en machine (ce que j'ai cité en te précisant que je n'utilisais pas). Peut-être que tu aurais pu te dire ``je ne sais pas ce que c'est et je m'abstiens'', non ?

    Dans notre histoire, on ne sort pas du corps $\Q$ des rationnels. Quant à écriture décimale, qui n'a pas à intervenir ici, on peut en reparler quand tu veux.

    Comme je m'intéresse au calcul, et pas seulement au calcul en algèbre, il m'arrive d'utiliser des ``réels en machine''. C'est important d'essayer d'en comprendre la sémantique. C'est peut-être ton cas : j'en attache une page (sur 40 pages) du manuel d'un système évolué. Une fois que tu auras lu ces 40 pages ainsi que le chapitre consacré à l'implémentation de $\Z$ puis celui consacré à l'implémentation de $\Q$, peut-être que l'on pourra commencer à en discuter. Après mais pas avant.115694
    115696
  • @ claude quitté.
    D’où vient cette interdiction de sortir du corps $\mathbb{Q}$ des rationnels, face à un problème d’arithmétique ??
    Mais cette question n’appelle pas de réponse, car il y a bien pire. J’ai l’impression que l’atmosphère s’est subitement rafraîchie.
    Dans ces conditions, mieux vaut sans plus tarder mettre fin à l’échange.
    Snégourotchka.
  • Ce que j'aime dans les échanges entre Sneg et claude quitté ce n'est pas tant le fond mais la forme.

    Le lecteur peut être quasiment certains qu'au bout d'un moment ça va péter... et tout le plaisir est d'essayer de reconnaître la petite phrase qui va tout faire basculer (:D

    Force est de constater que cette fois la tâche était ardue. En remontant les messages on arrive à pointer du doigts cette "malheureuse" phrase de claude quitté : "Ce qui est curieux dans tes posts, c'est l'alternance de faits précis rédigés avec le plus grand soin et de choses floues (voir plus loin)."

    La flatterie qui suit n'aura quasiment aucun effet : "J'ai donc envie de dire ``bravo''. Et je le dis : BRAVO. ". (:D

    Les questions rhétoriques de Sneg montrent que oui nous y sommes, c'est bien le point de non retour :

    - ""L'écriture décimale" (d'un quotient) t'est inconnue ?",
    - "L'intervalle des réels $[m,n]$" , c'est l'ensemble des nombres réels compris entre deux valeurs réelles $m$ et $n$ appartenant elles-mêmes à l'ensemble. J'ai du mal à croire que tu ne comprennes pas."

    Juste pour rigoler encore un coup je ferais remarquer à Sneg que le claude quitté à qui elle s'adresse est probablement le même qui a coécrit : Modules sur les anneaux commutatifs, Algèbre commutative : Méthodes constructives. (:D

    claude quitté un peu vexé (c'est compréhensible) renvoie Sneg à la lecture d'une quarantaine de pages sur l'implémentation des nombres. Cette dernière ayant l’impression que l’atmosphère s’est subitement rafraîchie préfère clore la discussion.

    Et voilà que notre histoire se termine. Il faudra probablement attendre plusieurs semaines avant le prochain échange... soyons patient. B-)-
  • Je suis plus optimiste sur cette relation, elle ne finira pas de si tôt, le fond de la discussion étant un lien solide !

    @Claude Quitté: merci pour tes remarques, et pour l'effort que tu as fait pour la réécriture de mon texte, ce n'était pas simple.

    @ Sneg: je commence à comprendre ton idée de réutiliser le " k " pour calculer le Frobenius. Bien sûr, je reste dans mon raisonnement vectoriel, et c'est précisément avec ces valeurs : (x1,y1) tel que ax1+by1 = 0 [c] et (x2,y2) tel que ax2 + by2 = k c, k min que je peux construire le "parallélogramme" qui encadre le Frobénius. C'est plus simple que ma propre méthode que j'ai du mal à relire.....
  • Coucou me revoilà.

    $\bullet$ nogdim. Tiens je vais te raconter ce que j'ai fait concernant tes affaires, cela va me détendre. Je dis toute la vérité. J'ai commencé Dimanche soir et quand j'ai vu que tu commençais par ``$k$ peut être trouvé par une voie directe'' et que tu me refourguais le même post (sans changer $j$ et $k$), je me suis dit ``Toi mon gars, tu vas t'en prendre une''.

    Puis j'ai vu l'ajout d'une précision, le mot ``fractions continues'', j'ai reconnu Stern-Brocot. Bref c'était bon. Vachement bon, même. C'est quelque chose que tu as dans tes notes personnelles, petit cachotier ?

    Je m'y suis recollé Lundi matin en faisant des tests plus systématiques (pour étudier la complexité), j'ai relu Bullejos & Rosales in
    http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=0FAC86ABA46AD8E26970E1634B07B7F1?doi=10.1.1.145.9528&rep=rep1&type=pdf qui en parle (de la complexité). J'ai revisité mes affaires, mis des choses à jour. Bref les choses de la vie. Ce qui a donné cela (le Lundi matin).
    [color=#000000]hilbert> ls -lt *
    -rw------- 1 quitte maths 1373 Jan 11 10:38 CommonAncestor.magma
    -rw------- 1 quitte maths 1320 Jan 11 10:24 nodgim.result
    -rw------- 1 quitte maths 1053 Jan 11 10:23 nodgim.magma
    -rw------- 1 quitte maths 2762 Jan 11 08:29 QuotientFromRosalesTools.magma
    -rw-r--r-- 1 quitte maths 6249 Jan 11 08:26 3SemiGroupTools.magma
    -rw------- 1 quitte maths 1393 Jan 11 06:38 QuotientFromRosales.magma
    -rw------- 1 quitte maths 1274 Jan  8 13:37 SnegHocusPocus.magma
    -rw------- 1 quitte maths  515 Jan  6 13:45 SnegHocusPocus.result
    -rw-r--r-- 1 quitte maths 4174 Jan  4 15:00 SternBrocot.magma
    [/color]
    
    Et l'après-midi, j'ai composé mon post pour toi. Comme je tape comme un gendarme, cela m'a pris du temps.

    Le tout dans le tout, au bout de 4-5 heures, en ce qui te concerne, c'était plié.
    Quant à Sneg, depuis le début, l'étude m'a demandé une petite dizaine d'heures.

    Je vais essayer d'envisager de renouer le dialogue avec elle en ce qui concerne les SPECIFICATIONS. J'attache pour la $n$-i!ème fois, le projet de la balançoire. Pour deux raisons : la première, c'est pour appuyer le fait que lorsque les choses sont mal spécifiées, cela peut partir en .ouille gros mot. Et la deuxième raison, c'est pour montrer l'incompréhension qui peut débarquer dans ce bas monde, y compris sur le forum.

    A j'oubliais. Avant la tempête, puisque tout marchait comme sur des roulettes et que j'étais vraiment épaté (ce n'est pas de la flatterie contrairement à ce qu'a écrit Lourran), épaté d'une part par ton truc efficace (par rapport à mon machin pourri) et d'autre part par le fait que Sneg retrouvait exactement la formule du nombre de Frobenius de $a\N + b\N + c\N$ (dans le contexte que l'on sait), j'avais préparé un petit truc. Un petit truc pour fêter cela ensemble en début d'année 2021.

    Ce petit truc, c'est le second attachement. Je sais c'est petit. Loin de faire péter le champagne ou un truc comme cela.

    Mais ça, c'était avant la tempête pas prévue par la météo. Mais j'ai confiance, le gros est passé, je crois que cela va s'arranger.

    $\bullet$ Lourran. Je suis également le co-auteur d'un livre qui a fait un bide ``Algorithmique algébrique''. Gros bide : c'est essentiellement un livre de maths mais l'éditeur (dont je tais le nom pudiquement) avait conseillé de le ranger chez les libraires, au rayon informatique, vers les logiciels. Entre Windows et Excel.115760
    115764
  • Bonsoir Claude,

    > Je suis également le co-auteur d'un livre qui a fait un bide ``Algorithmique algébrique''

    Il n'est pas donné chez Amazon !!...

    Cordialement,

    Rescassol
Connectez-vous ou Inscrivez-vous pour répondre.