The Standard Bank IT Challenge (SBITC) is an annual coding competition for undergraduate and honours students in South Africa. The contest consists of two rounds: a regional event named the “heats”, and the final. In the heats, teams of up to four students each compete against other teams from the same university, and the winning team from each of the nine top-performing universities is invited to the final round in Johannesburg. Each member of the winning team wins a prize, and the winning university receives a large cash prize, but students mostly participate for the enjoyment that is to be obtained in solving the problems, and to test their skills against a set of problems that is designed to challenge the participants.

This year, the final problem from the heats (which took place on Saturday, 16 May) was fairly mathematical in nature; or more-so than the other problems at least. Essentially, the problem asks the following:

We consider generalised Fibonacci sequences T_n which satisfy the same recurrence relation T_{n + 2} = T_{n + 1} + T_n as the Fibonacci numbers, but with the first two terms T_1 and T_2 being arbitrary positive integers.

Now for some positive integer N, we can ask if N will occur in such a sequence. The answer is yes, since one could consider any sequence where T_1 = N. Less trivially, one could consider the sequence where T_1 = \lceil\frac{N}{2}\rceil and T_2 = \lfloor\frac{N}{2}\rfloor. The problem from the heats asks for the values of T_1 and T_2 for which N occurs as late in the corresponding sequence as possible. If there is a tie between two sequences which contain N, then we choose the sequence for which T_1 is as small as possible.

Problems in coding contests usually have a story attached to them to make the problem statement more interesting. In this case, the problem was framed in terms of an archaeological expedition which sought to understand an ancient peoples to whom Fibonacci-like sequences were culturally significant. I have—however—lost my copy of the problems, and so am not able to provide the problem statement as it was given in the competition. I can provide a solution, however.

A good start to the problem would be to try to see what terms in these general Fibonacci-like sequence look like. If we start experimenting by calculating the first few terms, we see that
T_3 = T_1 + T_2
T_4 = T_3 + T_2 = T_1 + 2T_2
T_5 = T_4 + T_3 = 2T_1 + 3T_2
T_6 = T_5 + T_4 = 3T_1 + 5T_2
and we recognise the coefficients of T_1 and T_2 as the standard Fibonacci numbers F_n given by F_1 = F_2 = 1 and F_{n + 2} = F_{n + 1} + F_n for n \geq 1. We may conjecture that T_{n + 2} = F_n T_1 + F_{n + 1} T_2 for all n \geq 1. This is indeed true, and can be proven by using mathematical induction.

The statement that N occurs in such a sequence then becomes
F_n T_1 + F_{n + 1} T_2 = N for some positive integer n.
(We saw above that we can always make sure that N is at least the third term in the sequence, and so we do not lose any generality by only considering T_{n + 2} = N for positive n)

This suggests a method for trying to tackle the problem. We could consider all pairs (F_n, F_{n +1}) of Fibonacci numbers which are below N, and attempt solve the corresponding equation for T_1 and T_2. If we find a solution for which T_1 and T_2 are positive integers, then N occurs at position n + 2 in the corresponding sequence. We then simply find the largest n for which a solution exists, and use the solution (T_1, T_2) for which T_1 is as small as possible. (In accordance with the problem specification) Since Fibonacci numbers grow exponentially, the number of pairs which we have to consider is logarithmic in N, and so this solution is feasible provided that we can efficiently solve the equation F_n T_1 + F_{n + 1} T_2 = N for T_1 and T_2.

Such equations for which we seek integer solutions are known as Diophantine equations, after Diophantus of Alexandria. While it is known that there is no general algorithm for solving general Diophantine equations, and no algorithm for even determining whether an arbitrary Diophantine equation has a solution, solutions are known for many special cases.  In particular, there is a method for finding all solutions of linear Diophantine equations of the form am + bn = c, where a, b and c are known integers, and m and n are integers which are to be determined. This is exactly the form of the equation which we wish to solve, and I shall outline the method for finding all possible solutions below.

The first question which one may ask is: “When does the equation am + bn = c have integer solutions?”. Clearly, if (m, n) is a solution, then the greatest common divisor of a and b must be a factor of c. Is the converse true? If \gcd(a, b) divides c, then does the equation necessarily have a solution in integers? The answer is yes. To prove this, we will make use of the following lemma:

Bézout’s Lemma: If a and b are any integers, then there exist integers s and t such that as + bt = \gcd(a, b).

This is often proven by considering the set of all positive integers of the form as + bt, and showing that the smallest of them must be a divisor of both a and b. A proof that is more useful if we wish to find the integers s and t is based on Euclid’s Algorithm for finding the greatest common divisor of two elements. I shall prove the following:
Suppose that a and b are positive integers, each at most k. Then there exist integers s and t such that as + bt = \gcd(a, b).
This is clearly true for k = 1, since the only possibility is \gcd(1, 1) = 1\cdot 1 + 1\cdot 0. Now suppose that this holds for some k. We will show that it is also true for k + 1 as follows: Suppose a and b are positive integers, each at most k + 1. If a = b, then \gcd(a, b) = a = a \cdot 1 + b \cdot 0. Otherwise, suppose without loss of generality that k + 1 \geq a > b. Then \gcd(a, b) = \gcd(b, a - b) = s_1 b + t_1 (a - b) for some integers s_1 and t_1, and we can take s = t_1 and t = s_1 - t_1.

The general case (where a and b need not be positive) follows by noting that \gcd(a, b) = \gcd(-a, b) = \gcd(a, -b) = \gcd(-a, -b).
The proof above shows not only that the integers s and t exist, but provides a method for finding them recursively: first find the values of s and t for (b, a - b), and use them to calculate the values of s and t for (a, b) (if a > b. The case b > a is similar). The base case for the recursion is \gcd(a, 0)=1\cdot a+0\cdot 0.

Many results about divisibility of numbers rely on Bézout’s Lemma. I will not prove these results, but will freely make use of them.

We now return to the question of whether the equation am + bn = c has integer solutions if \gcd(a, b) \mid c. Let c = k\gcd(a, b). By Bézout’s Lemma, we can find integers s and t such that as + bt = \gcd(a, b). If we take m = ks and n = kt, then am + bn = k\gcd(a, b) = c, and so we have found a solution. The question now becomes “How does one find all possible solutions?”

Suppose that (m_1, n_1) is any solution to the equation, and that (m, n) is some other solution. Let p = n - n_1. Then am_1 + bn_1 = am + b(n_1 + p), and so bp = a(m_1 - m). Thus a \mid bp and so \frac{a}{d} \mid p where d = \gcd(a, b). Let p = \frac{ak}{d}. Then \frac{bk}{d} = m_1 - m, and so m = m_1 - \frac{bk}{d}. We see that the most general possible solution to the equation is a(m_1 - \frac{bk}{d}) + b(n_1 + \frac{ak}{d}) = c where d = \gcd(a, b), k is any integer, and (m_1, n_1) is any particular solution.

We now have all of the machinery which is needed to solve the problem. However, there are a few more results which greatly simplify the actual calculations which need to be performed.

Note that to find the general solution to F_n T_1 + F_{n+1} T_2 = N, we need to know the value of d = \gcd(F_n, F_{n + 1}). It is well known that the Fibonacci numbers possess the remarkable property that \gcd(F_m, F_n) = F_{\gcd(m, n)}. We do not need the general case here, but only that \gcd(F_n, F_{n+1})=1, which can easily be proved by induction.

We see that the equation  F_n T_1 + F_{n+1} T_2 = N always has a solution, and that the general solution is given by
T_1 = sN - F_{n + 1} k and
T_2 = tN + F_n k where
(s, t) is any solution to sF_n + tF_{n + 1} = 1, and k is an arbitrary integer.

We are interested in the cases where T_1 and T_2 are positive, and also in the smallest possible value for T_1. The largest value of k for which T_1 is positive is k = \lceil\frac{sN}{F_{n+1}}\rceil-1. This follows from noting that
sN-F_{n+1}k>0
\iff k < \frac{sN}{F_{n+1}}
\iff k < \lceil\frac{sN}{F_{n+1}}\rceil
\iff k \leq \lceil\frac{sN}{F_{n+1}}\rceil-1
This also gives us the smallest possible positive value of T_1 since T_1 is a decreasing function of k. If this value for k does not make T_2 positive, then we see that it is impossible for T_1 and T_2 to be simultaneously positive (T_2 is an increasing function of k), and so there is no solution. Otherwise, we can use the solution corresponding to this value of  k.

We can now solve the original problem as follows:

  • Loop over the pairs of Fibonacci numbers (F_n, F_{n + 1}) for which F_{n + 1} < N.
  • For each pair, find integers s and t such that sF_n + tF_{n + 1} = 1 using the algorithm from Bézout’s Lemma above.
  • Let k = \lceil\frac{sN}{F_{n + 1}}\rceil - 1.
  • Let T_1 = sN - F_{n + 1} k and T_2 = tN + F_n k. If T_1 and T_2 are positive, then store these values, along with n.
  • Output the values of T_1 and T_2 that correspond to the largest value of n for which these values were positive.

This is the solution which we submitted. It was accepted, and ran in time, but we can make a few improvements. When calculating the integers s and t such that sF_{n}+tF_{n+1}=1, for example, it is not necessary for the recursion to run to the base case. If (s, t) are the required integers for (F_{n - 1}, F_n) (which we have already computed), then the integers for the pair (F_n, F_{n + 1}) are (t - s, s).

It is also possible to find the required integers s and t explicitly. Cassini’s Identity tells us that F_{n + 1}F_{n - 1} - F_n^2 = (-1)^n, so that one possible solution is s = -F_n and t = F_{n - 1} if n is even, and s = F_n and t = -F_{n - 1} if n is odd.

We can prove Cassini’s Identity directly using induction, of course, but could also use the fact that if
A = \begin{pmatrix} 1&1\\ 1&0\end{pmatrix}
then
A^n = \begin{pmatrix} F_{n + 1} & F_n \\ F_n & F_{n - 1} \end{pmatrix}
This can be proven using induction. (There’s no avoiding it) If we accept that this identity is true, then Cassini’s Identity follows by noting that
F_{n+1}F_{n-1}-F_n^2=\det(A^n)=(\det(A))^n=(-1)^n

This matrix representation of the Fibonacci numbers also allows us to prove other identities relating to the Fibonacci numbers. For example
A^{m+n}=A^mA^n gives us that

\begin{pmatrix}F_{m+n+1}&F_{m+n}\\F_{m+n}&F_{m+n-1}\end{pmatrix} =\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}
and so
F_{m+n}=F_{m+1}F_{n}+F_mF_{n-1}=F_{n+1}F_{m}+F_nF_{m-1}.

We could use this to prove the claim from earlier that \gcd(F_m, F_n)=F_{\gcd(m, n)}. The key idea is to show that \gcd(F_{m+n}, F_m)=\gcd(F_n, F_m). Calculating the greatest common divisor of two Fibonacci numbers then becomes equivalent to applying Euclid’s Algorithm to their indices in the sequence. The proof makes use of the addition formula obtained above, and the fact that \gcd(F_n, F_{n+1})=1 which we also made use of earlier. Given these results, one obtains \gcd(F_{m+n}, F_m)=\gcd(F_{m+1}F_n+F_mF_{n-1}, F_m)=\gcd(F_{m+1}F_n, F_m)=\gcd(F_n, F_m), where the last equality holds because \gcd(F_{m+1}, F_m)=1.

There is a wealth of other identities which can be discovered about the Fibonacci numbers, but they become increasingly less relevant to the SBITC problem. I will not present any further properties of the numbers here, but I do encourage you to experiment on your own and to see what you can discover.

How clear is this post?