Ponder This

July 2010

<<June July August>>

Terse solution

The recursion formula x_t+3=3x_t+2-x_t with the initial values of x₀=3; x₁=3; and x₂=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²⁷!-1. A more careful calculation gives 217 * 10⁸-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²(x)+sin²(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²(x)-sin²(x) = 2cos²(x)-1.

(5) cos(3x) = cos(2x)cos(x)-sin(2x)sin(x) =
= (2cos²(x)-1)cos(x)-(2sin(x)cos(x))sin(x) =
= 2cos³(x)-cos(x)-2cos(x)sin²(x)=4cos³(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³(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³ - 3X - 0.5 = 0.

or, in integer coefficients,

(8) 8X³ - 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) ³-6((Y-1)/2)-1=0 → (Y³-3Y²+3Y-1) + (-3Y+3) -1 = Y³-3Y²+1 = 0.

We know, therefore, that the three solutions to the polynomial Y³-3Y²+1 = 0 are Y₁=1+2cos(20^�), Y₂=1+2cos(140^�) and Y₃=1+2cos(260^�).
Consider now, a sequence, a₀, a₁, a₂, ..., where a₀, a₁ and a₂ 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³ - 3Y² + 1 = 0, for each of them, the sequence 1, Y, Y², Y³, ... satisfies the recursion formula (even though it may have different initial conditions than a₀, a₁, a₂).
However, because (1,Y₁,Y₁²), (1,Y₂,Y₂²), (1,Y₃,Y₃²) are three linearly independent vectors, for any choice of (a₀,a₁,a₂) 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₁, Y₂ and Y₃ satisfy, we can also conclude that for any t

(12) a_t=A Y₁^t + B Y₂^t + C Y₃^t. We are interested in studying round(Y₁^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<Y₂,Y₃<1.

Y₁^t is therefore an exponentially increasing sequence, whereas Y₂^t and Y₃^t are exponentially diminishing sequences. For a sufficiently large t, a_t=round(A Y₁). In order to get rid of the A factor, we simply choose a₀, a₁ and a₂ 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₀, a₁ and a₂. They can be found as follows:

(15) a₀ = Y₁⁰ + Y₂⁰ + Y₃⁰ = 1 + 1 + 1 = 3.

(16) a₁ = Y₁1 + Y21 + Y31 = (1 + 2cos(20^�)) + (1 + 2cos(140^�)) + (1 + 2cos(260^�)) =
= 3 + 2(cos(20^�)+cos(140^�)+cos(260^�)) = 3.

(17) a₂ = Y₁² + Y₂² + Y₃² =
= (1+2cos(20^�)) ²+ (1+2cos(140^�)) ² + (1+2cos(260^�)) ² =
= (1+4cos(20^�)+4cos²(20^�)) + (1+4cos(140^�)+4cos²(140^�)) + (1+4cos(260^�)+4cos²(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²(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₀=3, a₁=3, a₂=9, for any t>2, a_t = 3a_t-1 – a_t-3, which we know to be equal to round(Y₁^t) as soon as t is large enough to allow

(22) |Y₂^t| + |Y₃^t| < 0.5.

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

From now on, we will therefore consider b_t= a_t mod 10⁹, 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⁹ possibilities for b_t, and at most (10⁹)³=10²⁷ possible triplets. If we look at (b₀,b₁,b₂), (b₁,b₂,b₃), ..., (b_10^27, b_10^27+1, b_10^27+2) at least two of these 10²⁷+1 triplets must be equal. This implies a cycle length of no more than 10²⁷.
Now, we begin to look for a value of t for which b_t=0. Though in the sequence b₀, b₁, b₂, ... none of the first few values fits this bill, in the extension to the negatives one is found easily:

(24) b_-1 = 3b₁ – b₂ = 3a₁ - a₂= 3*3-9 = 0 (mod 10⁹).

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₁^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²⁷. This means it must be one of a finite set of numbers: 1, 2, 3, ...., 10²⁷. 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²⁷!, 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²⁷!-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₂ and Y₃ must be EXTREMELY close to the value 1 in absolute value. (Their difference from 1 must be on the order of 1/10²⁷!.) 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₂^t| + |Y₃^t| is already very small.

Putting all this together, we see that round((1+2cos(20^�))^(10²⁷!-1)) divides 10⁹, and 10²⁷!-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