Expanding Can Be Tedious

Computer Science Level 2

The number

$\huge{(1+\sqrt{2})^{27}}$

can be represented as $x\sqrt{y} + z$ where $x,y$ and $z$ are positive integers.Find $x+y+z$ .

The answer is 18457556054.

6 solutions

Discussions for this problem are now closed

Pi Han Goh
Apr 23, 2014

$(1 + \sqrt 2)^{27} = \left ( \left ( (1 + \sqrt 2)^3 \right )^3 \right )^3$

By binomial expansion, $(a + b \sqrt 2)^3 = (a^3 + 6ab^2) + \sqrt2 (3a^2 b + 2b^3 )$

Let $(x_{n+1}, y_{n+1}) = (x_n^3 + 6x_n y_n^2 , 3x_n^2 y_n + 2y_n^3 )$ with $(x_0, y_0) = (1,1)$

Then $(x_1, y_1) = (7, 5), (x_2, y_2) = (1393, 985 ) , (x_3, y_3) = (10812186007,7645370045)$

Hence, $x + y + z = 10812186007 + 7645370045 + 2 = \boxed{18457556054}$

Thaddeus Abiy
Apr 23, 2014

Let

$t=1+\sqrt{2}$

$t^2=3+2\sqrt{2}=2(1+\sqrt{2}) + 1=2t+1$

$t^{ n+2 }=2t^{ n+1 }+t^{n}$

$t^2=2t+1$

$t^3=5t+2$

$t^4=12t+5$

$t^5=29t+12$

We observe that

$t^n=a_{n}t+a_{n-1}$

where

$a_{n}=2a_{n-1}+a_{n-2}$

for $a_{1}=1$ and $a_{2}=2$

Thus $t^{27}=a_{27}t+a_{26}$

The recursive equation is similar to the Fibonacci equation and similar code can be written to get $a_{n}$

def A(n):
    if n <= 2:
        return n
    a , b = A(n/2 + 1) , A(n/2)
    if n % 2 == 1:
        return a*a + b*b
    else:
        return 2*b*(a - b)

def Coefficients(n):
    a,b=A(n),A(n-1)
    return a,a+b

print sum(Coefficients(27))+2

Running the code yields the answer

$\large{18457556054}$

Look up fast fibonacci algorithms which do not calculate every single term like you did.

The 'standard' computing approach to calculate this quickly, is to repeatedly square and then multiply. Take a look at @Pi Han Goh 's solution, which does the cubing version.

Calvin Lin Staff - 7 years, 1 month ago

Yes,that is the quickest known Fibonacci algorithm. My previous code did unnecessary calculations. This new algorithm works by taking advantage of an expression based on the matrix identity of the Fibonacci sequence. Anyway, for this problem the expression becomes

$A_{2n}=2A_{n}(A_{n+1} - A_{n})$ $A_{2n+1}=A_{n}^2 + A_{n+1}^2$

So A(n) becomes

def A(n):
    if n <= 2:
        return n
    a , b = A(n/2 + 1) , A(n/2)
    if n % 2 == 1:
        return a*a + b*b
    else:
        return 2*b*(a - b)

Thank you for telling me about the algorithm( Fast Doubling ).I didnt know it before. Also thanks for changing the title of the problem.I realized it was wrong after I posted it and was thinking about mailing you to change it.

Thaddeus Abiy - 7 years, 1 month ago

Good problem!

Carlos E. C. do Nascimento - 7 years, 1 month ago

Emanuel Saringan
Jun 1, 2014

I wrote this Java code to solve this problem:

public class Expanding {
    public static void main(String[] args) {
        long a = 1;
        long b = 1;
        for (int i = 1; i <= 26; i++) {
            long tempA = 2 * b + a;
            long tempB = b + a;

            a = tempA;
            b = tempB;
        }

        System.out.println(a + b + 2);
    }
}

Agnishom Chattopadhyay
Jun 7, 2014

It is astonishing to see that no body tried sage:

expand((1+sqrt(2))^27)

Returns

7645370045*sqrt(2) + 10812186007

Or Mathematica

Expand[(1 + Sqrt[2])^27]
= 10812186007 + 7645370045 Sqrt[2]

Bernardo Sulzbach - 6 years, 11 months ago

Bill Bell
Dec 25, 2014

It's inevitable that hackers will do something like this:

(We're lazy and consequently never learn much mathematics.)

Kenny Lau
Sep 5, 2014

java code:

public class brilliant201409061443{
    public static void main(String[] args){
        long x = 0;
        long y = 2;
        long z = 1;
        for(int i=0;i<27;i++){
            long new_x = z+x;
            long new_z = z+2*x;
            x = new_x;
            z = new_z;
        } // (x*sqrt(2)+z)(sqrt(2)+1) = (z+x)sqrt(2)+(z+2x)
        System.out.println(x+y+z);
    }
}

Output: 18457556054

Expanding Can Be Tedious

The answer is 18457556054.

6 solutions

Discussions for this problem are now closed

0 pending reports