Plus petite fraction

[masmoudi]

Bonjour
je veux savoir si c'est possible de calculer, à partir d'un intervalle I appartenant à [0,1[, une fraction p/q appartenant à I avec p+q soit le plus petit possible

j'utilise la méthode des fractions continues mais elle ne permet pas de calculer toujours la bonne fraction

[Quidam]

Bonjour
je veux savoir si c'est possible de calculer, à partir d'un intervalle I appartenant à [0,1[, une fraction p/q appartenant à I avec p+q soit le plus petit possible

j'utilise la méthode des fractions continues mais elle ne permet pas de calculer toujours la bonne fraction

Il me semble que pour trouver une fraction comprise entre a et b (a<b) il suffit d'effectuer le développement en fraction continue de a et celui de b et de s'arrêter dès que les deux fractions obtenues diffèrent : alors l'une des deux fractions est forcément comprise entre a et b. Mais j'ai oublié la démonstration...

[masmoudi]

je sais que la fraction continue permet d'approximer un nombre rationnel par une fraction sous la forme p/q.
mais je veux savoir s'il existe une autre fraction p1/q1 tel que p1+q1car mon problème est de chercher p et q tel que p+q soit le plus petit possible ou bien le min

[Quidam]

je sais que la fraction continue permet d'approximer un nombre rationnel par une fraction sous la forme p/q.
mais je veux savoir s'il existe une autre fraction p1/q1 tel que p1+q1<p+q
car mon problème est de chercher p et q tel que p+q soit le plus petit possible ou bien le min

Je sais que tu sais ! J'ai bien compris ton problème...
Mais je ne peux pas en dire davantage ! Peut-être quelqu'un d'autre...

[emdro]

Bonjour,

cherches-tu une formule, ou bien une méthode?

Dans ce dernier cas, tu peux partir de l'idée simple qu'en posant , tu es certain d'avoir une fraction de dénominateur N+1 entre a et b.

En posant k/(N+1) la plus petite d'entre-elles, il te reste à regarder toutes les fractions de dénominateur inférieur à k+N+1 comprises entre a et b...

[emdro]

Je ne sais pas si cela peut te servir, mais pense que:
si alors et donc .

Comme je t'ai déjà trouvé un majorant M de p+q, il te reste à regarder les dénominateurs q inférieurs à

[emdro]

Bonjour,

j'ai repensé à ton problème.
Il se trouve qu'en cherchant une fraction p/q dans un intervalle ]a,b[ c [0,1],cela revient au même de chercher à minimiser q ou bien p+q.

En effet, si on suppose que p/q est une fraction de dénomintateur minimum dans ]a,b[ et u/v est une fraction de ]a,b[ minimisant la somme u+v, alors:
et .

On peut alors démontrer de manière élémentaire que:
a)
b)
c)

La fraction u/q est donc encore dans l'intervalle ]a,b[, et comme
(puisque u+v est le minimum), cela implique que et donc que v=q (puisque q est le dénominateur minimum).

Ainsi la fraction minimisant (num+den) est parmi celles qui minimisent (dén) celle qui a le plus petit (num).

Elle est alors très facile à trouver par algorithme:
puisque ,
il suffit de partir de q=2.
On cherche un entier p (le plus petit possible) qui vérifie . On prend donc p=E(aq)+1, et il reste à vérifier que p<bq.
Si c'est le cas, la fraction p/q est celle qu'on cherche, sinon, on ajoute 1 à q et on recommence.

[leon1789]

Trouver avec q (ou p+q) minimal, et a,b fixés, ça me fait penser à l'arbre de Stern-Brocot. Mais je ne me souviens plus du truc...

[Quidam]

On peut alors démontrer de manière élémentaire que:
a)
b)
c)

Ben,...comment fais-tu ? Je ne vois pas...

[emdro]

Bonjour Quidam,


a)

puisque q est le dénominateur minimum donc
et comme puisque u+v est le minimum, en multipliant,
soit encore


b)


Or .
D'où et enfin

c)
Comme alors,
Comme , alors .

[Quidam]

Merci emdro !

[emdro]

Eh bien, je vais fêter cela! Ce n'est pas tous les jours que je pourrai éclairer ta lanterne... :we:

[Quidam]

Eh bien, je vais fêter cela! Ce n'est pas tous les jours que je pourrai éclairer ta lanterne... :we:

Ravi de t'avoir rempli de joie. Tu peux festoyer à ma santé ! :ptdr: