Factorisation en puissances ?

Posté par -Orny- -Orny-

Bonjour à tous,

En ce moment, dans le cadre de projets perso, je travaille sur pas mal d'algorithmes mathématiques au point que j'en vient à aimer ça :p

J'aimerais savoir quelle est la méthode à suivre pour passer un nombre d'une forme n (avec n un entier naturel long, d'environ 40 digits) à une forme n^p + a (où n, p et a sont des entiers naturels).

N'hésitez pas à demander des détails si j'ai oublié de préciser des choses utiles.
Merci d'avance pour vos idées.

Posté par Aurelien08 Aurelien08

Coucou , déja quel langage utilise tu , ensuite tu veus faire en sorte que ton nombre n devienne n^p +a?

Posté par -Orny- -Orny-

Je travaille principalement en C++, mais l'algorithme étant mathématique, il ne se soucie pas du langage de programmation dans lequel il va être traduit =)

Concernant le problème lui-même, je vais essayer de le reformuler et de le compléter (une fonction d'édition des posts manque cruellement) :


On a une expression E1 composée d'un nombre n, entier naturel assez long (je pense à un maximum de 40 digits en base binaire).
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 naturel), de sorte que :
* E1 = E2
* L'expression E2 soit aussi courte que possible.


Suis-je plus clair ?

Posté par -Orny- -Orny-


--> Cela fait un nombre d'ordre 10¹² en base décimale, si je ne m'abuse (étant donné que le fait que je travaille en binaire n'a aucune influence sur l'algorithme en lui-même)

Posté par Aurelien08 Aurelien08

Effectivement ça na rien à voir ave ton Algorithme ,
Le plus simple c'est de faire un affichage d'écran avec ton nombre de départ placer des 3 variables que la personne changera elle mème après si tu veus je te fasse un code je peus
mais c'est simplement de la l'affichage d'écran et 6 touches pour changer les variables.

Posté par -Orny- -Orny-

Je crois que mon problème a été mal compris...

Cet algorithme prend une expression E1 en entrée, et donne une expression E2 en sortie (je ne parle pas d'utilisateur, parce qu'il ne traitera pas directement avec l'algo).
Les variables m, p et a doivent être déterminées par l'algorithme de façon totalement autonome à partir de E1, afin de sortir l'expression E2 optimale.

Ça me semble être des maths d'assez haut niveau, c'est pour ça que je viens demander sur ce forum

Posté par Aurelien08 Aurelien08

Bah tu devras forcement determiner un p et un a pour ton algo sinon ça marchera pas...

Posté par -Orny- -Orny-

Justement non, le but est de ne pas les fixer arbitrairement.
De même que dans l'énigme de la "bande de motards" (1), il est y a certainement une méthode pour trouver le résultat optimal.
Si j'ai retenu une chose de mes cours d'arithmétique et de cryptographie, c'est bien la puissance des maths pour ce genre de choses

Mon "instinct" me dit que la solution ne doit pas être loin des congruences, mais...


---
(1) : http://www.ilemaths.net/forum-sujet-288572.html

Posté par Aurelien08 Aurelien08

Je comprend pas ton problème , tu veus un algorithme qui transforme ton n en n^p + a par conséquent tu vas obligatoirement donner des valeurs...Sauf si tu met un Math.ramdom

Posté par -Orny- -Orny-



Justement, je n'en suis pas convaincu

Posté par -Orny- -Orny-

En attendant, je vais chercher une solution temporaire avec un dérivé de la forme la forme a[m!]...

Posté par Sai-kun Sai-kun

Bonjour,

Méthode trés moche je sais, mais mon autre idée n'est pas pas nette dans ma tête ... !
Soit x ton nombre entré.
Tu fais ensuite une boucle i de 1 à n (c'est toi qui choisis n, suffisamment grand bien sur) et tu cherches a et b tels que a^i+b=x

Parcours de matrices
a en colonne et b en ligne, a^i+b est la case m,p avec 1<mj et 1<pi

a\b	0	1	...	i
0
1
...
j

Donc ouais, c'est hideux, plein de boucles imbriquées les unes dans les autres et c'est assez nul car tu dois en quelques sorte fixer plusieurs trucs : i,j et n. Ouais suffit de les prendre trés grands mais bon ...

ça m'intéresse ton probléme, je réfléchis à une solution bien plus élégante !

Posté par -Orny- -Orny-

Bonjour Sai-kun,
Merci pour cette idée... un peu bourrinne comme vous le dites

Si je met ça en code, un tableau de cette taille ne passera jamais en RAM


De mon coté, je cherche aussi une méthode plus élégante en replongeant dans mes cours de crypto...

Posté par -Orny- -Orny-

L'arithmétique modulaire semble détenir les clefs de mon problème... avis aux pros ?

Posté par Sai-kun Sai-kun

Salut,

J'ai trouvé un algo plus élégant !!
Je code ça ce soir et te le poste dans la foulée !

_{Il est d'usage sur l'ile de tutoyer}

Posté par Sai-kun Sai-kun

Héééé le probléme de ram peut se régler en découpant le probléme du style A->Z revient à A->B->C...->Z

Plus sérieusement,
J'ai un petit probléme, mon algo n'est pas vraiment optimal (ie il y a plusieurs cas en fait de décompo et mon algo n'a pas forcément le b plus petit) !
Il faut que tu me donnes des infos supplémentaires en fait. Genre a, tu le veux comment ? et b? petit je pense ?

Parce que moi, je pense que ça serait sympa de le prendre premier a (genre si tu veux faire des trucs après avec) ...

Posté par -Orny- -Orny-


C'est noté.

En théorie, dans la forme n^p + a, je cherche à avoir le moins de nombres possible. Par exemple, 14^84 + 3 sera mieux que 7^86 + 157.

En pratique, il faudrait trouver une longueur définie pour n, p et a pour lesquelles on est sûr de trouver une forme n^p+a assez courte.

Posté par Sai-kun Sai-kun

Re!

Je te réponds vite fait car je ne voulais pas partir en vacances et te laisser dans l'attente.

Alors voici l'idée :

On fait une liste Nombres_premiers des p premiers nombres premiers
Soit X le nombre entré par l'utilisateur.
On parcours Nombres_premiers de la façon suivante :
de i=1 à p faire
Tant que X-i^n>0
incrémenter n
X-i^n à rentrer dans une liste A
fin boucle
Rechercher minimum dans la liste A-> on le notera min(A)
lorsque l'on passe à i+1, on ne vas pas tester toutes les valeurs de n, pour gagner du temps , on va juste le commencer à la puissance de min(A), en  effet, il faut que min(A)<i^n<X. On réitére le test
fin boucle


Tiens voici un truc intéressant auquel je viens de penser pour améliorer la vitesse de cet algo.
Détermine combien de chiffres aura un nombre qu'on éléve à la puissance n, du coup, ça limitera les cas.



Voilà, dis moi si c'est pas clair mon idée.

Posté par -Orny- -Orny-

Bonjour Sai-kun !

De mon coté, j'ai mis au point un algo basé sur des nombres premiers et quelques tests (qui ressemble en fait pas mal à celui que tu as fait ^^), et sur le papier tout ça semblait bien beau...

Et puis, je me suis posé LA question : comment je fais pour stocker des variables aussi grandes moi ? Je bosse sur un maximum de 127^127 , soit un ordre de 10^267...
Si les "double" stockent bien cette grandeur (et encore, il y a les "long double" qui stockent bien plus!), est-ce qu'il ont la précision de l'ordre de l'unité, indispensable à mon application ??
... Et là, c'est le drame.

Donc je vais me rabattre sur des "unsigned long int", ce qui va me bloquer à environ 1,84*10^19.
Du coup, je vais travailler avec des m et p entre 0 et 15 --4 bits-- (15^15 étant le plus proche de 10^19 que je puisse atteindre).

Tout ceci fait que l'algo devra calculer moins d'une centaine de possibilités sans optimisation (90 si je ne me trompe pas), donc encore moins une fois optimisé.

D'un point de vue informatique, mon problème semble donc à peu près résolu.
Mais je reste convaincu qu'il existe une jolie formule mathématique pour trouver ça

Posté par Ulusse Ulusse

Je reformule le problème en termes mathématiques, je verrai s'il y a une formule trouvable mais ça me paraît compliqué avec 3 variables entières.

Le problème est le suivant: étant donné n dans N*, on cherche a,b,c dans N^3 tels que:

- a^b + c = n
- log(abc) soit minimal [ceci représente la longueur de ton expression, d'ailleurs il est intéressant de noter que la solution ne dépend pas de la base que tu choisis pour écrire ton nombre]

Mais je vois difficilement comment concilier l'arithmétique modulaire avec ce problème de minimisation, qui passerait probablement par de l'analyse.

Posté par Ulusse Ulusse

Désolé de flooder, mais sinon il y a une parade simple pour stocker tes très grands entiers, en changeant de base. D'ailleurs même, pour des entiers de taille 10^267 tu peux probablement rester en base 10.

Par exemple, si tu passes en base 100, tu divises la longueur de ton tableau par 2 par rapport au décimal.

Pour coder, c'est simple (je connais pas le C++ mais ca doit se faire facile)
Tu utilises une liste qui stocke les digits du chiffre en base b.
Pour les calculs tu peux t'inspirer de la multiplication de polynômes [par exemple avec la FFT], ou par exemple avec l'algorithme de Horner [il y en a bien d'autres] pour calculer vite le nombre [ce qui ne devrait pas être nécessaire cela dit].

Posté par -Orny- -Orny-

Bon, je repasse ici pour dire que j'ai trouvé une autre approche du problème il y a quelques jours qui évite tous les problèmes évoqués dans le topic.

En tout cas, merci pour votre aide !


Et l'ile me plait bien, je pense que je vais cherche un bungalow