need help with math problem

[mrnutty]

#include<iostream>
#include<fstream>
#include<cmath>
#include<iomanip>
using namespace std;
/*
215 = 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 logic is to export 2^1000 into a text file. Then import it into an array and the add them. but it seems to be not working as planned. any help people?

int main(){

	ofstream Ofile("num.txt");

	unsigned long double two = 2.0;
	unsigned long double oneTh = 1000.0;
	unsigned long double result = pow(two,oneTh);

	Ofile << setprecision(1000000)<<result;
	//cout<< setprecision(1000000)<<result;
	
	__int64 arry[50000]= {0};

	for(int i=0;(i<50000 && (!Ofile.eof())) ; i++ )
	{
		Ofile << arry;
		if(arry[i]<1 && (arry[i+1] && arry[i+2] == 0) ) // if a sequence of 0 starts comming break;

			break;
		cout<<arry[i];
	}



	return 0;

}

[ddanbe]

Do something with logarithms base 2.

[Freaky_Chris]

for(int i=0;(i<50000 && (!Ofile.eof())) ; i++ ){
    Ofile << arry;
    if(arry[i]<1 && (arry[i+1] && arry[i+2] == 0) ){
       break;
    }
    cout<<arry[i];
}

Do not use eof() it can return true before the end of file is actually reached.

Ofile << arry; shouldn't you be reading from the file not trying to write to it? Which would also mean you need to reopen it as an instream.

arry[i]<1 && (arry[i+1] && arry[i+2] == 0)

This is evaluated as the following not what you are expecting

(arry[i]<1) && (arry[i+1]) && (arry[i+2] == 0)

Chris

[mrnutty]

Do something with logarithms base 2.

Alright check this out. I used a little logarithm properties.

let y = 2 ^1000

then

ln (y) = ln (2^1000)

=
ln(y) = 1000 *ln(2)

take the e of both sides.

y = e^(1000*ln(2));

I know how to implement this code in c++, but can i get the most significant digits.

unsigned long double TWO=2.000;

unsigned long double expValue = (unsigned long double)log(TWO)*1000;

cout<<setprecision(5000) << (unsigned long double)exp (expValue)<<endl;

but i don't believe this would give me all the digits I need. any hints?

[ddanbe]

Sorry there are things getting mixed up here.
First (my fault) base 2 should be base 10 (Again sorry for that)
Second : the sum of the digits... Is it the AMOUNT of digits or the digits summed up as you do?
The digits summed up as you do can not work(imho) because you always have a number of significant figures. For unsigned long double I don't know, but for double it is 16 or so.
But for the amount of digits I can give you:
10^x=2 or log2=x
so we have
2^1000=10^x^1000=10^1000*log2=10^1000*0.30103=10^301.03
So 2^1000 contains 301 or so digits.

[mrnutty]

I see what you did but my practice problem provided by euler is to find the sum of all the digits(ex.12343 = 13 and not 5)

IN that sense I need to output 2 ^1000 untill it reaches its max significant digits.

[Rashakil Fol]

A way to make this really easy is to get the GMP library (it comes with C++ bindings, right?) and use that.

It's silly to output the number to a file and then read the file back in.
Since you don't have enough precision in the built in numerical types, you need to use your own representation. One option is to represent numbers using a std::string.

It's fairly simple to write an algorithm that multiplies a std::string decimal representation by two, taking something like "54321" and returning "09642".

[ddanbe]

Roughly speaking one could say :
There are 10 digits, if they are equaly distributed over the 301 places we have :
45/10*301=1354,5
45 being the sum of the 10 digits. The sum you're seeking must be close to that number.

[ArkM]

s10(2^1000) == 1366
2^1000 == 1071508607186267320948425049060001810561404811705533607443750388370351
05112493612249319837881569585812759467291755314682518714528569231404359845775746
98574803934567774824230985421074605062371141877954182153046474983581941267398767
559165543946077062914571196477686542167660429831652624386837205668069376
;)

[mrnutty]

s10(2^1000) == 1366
2^1000 == 1071508607186267320948425049060001810561404811705533607443750388370351
05112493612249319837881569585812759467291755314682518714528569231404359845775746
98574803934567774824230985421074605062371141877954182153046474983581941267398767
559165543946077062914571196477686542167660429831652624386837205668069376
;)

could you hint on how you got 2^1000?

[ArkM]

I got it by the brutal force method.
I'm too lazy to install gdb library (probably the simplest solution).
The code below is not carefully tested, I did it for fan, no warranties ;):

class Num {
public:
    struct err { 
        const char* what() const {
            return "Num::err raised";
        }
    };
    Num(const char* pnum = 0);
    Num(const std::string& num);
    Num(unsigned long n);

    std::string toString() const;
    operator const std::string() const {
        return toString();
    }
    Num operator+(const Num& num) const;
    Num operator*(const Num& num) const;
    unsigned long s10() const;
    Num test(unsigned d) { return mult(d); }
private:
    void m10(unsigned n);
    Num mult(unsigned d) const;
    std::string s;
};

inline
std::ostream& operator <<(std::ostream& os, const Num& num)
{
    os << num.toString();
    return os;
}

const char* digits = "0123456789";
const std::string sdigits(digits);

Num Num::operator+(const Num& num) const
{
    std::string res;
    size_t len1 = s.size();
    size_t len2 = num.s.size();
    unsigned p, q, x, y = 0;
    size_t n = (len1 < len2? len2: len1);

    for (size_t i = 0; i < n; ++i) {
        p = (i < len1? s[i]: 0);
        q = (i < len2? num.s[i]: 0);
        x = p + q + y;
        if (x >= 10) {
            x -= 10;
            y = 1;
        } else
            y = 0;
        res += char(x);
    }
    if (y)
        res += '\1';
    Num sum;
    sum.s = res;
    return sum;
}


std::string Num::toString() const
{
    std::string res;
    if (s.size()) {
        size_t n = s.size() - 1;
        for (int i = n; i >= 0; --i)
            res += digits[s[i]];
    }
    return res;
}

Num::Num(const char* pnum)
{
    int len;
    if (!pnum || !*pnum)
        s = "\0";
    else if (strspn(pnum,digits) == (len=strlen(pnum))) {
        if (!*pnum)
            s = "0";
        else {
            int n = len - 1;
            for (int i = n; i >= 0; --i)
                s += (char)sdigits.find(pnum[i]);
        }
    } else throw Num::err();
}

Num::Num(const std::string& num)
{
    size_t pos, n = num.size();
    if (n) {
        pos = num.find_first_not_of(digits);
        if (pos != std::string::npos)
            throw Num::err();
        for (int i = --n; i >= 0; --i)
            s += (char)sdigits.find(num[i]);
    } else s = "\0"; 
}

Num::Num(unsigned long n)
{
    unsigned d;
    do {
        d = n % 10;
        s += char(d);
        n /= 10;
    } while (n);
}

Num Num::operator *(const Num& num) const
{
    Num prod("0");
    Num x("0");
    for (size_t i = 0; i < num.s.size(); ++i) {
        x = mult(num.s[i]);
        x.m10(i);
        prod = prod + x;
    }
    return prod;
}

unsigned long Num::s10() const
{
    unsigned long sum = 0;
    for (size_t i = 0; i < s.size(); ++i)
        sum += s[i];
    return sum;
}

void Num::m10(unsigned n)
{
    if (n) {
        if (n > 1000000) // debug stage only
            throw Num::err();
        s.insert(0,n,'\0');
    }
}

Num Num::mult(unsigned d) const
{
    if (d > 9)
        throw Num::err();
    if (d == 0 || s == "\0")
        return Num("0");
    std::string res;
    size_t n = s.size();
    unsigned x, y = 0;

    for (size_t i = 0; i < n; ++i) {
        x = s[i]*d + y;
        y = x / 10;
        res += char(x % 10);
    }
    if (y)
        res += (char)y;
    Num mul;
    mul.s = res;
    return mul;
}

using std::cout;
using std::endl;

int main()
{
    Num K("1024");
    Num Two100("1024");
    for (int i = 0; i < 99; ++i)
        Two100 = Two100 * K;
    cout << "s10(2^1000) == " << Two100.s10() << endl;
    cout << "2^1000 == " << Two100 << endl;
    return 0;
}

[mrnutty]

I got it by the brutal force method.
I'm too lazy to install gdb library (probably the simplest solution).
The code below is not carefully tested, I did it for fan, no warranties ;):

class Num {
public:
    struct err { 
        const char* what() const {
            return "Num::err raised";
        }
    };
    Num(const char* pnum = 0);
    Num(const std::string& num);
    Num(unsigned long n);

    std::string toString() const;
    operator const std::string() const {
        return toString();
    }
    Num operator+(const Num& num) const;
    Num operator*(const Num& num) const;
    unsigned long s10() const;
    Num test(unsigned d) { return mult(d); }
private:
    void m10(unsigned n);
    Num mult(unsigned d) const;
    std::string s;
};

inline
std::ostream& operator <<(std::ostream& os, const Num& num)
{
    os << num.toString();
    return os;
}

const char* digits = "0123456789";
const std::string sdigits(digits);

Num Num::operator+(const Num& num) const
{
    std::string res;
    size_t len1 = s.size();
    size_t len2 = num.s.size();
    unsigned p, q, x, y = 0;
    size_t n = (len1 < len2? len2: len1);

    for (size_t i = 0; i < n; ++i) {
        p = (i < len1? s[i]: 0);
        q = (i < len2? num.s[i]: 0);
        x = p + q + y;
        if (x >= 10) {
            x -= 10;
            y = 1;
        } else
            y = 0;
        res += char(x);
    }
    if (y)
        res += '\1';
    Num sum;
    sum.s = res;
    return sum;
}


std::string Num::toString() const
{
    std::string res;
    if (s.size()) {
        size_t n = s.size() - 1;
        for (int i = n; i >= 0; --i)
            res += digits[s[i]];
    }
    return res;
}

Num::Num(const char* pnum)
{
    int len;
    if (!pnum || !*pnum)
        s = "\0";
    else if (strspn(pnum,digits) == (len=strlen(pnum))) {
        if (!*pnum)
            s = "0";
        else {
            int n = len - 1;
            for (int i = n; i >= 0; --i)
                s += (char)sdigits.find(pnum[i]);
        }
    } else throw Num::err();
}

Num::Num(const std::string& num)
{
    size_t pos, n = num.size();
    if (n) {
        pos = num.find_first_not_of(digits);
        if (pos != std::string::npos)
            throw Num::err();
        for (int i = --n; i >= 0; --i)
            s += (char)sdigits.find(num[i]);
    } else s = "\0"; 
}

Num::Num(unsigned long n)
{
    unsigned d;
    do {
        d = n % 10;
        s += char(d);
        n /= 10;
    } while (n);
}

Num Num::operator *(const Num& num) const
{
    Num prod("0");
    Num x("0");
    for (size_t i = 0; i < num.s.size(); ++i) {
        x = mult(num.s[i]);
        x.m10(i);
        prod = prod + x;
    }
    return prod;
}

unsigned long Num::s10() const
{
    unsigned long sum = 0;
    for (size_t i = 0; i < s.size(); ++i)
        sum += s[i];
    return sum;
}

void Num::m10(unsigned n)
{
    if (n) {
        if (n > 1000000) // debug stage only
            throw Num::err();
        s.insert(0,n,'\0');
    }
}

Num Num::mult(unsigned d) const
{
    if (d > 9)
        throw Num::err();
    if (d == 0 || s == "\0")
        return Num("0");
    std::string res;
    size_t n = s.size();
    unsigned x, y = 0;

    for (size_t i = 0; i < n; ++i) {
        x = s[i]*d + y;
        y = x / 10;
        res += char(x % 10);
    }
    if (y)
        res += (char)y;
    Num mul;
    mul.s = res;
    return mul;
}

using std::cout;
using std::endl;

int main()
{
    Num K("1024");
    Num Two100("1024");
    for (int i = 0; i < 99; ++i)
        Two100 = Two100 * K;
    cout << "s10(2^1000) == " << Two100.s10() << endl;
    cout << "2^1000 == " << Two100 << endl;
    return 0;
}

how thats really complicated. I 'm only a beginner. maybe this problem in project euler is not for me.
Thanks for your help

[Rashakil Fol]

how thats really complicated. I 'm only a beginner. maybe this problem in project euler is not for me.
Thanks for your help

He made it waaay unnecessarily complicated.

#include <iostream>
#include <vector>

std::vector<int> mulTwo(const std::vector<int>& v) {
  std::vector<int> builder;
  int carry = 0;
  for (int i = 0; i < v.size(); ++i) {
    int s = v[i] * 2 + carry;
    carry = (s >= 10);
    builder.push_back(s[i] - 10 * carry)
  }
  if (carry)
    builder.push_back(1);
  return builder;
}

int sum(const std::vector<int>& v) {
  int sum = 0;
  for (int i = 0; i < v.size(); ++i)
    sum += v[i];
  return sum;
}

int main() {
  std::vector<int> n(1, 1);
  for (int i = 0; i < 1000; ++i) {
    n = mulTwo(n);
  }
  std::cout << sum(n);
}