Bossy Lobster

A blog by Danny Hermes; musing on tech, mathematics, etc.

Edit on GitHub

Finding (Fibonacci) Golden Nuggets Part 1

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

AF(z)=zF1+z2F2+z3F3+,A_F(z) = z F_1 + z^2 F_2 + z^3 F_3 + \ldots,

the generating polynomial for the Fibonacci sequence The problem defines (without stating so), a sequence {zn}n>0\left\{z_n\right\}_{n > 0} where AF(zn)=nA_F(z_n) = n and asks us to find the values nn for which znz_n is rational. Such a value nn is called a golden nugget. As noted in the problem statement, AF(12)=2,\displaystyle A_F\left(\frac{1}{2}\right) = 2, hence z2=12\displaystyle z_2 = \frac{1}{2} is rational and 22 is the first golden nugget.

As a first step, we determine a criterion for nn to be a golden nugget by analyzing the equation AF(z)=nA_F(z) = n. With the recurrence relation given by the Fibonacci sequence as inspiration, we consider

(z+z2)AF(z)=z2F1+z3F2+z4F3++z3F1+z4F2+z5F3+.\begin{aligned}(z + z^2)A_F(z) = z^2 F_1 &+ z^3 F_2 + z^4 F_3 + \ldots\\ &+z^3 F_1 + z^4 F_2 + z^5 F_3 + \ldots. \end{aligned}

Due to the fact that F2=F1=1F_2 = F_1 = 1 and the nature of the recurrence relation, we have

(z+z2)AF(z)=z2F2+z3F3+z4F4+=AF(z)z(z +z^2)A_F(z) = z^2 F_2 + z^3 F_3 + z^4 F_4 + \ldots = A_F(z) -z

which implies

AF(z)=z1zz2.A_F(z) = \frac{z}{1 - z -z^2}.

Now solvingAF(z)=n,A_F(z) = n, we have

z=nnznz2nz2+(n+1)zn=0.z = n - n z - n z^2 \Rightarrow n z^2 + (n + 1)z - n = 0.

In order for nn to be a golden nugget, we must have the solutions zz rational. This only occurs if the discriminant

(n+1)24(n)(n)=5n2+2n+1(n + 1)^2 - 4(n)(-n) = 5 n^2 + 2 n + 1

in the quadratic is the square of a rational.

So we now positive seek values nn such that 5n2+2n+1=m25 n^2 + 2 n + 1 = m^2 for some integer mm (the value mm must be an integer since a rational square root of an integer can only be an integer.) This equation is equivalent to

25n2+10n+5=5m225n^2 + 10n + 5 = 5m^2

which is equivalent to

5m2(5n+1)2=4.5m^2 - (5 n + 1)^2 = 4.

This is where Conway's topograph comes in. We'll use the topograph with the quadratic form

f(x,y)=5x2y2f(x, y) = 5 x^2 - y^2

to find our solutions. Note

  • A solution is only valuable if y1mod5y \equiv 1 \bmod{5} since y=5n+1y = 5 n + 1 must hold.
  • Since 5\sqrt{5} is irrational, ff can never take the value 00
  • Since f(1,0)=5f(1, 0) = 5 and f(0,1)=1,f(0, 1) = -1, there is a river on the topograph and the values of ff occur in a periodic fashion.
  • Finally, since we take pairs (x,y)(x, y) that occur on the topograph, we know xx and yy share no factors.

Hence solutions f(x,y)=4f(x, y) = 4 can come either come from pairs on the topograph or by taking a pair which satisfies f(x,y)=1f(x, y) = 1 and scaling up by a factor of 22. We will have

f(2x,2y)=221=4f(2x, 2y) = 2^2 \cdot 1 = 4

due to the homogeneity of ff.

Starting from the trivial base u=(1,0)u = (1, 0) and v=(0,1),v = (0, 1), the full period of the river has length 88 as seen below:

Golden Nugget

NOTE: In the above, the values denoted as combinations of uu and vv are the vectors for each face on the topograph while the numbers are the values of ff on these vectors.

Since every edge protruding from the river on the positive side has a value of 44 on a side — the value pairs are (5,4),(5, 4), (4,1),(4, 1), (1,4),(1, 4), and (4,5)(4, 5) — by the climbing lemma, we know all values above those on the river have value greater than 44. Thus, the only solutions we are concerned with

f(x,y)=1or4f(x, y) = 1 \quad \text{or} \quad 4

must appear on the river. Notice on the river, the trivial base (u,v)(u, v) is replaced by the base (9u+20v,4u+9v)(9 u + 20 v, 4 u + 9 v). 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 — nn comes from y,y, so it must be positive. As such, we have a sequence of bases {(uk,vk)}k0\left\{(u_k, v_k)\right\}_{k \geq 0} with u0=(1,0),u_0 = (1, 0), v0=(0,1)v_0 = (0, 1) and recurrence

uk+1=9uk+20vkvk+1=4uk+9vk.\begin{aligned}u_{k + 1} &= 9 u_k + 20 v_k \\ v_{k + 1} &= 4 u_k + 9 v_k. \end{aligned}

This implies that both {uk}\left\{u_k\right\} and {vk}\left\{v_k\right\} satisfy the same relation

uk+29uk+19(uk+19uk)=20vk+19(20vk)=20(4uk)vk+29vk+19(vk+19vk)=4uk+19(4uk)=4(20vk).\begin{aligned}u_{k + 2} - 9 u_{k + 1} - 9(u_{k + 1} - 9 u_k) &= 20 v_{k + 1} - 9(20 v_k) = 20(4 u_k) \\v_{k + 2} - 9 v_{k + 1} - 9(v_{k + 1} - 9 v_k) &=4 u_{k + 1} - 9(4 u_k) = 4(20 v_k). \end{aligned}

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 uku_k and vk,v_k, 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 u0+v0=(1,1)u_0 + v_0 = (1, 1) and u1+v1=(13,29)u_1 + v_1 = (13, 29); for the second solution we start with u0+2v0=(2,4)u_0 + 2 v_0 = (2, 4) and u1+2v1=(17,38)u_1 + 2 v_1 = (17, 38); and for the third solution we start with 5u0+11v0=(5,11)5 u_0 + 11 v_0 = (5, 11) and 5u1+11v1=(89,199)5 u_1 + 11 v_1 = (89, 199). For the second solution, since f(1,2)=1,f(1, 2) = 1, we use homogeneity to scale up to (2,4)(2, 4) and (34,76)(34, 76) to start us off. With these values, we take the second coordinate along the recurrence and get the following values:

n First Second Third
0 1 4 11
1 29 76 199
2 521 1364 3571
3 9349 24476 64079
4 167761 439204 1149851
5 3010349 7881196 20633239
6 54018521 141422324 370248451
7 969323029 2537720636 6643838879
8 17393796001 45537549124 119218851371
9 312119004989 817138163596 2139295485799
10 5600748293801 14662949395604 38388099893011

We don't get our fifteenth golden nugget candidate (value must be one more than a multiple of 5) until 5600748293801,5600748293801, which yields

n=1120149658760.n = 1120149658760.

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.

NOTE:

The Fibonacci sequence is given by

Fn=Fn1+Fn2,F0=0,F1=1.F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1.

Comments