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

Grand mulltiple

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

Grand multiiple

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

GGrand multiple

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

Grand multilpe

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

grznd 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 : 1533

Grand mltiple

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

grand mulriple

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

Grandd 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 : 1533

Grannd multiple

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

Grand multtiple

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

Grand mutiple

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

grand lultiple

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

rand multiple

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

gtand multiple

J'ai corrigé mon message #10.

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

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

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

grand multuple

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
11-03-2009 Blabla
27-06-2008 Blabla
P2T
Terre 2 par nobodydy
05-09-2016 Blabla
P2T
Mots croisés Le Monde par e-patant
08-08-2013 Blabla
05-04-2010 Blabla
P2T
Bonne Année 2017 par EfCeBa
02-01-2017 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