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 : 2860
Lieu: Luxembourg

grand miltiple

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



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 08-11-2017 14:51:14

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1558

geand 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 : 2860
Lieu: Luxembourg

Grand multple

@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 : 1558

grznd 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
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 473

Grand multple

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 : 1558

grand mulyiple

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 : 1558

Grand mutliple

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
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 473

gtand 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 : 1558

grand multuple

Tu peux regarder pour 1302? C'est le pire cas normalement

 #10 - 09-11-2017 15:14:04

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 473

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 : 1558

Grand multiplle

La magie du O(ln) big_smile
Et du PTF

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

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 473

Grand mutliple

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 : 2860
Lieu: Luxembourg

Grand multilpe

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
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 473

Grannd multiple

J'ai corrigé mon message #10.

 #15 - 10-11-2017 08:42:51

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1558

hrand multiple

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 : 2860
Lieu: Luxembourg

Grand multiiple

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 : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
P2T
14-12-2007 Blabla
22-07-2015 Blabla
09-04-2017 Blabla
03-12-2010 Blabla
14-02-2012 Blabla
P2T
Desproges, mon Amour ! par MthS-MlndN
04-07-2010 Blabla
P2T
21-10-2009 Blabla
24-09-2010 Blabla
P2T
Blocage DansGuardian par Lap1n0u
09-01-2011 Blabla

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