Discussion :

[mouradj2006]

bjr;
je cherche un algorithme qui permet de calculer la somme des chiffres de nombre obtenu par le calcule de 2^1000.

[Gakusei]

Bonjour,
Ce n'est pas le produit plutôt?
Sinon je n'ai pas compris la question, j'ai besoin d'éclaircissement.

[pseudocode]

Le plus simple c'est de calculer 2^1000 (en base 10) et d'additionner les chiffres.

Ca necessite d'utiliser une librairie qui gère les grands entiers, soit en binaire, soit en BCD.

[kwariz]

Salut,

quoique pour ce problème on peut encore s'en tirer "à la main". En effet 2^1000 est composé E(1000*log10(2))=302 chiffres en codant le nombre par un tableau de char par exemple.

[Gakusei]

D'accord j'ai mieux compris.

Une autre solution serait de constater que 2^1000-1=somme(2^i, i:0->999).
(Principe d'un compteur)
Du coup ça se code très bien de manière récursive.

Le plus simple c'est de calculer 2^1000 (en base 10) et d'additionner les chiffres.

Cette méthode doit être beaucoup plus rapide. Mais je ne vois pas du tout d'où ça vient.
Comment on calcul 2^1000 en base 10?

[kwariz]

D'accord j'ai mieux compris.

Une autre solution serait de constater que 2^1000-1=somme(2^i, i:0->999).
(Principe d'un compteur)
Du coup ça se code très bien de manière récursive.

Salut,
à ma connaissance il n'existe aucune relation simple entre la somme des chiffres (en base 10) de 2^n et les puissances précédantes.

Cette méthode doit être beaucoup plus rapide. Mais je ne vois pas du tout d'où ça vient.
Comment on calcul 2^1000 en base 10?

Comme on le ferait à la main, on commence à 1 et on multiplie par 2 mille fois, par exemple. Le tout est de stocker les chiffres décimaux dans une structure adéquate et implémenter une fonction qui multiplie par 2.

[Gakusei]

Salut,
à ma connaissance il n'existe aucune relation simple entre la somme des chiffres (en base 10) de 2^n et les puissances précédantes.

Pourtant c'est juste...
Un exemple s'impose avec 2^4:
En binaire: 1 0000
Hors 0 1111-> 2^4-1 en décimale
donc 2^4 = 2^3+2^2+2^1+2^0+1
Comme je l'ai dit c'est le principe d'un compteur binaire.

Comme on le ferait à la main, on commence à 1 et on multiplie par 2 mille fois, par exemple. Le tout est de stocker les chiffres décimaux dans une structure adéquate et implémenter une fonction qui multiplie par 2.

Je ne vois pas le rapport avec la base de 10... Et ce n'est plus une addition (mais multiplication)...

[kwariz]

Pourtant c'est juste...
Un exemple s'impose avec 2^4:
En binaire: 1 0000
Hors 0 1111-> 2^4-1 en décimale
donc 2^4 = 2^3+2^2+2^1+2^0+1
Comme je l'ai dit c'est le principe d'un compteur binaire.



Je ne vois pas le rapport avec la base de 10... Et ce n'est plus une addition (mais multiplication)...

Comme j'ai compris, si on prend par exemple 2^10 = 1024, la somme des chiffres (en base 10) est 1+0+2+4=7, 2^4=16 -> 1+6=7 , 2^8=256 -> 2+5+6=13 ....

En base 2 c'est trivial : la somme des chiffres de 2^n vaut 1 quel que soit n positif.

[mouradj2006]

Salut,
à ma connaissance il n'existe aucune relation simple entre la somme des chiffres (en base 10) de 2^n et les puissances précédantes.



Comme on le ferait à la main, on commence à 1 et on multiplie par 2 mille fois, par exemple. Le tout est de stocker les chiffres décimaux dans une structure adéquate et implémenter une fonction qui multiplie par 2.

bonne idée , je suis en pascal , quel structure qui va stocker 302 caractères?

[kwariz]

bonne idée , je suis en pascal , quel structure qui va stocker 302 caractères?

Le plus simple est de déclarer un tableau E de 302 entiers, par exemple 2^11=2048 sera stocké
E[1]=8, E[2]=4, E[3]=0, E[4]=2

Un procedure qui multiplie par deux (comme on ferait à la main, avec retenue, etc ...). Ensuite on somme tous les éléments du tableau pour avoir la somme des chiffres.

[Gakusei]

D'accord petit quiproquo, je n'ai pas bien lu le poste: "somme des chiffres".

Ce que j'ai dit n'a aucun rapport: calcul direct de 2^1000 à partir des sommes...

Du coup c'est direct.

[pseudocode]

Salut,

quoique pour ce problème on peut encore s'en tirer "à la main". En effet 2^1000 est composé E(1000*log10(2))=302 chiffres en codant le nombre par un tableau de char par exemple.

Effectivement. Quand je disais d'utiliser une bibliothèque c'était pour se simplifier la vie. On peut se coder une gestion de grands entiers spécifique à ce problème:

Méthode 1 : un codage BCD de 302 octets, initialisé à "1" et 1000 multiplications successives par 2.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int N=1000;
int len=1+(int)(N*Math.log10(2));
byte[] BCD = new byte[len];
BCD[0]=1; // initial value = 1
 
// successive multiplications
for(int loop=0;loop<N;loop++) {
	// in-place multiplication by 2
	int carry=0;
	for(int i=0; i<len; i++) {
		int d = 2*BCD[i] + carry;
		if (d<10) { carry=0; BCD[i] = (byte)d;      }
		else      { carry=1; BCD[i] = (byte)(d-10); }
	}
}
 
// sum of all digits
int digitalsum=0;
for(int i=0; i<len; i++)
	digitalsum += BCD[i];
 
System.out.println(digitalsum)

Méthode 2 : un codage binaire de 1001 bits, initialisé à "100...00" et 302 divisions successives par 10.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int N=1000;
BitSet bits = new BitSet(N+1);
bits.set(N); // initialize to 100...00
 
int digitalsum=0;
 
// successive divisions
while(!bits.isEmpty()) {
	// in-place division by 10
	int remainder=0; 
	for(int i=N;i>=0;i--) {
		remainder = remainder<<1;
		if (bits.get(i)) remainder+=1;
 
		if (remainder<10) { bits.clear(i); }
		else              { bits.set(i); remainder-=10; }
	}
 
	digitalsum+=remainder;
}
 
System.out.println(digitalsum);

[mouradj2006]

merci les amis voila c'est résolu enfin .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
program p1000;
uses wincrt;
type tab=array[1..302]of integer;
var t:tab;
i,j,p,s,r:integer;
v:boolean;
begin
 
 
for i:=1 to 302 do
t[i]:=-1;
 
t[302]:=1;
r:=0;
for j:=1 to 1000 do
begin
i:=302;
v:=true;
while (t[i]>-1)and(v=true) do
 begin
 
 p:=2*t[i]+r;
 
 if(p >=10) then
 begin
 
 t[i]:= p mod 10;
 
 r:= p div 10;
 end
 else
 begin
 t[i]:=p;
 r:=0;
 end;
 i:=i-1;
 if(t[i]=-1)and(r<>0) then
 begin
 t[i]:=r;
 r:=0;
 v:=false;
 end;
 end;
 
 end;
writeln('2^1000=');
 for i:=1 to 302 do
 write(t[i]);
 for i:=1 to 302 do
 s:=s+t[i];
 writeln;
 write('La somme des chiffres de  2^1000= ',s);  
end.