Sur une suite de fractions

[nodjim]

Bonjour à tous.
Soit la suite de fractions définie comme ci-après:
0/1 et 1/1 sont les données de départ.
f1 se positionne entre les 2 valeurs de départ et sa valeur est (= somme des numérateurs/somme des dénominateurs) des encadrants=(0+1)/(1+1)=1/2
La série s'écrit alors: 0/1, f1, 1/1.
f2 s'intercale entre 0/1 et f1, f3 entre f1 et 1/1 et se calcule comme f1, soit:
0,f2,f1,f3,1 qui donne les fractions: 0;1/3;1/2;2/3;1.
f4 à f7 se positionnent donc ainsi:0,f4,f2,f5,f1,f6,f3,f7,1.
etc...
On devine que f2^n est le premier à gauche et f(2^(n+1)-1) le dernier à droite.
La question est la suivante:
Que vaut la fraction qui précède 233/377 ?
Bon amusement

[carzou]

Ta question est elle : si f(n)=233/377, que vaut f(n-1) ?

[nodjim]

Oui, c'est bien ça.

[carzou]

Lorsqu'une fraction est simplifiable, est ce qu'on la réduit ou pas ?

[Doraki]

Une fraction obtenue par ce procédé est toujours réduite.

[nodjim]

J'ajoûte, pour ne pas pénaliser ceux qui l'ignorent, que les 2 termes 233 et 377 sont 2 nombres consécutifs de la suite de Fibonacci.

[Ben314]

D'un autre coté, vu les valeurs numériques données, on peut aussi faire une espèce de "bête dichotomie" qui s'avère (miraculeusement !!!) donner le résultat...

[Doraki]

c'est pas du tout miraculeux.
Par contre ça permet pas vraiment de généraliser à la même question en remplaçant 233/377 par Fn/Fn+1

[Ben314]

Je suis tout à fait d'accord sur le fait que au fond, ce n'est pas miraculeux, mais tel qu'il est, on peut résoudre le casse tête en écrivant :
Si x=233/377 alors
x est compris entre f1=1/2 et f0=1/1 -> "milieu" f3=2/3
x est compris entre f1=1/2 et f3=2/3 -> "milieu" f6=3/5
x est compris entre f6=3/5 et f3=2/3 -> "milieu" f13=5/8
etc.
et, vu le nombre d'étapes, on peut "tout faire à la main", i.e. sans même s'apercevoir que les nombres que l'on a sont ceux de la suite de fibonnacci.

Cette façon de résoudre le problème a quelque chose de "miraculeux" dans le sens qu'on peut faire la même chose avec n'importe quelle fraction x comprise entre 0 et 1mais qu'il n'y a ici pas le début de la moitié d'une preuve que l'on finira par atteindre x en un nombre fini d'étabes !!!!

D'ailleurs, atteint-on toute fraction x entre 0 et 1 ?
Si non, lesquelles atteint-on ?

[nodjim]

c'est pas du tout miraculeux.
Par contre ça permet pas vraiment de généraliser à la même question en remplaçant 233/377 par Fn/Fn+1

La question que je pose peut se rapporter aussi à 377/610. Ou n'importe quel autre couple de Fibonacci. Mais pas seulement ces valeurs là. Disons que les caractéristiques de la suite Fibo se prêtent bien pour la résolution du problème.

[nodjim]

D'un autre coté, vu les valeurs numériques données, on peut aussi faire une espèce de "bête dichotomie" qui s'avère (miraculeusement !!!) donner le résultat...

Oui, on peut faire par dichotomie, mais si je pose la question pour F30/F31 ?

[Ben314]

Oui, on peut faire par dichotomie, mais si je pose la question pour F30/F31 ?

Evidement, plus tu fait "grandir" la taille des nombres, plus on sent que la méthode "bourrin" que je propose au dessus n'est pas la bonne (mais je trouve que c'est un peu "pas beau" qu'une telle méthode existe)

Je t'avoue que la question "tout les x sont ils atteints ?" m'amuse plus (m'enfin, les gouts et les couleurs....)

[nodjim]

Je t'avoue que la question "tout les x sont ils atteints ?" m'amuse plus (m'enfin, les gouts et les couleurs....)

Je crois pouvoir te dire que oui, mais c'est une autre histoire. En fait, ici, j'ai décrit la suite de Farey, dont on a une bonne description sur Wikipédia (je n'ai regardé ça qu'aujourd'hui), mais ça n'aide pas beaucoup pour le problème que j'ai posé, mais pour le tien oui.

[Doraki]

La question que je pose peut se rapporter aussi à 377/610. Ou n'importe quel autre couple de Fibonacci. Mais pas seulement ces valeurs là. Disons que les caractéristiques de la suite Fibo se prêtent bien pour la résolution du problème.

Ben ma formule dépend de la parité de n dans Fn/Fn+1 et marche seulement parceque c'est du fibonacci.
Si on veut un truc vraiment général, j'pense que l'idée d'algo de Ben, qui se fait en O(log(dénominateur)) opérations est acceptable...

[nodjim]

La question de Ben m'a fait avancer un peu sur le sujet. Je crois pouvoir dire maintenant qu'a partir de n'importe quelle fraction, la énième de la suite, on peut trouver la énième-1 ou énième +1.

[Ben314]

Je pense aussi avoir la réponse :
Toutes les fractions a/b (irréductibles) entre 0 et 1 sont dans le tableau et une fois trouvé u et v tels que au-bv=1 (par exemple avec l'algo. d'euclide) on peut déterminer :
1) Par quelle "somme" a été fabriqué a/b (donc qui est avant et aprés a/b sur la première ligne où il apparait)
2) Si a/b=fn qui esr f(n-1)

Par contre, je n'ai pas regardé si on peut trouver le n tel que a/b=fn façilement.

P.S. Je trouve ça amusant de constater que l'algo que j'ai proposé ci dessus est en fait un "ersatz" d'algo d'euclide mais fait "à l'envers" (c'est à dire en faisant augmenter les valeurs plutôt que de les diminuer) pour trouver u,v tels que au+bv=1 (ou =pgcd(a,b) s'ils ne sont pas premiers entre eux)...

[nodjim]

C'est bien ça pour cette partie du problème! Reste la partie d'identification de f(n). Ce n'est pas plus difficile que de résoudre la 1ère partie, il faut juste travailler sur la position du n.

[benekire2]

P.S. Je trouve ça amusant de constater que l'algo que j'ai proposé ci dessus est en fait un "ersatz" d'algo d'euclide mais fait "à l'envers" (c'est à dire en faisant augmenter les valeurs plutôt que de les diminuer) pour trouver u,v tels que au+bv=1 (ou =pgcd(a,b) s'ils ne sont pas premiers entre eux)...

Ben justement cet algo, on l'utilise souvent en arithmétique je crois, notamment pour trouver ces fameux u et v dans au+bv=k PGCD(a,b) pour avoir une solution particulière de ax+by=c ;

[Ben314]

C'est bien ça pour cette partie du problème! Reste la partie d'identification de f(n). Ce n'est pas plus difficile que de résoudre la 1ère partie, il faut juste travailler sur la position du n.

J'ai pas trop bien compris (encore .....) l'objectif de la suite de l'énigme...
Qu'entend tu par "identification de f(n)" ?
Tu veut une formule "rapide" qui donne f(n) en fonction de n ?
Le seul truc que j'ai, c'est que, si n=2^p+r où r<2^p alors f(n)=Ar/(Ar.p+Br) où Ar et Br ne dépendent que de r...

Sinon, s'il y en as que ça interesse, je me suis posé la question suivante :
Si on écrit les lignes succéssives :
Ligne 1 : 0/1 1/2 1/1
Ligne 2 : 0/1 1/3 1/2 2/3 1/1
Ligne 3 : 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1
...etc
puis que, pour un réel t et un entier n donné on note fn(t) le "pourcentage" (entre 0 et 1) de fractions de la n-ième ligne qui sont inférieurs à t.

Questions :
1) La suite de fonctions fn est elle convergente vers une fonction f ?
uniformément convergente vers f ?
2) f est-elle continue partout ? en certains points ?
3) Est elle dérivable partout ? en certains points ? que vaut la dérivée ?

P.S. J'ai pas fini de répondre à toute les questions (vous en déduisez quoi ?)...

@benekire2 : pour moi, l'algo de détermination (pour a,b fixés) de u,v tels que au+bv=pgcd(a,b) c'est l'algo d'euclide avec un "suivi" permettant d'exprimer tout les termes calculés en fonction de a et b.
Je ne pense pas que ça corresponde exactement à l'algo. ci dessus qui procède par encadrement succéssifs de la fraction a/b.
Il faudrait écrire les deux algo sur un petit exemple (a=174, b=102 par exemple) pour voir si les calculs intermédiaires sont semblables.

[nodjim]

J'ai pas trop bien compris (encore .....) l'objectif de la suite de l'énigme...

Pour l'instant, juste la réponse à la question initiale.

Sinon, s'il y en as que ça interesse, je me suis posé la question suivante :
Si on écrit les lignes succéssives :
Ligne 1 : 0/1 1/2 1/1
Ligne 2 : 0/1 1/3 1/2 2/3 1/1
Ligne 3 : 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1
...etc
puis que, pour un réel t et un entier n donné on note fn(t) le "pourcentage" (entre 0 et 1) de fractions de la n-ième ligne qui sont inférieurs à t.

Questions :
1) La suite de fonctions fn est elle convergente vers une fonction f ?
uniformément convergente vers f ?

Hum, ça converge vers...t (si t est compris entre 0 et 1) ou alors je n'ai pas compris la question.