|
#1 - 05-10-2018 19:12:31
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Somme de fractiosn égyptiennes
Bonjour @ tous
Il s'agit dans ce problème de trouver le plus possible de fractions égyptiennes distinctes strictement supérieures à 1/200 dont la somme est égale à 1.
Pour rappel, une fraction égyptienne est une fraction du type 1 / n, n entier naturel, dont les égyptiens antiques raffolaient, parait-il.
Ce problème est ouvert, j'ai un score établi presqu'à la main, mais il est sans doute loin d'être le meilleur.
A vos machines !
#2 - 05-10-2018 20:12:02
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Somme de fractions éygptiennes
Bonsoir, Je ne suis pas sûr d'avoir bien compris le problème. Sinon, 199 fois la fraction 1/199 semble répondre à la question.
#3 - 06-10-2018 08:13:29
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
sommr de fractions égyptiennes
Pffff.... Même pas eu le temps d'ajouter " distinct " avant la remarque.
#4 - 06-10-2018 09:50:45
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Somme de fractons égyptiennes
Alors là, c'est plus difficile…
#5 - 06-10-2018 19:10:43
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Somme de fratcions égyptiennes
Si je comprends bien l'énoncé, il faut écrire quelque chose comme : 1 = 1/2 + 1/8 + 1/9 + 1/10 + 1/15 + 1/18 + 1/24, sauf qu'au lieu de seulement 7 fractions, il faut le plus grand nombre possible de fractions, distinctes, avec des dénominateurs <200 ?
PS : peux-tu donner ton score et celui des participants, afin qu'on sache contre quoi on se bat ?
#6 - 06-10-2018 20:04:02
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Somme de fractions égptiennes
C'est bien cela, Ebichu.
Enigmatus n'a pas encore donné de résultats.
A titre de renseignement, 1/199 + 1/198 + 1/197.....arrive à 1 avec 126 termes si j'ai bonne mémoire. Bien entendu, cette façon de faire est vouée à l'échec.
Perso, j'arrive à un peu plus de la moitié de ce 126.
L'idée de cette énigme vient d'une question de cours vue sur un site voisin où on demandait de faire la preuve qu'on peut obtenir 1 comme somme d'autant de fractions égyptiennes distinctes qu'on veut, ce qui se prouve facilement.
#7 - 07-10-2018 19:23:27
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Somme de fractions égpytiennes
Voici ma plus longue liste de dénominateurs pour l'instant (10 éléments) :
Sans la limitation à 199, on peut en effet obtenir une liste aussi longue que l'on veut. Par exemple : 1) On part de (2, 3, 6) 2) On obtient une liste de longueur triple en multipliant tous les termes par 2, 3 et 6 (4, 6, 12, 6, 9, 18, 12, 18, 36) 3) Une valeur (n) en double est remplacée par (n+1,n*(n+1)), car 1/n = 1/(n+1) + 1/(n*(n+1)) 4) S'il reste des doubles, retour en 3) 5) Retour en 2)
#8 - 07-10-2018 21:44:42
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
somme de fractionq égyptiennes
Je tente ma chance avec :
23, 28, 33, 36, 39, 40, 44, 45, 48, 51, 52, 55, 57, 58, 60, 62, 64, 65, 68, 69, 70, 72, 75, 76, 77, 78, 80, 81, 84, 85, 87, 88, 90, 91, 92, 93, 96, 99, 100, 102, 104, 105, 108, 110, 112, 114, 115, 116, 117, 119, 120, 126, 130, 132, 133, 135, 136, 138, 140, 143, 144, 145, 147, 150, 152, 153, 154, 155, 156, 160, 161, 162, 165, 168, 171, 174, 175, 176, 195, 196, 182, 180, 184, 189, 190, 192, 198
(87 éléments)
C'est sans doute encore un petit peu optimisable.
#9 - 08-10-2018 08:05:45
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Sommee de fractions égyptiennes
#10 - 08-10-2018 16:05:42
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
somme dz fractions égyptiennes
Je fais un poil mieux avec :
23, 27, 28, 36, 39, 40, 44, 48, 52, 54, 55, 57, 58, 60, 62, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 81, 84, 85, 87, 88, 90, 91, 92, 93, 96, 99, 100, 104, 105, 108, 110, 112, 114, 115, 116, 117, 119, 120, 126, 130, 132, 133, 135, 136, 138, 140, 143, 144, 145, 147, 150, 152, 153, 154, 155, 156, 160, 161, 162, 165, 168, 170, 171, 174, 175, 176, 180, 182, 184, 187, 189, 190, 192, 195, 196, 198
soit 88 éléments. Ça devient vraiment dur de l'améliorer.
Quelques pistes pour faciliter la recherche : * on peut s'abstenir de sélectionner les nombres qui comportent un facteur premier au moins égal à 37, car il ne sera pas possible de faire disparaître ce facteur premier du dénominateur de la somme. * de même, inutile de jouer avec 31, 124 ou 186 (considérer les multiples de 31 pour voir cela). * 121, 169, 125 et 128 peuvent également être oubliés. * on peut ensuite s'intéresser aux multiples des grands nombres premiers. Par exemple, avec 29, on voit que les deux seules façons de faire disparaître 29 au dénominateur sont 1/29+1/116+1/145 ou 1/58+1/87+1/116+1/145+1/174, la deuxième étant la meilleure. * on peut faire la même chose avec les autres grands nombres premiers, en faisant attention aux interférences qui apparaissent quand ces nombres diminuent, comme 1/187 = 1/11+1/17 qui va avoir de l'influence sur les multiples de 11 comme ceux de 17.
En tenant compte de tout ça, ça limite les possibilités.
#11 - 08-10-2018 17:25:41
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Somme de fractions égyptiiennes
OK, mais quel intérêt de faire disparaitre 1/29 en faisant la somme de 3 fractions ? Pour repartir depuis 1/20 et espérer se déployer davantage ?
#12 - 08-10-2018 18:58:32
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
somme fe fractions égyptiennes
Ce que je dis, c'est que dans l'ensemble de nombres dont la somme des inverses vaut 1 que l'on cherche à déterminer, il y a : * soit aucun multiple de 29 * soit uniquement 29 et 116 et 145 * soit uniquement 58 et 87 et 116 et 145 et 174 Ce sont les seules possibilités, car toutes les autres aboutiraient à une somme de la forme a/(29*b) avec 29 ne divisant pas a, donc la somme ne pourrait valoir 1.
Après, c'est à toi de voir lequel de ces 3 choix est le plus pertinent. Ce n'est clairement pas le deuxième, car le troisième aboutirait à la même somme avec deux nombres de plus, donc fournirait un meilleur ensemble. Mais entre le premier et le troisième, cela dépend. Le deuxième coûte 1/20 mais permet de placer 5 nombres ; si tous les nombres choisis étaient aussi coûteux, on aurait à la fin un ensemble de 100 nombres, ce qui est bien. J'ai donc gardé ces 5 nombres dans mon ensemble ; il est toutefois possible qu'un meilleur ensemble ne les utilise pas.
#13 - 09-10-2018 08:11:52
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Somme de fractions égyptienns
#14 - 12-10-2018 17:49:33
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Somme de fractions éggyptiennes
Ce temps là est au fond du seau.
Avec mes seulement 67 nombres, je suis loin du record d'Ebichu avec son 88. Le challenge est ouvert, avis aux amateurs !
Je donne ici mon algo, pour que vous ne le reproduisiez pas.
1) Lister au préalable, pour tout n, toutes les paires (a,b) telles que 1/n = 1/a + 1/b avec a et b distincts. ça se fait facilement en se servant des diviseurs de n² < n.
2) En commençant par 1/2 + 1/3 + 1/6, remplacer la plus grosse fraction par la paire disponible. Si plusieurs choix, choisir celle avec I a - b I minimum.
3) Recommencer en 2)
A la fin, on peut améliorer en choisissant 1 / n = 1 / 2n + 1 / 2n si 1/ 2n libre et 1 / 2n remplaçable par une paire (a,b) libre également.
11 12 15 20 28 35 36 39 40 44 48 52 55 56 60 63 64 65 66 70 75 78 80 81 84 88 90 91 96 99 100 102 104 105 108 110 112 117 119 120 126 130 135 136 143 144 147 150 153 154 156 160 162 168 170 171 175 176 180 182 187 189 190 192 195 196 198
Mots clés des moteurs de recherche
|
|