Polynomial Recursion

A sequence of polynomials g k ( x ) g_k(x) is defined recursively as follows. g 0 ( x ) = x ; g k + 1 ( x ) = g k ( x 2 + 2 x ) g k ( x ) g_0(x)=x; \ g_{k+1}(x)=g_k(x^2+2x)-g_k(x) Find the last three digits of the coefficient of x 2 x^2 in g 299 ( x ) g_{299}(x) .


The answer is 333.

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.

9 solutions

Nishant Rai
May 20, 2014

Let us take g k g_k to be a general polynomial, and thus write it as,

g k = i = 0 n ( a i x i ) g_k = \sum_{i=0}^n ( a_i \cdot x^i ) ( Where n is the degree... some number )

So, putting this in the given recursive relation, and also noticing that in,

g k 1 ( x ( x + 2 ) ) g_{k-1} (x \cdot ( x + 2 ) ) ,

we cannot get coefficients of x 2 x^2 anywhere except in

( x ( x + 2 ) ) 2 a n d ( x ( x + 2 ) ) . (x \cdot ( x + 2 ) ) ^2 and (x \cdot ( x + 2 ) ).

Let A k A_k be the coefficient of x 2 x^2 and B k B_k be the coefficient of x. We get a recursive relation for the coefficients as,

A k = ( 3 A k 1 ) + B k 1 A_k = (3 \cdot A_{k-1} ) + B_{k-1}

B k = B k 1 B_k = B_{k-1} (Thus B k = B 0 B_k = B_0 for all k) Solving this recurrence relation will give us, A k = ( 3 k 1 ) / 2 A_k = (3^k -1)/2 . This can be obtained by repeatedly substituting it in the relation(Short way) or by some other prevalent methods.

Now , putting k=299 we just have to find the remainder with 1000, which can be easily done using binomial. Writing 3 299 3^{299} as 3 ( ( 10 1 ) 149 ) 3 * ((10-1)^{149}) . We leave the terms with 1000 as a factor alone and get the answer as 333.

This solution is much easier than the intended one (since we intentionally avoided calculus approaches), and all submitted correct solutions followed the same strategy to show that the answer is the last three digits of ( 3 299 1 ) / 2 (3^{299}-1)/2 . This solution, and many others, contains a slight mistake: it is not enough to know 3 299 1 3^{299}-1 modulo 1000 1000 , one needs 2000 , 2000, because we must eventually divide by 2 2 (indeed, ( 1667 1 ) / 2 = 833 (1667-1)/2=833 . A few solutions avoided this mistake; some solutions were also rather sketchy.

Calvin Lin Staff - 7 years ago
Tan Kiat
May 20, 2014

Consider the recursive polynomials g k ( x ) g_{k}(x) ,

g 0 ( x ) g_{0}(x) = x x and g k + 1 ( x ) g_{k+1}(x) = g k ( x 2 g_{k}(x^{2} + + 2 x ) 2x) - g k ( x ) g_{k}(x)

Thus,

g 1 ( x ) g_{1}(x)

= x 2 x^{2} + + 2 x 2x - x x

= x 2 x^{2} + + x x

Going on,

g 2 ( x ) g_{2}(x)

= g 1 ( x 2 g_{1}(x^{2} + + 2 x ) 2x) - g 1 ( x ) g_{1}(x)

= ( x 2 (x^{2} + + 2 x ) 2 2x)^{2} - x 2 x^{2} - x x by substituting g 1 ( x ) g_{1}(x) back into the expression previously obtained.

= ... + + 4 x 2 4x^{2} + + x x , where degrees of x x greater than 2 can be ignored as it does not affect the coefficient of x 2 x^{2}

Repeat the process for further values of k k to obtain the coefficient of x x and x 2 x^{2}

g 3 ( x ) g_{3}(x) = ... + + 13 x 2 13x^{2} + + x x

g 4 ( x ) g_{4}(x) = ... + + 40 x 2 40x^{2} + + x x

Hence, observe the pattern for g k ( x ) g_{k}(x) for coefficient of x 2 x^{2} that is as follows

g 1 ( x ) g_{1}(x) -> 3 1 1 2 \frac{3^{1}-1}{2} x 2 x^{2} = x 2 x^{2}

g 2 ( x ) g_{2}(x) -> 3 2 1 2 \frac{3^{2}-1}{2} x 2 x^{2} = 4 x 2 4x^{2}

g 3 ( x ) g_{3}(x) -> 3 3 1 2 \frac{3^{3}-1}{2} x 2 x^{2} = 13 x 2 13x^{2}

g 4 ( x ) g_{4}(x) -> 3 4 1 2 \frac{3^{4}-1}{2} x 2 x^{2} = 40 x 2 40x^{2}

g k ( x ) g_{k}(x) -> 3 k 1 2 \frac{3^{k}-1}{2} x 2 x^{2}

Hence, we need to determine the last 3 digit for 3 299 3^{299} to determine the coefficient of x 2 x^{2} of g 299 ( x ) g_{299}(x)

The method I use is to use binomial theorem as follows :

3 299 3^{299}

= 3. 3 298 3.3^{298}

= 3. 9 149 3.9^{149}

= 3 ( 10 1 ) 149 3(10-1)^{149}

= 3 ( 3( ( 1 ) 149 (-1)^{149} + ( 149 1 ) ( 1 ) 148 ( 10 ) 1 \bigl(\begin{matrix}149\\ 1\end{matrix} \bigr)(-1)^{148}(10)^{1} + ( 149 2 ) ( 1 ) 147 ( 10 ) 2 ) \bigl(\begin{matrix}149\\ 2\end{matrix} \bigr)(-1)^{147}(10)^{2} )

= 3 ( 3( 1 + 1490 1102600 ) -1+1490-1102600)

= 333 -333

which also means that the last 3 digit is

= 1000 333 1000 - 333

= 667 667

Hence, reapply the last 3 digits of 3 299 3^{299} to the general formula, we get,

g k ( x ) g_{k}(x) -> 3 k 1 2 \frac{3^{k}-1}{2} x 2 x^{2}

g 299 ( x ) g_{299}(x) -> 3 299 1 2 \frac{3^{299}-1}{2} x 2 x^{2}

= 666 2 \frac{666}{2} x 2 x^{2}

= 333 333 x 2 x^{2}

Thus, the coefficient of x 2 x^{2} in g 299 ( x ) g_{299}(x) is 333.

Slight inaccuracy: it is not enough to know 3 299 1 3^{299}-1 modulo 1000 1000 , one needs 2000 , 2000, because divided by 2 2 later on.

Calvin Lin Staff - 7 years ago
Joe Tomkinson
May 20, 2014

To get a feel of the recurrence we calculate the first few terms -

g 1 ( x ) = g 0 ( x 2 + 2 x ) g 0 ( x ) = x 2 + 2 x x = x 2 + x g 2 ( x ) = ( ( x 2 + 2 x ) 2 + x 2 + 2 x ) ( x 2 + x ) = x 4 + 4 x 3 + 4 x 2 + x 2 + 2 x x 2 x = x 4 + 4 x 3 + 4 x 2 + x g_1(x) = g_0(x^2 + 2x) - g_0(x) = x^2 + 2x - x = x^2 + x\\ g_2(x) = ((x^2+2x)^2 + x^2 + 2x) - (x^2+x)\\ \qquad \, \, = x^4 + 4x^3 + 4x^2 + x^2 + 2x - x^2 - x\\ \qquad \, \, = x^4 + 4x^3 + 4x^2 + x

Now we notice that x 3 x^3 terms or higher are irrelevant to the x 2 x^2 coefficient - they are never reduced down to x 2 x^2 or lower terms again, so can have no effect on the coefficient of x 2 x^2 . This means we can just look at the recurrence in terms of the x 2 x^2 and x x terms, casting out any higher terms.

Finding the recurrence and general formula for the x 2 x^2 term -

Starting from g k ( x ) = a x 2 + b x + O ( x 3 ) g_k(x) = ax^2 + bx + \mathcal{O}(x^3) ,

g k + 1 ( x ) = a ( x 2 + 2 x ) 2 + b ( x 2 + 2 x ) ( a x 2 + b x ) + O ( x 3 ) = a x 4 + 4 a x 3 + 4 a x 2 + b x 2 + 2 b x a x 2 b x + O ( x 3 ) = ( 3 a + b ) x 2 + b x + O ( x 3 ) g_{k+1}(x) = a(x^2 + 2x)^2 + b(x^2 + 2x) - (ax^2 + bx) + \mathcal{O}(x^3)\\ \qquad \quad \, \, = ax^4 + 4ax^3 + 4ax^2 + bx^2 + 2bx - ax^2 - bx + \mathcal{O}(x^3)\\ \qquad \quad \, \, = (3a+b)x^2 + bx + \mathcal{O}(x^3)

Using a k a_k to refer to the coefficient of x 2 x^2 in g k ( x ) g_k(x) , we can write that a k + 1 = 3 a k + b a_{k+1} = 3a_k + b , where b b is the coefficient of x x in g 0 ( x ) g_0(x) (or any other g k ( x ) g_k(x) , as the recurrence found above tells us it does not change). In this particular case, a k + 1 = 3 a k + 1 a_{k+1} = 3a_k + 1 .

To turn this into a homogeneous recurrence equation, we note that a k + 2 3 a k + 1 = 1 = a k + 1 3 a k a_{k+2} - 3a_{k+1} = 1 = a_{k+1} - 3a_k , so that a k + 2 = 4 a k + 1 3 a k \\ \qquad a_{k+2} = 4a_{k+1} - 3a_k .

We now solve this in the usual manner - the characteristic quadratic here is x 2 = 4 x 3 , x 2 4 x + 3 = 0 , ( x 3 ) ( x 1 ) = 0 x^2 = 4x - 3, x^2 - 4x + 3 = 0, (x-3)(x-1) = 0 , so a k a_k can be expressed in the form A ( 3 ) k + B ( 1 ) k = A ( 3 ) k + B A(3)^k + B(1)^k = A(3)^k + B . Looking at the first two polynomials gives the simultaneous equations

A ( 3 ) 0 + B = A + B = 0 A ( 3 ) 1 + B = 3 A + B = 1 2 A = 1 , A = 1 2 , B = 1 2 \qquad A(3)^0 + B = A+B = 0 \\ \qquad A(3)^1 + B = 3A + B = 1 \\ \qquad 2A = 1, A = \frac{1}{2}, B = -\frac{1}{2}

which means that

a k = 3 k 1 2 \qquad a_k = \frac{3^k - 1}{2} .

Finding the last 3 3 digits of the x 2 x^2 coefficient for g 299 ( x ) g_{299}(x) -

In particular, the x 2 x^2 coefficient in g 299 ( x ) g_{299}(x) is 3 299 1 2 \frac{3^{299} - 1}{2} . This is impractical to calculate, but this can be mostly avoided in the following manner -

3 299 1 2 = 3 300 1 2 + 3 299 3 300 2 = 3 300 1 2 + 3 299 ( 1 3 ) 2 = 3 300 1 2 3 299 \qquad \frac{3^{299} - 1}{2} = \frac{3^{300} - 1}{2} + \frac{3^{299} - 3^{300}}{2} \\ \qquad \qquad \: \; = \frac{3^{300} - 1}{2} + \frac{3^{299}(1-3)}{2} \\ \qquad \qquad \: \; = \frac{3^{300} - 1}{2} - 3^{299}

If we now find 3 300 1 2 ( m o d 1000 ) \frac{3^{300}-1}{2} \pmod{1000} , this should make it easier to find 3 299 1 2 ( m o d 1000 ) \frac{3^{299}-1}{2} \pmod{1000} .

Using the generalisation to Fermat's little theorem, that x ϕ ( n ) 1 ( m o d n ) x^{\phi(n)} \equiv 1 \pmod{n} , we have that 3 100 1 ( m o d 125 ) 3^{100} \equiv 1 \pmod{125} , because ϕ ( 125 ) = 125 ( 4 5 ) = 100 \phi(125) = 125(\frac{4}{5}) = 100 . This means 3 300 1 ( m o d 125 ) 3^{300} \equiv 1 \pmod{125} .

Then, by simple calculation, we find 3 4 9 2 1 ( m o d 16 ) 3^4 \equiv 9^2 \equiv 1 \pmod{16} , so 3 300 1 ( m o d 16 ) 3^{300} \equiv 1 \pmod{16} .

Together these imply 3 300 1 ( m o d 2000 ) 3^{300} \equiv 1 \pmod{2000} . This means 3 300 1 0 ( m o d 2000 ) 3^{300} - 1 \equiv 0 \pmod{2000} and 3 300 1 2 0 ( m o d 1000 ) \frac{3^{300}-1}{2} \equiv 0 \pmod{1000} .

Putting this into the earlier equations, we have that

3 299 1 2 3 299 ( m o d 1000 ) \qquad \quad \frac{3^{299}-1}{2} \equiv -3^{299} \pmod{1000}

But 3 300 1 ( m o d 1000 ) 3^{300} \equiv 1 \pmod{1000} . If we let x = 3 299 x=3^{299} , then 3 x 1 ( m o d 1000 ) 3x \equiv 1 \pmod{1000} . A little consideration throws up x = 667 x=667 as a solution, which is unique because of the uniqueness of multiplicative inverses. Therefore, 3 299 667 ( m o d 1000 ) 3^{299} \equiv 667 \pmod{1000} .

Putting this back in,

3 299 1 2 3 299 1000 667 333 ( m o d 1000 ) \qquad \quad \frac{3^{299}-1}{2} \equiv -3^{299} \equiv 1000-667 \equiv 333 \pmod{1000}

Which means that the last 3 3 digits of the x 2 x^2 coefficient in g 299 ( x ) g_{299}(x) are 333 \underline{333} .

Slight inaccuracy: it is not enough to know 3 299 1 3^{299}-1 modulo 1000 1000 , one needs 2000 , 2000, because divided by 2 2 later on.

Calvin Lin Staff - 7 years ago

By induction we can easily prove that the coefficient of x^2 in g_{n}(x) is \frac {3^n - 1}{2}

It's easy to check that: 3^20 \equiv 4401 \pmod{10000} Then 3^40 \equiv 8801 \pmod{10000}, 3^60 \equiv 3201 \pmod{10000}, 3^80 \equiv 7601 \pmod{10000}, 3^100 \equiv 2001 \pmod{10000},

Hence 3^300 \equiv 2001 \pmod{10000} Denote 3^300=10000 \times k + 2001 Then k \equiv 0 \pmod{3} Thus 3^299 \equiv 0667 \pmod{10000} Therefore \frac {3^299-1}{2} \equiv 333 \pmod{1000} The answer is 333.

A very sketchy solution, which, however, avoids the most common mistake.

Calvin Lin Staff - 7 years ago

Let the coefficient of x 2 x^2 and x x in g k ( x ) g_k(x) be defined by the functions m ( k ) m(k) and n ( k ) n(k) respectively for all positive integers k > 0 k>0 . Now we should find the coefficient of x 2 x^2 and x x in g k ( x 2 + 2 x ) g_k(x^2 + 2x) . Note that the term x 2 x^2 will occur in the expansion of g k ( x 2 + 2 x ) g_k(x^2 + 2x) only in the terms ( x 2 + 2 x ) 2 (x^2 + 2x)^2 and x 2 + 2 x x^2 + 2x , because in all other terms in the expansion of g k ( x 2 + 2 x ) g_k(x^2 + 2x) , the power of x x will be greater than 2 2 . Similarly the term x x will occur in the expansion of g k ( x 2 + 2 x ) g_k(x^2 + 2x) only in the term x 2 + 2 x x^2 + 2x . Now coefficient of x 2 + 2 x x^2 + 2x in g k ( x 2 + 2 x ) g_k(x^2 + 2x) is n ( k ) n(k) , and coefficient of ( x 2 + 2 x ) 2 (x^2 + 2x)^2 in g k ( x 2 + 2 x ) g_k(x^2 + 2x) is m ( k ) m(k) . Since coefficient of x x in x 2 + 2 x x^2 + 2x is 2 2 , coefficient of x x in g k ( x 2 + 2 x ) g_k(x^2 + 2x) will be 2 n ( k ) 2n(k) . Again since coefficient of x 2 x^2 in x 2 + 2 x x^2 + 2x is 1 1 and that in ( x 2 + 2 x ) 2 (x^2 + 2x)^2 is 4 4 , coefficient of x 2 x^2 in g k ( x 2 + 2 x ) g_k(x^2 + 2x) will be 4 m ( k ) + n ( k ) 4m(k) + n(k) . Now coefficient of x 2 x^2 in g k ( x ) g_k(x) is m ( k ) m(k) , and that of x x in g k ( x ) g_k(x) is n ( k ) n(k) . Thus coefficient of x 2 x^2 in g k + 1 ( x ) g_{k+1}(x) = 4 m ( k ) + n ( k ) m ( k ) = 3 m ( k ) + n ( k ) 4m(k) + n(k) - m(k)= 3m(k) + n(k) , and coefficient of x x in g k + 1 ( x ) g_{k+1}(x) = 2 n ( k ) n ( k ) = n ( k ) 2n(k)-n(k) = n(k) . Thus we obtain m ( k + 1 ) = 3 m ( k ) + n ( k ) m(k+1)= 3m(k) + n(k) , n ( k + 1 ) = n ( k ) n(k+1)= n(k) . Hence we can conclude that n ( k ) n(k) is constant. Since n ( 0 ) = 1 n(0)= 1 , n ( k ) = 1 n(k)= 1 for all k k . Thus m ( k + 1 ) = 3 m ( k ) + 1 m(k+1)= 3m(k)+1 . To apply characteristic equation, we should establish a relation between m ( k + 2 ) m(k+2) , m ( k + 1 ) m(k+1) , and m ( k ) m(k) . Note that m ( k + 2 ) = 3 m ( k + 1 ) + 1 = 3 m ( k + 1 ) + m ( k + 1 ) 3 m ( k ) = 4 m ( k + 1 ) 3 m ( k ) m(k+2)= 3m(k+1) + 1= 3m(k+1) + m(k+1) - 3m(k)= 4m(k+1) - 3m(k) . This implies m ( k + 2 ) 4 m ( k + 1 ) + 3 m ( k ) = 0 m(k+2) - 4m(k+1) + 3m(k)= 0 . Hence the characteristic equation of this recurrence relation will be x 2 4 x + 3 = 0 x^2 - 4x + 3= 0 . Note that x 2 4 x + 3 = ( x 1 ) ( x 3 ) x^2 - 4x + 3= (x-1)(x-3) . Thus the roots of the characteristic equation will be 1 1 and 3 3 . Thus we can conclude that for all k k , m ( k ) = p 1 k + q 3 k = p + q 3 k m(k)= p*1^k + q*3^k= p + q*3^k , where p p and q q are constants. Now the values of p p and q q have to be found. Note that m ( 0 ) = 0 m(0)= 0 , so p + q = 0..... ( 1 ) p+q= 0 .....(1) , and note that m ( 1 ) = 3 m ( 0 ) + 1 = 1 m(1)= 3m(0)+1= 1 , so p + 3 q = 1..... ( 2 ) p+3q= 1 .....(2) . Subtracting equation 1 1 from equation 2 2 , we obtain 2 q = 1 q = 1 2 2q= 1 \implies q= \frac{1}{2} . Plugging this value of q q into equation 1 1 , we obtain p = 1 2 p= -\frac{1}{2} . Thus for all k k , m ( k ) = 1 2 + 1 2 3 k = 3 k 1 2 = 3 k 1 + 3 k 2 + . . . + 1 m(k)= -\frac{1}{2} + \frac{1}{2}*3^k = \frac{3^k - 1}{2}= 3^{k-1} + 3^{k-2} + ... + 1 . According to the question k = 299 k= 299 , so we should find the value of 3 299 1 2 \frac{3^{299} - 1}{2} modulo 1000 1000 , which is 333 333 . So our final answer is 333 333 .

"According to the question k = 299 k= 299 , so we should find the value of 3 299 1 2 \frac{3^{299} - 1}{2} modulo 1000 1000 , which is 333 333 . So our final answer is 333 333 ." This is a relatively small part of the problem, but still should have been explained more.

Calvin Lin Staff - 7 years ago
Zef RosnBrick
May 20, 2014

We prove, by induction on k k , that g k ( x ) = x + c k x 2 + x 3 h k g_k(x) = x + c_kx^2 + x^3 \cdot h_k , where h k h_k is some polynomial in x x , so that we need to find c 299 m o d 1000 c_{299} \bmod 1000 . Moreover, we also show that c k = 3 k 1 2 c_k = \frac{3^k - 1}{2} .

Base Case: k = 0 k = 0 : g k ( x ) = x = x + 0 x 2 + x 3 ( 0 ) g_k(x) = x = x + 0 \cdot x^2 + x^3 \cdot (0) , as needed. Moreover, we also have that 0 = 1 1 2 = 3 0 1 2 0 = \frac{1 - 1}{2} = \frac{3^0 - 1}{2} .

Induction Step: Assume that g k ( x ) = x + c k x 2 + x 3 h k g_k(x) = x + c_kx^2 + x^3 \cdot h_k , and c k = 3 k 1 2 c_k = \frac{3^k - 1}{2} . Then, by definition,

g k + 1 ( x ) = g k ( x 2 + 2 x ) g k ( x ) g_{k + 1}(x) = g_k(x^2 + 2x) - g_k(x) = ( x 2 + 2 x ) + c k ( x 2 + 2 x ) 2 + ( x 2 + 2 x ) 3 h k ( x + c k x 2 + x 3 h k ) = (x^2 + 2x) + c_k(x^2 + 2x)^2 + (x^2 + 2x)^3 \cdot h_k - \left( x + c_kx^2 + x^3 \cdot h_k \right) = x + ( 3 c k + 1 ) x 2 + 4 c k x 3 + c k x 4 + ( x 6 + 6 x 5 + 12 x 4 + 7 x 3 ) h k = x + (3c_k + 1)x^2 + 4c_kx^3 + c_kx^4 + (x^6 + 6x^5 + 12x^4 + 7x^3) \cdot h_k = x + ( 3 c k + 1 ) x 2 + x 3 ( 4 c k + c k x + ( x 3 + 6 x 2 + 12 x + 7 ) h k ) = x + (3c_k + 1)x^2 + x^3 \cdot \left( 4c_k + c_kx + (x^3 + 6x^2 + 12x + 7) \cdot h_k \right) ,

and so g k + 1 ( x ) g_{k + 1}(x) is of the necessary form, and moreover, c k + 1 = 3 c k + 1 = 3 3 k 1 2 + 1 = 3 k + 1 3 2 + 2 2 = 3 k + 1 1 2 c_{k + 1} = 3c_k + 1 = 3 \cdot \frac{3^k - 1}{2} + 1 = \frac{3^{k + 1} - 3}{2} + \frac{2}{2} = \frac{3^{k + 1} - 1}{2} .

It remains to calculate c 299 = 3 299 1 2 m o d 1000 c_{299} = \frac{3^{299} - 1}{2} \bmod 1000 . Now, 3 299 = 3 9 149 = 3 ( 10 1 ) 149 3^{299} = 3 \cdot 9^{149} = 3 \cdot (10 - 1)^{149} . By the binomial theorem, this expands to 3 k = 0 149 ( 149 k ) 1 0 k ( 1 ) 149 k 3 \cdot \sum_{k = 0}^{149}{{149 \choose k}10^k(-1)^{149 - k}} which is equivalent to 3 ( ( 149 0 ) 1 0 0 ( 1 ) 149 + ( 149 1 ) 1 0 1 ( 1 ) 148 + ( 149 2 ) 1 0 2 ( 1 ) 1 47 ) m o d 1000 3 \cdot ({149 \choose 0}10^0(-1)^{149} + {149 \choose 1}10^1(-1)^{148} + {149 \choose 2}10^2(-1)^147) \bmod 1000 , since every other term of the sum is divisible by 1000. Furthermore, we see by straightforward calculation that this value is equivalent to 3 ( 1 + 149 10 + 11026 100 1 ) = 3303333 667 m o d 1000 3 \cdot (-1 + 149 \cdot 10 + 11026 \cdot 100 \cdot -1) = -3303333 \equiv 667 \bmod 1000 . Therefore, 3 299 1 2 667 1 2 333 m o d 1000 \frac{3^{299} - 1}{2} \equiv \frac{667 - 1}{2} \equiv 333 \bmod 1000 , and so c 299 = 333 c_{299} = 333 .

Note: This is only one of many ways of calculating 3 299 m o d 1000 3^{299} \bmod 1000 . Another method is to recall that λ ( 1000 ) = 100 \lambda(1000) = 100 where λ ( n ) \lambda(n) is the n n th Carmichael number, and so 3 100 1 m o d 1000 3^{100} \equiv 1 \bmod 1000 . Using the extended Euclidean algorithm, it follows that 3 99 667 m o d 100 3^{99} \equiv 667 \bmod 100 and so 3 299 667 m o d 1000 3^{299} \equiv 667 \bmod 1000 .

Slight inaccuracy: it is not enough to know 3 299 1 3^{299}-1 modulo 1000 1000 , one needs 2000 , 2000, because divided by 2 2 later on. What is called Carmichael number here is the Euler's totient function. Carmichael number is a different, though related, notion.

Calvin Lin Staff - 7 years ago
Michal Forišek
May 20, 2014

Consider a fixed k k . Let g k ( x ) = i = 0 n a n x n g_k(x) = \sum_{i=0}^n a_nx^n . From the formula to compute g k + 1 g_{k+1} we can easily see that the coefficient of x 2 x^2 in g k + 1 g_{k+1} only depends on ( a 0 , a 1 , a 2 ) (a_0,a_1,a_2) , because higher powers of x 2 + 2 x x^2+2x do not contain the term x 2 x^2 . Hence it is sufficient to keep track of the last three coefficients of each polynomial.

Additionally, we can easily see that in each g k g_k the units coefficient is a 0 = 0 a_0=0 (obvious) and the coefficient of x 1 x^1 is a 1 = 1 a_1=1 (easily proved by induction).

This leaves us with a single remaining step: given the coefficient a 2 a_2 of x 2 x^2 in g k g_k , we should compute the coefficient of x 2 x^2 in g k + 1 g_{k+1} . From the definition of g k + 1 g_{k+1} we easily obtain that the new coefficient is 4 a 2 + a 1 a 2 = 3 a 2 + a 1 = 3 a 2 + 1 4a_2 + a_1 - a_2 = 3a_2 + a_1 = 3a_2+1 .

Together with the initial condition that in g 0 g_0 the coefficient of x 2 x^2 is 0 0 , this produces the sequence 0, 1, 4, 13, 40, 121, 364, ... Note that the initial terms of this sequence can also be obtained by completely evaluating the first few terms of our polynomial sequence. And having these terms, guessing the pattern is trivial.

We can now use the obtained recurrence to compute the required coefficient in g 299 g_{299} directly (possibly doing all operations modulo 1000 to avoid large numbers). Alternately, we may note that our coefficient in g i g_i can be written as ( 3 i 1 ) / 2 (3^i-1)/2 .

"We can now use the obtained recurrence to compute the required coefficient in g 299 g_{299} directly (possibly doing all operations modulo 1000 to avoid large numbers). Alternately, we may note that our coefficient in g i g_i can be written as ( 3 i 1 ) / 2 (3^i-1)/2 ." A computer was probably used, though the problem is basically solved by hand.

Calvin Lin Staff - 7 years ago
Zhang Shaoshi
May 20, 2014

g 0 ( x ) = x g_{0}(x)=x , and coefficient of x 2 x^2 is 0, g 1 ( x ) = x 2 + x g_{1}(x)=x^2+x , and coefficient of x 2 x^2 is 1, g 2 ( x ) = x 4 + 4 x 3 + 4 x 2 + x g_{2}(x)=x^4+4x^3+4x^2+x , and coefficient of x 2 x^2 is 4, then for g 3 g_{3} , we only need to focus the quadratic terms, which is 4 ( x 2 + 2 x ) 2 4 x 2 4(x^2+2x)^2-4x^2 , (the first term is from g 3 g_{3} and the second term is from g 2 g_{2} .) And coefficient of x 2 x^2 in g 3 g_{3} is 40. Now we can let the coefficient of g 0 ( x ) g_{0}(x) be a 0 a_{0} and so on. Then a 0 = 0 , a 1 = 1 , a 2 = 4 , a 3 = 13 , a 4 = 40.... , a n = 3 a n 1 + 1 a_{0}=0, a_{1}=1,a_{2}=4,a_{3}=13, a_{4}=40....,a_{n}=3a_{n-1}+1 , and therefore a n = 3 ( 3 a n 2 + 1 ) + 1 = 3 2 a n 2 + 3 + 1 = 3 2 ( 3 a n 1 ) + 3 + 1 = . . . = 3 n 1 + 3 n 2 + 3 n 3 + . . . + 3 2 + 3 + 1 = ( 3 n 1 ) / 2 a_{n}=3(3a_{n-2}+1)+1=3^2a_{n-2}+3+1=3^2(3a_{n-1})+3+1= ... =3^{n-1}+3^{n-2}+3^{n-3}+...+3^2+3+1=(3^n-1)/2 So now we need to figure out the last three digits of ( 3 299 1 ) / 2 (3^{299}-1)/2 . And we know the last 3 digits of power of 3 repeats every 100 terms , i.e. the last 3 digits of 3 0 3^0 is 001 001 and it is the same as 3 100 3^{100} . Therefore the last three digits of 3 299 3^{299} must be 667 667 in order to let the last three digits of 3 300 3^{300} be 001 001 again. Then the last three digits ( 3 299 1 ) / 2 (3^{299}-1)/2 is ( 667 1 ) / 2 = 333 (667-1)/2=333 .

possibly feature Slight inaccuracy: it is not enough to know 3 299 1 3^{299}-1 modulo 1000 1000 , one needs 2000 , 2000, because divided by 2 2 later on.

Calvin Lin Staff - 7 years ago
Calvin Lin Staff
May 13, 2014

Define polynomial f k ( x ) f_k(x) as g k ( x 1 ) g_k(x-1) . Then f 0 ( x ) = x 1 f_0(x)=x-1 and the recursive equation rewrites as follows: f k + 1 ( x ) = g k + 1 ( x 1 ) = g k ( ( x 1 ) 2 + 2 ( x 1 ) ) g k ( x 1 ) = f_{k+1}(x)=g_{k+1}(x-1)=g_k((x-1)^2+2(x-1))-g_k(x-1)= = g k ( x 2 1 ) g k ( x 1 ) = f k ( x 2 ) f k ( x ) =g_k(x^2-1)-g_k(x-1)=f_k(x^2)-f_k(x)

The first few polynomials f i ( x ) f_i(x) are:

f 1 ( x ) = x 2 x f 2 ( x ) = x 4 2 x 2 + x f 3 ( x ) = x 8 3 x 4 + 3 x 2 x \begin{aligned} f_1(x) &=x^2-x \\ f_2(x) &=x^4-2x^2+x\\ f_3(x) &=x^8-3x^4+3x^2-x\\ \end{aligned}

Notice how the binomial coefficients appear. One can prove by induction that for all k 1 k\geq 1 f k ( x ) = i = 0 k k ! i ! ( k i ) ! ( 1 ) k i x 2 i f_k(x)=\sum \limits_{i=0}^k \frac{k!}{i!(k-i)!} (-1)^{k-i} x^{2^i} Therefore, g k ( x ) = i = 0 k k ! i ! ( k i ) ! ( 1 ) k i ( x + 1 ) 2 i g_k(x)=\sum \limits_{i=0}^k \frac{k!}{i!(k-i)!} (-1)^{k-i} (x+1)^{2^i} The coefficient of x 2 x^2 in g k ( x ) g_k(x) is i = 0 k k ! i ! ( k i ) ! ( 1 ) k i 2 i ( 2 i 1 ) 2 \sum \limits_{i=0}^{k} \frac{k!}{i!(k-i)!} (-1)^{k-i} \frac{2^i(2^i-1)}{2} . This equals 1 2 ( i = 0 k k ! i ! ( k i ) ! ( 1 ) k i 2 2 i i = 0 k k ! i ! ( k i ) ! ( 1 ) k i 2 i ) = ( 1 + 4 ) k ( 1 + 2 ) k 2 = 3 k 1 2 \frac{1}{2}\left( \sum \limits_{i=0}^{k} \frac{k!}{i!(k-i)!} (-1)^{k-i} 2^{2i} - \sum \limits_{i=0}^{k} \frac{k!}{i!(k-i)!} (-1)^{k-i} 2^{i}\right) = \frac{(-1+4)^k-(-1+2)^k}{2} =\frac{3^k-1}{2}

To find the last three digits of 3 299 1 2 \frac{3^{299}-1}{2} , we first note that 3 4 = 81 1 ( m o d 16 ) , 3^4=81\equiv 1 \pmod {16}, so 3 299 3 3 11 ( m o d 16 ) 3^{299} \equiv 3^3 \equiv 11 \pmod {16} . Therefore 3 299 1 2 5 ( m o d 8 ) \frac{3^{299}-1}{2}\equiv 5\pmod 8 . Also, by Euler's theorem, 3 100 1 ( m o d 125 ) 3^{100}\equiv 1 \pmod {125} . So 3 299 1 3 42 ( m o d 125 ) 3^{299}\equiv \frac{1}{3} \equiv 42\pmod {125} . So 3 299 1 2 83 ( m o d 125 ) . \frac{3^{299}-1}{2}\equiv 83 \pmod {125}. Putting these together and considering that 125 1 ( m o d 8 ) 125\equiv 1 \pmod 8 , the last three digits of 3 299 1 2 \frac{3^{299}-1}{2} are 83 + 2 125 = 333. 83+2\cdot 125= 333.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...