3 puissance n en binaire

[Ericovitchi]

Bonjour,
On m'a posé ce problème mais je n'arrive pas à trouver.


On note Un (respectivement Zn) le nombre de 1 (respectivement de 0) dans l'écriture de 3^n en base 2.

Montrer que Un/Zn tend vers 1 lorsque n tend vers l'infini.

J'ai essayé de voir comme les coef se transformaient chaque fois que l'on multiplie par 3 mais avec les retenus c'est assez chaotique comme suite.

Bref, je sèche.
Auriez vous une idée ?

[Nightmare]

Salut,

les coefs ne sont-ils pas les Cn^k ?

[Ericovitchi]

ha oui je suis bête, (2+1)^n par newton. Oui OK

[Ericovitchi]

Oui mais il y a un truc qui ne va pas. Ces coef du binôme, il ne valent pas que zéro ou un donc ça n'est pas l'expression de 3^n en binaire ?

Et puis pour passer aux suites Un et Zn ?

[Ben314]

Pssssst,
Le "exercice" en question sur l'autre forum, c'est moi qui l'ai mis suite à une suggestion de Beagle (il me semble ?) elle même suite à une 'pub' pour l'autre forum affirmant que tu avait une réponse dans les 24 heures...

Le point de départ est là : http://maths-forum.com/showthread.php?t=103352

Plus ça va, plus je considère le truc comme "imbuvable" : voir par exemple la remarque de Doraki à la fin qui signale que, rien que montrer que Un tend vers l'infini, ça revient déjà à montrer que toute équation diophantienne de la forme 2^a1+2^a2+...+2^ak=3^b n'a qu'un nombre fini de solution...

Et, déjà, pour k=3, je sais pas faire...
J'ai pas totalement jeté l'éponge, mais depuis le temps que je triture des trucs, j'arrive à rien...

D'un autre coté, si vous arrivez à quelque chose (même un début de piste), j'aplaudit des trois mains...

[Ericovitchi]

Hou là là, OK je comprends pourquoi je pédale dans la semoule.
Bon OK laissons tomber.

[ffpower]

Ah bah merci, beagle, Doraki, alors que les 2 post étaient de moi XD

[Ben314]

Oups....
Pour le premier (idée d'aller poser une "colle") j'ai une excuse : le thread a été supprimé.
Pour le deuxième... j'en ait aucune... :triste:

P.S. Tu as continué à chercher ?

[ffpower]

A part eventuellement celle que je suis passé pour un gros noob qur le sujet avec ma pseudo solution à 3 sous :we: ( que je viens un peu de modérer au passage histoire d avoir moins la honte^^)

[ffpower]

Je cherche pas beaucoup en ce moment faute de temps, mais je ne désespere pas. AU pire je posterai ca sur math.net, ya des monstres de théo des nombres la bas (par contre a coup sur ils utiliseront des résultats super récents imbitables^^)

[fatal_error]

salut,

je sais pas si ca vous avance, mais voici la gueule que ca a :


l'absisse : la valeur de n.
en rouge le nombre de 1 dans 3^n
en vert le nombre de 0,
et en bleu le rapport nombre de un/nombre de 0 (sachant que ya jamais un nombre full de 1, sauf pour 1 et 3).

Jpense que ca pourrait etre intéressant de voir si ya pas des trucs récurrents.
Par exemple, en rentrant plus dans le détail des automates de doraki, pis en regardant si ya pas des chaines qui se retrouvent. (style R0R1R2R0...). Mais ca a peut etre été déjà écarté...vous m'avez perdu à partir des modulo XD

[Doraki]

Sur ton graphe on dirait que le nombre de zéros est borné, ça va pas.

[fatal_error]

snormal, sparce que je suis daltonien.

En vert le nombre de un et en rouge le nombre de zéros.
Vérifié à la console pour les premières valeurs à l'instant.

[Ben314]

Si tu t'est pas gourré (???) c'est sacrément bizare...

[fatal_error]

bon, jvous joins un log, des résultats pour les 20 premières valeurs

Code: Tout sélectionner

s = 1
a =

   1   0

s = 11
a =

   2   0

s = 1001
a =

   2   2

s = 11011
a =

   4   1

s = 1010001
a =

   3   4

s = 11110011
a =

   6   2

s = 1011011001
a =

   6   4

s = 100010001011
a =

   5   7

s = 1100110100001
a =

   6   7

s = 100110011100011
a =

   8   7

s = 1110011010101001
a =

   9   7

s = 101011001111111011
a =

   13    5

s = 10000001101111110001
a =

   10   10

s = 110000101001111010011
a =

   11   10

s = 10010001111101101111001
a =

   14    9

s = 110110101111001001101011
a =

   15    9

s = 10100100001101011101000001
a =

   11   15

s = 111101100101000010111000011
a =

   14   13

s = 10111000101111001000101001001
a =

   14   15




pour la variable a : la premiere colonne le nombre de 1.
la seconde colonne le nombre de 0
pour la variable s, c'est la chaine binaire associée a 3^n

On commence à n = 0, soit le nombre 1 (décimal)

[nodjim]

il me semble qu'il y a des erreurs dans ton algo. le 9ème résultat ne me semble pas correct.

[fatal_error]

euh, je viens de regarder.
Le neuvieme résultat correspond à n = 8.

La valeur de 3^8 est 6561.
La valeur binaire de 6561 est 1100110100001

Après, jveux bien que yait une erreur dans lencodage (mais ca me surprendrais TRES fort).
En vérifiant :
1,1001,1010,0001
1,9,A,1
1 + 160 + 9*256 + 16^3 = 6561

Je vois pas trop ou est l'erreur. Edit, vous l'aimez pas mon algo :'(.
Jvous le joins au lieu de vous faire une boite noire...

Code: Tout sélectionner

BASE = 3;
N = 100;
REF = dec2bin(1);
if exist('ind')==0
disp('existe pas');
   ind = 1;
   nb = 1;
   v(1:N-1,1:3)=0;
else
   % on laisse nb
   % il faut réallouer v!
   v(ind:N-1,1:3)=0;
end
while ind < N
   s = dec2bin(nb);
   t = size(s)(2);
   for j = 1:t
      if s(j)==REF
         v(ind,1)++;%nombre de uns
      else
         v(ind,2)++;%nombre de zeros
      end
   end
   %si pas de 0
   if v(ind,2)==0   
      ind;
      v(ind,3)=-1;
   else
      v(ind,3) = v(ind,1)/v(ind,2);
   end
   nb = nb*BASE;
   ind++;
end

plot(v(:,1),'color','green');
hold('on');
plot(v(:,2),'color','red');
hold('on');
plot(v(:,3),'color','blue');
hold('off');


[Doraki]

Le début ça a l'air bon (les deux courbes sont toutes les deux à peu près des droites de même pente) mais c'est à partir d'environ 3^50 que ça va pas (y'a une courbe qui commence à monter deux fois plus vite, et l'autre qui décide de rester bornée)

[fatal_error]

hoké.

Jregarderai ça après manger :hum:

[Doraki]

L'erreur c'est que tes entiers sont sur 64 bits.
Ou plutot, tes flottants, vu qu'il a le bon nombre de chiffres au total.