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 which satisfy the same recurrence relation as the Fibonacci numbers, but with the first two terms and being arbitrary positive integers.
Now for some positive integer , we can ask if will occur in such a sequence. The answer is yes, since one could consider any sequence where . Less trivially, one could consider the sequence where and . The problem from the heats asks for the values of and for which occurs as late in the corresponding sequence as possible. If there is a tie between two sequences which contain , then we choose the sequence for which 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
and we recognise the coefficients of and as the standard Fibonacci numbers given by and for . We may conjecture that for all . This is indeed true, and can be proven by using mathematical induction.
The statement that occurs in such a sequence then becomes
for some positive integer .
(We saw above that we can always make sure that is at least the third term in the sequence, and so we do not lose any generality by only considering for positive )
This suggests a method for trying to tackle the problem. We could consider all pairs of Fibonacci numbers which are below , and attempt solve the corresponding equation for and . If we find a solution for which and are positive integers, then occurs at position in the corresponding sequence. We then simply find the largest for which a solution exists, and use the solution for which 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 , and so this solution is feasible provided that we can efficiently solve the equation for and .
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 , where , and are known integers, and and 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 have integer solutions?”. Clearly, if is a solution, then the greatest common divisor of and must be a factor of . Is the converse true? If divides , 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 and are any integers, then there exist integers and such that .
This is often proven by considering the set of all positive integers of the form , and showing that the smallest of them must be a divisor of both and . A proof that is more useful if we wish to find the integers and is based on Euclid’s Algorithm for finding the greatest common divisor of two elements. I shall prove the following:
Suppose that and are positive integers, each at most . Then there exist integers and such that .
This is clearly true for , since the only possibility is . Now suppose that this holds for some . We will show that it is also true for as follows: Suppose and are positive integers, each at most . If , then . Otherwise, suppose without loss of generality that . Then for some integers and , and we can take and .
The general case (where and need not be positive) follows by noting that .
The proof above shows not only that the integers and exist, but provides a method for finding them recursively: first find the values of and for , and use them to calculate the values of and for (if . The case is similar). The base case for the recursion is .
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 has integer solutions if . Let . By Bézout’s Lemma, we can find integers and such that . If we take and , then , and so we have found a solution. The question now becomes “How does one find all possible solutions?”
Suppose that is any solution to the equation, and that is some other solution. Let . Then , and so . Thus and so where . Let . Then , and so . We see that the most general possible solution to the equation is where , is any integer, and 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 , we need to know the value of . It is well known that the Fibonacci numbers possess the remarkable property that . We do not need the general case here, but only that , which can easily be proved by induction.
We see that the equation always has a solution, and that the general solution is given by
is any solution to , and is an arbitrary integer.
We are interested in the cases where and are positive, and also in the smallest possible value for . The largest value of for which is positive is . This follows from noting that
This also gives us the smallest possible positive value of since is a decreasing function of . If this value for does not make positive, then we see that it is impossible for and to be simultaneously positive ( is an increasing function of ), and so there is no solution. Otherwise, we can use the solution corresponding to this value of .
We can now solve the original problem as follows:
- Loop over the pairs of Fibonacci numbers for which .
- For each pair, find integers and such that using the algorithm from Bézout’s Lemma above.
- Let .
- Let and . If and are positive, then store these values, along with .
- Output the values of and that correspond to the largest value of 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 and such that , for example, it is not necessary for the recursion to run to the base case. If are the required integers for (which we have already computed), then the integers for the pair are .
It is also possible to find the required integers and explicitly. Cassini’s Identity tells us that , so that one possible solution is and if is even, and and if is odd.
We can prove Cassini’s Identity directly using induction, of course, but could also use the fact that if
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
This matrix representation of the Fibonacci numbers also allows us to prove other identities relating to the Fibonacci numbers. For example
gives us that
We could use this to prove the claim from earlier that . The key idea is to show that . 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 which we also made use of earlier. Given these results, one obtains , where the last equality holds because .
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.