Chain Reaction

Algebra Level 3

( 2 2 0 + 1 ) ( 2 2 1 + 1 ) ( 2 2 2 + 1 ) ( 2 2 10 + 1 ) \large (2^{2^0} +1)(2^{2^1} + 1)(2^{2^2} + 1) \cdots (2^{2^{10}} + 1 )

Given that the expression above simplifies to 2 n b 2^n - b , where a , b a,b and n n are positive integers and 0 b < 2 n 1 0 \leq b < 2^{n-1} , find 2 + b + n 2+b+n .


The answer is 2051.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Method 1 : Repeated application of difference of two squares identity , a 2 b 2 = ( a + b ) ( a b ) a^2 -b^2 = (a+b)(a-b) .

Multiply the expression by 1 = 2 1 1 = 2-1 gives

( 2 1 ) ( 2 + 1 ) ( 2 2 + 1 ) ( 2 4 + 1 ) ( 2 8 + 1 ) ( 2 16 + 1 ) ( 2 32 + 1 ) ( 2 64 + 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 2 1 ) ( 2 2 + 1 ) ( 2 4 + 1 ) ( 2 8 + 1 ) ( 2 16 + 1 ) ( 2 32 + 1 ) ( 2 64 + 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 4 1 ) ( 2 4 + 1 ) ( 2 8 + 1 ) ( 2 16 + 1 ) ( 2 32 + 1 ) ( 2 64 + 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 8 1 ) ( 2 8 + 1 ) ( 2 16 + 1 ) ( 2 32 + 1 ) ( 2 64 + 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 16 1 ) ( 2 16 + 1 ) ( 2 32 + 1 ) ( 2 64 + 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 32 1 ) ( 2 32 + 1 ) ( 2 64 + 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 64 1 ) ( 2 64 + 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 128 1 ) ( 2 128 + 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 256 1 ) ( 2 256 + 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 512 1 ) ( 2 512 + 1 ) ( 2 1024 + 1 ) = ( 2 1024 1 ) ( 2 1024 + 1 ) = 2 2048 1 \begin{aligned} &&(2-1)(2+1) (2^2 + 1)(2^4 + 1) (2^8 + 1) (2^{16} + 1)(2^{32} + 1)(2^{64} + 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^2 - 1)(2^2 + 1)(2^4 + 1) (2^8 + 1) (2^{16} + 1)(2^{32} + 1)(2^{64} + 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^4- 1)(2^4 + 1) (2^8 + 1) (2^{16} + 1)(2^{32} + 1)(2^{64} + 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^8-1) (2^8+1)(2^{16} + 1)(2^{32} + 1)(2^{64} + 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^{16}-1)(2^{16} + 1)(2^{32} + 1)(2^{64} + 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^{32} -1)(2^{32} + 1)(2^{64} + 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^{64} - 1)(2^{64} + 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^{128}- 1)(2^{128} + 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^{256} - 1)(2^{256} + 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^{512} - 1)(2^{512} + 1) (2^{1024} + 1) \\ &=& (2^{1024} - 1) (2^{1024} + 1) \\ &=& 2^{2048} - 1 \end{aligned}

Because the base power is minimized, then a = 2 , n = 2048 , b = 1 a + b + n = 2051 a=2, n = 2048,b=1\Rightarrow a+b+n=\boxed{2051} .

Method 2 : Find a general pattern.

The expression represents the product of 11 integers.

Let us try to find the pattern of the product of the first few terms (from left to right),

2 2 0 + 1 = 2 1 + 1 = 3 = 2 2 1 = 2 2 1 1 ( 2 2 0 + 1 ) ( 2 2 1 + 1 ) = 3 × ( 2 2 + 1 ) = 3 × 5 = 15 = 2 4 1 = 2 2 2 1 ( 2 2 0 + 1 ) ( 2 2 1 + 1 ) ( 2 2 2 + 1 ) = 15 × ( 2 4 + 1 ) = 15 × 17 = 2 8 1 = 2 2 3 1 \begin{aligned} && 2^{2^0} + 1 = 2^1 + 1 = 3 = 2^2 - 1 = 2^{2^1} - 1 \\ && (2^{2^0} + 1)(2^{2^1} + 1) = 3 \times (2^2 + 1) = 3 \times5 = 15 = 2^4 - 1 = 2^{2^2} - 1 \\ && (2^{2^0} + 1)(2^{2^1} + 1)(2^{2^2} + 1) = 15 \times (2^4 + 1) = 15\times17 = 2^8 - 1 = 2^{2^3} - 1 \\ \end{aligned}

This suggests that the product of the first n n terms is equal to 2 2 n 1 2^{2^n} - 1 . And this can be proven using induction .

This is obviously true for its base case, n = 0 n=0 gives 2 2 0 + 1 = 2 2 1 1 2^{2^0} + 1 = 2^{2^1} - 1 .

Inductive step: If n = k n=k is true for non-negative integer k k , then the following equation is true.

( 2 2 0 + 1 ) ( 2 2 1 + 1 ) ( 2 2 2 + 1 ) ( 2 2 k + 1 ) = 2 2 k 1 (2^{2^0} + 1)(2^{2^1} + 1)(2^{2^2} + 1) \cdots ( 2^{2^k} + 1)= 2^{2^k} - 1

Multiplying both sides by 2 2 k + 1 2^{2^{k}} + 1 gives ( 2 2 0 + 1 ) ( 2 2 1 + 1 ) ( 2 2 2 + 1 ) ( 2 2 k 1 ) ( 2 2 k + 1 ) = 2 2 k + 1 1 (2^{2^0} + 1)(2^{2^1} + 1)(2^{2^2} + 1) \cdots ( 2^{2^k} - 1)(2^{2^{k}} + 1) = 2^{2^{k+1}} - 1

Which is true as well. Hence our claim is right and so the product of these 11 terms in question is simply 2 2 11 1 = 2 2048 1 2^{2^{11}} - 1 = 2^{2048} - 1 .

And because the base power (2) is already minimized, then a = 2 , n = 2048 , b = 1 a + b + n = 2051 a=2,n=2048,b=1\Rightarrow a+b+n=\boxed{2051} .

Nice question. I've edited the problem for clarity, since otherwise we could have expressed it as 2 2049 ( 2 2048 + 1 ) 2^{2049 } - (2^{2048} + 1) .

Calvin Lin Staff - 5 years, 3 months ago

Good work.

Angel Raygoza - 1 year, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...