As I mentioned in my last set ofposts, the content would go somewhere and this post will be the first to deliver on that. In fact this is the all math, no code first half of a two part post that will deliver. If you see words like topograph, river, and base and you aren't sure what I mean, you may want to read that last set of posts.
In this post, I outline a solution to Project Euler problem 137, so stop reading now if you don't want to be spoiled. There is no code here, but the second half of this post has a pretty useful abstraction.
The problems asks us to consider
the generating polynomial for the Fibonacci sequence The problem defines (without stating so), a sequence where and asks us to find the values for which is rational. Such a value is called a golden nugget. As noted in the problem statement, hence is rational and is the first golden nugget.
As a first step, we determine a criterion for to be a golden nugget by analyzing the equation . With the recurrence relation given by the Fibonacci sequence as inspiration, we consider
Due to the fact that and the nature of the recurrence relation, we have
Now solving we have
In order for to be a golden nugget, we must have the solutions rational. This only occurs if the discriminant
in the quadratic is the square of a rational.
So we now positive seek values such that for some integer (the value must be an integer since a rational square root of an integer can only be an integer.) This equation is equivalent to
which is equivalent to
This is where Conway's topograph comes in. We'll use the topograph with the quadratic form
to find our solutions. Note
- A solution is only valuable if since must hold.
- Since is irrational, can never take the value
- Since and there is a river on the topograph and the values of occur in a periodic fashion.
- Finally, since we take pairs that occur on the topograph, we know and share no factors.
Hence solutions can come either come from pairs on the topograph or by taking a pair which satisfies and scaling up by a factor of . We will have
due to the homogeneity of .
Starting from the trivial base and the full period of the river has length as seen below:
NOTE: In the above, the values denoted as combinations of and are the vectors for each face on the topograph while the numbers are the values of on these vectors.
Since every edge protruding from the river on the positive side has a value of on a side — the value pairs are and — by the climbing lemma, we know all values above those on the river have value greater than . Thus, the only solutions we are concerned with
must appear on the river. Notice on the river, the trivial base is replaced by the base . This actually gives us a concrete recurrence for the river and with it we can get a complete understanding of our solution set.
When we start from the trivial base, we only need consider moving to the right (orientation provided by the above picture) along the river since we only care about the absolute value of the coordinates — comes from so it must be positive. As such, we have a sequence of bases with and recurrence
This implies that both and satisfy the same relation
With these recurrences, you can take the three base solutions on the river and quickly find each successive golden nugget. Since each value is a coordinate in a vector, it satisfies the same linear recurrence as the vector. Also, since each of the solution vectors occur as linear combinations of and they must satisfy the same recurrence as well.
Since the recurrence is degree two, we need the first two values to determine the entire sequence. For the first solution we start with and ; for the second solution we start with and ; and for the third solution we start with and . For the second solution, since we use homogeneity to scale up to and to start us off. With these values, we take the second coordinate along the recurrence and get the following values:
We don't get our fifteenth golden nugget candidate (value must be one more than a multiple of 5) until which yields
By no means did I do this by hand in real life; I didn't make a pretty representation of the river either. I just wanted to make the idea clear without any code. To get to the code (and the way you should approach this stuff), move on to the second half of this post.
The Fibonacci sequence is given by