Solution to Problem 16 on ProjectEuler.net


Here’s the problem:

—–
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?
—–

My Solution

Here’s the solution implementing the large number as an array of digits:

#include <stdio.h>

#define MAX 400

int main(){
int vet[MAX]={0};
int i,x,y,v,f,sum;

vet[0]=1;
y=1000;

while (y>0){
  v = 0;
  for (i=0;i<MAX;i++){
    x = vet[i]*2 + v;
    v = 0;
    if (x > 9){
      f = x % 10;
      v = x / 10;      
    }
    else
      f = x;
    vet[i] = f;
  }
  y = y - 1;
}
  sum=0;
  for (i=MAX-1;i>=0;i--)
    sum=sum+vet[i];
  printf("%dn",sum);
  return 0;
}

And using the bignum library:

#include <stdio.h>
#include <math.h>
#include <gmp.h>

int main(){
mpz_t x,y;
int i,sum;
sum=0;
mpz_init(x);
mpz_init(y);

mpz_ui_pow_ui(x,2,1000);

while (mpz_sgn(x)){
  sum += mpz_mod_ui(y,x,10);
  mpz_fdiv_q_ui(x,x,10);
}
  printf("%dn",sum);
  return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *