Enigme Nombre composé de 0 et de 1 @ Prise2Tete

gabrielduflot · #1

Peut-on toujours trouver un nombre de n chiffres composés que de 0 ou 1 qui soit divisible par n?

Exemple: 1 est divisible par 1
10 est divisible par 2
111 est divisible par 3

Spoiler : [Afficher le message]

EfCeBa · #2

J'ai tenté les 50 premiers avec http://www.dcode.fr/?outil=programmation-javascript

Code:

for (i = 1; i <= 50; i++) {
 diviseur_existe(i);
}

function diviseur_existe(longueur) {
 var imin = "1";
 var imax = "1";
 for (var i = 0; i < longueur-1; i++) {
  imin += "0";
  imax += "1";
 }
 imin = parseInt(base_convert(imin,2,10));
 imax = parseInt(base_convert(imax,2,10));
 for (var i = imin; i <= imax; i++) {
  a = new BigInt(base_convert(i,10,2));
  if (bigint_mod(a,longueur)==0) {
   document.write(longueur+' => '+a+'<br>');
   break;
  }
 }
}

function base_convert(number, frombase, tobase) {
 return parseInt(number+'', frombase+0).toString(tobase+0);
}

Le résultat :

Code:

1 => 1
2 => 10
3 => 111
4 => 1000
5 => 10000
6 => 100110
7 => 1000111
8 => 10000000
9 => 111111111
10 => 1000000000
11 => 10000000010
12 => 100000001100
13 => 1000000001000
14 => 10000000001110
15 => 100000000000110
16 => 1000000000000000
17 => 10000000000000101
18 => 100000000111111110
19 => 1000000000000001101
20 => 10000000000000000000
21 => 100000000000000000110
22 => 1000000000000000000100
23 => 10000000000000000001011
24 => 100000000000000000011000
25 => 1000000000000000000000000
26 => 10000000000000000000010000
27 => 100000000000000000110111111
28 => 1000000000000000000000001100
29 => 10000000000000000000000001101
30 => 100000000000000000000000000110
31 => 1000000000000000000000000110111
32 => 10000000000000000000000000000000
33 => 100000000000000000000000000101111
34 => 1000000000000000000000000000001010
35 => 10000000000000000000000000000000010
36 => 100000000000000000000000001111111100
37 => 1000000000000000000000000000000000110
38 => 10000000000000000000000000000000011010
39 => 100000000000000000000000000000000010001
40 => 1000000000000000000000000000000000000000
41 => 10000000000000000000000000000000000011110
42 => 100000000000000000000000000000000000001010
43 => 1000000000000000000000000000000000000111111
44 => 10000000000000000000000000000000000000000100
45 => 100000000000000000000000000000000000111111110
46 => 1000000000000000000000000000000000000000010110
47 => 10000000000000000000000000000000000000000010010
48 => 100000000000000000000000000000000000000000110000
49 => 1000000000000000000000000000000000000000000100001
50 => 10000000000000000000000000000000000000000000000000

Certes, ce n'est pas une preuve mais ça semble possible, les nombres étant tellement grands que la probabilités qu'aucun n'existe tend vers 0.

Je vais réfléchir à une démo en attendant un indice.

Edit : comme il n'y aura pas d'indice, je vais noter quelques pistes :
Déjà les nombres ayant un nombre de chiffres égal à une puissance de 2 ou un multiple de 10 donnent systématiquement des solutions simples : 1000...000
Visuellement, les cas les plus complexes apparaissent pour les multiples de 9 mais en réalité on trouvera toujours un multiple de 9 puisqu'il suffit que le nombre ait 9 fois le chiffre 1.

dhrm77 · #3

Je pense que oui.
Mais la demonstration n'est probablement pas simple.
j'y arrive facilement à la main jusqu'à 22 chiffres...
pour le reste je crois qu'il suffisse de se concentrer sur les nombres premiers.

nikles007 · #4

Tout nombre à n chiffres bianires (commencant par 1) définit un intervalle des possbles compris entre 2^(n-1) et (2^n)-1

Si n= 2 I(2) = 2...3
Si n =3 I(3) = 4.. 7
Si n=4 I(4) = 8..15
Si n= 5 I(5) = 16...31
..

P(n) : A chaque fois on considère qu'il existe k tel que x tel que x est element de I(n) et est divisble par n... c'est a dire que x = kn

P(2) est vrai avec k = 1
P(3) est vrai avec k=2
P(4) est vrai avec k = 1, 2, 3
P(5) est vrai avec k = 3,4,5,6

On admet: Si intervalle numérique admet une suite de k nombres consécutifs strictement supérieur à 0, alors il existe parmis ces nombres un multiple de k.
Pour preuve,

On considère la suite de k nombres consécutifs suivants;

a,a+1,...a+k

situation 1: Si a<k, alors il existe le nombre k dans la suite, donc un multiple.

situation 2: Si a> k, alors on considère la suite a-k, a+1-k, ...a, et on reprend le raisonnement ave cette suite, autant de fois que nécessaire, pour se retrouver en situation 1. Le nombre de fois que l'on ote k, de a est noté p. On arrive donc à une suite a-kp, a+1-kp, ...a+k-kp, avec a-kp < k. On en déduit que (p+1)*k est un multiple de k, et est présent dans l'intervalle I(k)

DONC,

Si intervalle numérique admet une suite de k nombres consécutifs strictement supérieur à 0, alors il existe parmis ces nombres un multiple de k.

Comme chaque intervalle I(n) admet un nombre d'éléments consécutifs plus grand que n, alors il existe parmis ces nombres un multiple de n.

En effet, card(2^(n-1)... (2^n)-1) = 2^(n-1) >= n

DONC, CQFD

C'est peut etre pas clair.. :-), tout est question de modulo et d'intervalles

nikles007 · #5

Je crois que j'ai confondu nombres binaires et nombres décimaux composé de 0 et de 1.

Dans tous les cas, tout nombre binaire de n chiffres admet une combinaison de 0 et de 1 tel que le nombre obtenu soit divisible par n.

MthS-MlndN · #6

La démo semble tenir debout, sauf que je ne comprends pas d'où tu sors Ai congru à Aj modulo n... Puis-je avoir un supplément d'explication ?..

MthS-MlndN · #7

Superbe démo, félicitations ! Nous avons un très bon matheux dans nos rangs

Ef' pourrait-il modifier son programme pour ne chercher que des nombres de la forme 1...10...0 ? (Si ce n'est pas trop long à faire.)

Pour les premiers :

1 : 1
2 : 10
3 : 111
4 : 1000 ou 1100
5 : 10000 ou 11000 ou 11100 ou 11110
6 : 111000
7 : 1111110
8 : 10000000 ou 11000000 ou 11100000 ou 11110000 ou 11111000
9 : 111111111
10 : neuf possibles
11 : cinq possibles
12 : 111000000000 ou 111111000000 ou 111111111000
13 : 1111110000000
14 : 11111100000000 ou 11111111111100
etc.

kosmogol · #8

Nous avons un très bon matheux dans nos rangs

encore un ! pffftttt

MthS-MlndN · #9

Ce n'est pas parce que tu es nul qu'il faut être jaloux

kosmogol · #10

On est tous le nul de quelqu'un

Nicouj · #11

Un petit programme en scheme :

Code:

(define (multiple_un_zero n) 
  (local [(define (iter s i) 
            (if (= 0 (modulo s n)) 
                s 
                (iter (+ s i) (/ i 10))))]
    (iter (expt 10 (- n 1)) (expt 10 (- n 2)))))
 
(define (premiers_multiples_un_zero n)
  (map multiple_un_zero (build-list n add1)))

Code:

1: 1
2: 10
3: 111
4: 1000
5: 10000
6: 111000
7: 1111110
8: 10000000
9: 111111111
10: 1000000000
11: 11000000000
12: 111000000000
13: 1111110000000
14: 11111100000000
15: 111000000000000
16: 1000000000000000
17: 11111111111111110
18: 111111111000000000
19: 1111111111111111110
20: 10000000000000000000
21: 111111000000000000000
22: 1100000000000000000000
23: 11111111111111111111110
24: 111000000000000000000000
25: 1000000000000000000000000
26: 11111100000000000000000000
27: 111111111111111111111111111
28: 1111110000000000000000000000
29: 11111111111111111111111111110
30: 111000000000000000000000000000
31: 1111111111111110000000000000000
32: 10000000000000000000000000000000
33: 111111000000000000000000000000000
34: 1111111111111111000000000000000000
35: 11111100000000000000000000000000000
36: 111111111000000000000000000000000000
37: 1110000000000000000000000000000000000
38: 11111111111111111100000000000000000000
39: 111111000000000000000000000000000000000
40: 1000000000000000000000000000000000000000
41: 11111000000000000000000000000000000000000
42: 111111000000000000000000000000000000000000
43: 1111111111111111111110000000000000000000000
44: 11000000000000000000000000000000000000000000
45: 111111111000000000000000000000000000000000000
46: 1111111111111111111111000000000000000000000000
47: 11111111111111111111111111111111111111111111110
48: 111000000000000000000000000000000000000000000000
49: 1111111111111111111111111111111111111111110000000
50: 10000000000000000000000000000000000000000000000000
51: 111111111111111111111111111111111111111111111111000
52: 1111110000000000000000000000000000000000000000000000
53: 11111111111110000000000000000000000000000000000000000
54: 111111111111111111111111111000000000000000000000000000
55: 1100000000000000000000000000000000000000000000000000000
56: 11111100000000000000000000000000000000000000000000000000
57: 111111111111111111000000000000000000000000000000000000000
58: 1111111111111111111111111111000000000000000000000000000000
59: 11111111111111111111111111111111111111111111111111111111110
60: 111000000000000000000000000000000000000000000000000000000000
61: 1111111111111111111111111111111111111111111111111111111111110
62: 11111111111111100000000000000000000000000000000000000000000000
63: 111111111111111111000000000000000000000000000000000000000000000
64: 1000000000000000000000000000000000000000000000000000000000000000
65: 11111100000000000000000000000000000000000000000000000000000000000
66: 111111000000000000000000000000000000000000000000000000000000000000
67: 1111111111111111111111111111111110000000000000000000000000000000000
68: 11111111111111110000000000000000000000000000000000000000000000000000
69: 111111111111111111111111111111111111111111111111111111111111111111000
70: 1111110000000000000000000000000000000000000000000000000000000000000000
71: 11111111111111111111111111111111111000000000000000000000000000000000000
72: 111111111000000000000000000000000000000000000000000000000000000000000000
73: 1111111100000000000000000000000000000000000000000000000000000000000000000
74: 11100000000000000000000000000000000000000000000000000000000000000000000000
75: 111000000000000000000000000000000000000000000000000000000000000000000000000
76: 1111111111111111110000000000000000000000000000000000000000000000000000000000
77: 11111100000000000000000000000000000000000000000000000000000000000000000000000
78: 111111000000000000000000000000000000000000000000000000000000000000000000000000
79: 1111111111111000000000000000000000000000000000000000000000000000000000000000000
80: 10000000000000000000000000000000000000000000000000000000000000000000000000000000
81: 111111111111111111111111111111111111111111111111111111111111111111111111111111111
82: 1111100000000000000000000000000000000000000000000000000000000000000000000000000000
83: 11111111111111111111111111111111111111111000000000000000000000000000000000000000000
84: 111111000000000000000000000000000000000000000000000000000000000000000000000000000000
85: 1111111111111111000000000000000000000000000000000000000000000000000000000000000000000
86: 11111111111111111111100000000000000000000000000000000000000000000000000000000000000000
87: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000
88: 1100000000000000000000000000000000000000000000000000000000000000000000000000000000000000
89: 11111111111111111111111111111111111111111111000000000000000000000000000000000000000000000
90: 111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
91: 1111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000
92: 11111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000
93: 111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000
94: 1111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
95: 11111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000
96: 111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
97: 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
98: 11111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000
99: 111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
100: 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

EfCeBa · #12

Code:

for (var i = 1; i <= 100; i++) {
 if (diviseur_existe(i)) continue;
 else break;
}

function diviseur_existe(longueur) {
 for (var i = 0; i < longueur; i++) {
  var nb = "1";
  for (var j = 1; j < longueur; j++)
   if (j <= i) nb += "1";
   else nb += "0";
  if (bigint_mod(nb,longueur)==0) {
   document.write(longueur+' => '+nb+'<br>');
   return true;
  }
 }
 return false;
}

dhrm77 · #13

J'arrive un peu apres la bataille..
mais voici un programme en C n'utilisant aucune fonction de math externe.

Code:

#include <stdio.h>

unsigned a,b,c,d,e,r;

void main()
{
  for (a=1; a<105; ++a)
  {
    r=1; b=c=a; d=e=0;
    while ((b%5)==0) b/=5;
    while ((b&1)==0) b/=2;
    while(c)
    {
      ++e; --c;
      d*=10; d+=r; d%=b;
      if (d==0) break;
    }
    printf("%u digits:", a);
    if (d)
      printf("not found\n");
    else
    {
      while (e--) printf("1");
      while (c--) printf("0");
      printf("\n");
    }
  }
}

et le resultat:

Code:

1 digits:1
2 digits:10
3 digits:111
4 digits:1000
5 digits:10000
6 digits:111000
7 digits:1111110
8 digits:10000000
9 digits:111111111
10 digits:1000000000
11 digits:11000000000
12 digits:111000000000
13 digits:1111110000000
14 digits:11111100000000
15 digits:111000000000000
16 digits:1000000000000000
17 digits:11111111111111110
18 digits:111111111000000000
19 digits:1111111111111111110
20 digits:10000000000000000000
21 digits:111111000000000000000
22 digits:1100000000000000000000
23 digits:11111111111111111111110
24 digits:111000000000000000000000
25 digits:1000000000000000000000000
26 digits:11111100000000000000000000
27 digits:111111111111111111111111111
28 digits:1111110000000000000000000000
29 digits:11111111111111111111111111110
30 digits:111000000000000000000000000000
31 digits:1111111111111110000000000000000
32 digits:10000000000000000000000000000000
33 digits:111111000000000000000000000000000
34 digits:1111111111111111000000000000000000
35 digits:11111100000000000000000000000000000
36 digits:111111111000000000000000000000000000
37 digits:1110000000000000000000000000000000000
38 digits:11111111111111111100000000000000000000
39 digits:111111000000000000000000000000000000000
40 digits:1000000000000000000000000000000000000000
41 digits:11111000000000000000000000000000000000000
42 digits:111111000000000000000000000000000000000000
43 digits:1111111111111111111110000000000000000000000
44 digits:11000000000000000000000000000000000000000000
45 digits:111111111000000000000000000000000000000000000
46 digits:1111111111111111111111000000000000000000000000
47 digits:11111111111111111111111111111111111111111111110
48 digits:111000000000000000000000000000000000000000000000
49 digits:1111111111111111111111111111111111111111110000000
50 digits:10000000000000000000000000000000000000000000000000
51 digits:111111111111111111111111111111111111111111111111000
52 digits:1111110000000000000000000000000000000000000000000000
53 digits:11111111111110000000000000000000000000000000000000000
54 digits:111111111111111111111111111000000000000000000000000000
55 digits:1100000000000000000000000000000000000000000000000000000
56 digits:11111100000000000000000000000000000000000000000000000000
57 digits:111111111111111111000000000000000000000000000000000000000
58 digits:1111111111111111111111111111000000000000000000000000000000
59 digits:11111111111111111111111111111111111111111111111111111111110
60 digits:111000000000000000000000000000000000000000000000000000000000
61 digits:1111111111111111111111111111111111111111111111111111111111110
62 digits:11111111111111100000000000000000000000000000000000000000000000
63 digits:111111111111111111000000000000000000000000000000000000000000000
64 digits:1000000000000000000000000000000000000000000000000000000000000000
65 digits:11111100000000000000000000000000000000000000000000000000000000000
66 digits:111111000000000000000000000000000000000000000000000000000000000000
67 digits:1111111111111111111111111111111110000000000000000000000000000000000
68 digits:11111111111111110000000000000000000000000000000000000000000000000000
69 digits:111111111111111111111111111111111111111111111111111111111111111111000
70 digits:1111110000000000000000000000000000000000000000000000000000000000000000
71 digits:11111111111111111111111111111111111000000000000000000000000000000000000
72 digits:111111111000000000000000000000000000000000000000000000000000000000000000
73 digits:1111111100000000000000000000000000000000000000000000000000000000000000000
74 digits:11100000000000000000000000000000000000000000000000000000000000000000000000
75 digits:111000000000000000000000000000000000000000000000000000000000000000000000000
76 digits:1111111111111111110000000000000000000000000000000000000000000000000000000000
77 digits:11111100000000000000000000000000000000000000000000000000000000000000000000000
78 digits:111111000000000000000000000000000000000000000000000000000000000000000000000000
79 digits:1111111111111000000000000000000000000000000000000000000000000000000000000000000
80 digits:10000000000000000000000000000000000000000000000000000000000000000000000000000000
81 digits:111111111111111111111111111111111111111111111111111111111111111111111111111111111
82 digits:1111100000000000000000000000000000000000000000000000000000000000000000000000000000
83 digits:11111111111111111111111111111111111111111000000000000000000000000000000000000000000
84 digits:111111000000000000000000000000000000000000000000000000000000000000000000000000000000
85 digits:1111111111111111000000000000000000000000000000000000000000000000000000000000000000000
86 digits:11111111111111111111100000000000000000000000000000000000000000000000000000000000000000
87 digits:111111111111111111111111111111111111111111111111111111111111111111111111111111111111000
88 digits:1100000000000000000000000000000000000000000000000000000000000000000000000000000000000000
89 digits:11111111111111111111111111111111111111111111000000000000000000000000000000000000000000000
90 digits:111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
91 digits:1111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000
92 digits:11111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000
93 digits:111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000
94 digits:1111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
95 digits:11111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000
96 digits:111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
97 digits:1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
98 digits:11111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000
99 digits:111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
100 digits:1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
101 digits:11110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
102 digits:111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000
103 digits:1111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000
104 digits:11111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

kosmogol · #14

Cela fait 10 ans que je ne code plus, mais je constate que vous n'êtes pas dans le même monde que les autres
C'est vraiment incompréhensible

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 - 03-08-2009 14:21:37

Nombre composé de 0 et d e1

#0 Pub

#2 - 03-08-2009 18:22:45

Nombre composé de 0 et de

Code:

Code:

#3 - 03-08-2009 20:41:57

ombre composé de 0 et de 1

#4 - 05-08-2009 11:48:23

Nmobre composé de 0 et de 1

#5 - 06-08-2009 10:00:42

nombre composé de 0 ey de 1

#6 - 07-08-2009 00:14:51

Nombre compos de 0 et de 1

#7 - 07-08-2009 15:36:45

ombre composé de 0 et de 1

#8 - 07-08-2009 16:32:50

nomvre composé de 0 et de 1

#9 - 07-08-2009 16:34:19

nombre compisé de 0 et de 1

#10 - 07-08-2009 16:49:23

Noombre composé de 0 et de 1

#11 - 07-08-2009 16:59:17

nimbre composé de 0 et de 1

Code:

Code:

#12 - 07-08-2009 17:32:46

nombre composé de 0 et dz 1

Code:

#13 - 08-08-2009 14:46:36

Nombrre composé de 0 et de 1

Code:

Code:

#14 - 08-08-2009 14:49:59

nombre compodé de 0 et de 1

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums