## July 2010

**Terse solution**

The recursion formula x_{t+3}=3x_{t+2}-x_{t} with the initial values of x_{0}=3; x_{1}=3; and x_{2}=9; has the following closed formula x_{t} = a^{t} + b^{t} + c^{t}; where a=1+2 cos(20^{�}); b=1-2cos(40^{�}); and c=1-2cos(80^{�}). Since -1<b,c<1 the last two addends are negligible, so x_{t}=round(a^{t}). x_{-1}=0, so bounding the cycle gives us a solution like 10^{27}!-1. A more careful calculation gives 217 * 10^{8}-1 as the cycle length. The smallest n is actually 169,531,249.

**Thanks**

Thanks to Simi Haber, who drew my attention (in his talk "The number of F-matchings in a random tree is almost always a zero residue" given at Noga Alon's combinatorics seminar at Tel-Aviv University) to the cyclic nature of the Fibonacci series modulo N, and thereby gave me the idea for this riddle. The principles applied in this riddle can be used with any recursion formula, and not just with the recursion formula used here. The Fibonacci recursion formula provides one such additional example.

And to Michael Brand for his elaborate solution:

**Elaborate solution**

Consider the following well-known trigonometric equalities:

(1) cos(x+y) = cos(x)cos(y)-sin(x)sin(y).

(2) sin(x+y) = sin(x)cos(y)+sin(y)cos(x).

(3) cos^{2}(x)+sin^{2}(x) = 1.

From these, it is possible to calculate cos(2x) and cos(3x) as a polynomial of cos(x), as follows:

(4) cos(2x) = cos^{2}(x)-sin^{2}(x) = 2cos^{2}(x)-1.

(5) cos(3x) = cos(2x)cos(x)-sin(2x)sin(x) =

= (2cos^{2}(x)-1)cos(x)-(2sin(x)cos(x))sin(x) =

= 2cos^{3}(x)-cos(x)-2cos(x)sin^{2}(x)=4cos^{3}(x)-3cos(x).

The question asks about cos(20^{�}). Equation (5) gives us the ability to express cos(20^{�}) in terms of cos(3*20^{�})=cos(60^{�}), which is known to be 0.5.

(6) 0.5=cos(60^{�})=4*cos^{3}(20^{�})-3cos(20^{�}).

In other words, instead of trying to calculate cos(20^{�}) explicitly, we can simply treat it as a solution to the polynomial

(7) 4X^{3} - 3X - 0.5 = 0.

or, in integer coefficients,

(8) 8X^{3} - 6X – 1 = 0.

Notably, cos(60^{�})=cos(60^{�}+360^{�})=cos(60^{�}+720^{�}), so the other two solutions to this cubic polynomial are cos((60^{�}+360^{�})/3)=cos(140^{�}) and cos((60^{�}+720^{�})/3)=cos(260^{�}).However, the question does not ask about cos(20^{�}) directly. It asks about 1+2cos(20^{�}). If we substitute

(9) Y=1+2X → X = (Y-1)/2,

into equation (8) we get

(10) 8((Y-1)/2) ^{3}-6((Y-1)/2)-1=0 → (Y^{3}-3Y^{2}+3Y-1) + (-3Y+3) -1 = Y^{3}-3Y^{2}+1 = 0.

We know, therefore, that the three solutions to the polynomial Y^{3}-3Y^{2}+1 = 0 are Y_{1}=1+2cos(20^{�}), Y_{2}=1+2cos(140^{�}) and Y_{3}=1+2cos(260^{�}).

Consider now, a sequence, a_{0}, a_{1}, a_{2}, ..., where a_{0}, a_{1} and a_{2} are determined to be some constants, and for any t>2, a_{t}=3a_{t-1}-a_{t-3}. Because 1+2cos(20^{�}), 1+2cos(140^{�}) and 1+2cos(260^{�}) all solve the polynomial Y^{3} - 3Y^{2} + 1 = 0, for each of them, the sequence 1, Y, Y^{2}, Y^{3}, ... satisfies the recursion formula (even though it may have different initial conditions than a_{0}, a_{1}, a_{2}).

However, because (1,Y_{1},Y_{1}^{2}), (1,Y_{2},Y_{2}^{2}), (1,Y_{3},Y_{3}^{2}) are three linearly independent vectors, for any choice of (a_{0},a_{1},a_{2}) one can find linear coefficients A, B and C, such that

(11) A(1,Y1,Y12)+B(1,Y2,Y22)+C(1,Y3,Y32) = (a0,a1,a2).

Because this linear combination must also satisfy the recursion formula that each of Y_{1}, Y_{2} and Y_{3} satisfy, we can also conclude that for any t

(12) a_{t}=A Y_{1}^{t} + B Y_{2}^{t} + C Y_{3}^{t}. We are interested in studying round(Y_{1}^{t}). We can do this by looking at a^{t}, instead. The reason for this is that

(13) cos(x) < 0 if 90 < x < 270 (mod 360); cos(x) > 0 if x < 90 or x > 270 (mod 360),

from which we know that

(14) Y_{1}>1, -1<Y_{2},Y_{3}<1.

Y_{1}^{t} is therefore an exponentially increasing sequence, whereas Y_{2}^{t} and Y_{3}^{t} are exponentially diminishing sequences. For a sufficiently large t, a_{t}=round(A Y_{1}).
In order to get rid of the A factor, we simply choose a_{0}, a_{1} and a_{2} such that A=1. The theory of symmetric polynomials guarantees that if we also choose B and C with the same value, the entire sequence will be an integer sequence. (For some more details on this, see the November 2009 Using your Head is Permitted riddle (external link).)

In this particular case, we don't need to invoke the full set of tools provided by symmetric polynomials in order to calculate a_{0}, a_{1} and a_{2}. They can be found as follows:

(15) a_{0} = Y_{1}^{0} + Y_{2}^{0} + Y_{3}^{0} = 1 + 1 + 1 = 3.

(16) a_{1} = Y_{1}1 + Y21 + Y31 = (1 + 2cos(20^{�})) + (1 + 2cos(140^{�})) + (1 + 2cos(260^{�})) =

= 3 + 2(cos(20^{�})+cos(140^{�})+cos(260^{�})) = 3.

(17) a_{2} = Y_{1}^{2} + Y_{2}^{2} + Y_{3}^{2} =

= (1+2cos(20^{�})) ^{2}+ (1+2cos(140^{�})) ^{2} + (1+2cos(260^{�})) ^{2} =

= (1+4cos(20^{�})+4cos^{2}(20^{�})) + (1+4cos(140^{�})+4cos^{2}(140^{�})) + (1+4cos(260^{�})+4cos^{2}(260^{�}))=

= (1+4cos(20^{�})+(2cos(40^{�})+2)) + (1+4cos(140^{�})+(2cos(280^{�})+2)) + (1+4cos(260^{�})+(2cos(520^{�})+2)) =

= (1+1+1+2+2+2) + 4(cos(20^{�})+cos(140^{�})+cos(260^{�})) + 2(cos(40^{�})+cos(280^{�})+cos(520^{�}))=

= 9.

In this derivation we utilized two main facts:

(18) cos^{2}(x) = (cos(2x)+1)/2.

and

(19) cos(20^{�})+cos(140^{�})+cos(260^{�}) = cos(40^{�})+cos(280^{�})+cos(520^{�}) = 0;

Equation (18) is a reordering of equation (4). Equation (19) is easier to see if we consider it in the complex domain and use the notation cis(x)=cos(x)+i sin(x):

(20) cis(20^{�}) + cis(140^{�}) + cis(260^{�}) = cis(20^{�}) * (cis(0^{�})+cis(120^{�})+cis(240^{�})) = 0.

(21) cis(40^{�}) + cis(280^{�}) + cis(520^{�}) = cis(40^{�}) * (cis(0^{�})+cis(240^{�})+cis(480^{�})) = 0.

The three vectors form an equilateral triangle in the complex plain, meaning that their sum must be zero. The same is true for the sum of any other full set of roots of unity.

So, we now have the sequence a_{0}=3, a_{1}=3, a_{2}=9, for any t>2, a_{t} = 3a_{t-1} – a_{t-3}, which we know to be equal to round(Y_{1}^{t}) as soon as t is large enough to allow

(22) |Y_{2}^{t}| + |Y_{3}^{t}| < 0.5.

Let us consider the properties of this sequence, and specifically, let us consider the sequence modulo 10^{9}, as we are asked to determine a t value for which, modulo 10^{9} the sequence equals zero. The first observation is that we can calculate the series entirely modulo 10^{9}, because in order to calculate the next element modulo 10^{9}, we only need to know the preceding elements modulo 10^{9}. The rest of their digits do not enter into the calculation.

From now on, we will therefore consider b_{t}= a_{t} mod 10^{9}, instead of a_{t}.

Next, we observe that if any triplet (b_{t},b_{t+1},b_{t+2}) equals a triplet at a different set of positions (b_{s},b_{s+1},b_{s+2}), the next value, b_{t+3}, will equal b_{s+3} and, for the same reason, for any positive n, b_{t+n} = b_{s+n}. To see this, simply reuse the argument with (b_{t+1},b_{t+2},b_{t+3}) replacing (b_{t},b_{t+1},b_{t+2}). This means that from such a point on, the entire function will become cyclic. Moreover, consider that the recursive function can be applied also in reverse:

(23) a_{t} = 3a_{t-1} – a_{t-3} → a_{t-3} = 3a_{t-1} – a_{t}.

This means that the cyclic behavior, b_{t+n} = b_{s+n}, extends not only to all positive n, but in fact to all integer n. In fact, if we use the inverse recursion formula to extend the a_{t} sequence naturally also to negative values of t, the cyclic behavior will continue to hold even if t+n<0 or if s+n<0. Does such a cycle actually occur? Can one actually find such (s,t) pairs? The answer is that such (s,t) pairs must exist, for the simple reason that the domain of b_{t} is finite, and therefore also the domain of (b_{t}, b_{t+1}, b_{t+2}) triplets. There are only 10^{9} possibilities for b_{t}, and at most (10^{9})^{3}=10^{27} possible triplets. If we look at (b_{0},b_{1},b_{2}), (b_{1},b_{2},b_{3}), ..., (b_{10^27}, b_{10^27+1}, b_{10^27+2}) at least two of these 10^{27}+1 triplets must be equal. This implies a cycle length of no more than 10^{27}.

Now, we begin to look for a value of t for which b_{t}=0. Though in the sequence b_{0}, b_{1}, b_{2}, ... none of the first few values fits this bill, in the extension to the negatives one is found easily:

(24) b_{-1} = 3b_{1} – b_{2} = 3a_{1} - a_{2}= 3*3-9 = 0 (mod 10^{9}).

Unfortunately, t=-1 is not a valid solution to the riddle (and even if it were, this is a value of t too low for the equality a_{t} = round(Y_{1}^{t}) to hold in it.

On the other hand, if we knew the cycle length, L, then the cyclic behavior guarantees that for any integer, k, b_{-1}=b_{kL-1}. Choosing a large enough k will bring us to the useful range of t values, and will solve the riddle.

For this, however, we need to determine the cycle length L, which is not trivial. Instead, we will settle for finding some multiple of it, which works in this case just as well. We know that the cycle length is smaller than or equal to 10^{27}. This means it must be one of a finite set of numbers: 1, 2, 3, ...., 10^{27}. A simple way for finding a value that is a multiple of the cycle length is to multiply all of these together. The result is 10^{27}!, where "!" is the factorial function.

So, for any integer k, b_{k*(10^27)!-1}=0, and for a large enough k, t=k*10^{27}!-1 solves the riddle. We claim that even the choice k=1 provides a large enough t here. To see this, consider that in order to be "large enough", t must satisfy equation (22). However, for this NOT to hold true, Y_{2} and Y_{3} must be EXTREMELY close to the value 1 in absolute value. (Their difference from 1 must be on the order of 1/10^{27}!.) This is far from the case, however. Note, for example, that cos(140^{�}) is between cos(135^{�})=-(√2)/2 and cos(150^{�}) = -0.5. In fact, for t values as low as 10 or 20, the value of |Y_{2}^{t}| + |Y_{3}^{t}| is already very small.

Putting all this together, we see that round((1+2cos(20^{�}))^(10^{27}!-1)) divides 10^{9}, and 10^{27}!-1 is a simple-to-compute solution to the riddle (though far from being the minimal one).

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com