need help with a coding homework

>>310708
int sum = 0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
sum += pow(3, i+j);

do some casting

>>310708
∑∑3^i+j = ∑3^i * ∑3^j = ∑3^i (3^(n+1) - 1)/2 = (3^(n+1) - 1)^2 /4

unsigned long long ans_direct(unsigned n){
unsigned long long result = 3;
unsigned long long pow = 3;
while(n){ // compute 3^n+1 by repeated squaring
if(n&1){
result *= pow;
}
pow*=pow;
n>>=1;
}

result--; //3^n+1 - 1
result>>=1; (3^n+1 - 1)/2
result*=result; //(3^n+1 - 1)^2 /4

return result;
}

unsigned long long ans_sum(unsigned n){
unsigned long long result=0;
unsigned long long three_i=1;
unsigned long long three_i_j=1;
for(unsigned i=0; i<=n; i++){
three_i_j=three_i;
for(unsigned j=0; j<=n; j++){
result += three_i_j;
three_i_j*=3;
}
three_i*=3;
}
return result;
}

Protip: n>19 will overflow. since log_2(3) * 21 * 2 - 2 = 64.6~ bits

Sum is equal to ((3^(n+1)-1)/2)^2
Translate that into C, the other algorithms posted here are naive brute force and not efficient

>>311342
good way of starting an argument with the instructor
>nice but this is not a maths course
>but programming is maths
etc...

>>311342
>other algorithms posted here are naive brute force and not efficient

Did you miss the post right above you?

>>311342
What's the method for solving these? Curious

>>312088
(x-1)(1+x+x^2+...+x^n) = x^(n+1) - 1
1+x+x^2+...+x^n = (x^(n+1) - 1) / (x-1)

>>311347
It's the computer that's supposed to be doing the math, not you. So if you want to implement what you did to simplify that and make a tiny MATLAB, then go right ahead.

>>311752
Formatting is important. That post is a lot of effort to decipher, and I imagine no-one bothered. I hope OP didn't, because he's gonna get marked for implementing the algorithm as described.

>>312088
It's just a geometric sum. It's the same principle as figuring out 0.333...=1/3.

Take the sum S=∑3^j [from j=0 to n] and multiple it by its ratio between sequential terms
3^(j+1)/3^j = 3
3S = ∑3^(j+1) [from j=0 to n] = ∑3^j [from j=1 to n+1]

Now subtract the original sum and notice that nearly all the terms cancel out.

3S-S = ∑3^j [from j=1 to n+1] - ∑3^j [from j=0 to n] = ∑3^j [j = n+1 to n+1] + ∑(3^j - 3^j) [from j=1 to n] - ∑3^j [from j=0 to 0] = 3^(n+1) - 3^0

Solve for S:
3^(n+1) - 3^0 = 3S-S = (3-1)*S
S= (3^(n+1) - 3^0) / (3-1)

In general, for a sum of ratio to a power ∑ratio^j [from j=k to n] is equal to (ratio^(n+1) - ratio^k)(ratio - 1). If the ratio is less than 1 then n can become infinite.

ex:
∑3((1/10)^j) [from j=1 to infinity] = 3∑(1/10)^j [from j=1 to infinity] = 3( (1/10)^inf - 1/10^1 ) / (1/10 - 1) = 3( -1/10 ) / (-9/10) = 3*(1/9) = 1/3

>>312099
>Formatting is important

It's not my fault there are no code or math tags on /wsr/

unsigned long long ans_direct(unsigned n){
░░unsigned long long result = 3;
░░unsigned long long pow = 3;
░░while(n){ // compute 3^n+1 by repeated squaring
░░░░if(n&1){
░░░░░░result *= pow;
░░░░}
░░░░pow*=pow;
░░░░n>>=1;
░░}
░░result--; //3^n+1 - 1
░░result>>=1; (3^n+1 - 1)/2
░░result*=result; //(3^n+1 - 1)^2 /4
░░return result;
}

unsigned long long ans_sum(unsigned n){
░░unsigned long long result=0;
░░unsigned long long three_i=1;
░░unsigned long long three_i_j=1;
░░for(unsigned i=0; i<=n; i++){
░░░░three_i_j=three_i;
░░░░for(unsigned j=0; j<=n; j++){
░░░░░░result += three_i_j;
░░░░░░three_i_j*=3;
░░░░}
░░░░three_i*=3;
░░}
░░return result;
}

>>312296
instead of using long long you should error out for large n values

>>312301
>effort

>>312370
>unsigned long long