Grand multiple @ Prise2Tete

Franky1103 · #1

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.

scarta · #2

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

Franky1103 · #3

@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) ?

scarta · #4

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

enigmatus · #5

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

scarta · #6

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)
}

scarta · #7

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)

enigmatus · #8

@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

scarta · #9

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

enigmatus · #10

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.

scarta · #11

La magie du O(ln)
Et du PTF

enigmatus · #12

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

Franky1103 · #13

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.

enigmatus · #14

J'ai corrigé mon message #10.

scarta · #15

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...)

Franky1103 · #16

Merci scarta pour ces explications qui sont très claires.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 08-11-2017 09:53:15

Grand mulltiple

#0 Pub

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

Grad multiple

#3 - 08-11-2017 15:54:43

Grand multipe

#4 - 08-11-2017 21:30:33

Grand muliple

#5 - 09-11-2017 07:07:07

gtand multiple

Code:

Code:

#6 - 09-11-2017 12:49:04

gtand multiple

#7 - 09-11-2017 13:02:55

grand mumtiple

Code:

#8 - 09-11-2017 13:47:11

Grand multipl

Code:

#9 - 09-11-2017 13:53:28

Grand multpile

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

Grand multipple

scarta #9 a écrit:

#11 - 09-11-2017 17:00:07

Grand multiiple

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

Grand muultiple

Code:

#13 - 09-11-2017 20:49:32

Grand multilpe

#14 - 09-11-2017 21:15:08

Grand mltiple

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

rGand multiple

#16 - 10-11-2017 11:53:05

grand multople

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums