le pgcd sans algorithme

chamath

Bonjour à tous
une formule donnée par le mathématicien Marcelo Polezzi en 1997
exprime le pgcd de deux entiers m et n par l'expression
$\displaystyle PGCD\ (m,n)\ =\ m\ +\ n\ -\ m.n\ +\ 2.\sum_{i=1}^{m-1} \begin {bmatrix} \displaystyle \frac {i.n}{m} \end {bmatrix}$
où la notation [r] désigne la partie entière de r

afin d'éviter d'utiliser le très efficace algorithme d'Euclide et suite à des recherches sur le net (en tapant Polezzi sur google) et n'ayant strictement rien trouvé à ce sujet là (c'est à dire s'éviter d'utiliser cet algorithme pourtant très efficace):
je propose ici de donner en plusieurs fois les expressions possibles pour toute sommation

$\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix} $

sinon à part ça les deux avantages de l'algorithme d'Euclide est qu'il est rapide et de plus permet de déterminer les coefficients de Bachet-Bézout

je commence par les 6 premiers résultats (il y en a encore d'autres mais je fais ce fil en plusieurs fois ) et sans les démontrations car elles sont trop longues bien que cependant elles sont du niveau de la troisième environ

1)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ 0 $
dans l'un de ces trois cas là:
*lorsque $\ n\ =\ 1\ $ et $\ m> \ l$
*lorsque $\ 0\ <\ n\ <\ m\ $ et $\ m\ -\ n.\begin {bmatrix} \displaystyle \frac {m}{n} \end {bmatrix}\ =\ 0\ $ et $\ \displaystyle \frac {m}{n} \ >\ l \ $
*lorsque $\ 0\ <\ n\ <\ m\ $ et $\ m\ -\ n.\begin {bmatrix} \displaystyle \frac {m}{n} \end {bmatrix}\ >\ 0\ $ et $\ \begin {bmatrix} \displaystyle \frac {m}{n} \end {bmatrix}\ +\ 1\ >\ l$

2)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ 1 $
*lorsque $\ 0\ <\ n\ <\ m\ $ et $\ m\ -\ n.\begin {bmatrix} \displaystyle \frac {m}{n} \end {bmatrix}\ >\ 0\ $ et $\ \begin {bmatrix} \displaystyle \frac {m}{n} \end {bmatrix}\ +\ 1\ =\ l$

3)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ \begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}.\frac {l^2+l}{2}$
on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}$
dans l'un de ces trois cas là:
*lorsque $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ =\ 0\ $
*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ =\ 0\ $ et $\ \displaystyle \frac {m}{r} \ >\ l \ $
*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $ et $\ \begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ +\ 1\ >\ l$

4)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}.\frac {l^2+l}{2}$
on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}$
*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $ et $\ \begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ +\ 1\ =\ l$

5)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ v\ +\ v.l\ -\ \frac {m}{n}.\frac {v^2+v}{2}$
on pose $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.n}{m}\ -\ 1 \end {bmatrix}$
*lorsque $\ 0\ <\ n\ <\ m\ $ et $\ m\ -\ n.\begin {bmatrix} \displaystyle \frac {m}{n} \end {bmatrix}\ =\ 0\ $ et $\ \displaystyle \frac {m}{n} \ \leq \ l $

6)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ v\ +\ v.l\ +\ \begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}.\frac {l^2+l}{2} -\ \frac {m}{r}.\frac {v^2+v}{2}$
on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ $ et $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.r}{m}\ -\ 1 \end {bmatrix}$
*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ =\ 0\ $ et $\ \displaystyle \frac {m}{r} \ \leq \ l $

chamath

le cas suivant avant de stopper aujourd'huit

7)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ -\ \frac {u_0.r}{2.m}.(u_0\ -\ 1)\ +\ \frac {r}{2.m}.(u_0\ -\ l\ -\ 1).(l\ +\ u_0)\ +\ l\ -\ u_0\ +\ 1$
on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ $ et $\ u_0\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {m}{r}\ \end {bmatrix}\ $ et $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.r}{m} \end {bmatrix}$
*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $ et $\ u_0\ <\ l\ $ et $\ v\ =\ 2\ $

kolotoko0

Bonjour,

on obtient rien sans rien

bien cordialement

kolotoko

chamath

bonjour kolotoko
dans le même temps la formulation de Marcelo Polezzi je l'ai obtenu "sans rien en fait"
le prix d'un bouquin lambda
mais quand on songe que ces gens là (Euclide et Euler et ...) on en parlera dans 1 000 000 000 d'années franchement ...
[*** modéré ***, hors sujet, sans rapport avec les maths. AD]

chamath

le cas suivant

8)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ -\ \frac {u_0.r}{2.m}.(u_0\ -\ 1)\ +\ \frac {r}{2.m}.(u_1\ -\ l\ -\ 1).(l\ +\ u_1)\ +\ ...$
$...\ +\ 2.(l\ -\ u_1\ +1)\ +\ h_2.\begin {pmatrix} \displaystyle 1\ -\ \frac {r.u_1}{m}\ +\ \frac {r}{2.m}.(1\ +\ h_2) \end {pmatrix} $

*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $ et $\ u_0\ <\ l\ $ et $\ v\ =\ 3\ $

---

on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ $ & $\ u_0\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {m}{r}\ \end {bmatrix}\ $ & $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.r}{m} \end {bmatrix}$ & $\ h_2\ =\ u_1\ -\ u_0$
&
**lorsque $\displaystyle \ 2.m\ -\ r.\begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}\ =\ 0\ $ on pose $u_1\ =\ \begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}$
**lorsque $\displaystyle \ 2.m\ -\ r.\begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}\ >\ 0\ $ on pose $u_1\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}$

chamath

bonne nuit à tous [*** modéré ***, hors sujet, sans rapport avec les maths. AD]

9)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ +\ 3.(l\ -\ u_2\ +\ 1)\ +\ \frac {r}{2.m}.(u_2\ -\ l\ -\ 1).(l\ +\ u_2)\ +\ ...$
$\displaystyle ...\ +\ \frac {r.u_0^2}{2.m}\ +\ \frac {r.t}{2.m}\ -\ \frac {r.t.u_0}{m}\ -\ \frac {r.h_2.h_3}{m}\ -\ \frac {r.h_2^2}{2.m}\ -\ \frac {r.h_3^2}{2.m}\ +\ h_2\ +\ 2.h_3$

*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $
et $\ u_0\ <\ l\ $ et $\ v\ =\ 4\ $

---

on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ $ & $\ u_0\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {m}{r}\ \end {bmatrix}\ $ & $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.r}{m} \end {bmatrix}$
& $\ h_2\ =\ u_1\ -\ u_0\ $ & $\ h_3\ =\ u_2\ -\ u_1\ $
&
**lorsque $\displaystyle \ 2.m\ -\ r.\begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}\ =\ 0\ $ on pose $u_1\ =\ \begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}$
**lorsque $\displaystyle \ 2.m\ -\ r.\begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}\ >\ 0\ $ on pose $u_1\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {2.m}{r} \end {bmatrix}$
&
**lorsque $\displaystyle \ 3.m\ -\ r.\begin {bmatrix} \displaystyle \frac {3.m}{r} \end {bmatrix}\ =\ 0\ $ on pose $u_2\ =\ \begin {bmatrix} \displaystyle \frac {3.m}{r} \end {bmatrix}$
**lorsque $\displaystyle \ 3.m\ -\ r.\begin {bmatrix} \displaystyle \frac {3.m}{r} \end {bmatrix}\ >\ 0\ $ on pose $u_2\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {3.m}{r} \end {bmatrix}$

chamath

j'avance un peu car il en reste pas mal

10)On obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ +\ 4.(l\ -\ u_3\ +\ 1)\ +\ \frac {r}{2.m}.(u_3\ -\ l\ -\ 1).(l\ +\ u_3)\ +\ ...$
$\displaystyle ...\ +\ \frac {r.u_0^2}{2.m}\ +\ \frac {r.u_3}{2.m}\ -\ \frac {r.u_3.u_0}{m}\ -\ \frac {r.h_2.h_4}{m}\ -\ \frac {r.h_2^2}{2.m}\ -\ \frac {r.h_3^2}{2.m}\ -\ \frac {r.h_4^2}{2.m}\ +\ ...$
$\displaystyle ...\ +\ h_2\ +\ 2.h_3\ +\ 3.h_4\ -\ \frac {r.h_2.h_3}{m}\ -\ \frac {r.h_3.h_4}{m}$

*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $
et $\ u_0\ <\ l\ $ et $\ v\ =\ 5\ $

---

on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ $ & $\ u_0\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {m}{r}\ \end {bmatrix}\ $ & $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.r}{m} \end {bmatrix}$
& pour $\ i\ \geq \ 2\ $ alors $\ h_i\ =\ u_{i-1}\ -\ u_{i-2}\ $
& pour $\ i\ \geq \ 1\ $
**lorsque $\displaystyle \ (i+1).m\ -\ r.\begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}\ =\ 0\ $ on pose $u_i\ =\ \begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}$
**lorsque $\displaystyle \ (i+1).m\ -\ r.\begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}\ >\ 0\ $ on pose $u_i\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}$

chamath

on est arrivé jusqu'à $\ v\ = \ 5\ $ à partir de là ça commence à se compliquer un peu
je donne la formulation générale (qui reste valable pour $\ v\ =\ 5\ $)
pour les autres valeurs $\ v \geq \ 6$ afin de mieux visualiser ce que l'on recherche

*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $
et $\ u_0\ <\ l\ $ et $\ v\ \geq \ 6\ $

alors on obtiens après une grosse simplification $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ +\ (l\ -\ u_{v-2}\ +\ 1).(v\ -\ 1)\ -\ \frac {r.l}{2.m}.(l+1)\ +\ \sum_{i=2}^{v-1}h_i.(i-1)$

*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $
et $\ u_0\ <\ l\ $ et $\ v\ \geq \ 5\ $

---

on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ $ & $\ u_0\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {m}{r}\ \end {bmatrix}\ $ & $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.r}{m} \end {bmatrix}$
& pour $\ i\ \geq \ 2\ $ alors $\ h_i\ =\ u_{i-1}\ -\ u_{i-2}\ $
& pour $\ i\ \geq \ 1\ $
**lorsque $\displaystyle \ (i+1).m\ -\ r.\begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}\ =\ 0\ $ on pose $u_i\ =\ \begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}$
**lorsque $\displaystyle \ (i+1).m\ -\ r.\begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}\ >\ 0\ $ on pose $u_i\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}$

chamath

on en arrive là

11)*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $
et $\ u_0\ <\ l\ $ et $\displaystyle 2.m\ -\ r\ -\ 2.r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ =\ 0$
ET $\ v\ \geq \ 5\ $ est impair

alors on obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ +\ (l\ -\ u_{v-2}\ +\ 1).(v\ -\ 1)\ -\ \frac {r.l}{2.m}.(l+1)\ +\ ...$
$\displaystyle ...\ +\ u_0.\begin {pmatrix} \displaystyle \frac {v^2+v}{2}\ -\ 4.v\ +\ 4 \end {pmatrix}\ +\ 2.u_{v-2}\ +\ u_0\ -\ u_1\ -\ \frac {v^2}{4}\ +\ \frac {3.v}{2}\ -\ \frac {9}{4}$

*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $
et $\ u_0\ <\ l\ $ et $\displaystyle 2.m\ -\ r\ -\ 2.r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ =\ 0$
ET $\ v\ \geq \ 6\ $ est pair

alors on obtiens $\displaystyle \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ +\ (l\ -\ u_{v-2}\ +\ 1).(v\ -\ 1)\ -\ \frac {r.l}{2.m}.(l+1)\ +\ ...$
$\displaystyle ...\ +\ u_0.\begin {pmatrix} \displaystyle \frac {v^2+v}{2}\ -\ 4.v\ +\ 4 \end {pmatrix}\ +\ 2.u_{v-2}\ +\ u_0\ -\ u_1\ -\ \frac {v^2}{4}\ +\ 2.v\ -\ 4$

---

on pose $\ r\ =\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ $ & $\ u_0\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {m}{r}\ \end {bmatrix}\ $ & $\ v\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {l.r}{m} \end {bmatrix}$
& pour $\ i\ \geq \ 1\ $
**lorsque $\displaystyle \ (i+1).m\ -\ r.\begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}\ =\ 0\ $ on pose $u_i\ =\ \begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}$
**lorsque $\displaystyle \ (i+1).m\ -\ r.\begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}\ >\ 0\ $ on pose $u_i\ =\ 1\ +\ \begin {bmatrix} \displaystyle \frac {(i+1).m}{r} \end {bmatrix}$



CE QUI RESTE A FAIRE (plus tard)

*lorsque $\ 0\ <\ m\ <\ n\ $ et $\ n\ -\ m.\begin {bmatrix} \displaystyle \frac {n}{m} \end {bmatrix}\ >\ 0\ $ et $\ m\ -\ r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ >\ 0\ $
et $\ u_0\ <\ l\ $ et $\displaystyle 2.m\ -\ r\ -\ 2.r.\begin {bmatrix} \displaystyle \frac {m}{r} \end {bmatrix}\ \neq \ 0\ $ et $\ v\ \geq \ 6$ car $\ v\ =\ 5\ $ est fait en 10)

Alors $\displaystyle \ \sum_{u=1}^{l} \begin {bmatrix} \displaystyle \frac {u.n}{m} \end {bmatrix}\ =\ ...$
$...\ =\ \begin {pmatrix} \displaystyle \begin {bmatrix} \displaystyle \frac {n}{m}\end {bmatrix}\ +\ \frac {r}{m} \end {pmatrix}. \displaystyle \frac {l^2+l}{2}\ +\ (l\ -\ u_{v-2}\ +\ 1).(v\ -\ 1)\ -\ \frac {r.l}{2.m}.(l+1)\ +\ \sum_{i=2}^{v-1}h_i.(i-1)$

chamath

là je dois partir

pour ces 11 cas qui donne la solution du PGCD pour une infinité de couples (m,n) mais non tous

je viens juste de corriger la dernière faute
j'en vois plus...

je reviendrai pour terminer ce fil
Bonne journée à tous

A-dent

Sauf erreur, on la trouve dans :
exos arithmétique

chamath

Merci A-dent Super!!
eh bien là je viens de voir vite fait oui elle est dite là!!!

sinon là je fais une pause et puis je vais re revérifier encore une fois (la chez plus combien) que les 11) sont bons
avant de continuer et terminer le reste

[*** modéré ***, hors sujet, sans rapport avec les maths. AD]

Bonne soirée AMI

isabelle2

chamath j'admire ton courage d'avoir éplucher autant de cas pour la formule de Polezzi.

Aussi permet de t'offrir la preuve de Polezzi la géométrie a son importance.

JLT

Je viens de cacher quelques messages hors-maths.

chamath

Merci Isabelle!
Bonne soirée
[*** modéré ***, hors sujet, sans rapport avec les maths. AD]

chamath

Bonsoir AD
une motivation maths ou pseudo ne s'explique pas par des maths chez des gens comme moi

je reprendrai ce fil quand je serai vraiment (là tout de suite je suis ailleurs) ce à quoi au fond je rêve mais
aucune motivation formalisable n'est justifiable pour mon rêve
bonne nuit mes amis

aymane.maysae

Bonjour,
Avant tout, j'aimerais vous féliciter pour votre lumineuse idée et les efforts qu'a nécessité sa mise à jour. Ensuite, je viens au but de mon message et qui est comme suit:
En cherchant des indications pour résoudre une série d'exercices proposée sur un autre site, j'ai trouvé votre série qui est presque la jumelle de l'autre sauf qu'elle est plus âgée : un paradoxe, non? . Mon problème n'est pas là, en essayant de résoudre les trois premiers exercices, il m' a paru qu'il y avait des conditions superflues, ce qui m'a poussé a vous écrire pour m'orienter, m'éclairer et me dire s' il y a un document de référence auquel on peut se référer pour comparer les propositions de solutions, sinon et si c'est purement un louable effort personnel, veuillez avoir l'obligeance de lire ma présumée solution de l'exercice 1, et la corriger, le cas échéant. Veuillez la trouver dans le lien ci-joint.

Professeur Rectangle

chamath écrivait: a écrit:

une formule donnée par le mathématicien Marcelo Polezzi en 1997 exprime le pgcd de deux entiers m et n par l'expression $\displaystyle PGCD\ (m,n)\ =\ m\ +\ n\ -\ m.n\ +\ 2.\sum_{i=1}^{m-1} \begin {bmatrix} \displaystyle \frac {i.n}{m} \end {bmatrix}$ où la notation désigne la partie entière de r

Que voulez-vous dire par "sans algorithme" ?
Votre formule contient un $\Sigma$, ce qui, à priori, correspond à une boucle for, donc à un algorithme en complixité $\mathcal{O}(m)$.

A vrai dire, je ne vois pas ce qu'apporte cette formule d'un point de vue algorithmique.