Algorithme en détresse cherche aide en maths
Utilisateur anonyme
-
Utilisateur anonyme -
Utilisateur anonyme -
Bonsoir à tous,
Dans un de mes projets personnels, je me suis trouvé face à un problème d'ordre mathématique, dont je présent qu'il a une réponse mais que je ne suis pas en mesure de déterminer.
Voici une petite explication de la situation et de ce que je recherche :
J'ai une expression E1 composée d'un nombre n, entier naturel assez long (la longueur que je choisirai dépendra du temps que prendra l'algo à trouver la solution, mais je pense à des nombres entre 10^20 et 10^57).
J'aimerai savoir comment je dois m'y prendre pour trouver une expression E2 équivalente, de la forme m^p + a où m, p et a sont des entiers naturels, de sorte que :
* E1 = E2
* L'expression E2 soit aussi courte que possible.
Mon intuition me souffle que la solution peut se trouver du coté des congruences ou encore des factoriels, mais je n'en sais pas beaucoup plus...
Toute aide sera la bienvenue =)
--
S'il n'y a pas de solution, c'est qu'il n'y a pas de problème (sagesse Shadok)
--{[ ~Fedora~ evolve your computing ]}--
Dans un de mes projets personnels, je me suis trouvé face à un problème d'ordre mathématique, dont je présent qu'il a une réponse mais que je ne suis pas en mesure de déterminer.
Voici une petite explication de la situation et de ce que je recherche :
J'ai une expression E1 composée d'un nombre n, entier naturel assez long (la longueur que je choisirai dépendra du temps que prendra l'algo à trouver la solution, mais je pense à des nombres entre 10^20 et 10^57).
J'aimerai savoir comment je dois m'y prendre pour trouver une expression E2 équivalente, de la forme m^p + a où m, p et a sont des entiers naturels, de sorte que :
* E1 = E2
* L'expression E2 soit aussi courte que possible.
Mon intuition me souffle que la solution peut se trouver du coté des congruences ou encore des factoriels, mais je n'en sais pas beaucoup plus...
Toute aide sera la bienvenue =)
--
S'il n'y a pas de solution, c'est qu'il n'y a pas de problème (sagesse Shadok)
--{[ ~Fedora~ evolve your computing ]}--
1 réponse
-
ouah ca m'a l'air d'etre pas mal dur tout ca.
a ta place je ferai 3 boucle for imbriquées les unes dans les autres.
puis je garderai les resultats satisfaisant E1 = E2 dans uen variable res
puis a chaque nouvelle solution je teste la longueur.
(je n'ai aps compris l'histoire de longueur
en gros ça donnerait :
res = ???
for m = 1 to n
___for p = 1 to 58
______for a = 1 to n^(p-1)
_________if m^p+a = n then
____________if res plus long que m^p+a then
____________res = m^p+a
____________endif
_________endif
______end
___end
end
printf res
en fait, en l'écrivant je viens de em rendre comtpe de la longueur que prendrai un tel calcul!
mais bon, c'est deja une base, apres tu peux largement optimiser les limites des boucles for-
Oui, j'avais bien pensé à un truc dans ce genre, mais je ne dispose pas d'un super-calculateur ^^ Et encore, ça ne serait probablement pas suffisant...
A mon avis, une méthode de tâtonnement (explorer toutes les possibilités possibles) ne pourra pas aller parce qu'elle sera super-chronophage...
Je pense qu'une solution doit être possible en se basant sur des notions d'arithmétique modulaire, mais je n'ai pas le niveau mathématique pour manipuler correctement ces notions =(
-
