Power of 2(Problem 2)

Points : 20

Answer : 102826018491314080

Given the equation 2n=7A2+B2, we have to find odd A and B for each n>2.

For example,
If n=3 then A=1 and B=1.
If n=10 then A=3 and B=31.

The sum of all such As and Bs for n below 22 is 4344.

Find the sum of all such As and Bs for n<111.

Solution

By looking at the above table we can derive the transformation that

If (An-1 + Bn-1)/2 is even
An = (|An-1 - Bn-1|)/2
Bn = (7An-1 +Bn-1)/2
Else if (An-1 + Bn-1)/2 is odd
An = (An-1 + Bn-1)/2
Bn = (|7An-1 - Bn-1|)/2

Here is the judge solution :

Code

View Plain Text

#include<iostream>
using namespace std;
int main()
{
long long x1=1,y1=1,x2,y2,sumx=1,sumy=1,x;
for (int n=4;n<111;n++)
{
x = (x1+y1)/2;
if (x%2==0)
{
x2=(x1-y1)/2.0;
y2=(7*x1+y1)/2.0;
}
else
{
x2=(x1+y1)/2.0;
y2=(7*x1-y1)/2.0;
}
sumx+=x2;
sumy+=y2;
x1=x2;
y1=y2;
}
cout<<sumx+sumy<<endl;
}

#include<iostream>
using namespace std;
int main()
{
    long long x1=1,y1=1,x2,y2,sumx=1,sumy=1,x;
    for (int n=4;n<111;n++)
    {
        x = (x1+y1)/2;
        if (x%2==0)
        {
                   x2=(x1-y1)/2.0;
                   y2=(7*x1+y1)/2.0;
        }
        else
        {
            x2=(x1+y1)/2.0;
            y2=(7*x1-y1)/2.0;
        }
        sumx+=x2;
        sumy+=y2;
        x1=x2;
        y1=y2;
    }
    cout<<sumx+sumy<<endl;
}

Submit your solution

You need to be logged in to submit a solution.

discussions

Striker	software
Q:	in which software this code works ?n
A:	Its a CPP code. Use GNU CPP Compiler.

Kronos	multiple sums
Q:	if a value of n has multiple values of A and B that work, we count them too right?
A:	Multiple values are not possible.

elixir786	multiple answers
Q:	for n =10, is the pair A = 8 and B=24 possible?
A:	No. Both A and B has to be odd as mentioned in the problem statement.

A_A_Lunyov	answer to large
Q:	May be we need find remainder of this sum some modulo?nBecause obviously A and B is about 2^(n/2)nwhich is really large numbers.
A:	Thanks for the catch. The statement will be rectified soon.

KoenR	195
DrKorbin	185
Silence	150
A_A_Lunyov	145
cedricl	145
kozima	145
cgy4ever	135
ProjectYoung	130
pankdm	130
dzetkulic	130

Codefest