|
#1 - 08-11-2017 09:53:15
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3222
- Lieu: Luxembourg
Grand mutliple
Voici un problème (peut-être sans solution) qui m'embête depuis quelques temps. Soient n un entier naturel et p un nombre premier. Dans l’intervalle [1 + 10^n; p + 10^n] il n’y a qu’un seul multiple de p. Existe-t-il une méthode simple pour trouver ce multiple, de la forme: m + 10^n, avec m € [1;p] ? J’ai essayé sans succès avec la méthode dite par unité tronqué ou d’autres critères de divisibilité. Merci de vous tracasser avec moi.
#2 - 08-11-2017 14:51:14
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Grad multiple
Hello
Je saisis mal... Tu fait 10^n modulo p, ça te donne p-m, et donc m
Ensuite, si n est très très grand, en FastPow ça se fait en log(n), et même avec le petit théorème de Fermat en log(p) (pire cas) si p n'est ni 2 ni 5 - à voir quel est le plus rentable
#3 - 08-11-2017 15:54:43
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3222
- Lieu: Luxembourg
Gran dmultiple
@scarta
Par exemple, je cherche le premier multiple de 1303 (qui est premier) immédiatement supérieur à 10^100: comment faire ? Y a t-il une méthode générale ? Je sais que ce nombre est compris (au sens large) entre 1+10^100 et 1303+10^100.
Ou, en d'autres termes, comment évaluer rapidement 10^n modulo p (10^100 modulo 1303 dans l'exemple) ?
#4 - 08-11-2017 21:30:33
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Grnad multiple
Ben, comme je le disais, avec fastpow. Soit sur n, soit sur n mod (p-1), suivant les cas Ça prendra donc ln(100) opération, une méthode en ln(n) c'est plutôt bien en général
#5 - 09-11-2017 07:07:07
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
rand multiple
Bonjour,
python calcule ce résultat (1240) en 0,03 seconde
et celui-ci (838) en moins de 0,5 seconde
#6 - 09-11-2017 12:49:04
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
granf multiple
Tu peux faire encore mieux je pense. Le ** de python implémente FastPow. Le fait de faire puissance suivi de mod, c'est différent et plus long que FastPow modulaire directement. Plus le fait que le petit théorème de Fermat te sauve la plupart des calculs...
J'ai rien pour tester, mais bon si tu peux regarder pour moi combien ça fait : function (n,p) { Si n < p ==> PowMod(10,n,p) Sinon ==> PowMod(10,n%(p-1),p) }
PowMod(base, exp, mod) { Si exp == 0 ==> 1 Base2 = base * base % mod Si (exp & 1) == 0 ==> PowMod(Base2, exp>>1,mod) Sinon ==> base * PowMod(Base2, exp>>1,mod) }
#7 - 09-11-2017 13:02:55
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Grand mulitple
En c#
Très rapide (et pas plus lent que le pire cas : 1302)
#8 - 09-11-2017 13:47:11
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
hrand multiple
@scarta : J'ai programmé en python l'algorithme que tu donnes en #6 (il manque le %mod à la fin de la dernière ligne)
Très rapide en effet : pour n=1000000000 et p=1303, résultat=788, obtenu en 0,02 seconde
#9 - 09-11-2017 13:53:28
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Grand multiplle
Tu peux regarder pour 1302? C'est le pire cas normalement
#10 - 09-11-2017 15:14:04
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Gand multiple
scarta #9 a écrit:Tu peux regarder pour 1302? C'est le pire cas normalement
Résultat=10, en 0,02 seconde aussi
Édité : Le bon résultat est 718. J'ai cru comprendre que ton algorithme suppose que le nombre p est premier.
#11 - 09-11-2017 17:00:07
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Grand mulltiple
La magie du O(ln) Et du PTF
#12 - 09-11-2017 20:20:03
#13 - 09-11-2017 20:49:32
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3222
- Lieu: Luxembourg
grand miltiple
Merci à tous pour votre implication, mais comme tout vieux, je ne connais ni fastpow ni python. Je rêvais d'une solution s'appuyant sur un théorème d'arithmétique modulaire (Fermat ou autre) donnant un résultat "manuel" rapidement. En effet, à priori, sans vraiment la connaitre, la méthode dite par unité tronqué semblait bien s"appliquer à 10^n puisque ce nombre est facile à tronquer et ses chiffres faciles à ajouter.
#14 - 09-11-2017 21:15:08
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
grand mulyiple
J'ai corrigé mon message #10.
#15 - 10-11-2017 08:42:51
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1970
Grand multipl
La méthode par unité tronquée marche, oui. Ça ne veut pas dire qu'elle est simple! Elle ne sert pas à calculer un modulo, mais simplement de savoir si un nombre divise un autre. Là, avec 10^100 et 1303, oui tu trouve très vite que ça n'est pas divisible mais bon c'est normal Ensuite, 1303 - (1303*7-1)/10 = 391, donc 10^100+1 => 10^99+391 => 10^98 + 39 + 391 = 10^98 + 430 => 10^97 + 43 => 10^96 + 4 + 1173 etc.. Au final il te faudra 100 (n) étapes, pour chacun des 1303 (p) entiers considérés. C'est très long, c'est en n*p.
La méthode FastPow et PTF peut se faire même à la main 1) tu prends n % (p-1) au lieu de n. Ça fera toujours des calculs en moins (PTF) 2) pour faire q^n modulo p, tu fais - (q*q modulo p)^(n/2) modulo p si n est pair - ou q fois ça si n est impair 10^1000000 mod 1302 => 64 au lieu de 1000000 ==> 10^64 ==> 100^32 ==> 10000^16 = 879^16 (puisqu'en modulo 1303) ==> 1265^8 ==> 141^4 ==> 336^2 ==> 838^1 = 838
Donc 10^1000000 = 838 modulo 1303, et 10^1000000 + 465 est un multiple de 1303. Tu passes de p*n opérations à log2(p-2) opérations au pire
Je rajoute un lien wikipédia: https://fr.wikipedia.org/wiki/Exponentiation_modulaire et aussi que FastPow n'est apparemment pas un nom officiel (c'est juste celui que je donne à chaque fois à ma méthode...)
#16 - 10-11-2017 11:53:05
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3222
- Lieu: Luxembourg
Gand multiple
Merci scarta pour ces explications qui sont très claires.
Mots clés des moteurs de recherche
|
|