Tester divisibilité d'un nombre de la forme 2^n-1

[Kaluza]

Bonjour.

J'aimerai savoir si il y a un moyen sioux très rapide de tester la divisibilité d'un nombre N = 2^n-1 (donc une suite de n "1" en binaire) par un autre nombre D avec n pouvant être très grand (possibilité d'utiliser une libraire pour de la précision arbitraire) et D un entier 64 bits. (ou dit autrement, tester si (2^n-1)%D == 0) .

Merci

[droggo]

Pye,

Ce sont des nombres de Mersennes, une petite recherche s'impose.

[pseudocode]

Envoyé par droggo

Ce sont des nombres de Mersennes, une petite recherche s'impose.

D'autant plus qu'on n'en connait pour l'instant qu'une 50aine. Un simple switch/case devrait suffire pour ton test.

[droggo]

Fue,

Envoyé par pseudocode

D'autant plus qu'on n'en connait pour l'instant qu'une 50aine. Un simple switch/case devrait suffire pour ton test.

Ça, c'est le nombre de ceux qui sont premiers.

De mémoire le plus grand trouvé dans ce cas correspond à n > 43 000 000, je ne sais plus précisément.

[pseudocode]

Envoyé par droggo

Ça, c'est le nombre de ceux qui sont premiers.

Ah oui, mince. Lu trop vite.

[Franck Dernoncourt]

Envoyé par droggo

De mémoire le plus grand trouvé dans ce cas correspond à n > 43 000 000, je ne sais plus précisément.

n = 43,112,609
http://en.wikipedia.org/wiki/Mersenn...ersenne_primes
Bourrinés à coups de GIMPS

[Kaluza]

Je m'étais renseigné sur les nombres de Mersenne avant, et ce n'est pas ce que je recherche. Un nombre de Mersenne est un nombre, effectivement de la forme 2^n-1 mais où, dans la plupart des définitions que l'on trouve, n est premier.

Mais ce qui m'intéresse est la chose suivante : à n donné (genre 1 milliard (donc 2^(10^9) ne passe bien entendu pas en mémoire), j'ai une liste de nombres D (genre 1 million de D différents) et je veux savoir le plus rapidement possible lesquels parmi ceux là divisent 2^n-1. Ma problématique n'est donc pas la même que celle des nombres de Mersenne premiers...

Si vous avez des idées...

[souviron34]

Envoyé par Kaluza

à n donné (genre 1 milliard (donc 2^(10^9)

Déjà tu as un petit problème, là

Maintenant, qu'entends-tu par :

Envoyé par Kaluza

ne passe bien entendu pas en mémoire),

J'avoue ne pas comprendre ..

Pose correctement ton problème, stp, parce que là c'est un peu flou..

[pseudocode]

Envoyé par Kaluza

Je m'étais renseigné sur les nombres de Mersenne avant, et ce n'est pas ce que je recherche. Un nombre de Mersenne est un nombre, effectivement de la forme 2^n-1 mais où, dans la plupart des définitions que l'on trouve, n est premier.

Mais ce qui m'intéresse est la chose suivante : à n donné (genre 1 milliard (donc 2^(10^9) ne passe bien entendu pas en mémoire), j'ai une liste de nombres D (genre 1 million de D différents) et je veux savoir le plus rapidement possible lesquels parmi ceux là divisent 2^n-1. Ma problématique n'est donc pas la même que celle des nombres de Mersenne premiers...

Si vous avez des idées...

Tu peux construire dynamiquement un critère de divisibilité pour chacun de tes nombres D, et l'appliquer sur ton nombre Mn. Il vaut mieux travailler sur un critère en binaire vu que Mn est constitué uniquement de 1 en binaire : ca évite de devoir le représenter en mémoire.

Cela dit, avec un "n" proche de 1 milliard, ca risque quand même de prendre plusieurs secondes pour chaque D, donc plusieurs mois de calculs au total.


NB: et pour le fun, (2^(10^9)-1) est divisible par 5 d'après mon programme.

[pseudocode]

Oublié de poster le code.

Code java :

1
2
3
4
5
6
7
8
9
10
11
long n=1199;       // n such as Mn = (2^n)-1 
long d=745988807;  // divisor to test
 
long r=1;   // r = remainder of {(BASE^i)/d}, modulo d
long sum=0; // sum of {digit(i)*remainder(i)}, modulo d
for(int i=0; i<n; i++, r=(r*2)%d) {
	// all digits are "1" for Mn in base 2
	sum = (sum + 1*r) % d;
}
 
System.out.printf("(2^%d)-1 = %d (mod %d)",n,sum,d);

(2^1199)-1 = 0 (mod 745988807)

NB : ce code peut être optimisé pour la vitesse, en particulier sur les calculs de modulo car les valeur de 'r' et 'sum' n'augmentent pas de beaucoup à chaque tour de boucle.