Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #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. smile

  • |
  • Répondre

#0 Pub

 #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,

Code:

print((10**100)%1303)

python calcule ce résultat (1240) en 0,03 seconde

Code:

print((10**1000000)%1303)

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#

Code:

using System;
public class MainClass {
  public static void Main(string[] args) {
  long n=1000000000;
  long p=1303;
  if(n>p) n%=p-1;
  Console.WriteLine(FPM(10,n,p));
  }
  public static long FPM(long b, long e, long m)
  {
    if(e==0) return 1;
    long b2=(b*b)%m;
    if((e&1)==0) return FPM(b2, e>>1, m);
    return (b*FPM(b2, e>>1, m))%m;
  }
}

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)

Code:

import sys
n=int(sys.argv[1])
p=int(sys.argv[2])

def function(n,p): return PowMod(10,n,p) if n<p else PowMod(10,n%(p-1),p)

def PowMod(base,exp,mod):
   if exp==0: return 1
   Base2=(base*base)%mod
   ret = PowMod(Base2,exp>>1,mod)
   if exp & 1: return (base * ret)%mod
   else:       return ret

print(function(n,p))

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) big_smile
Et du PTF

 #12 - 09-11-2017 20:20:03

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

grabd multiple

Je viens de découvrir qu'en python, il existe une fonction, très rapide, qui fait le boulot :

Code:

print( pow(10,1000000,1303) )

https://en.wikibooks.org/wiki/Algorithm … nentiation

 #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 smile
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.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
22-07-2015 Blabla
09-04-2017 Blabla
P2T
14-12-2007 Blabla
P2T
12-02-2016 Blabla
P2T
Sauvez la chenille ! par papiauche
26-06-2009 Blabla
P2T
Visite au zoo par HAMEL
13-05-2010 Blabla
06-07-2013 Blabla
P2T
Hello à tous par littlemiss69
26-01-2008 Blabla
12-08-2007 Blabla

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete