# project-euler / project-euler / 137 / html-analysis.html

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86  Project Euler #137: Fibonacci Golden Nuggets

Project Euler #137: Fibonacci Golden Nuggets

Link to Project Euler problem No. 137

$s = \sqrt{5} \\ F[n] = \frac{1}{s} \cdot \left\{ \left[ \frac{1+s}{2} \right]^n - \left[\frac{1 - s}{2}\right]^n \right\}$

Therefore: [ Given limits according to the |q| < 1 ]

$A_F(x) = \frac{1}{s} \cdot \left\{ \dfrac{ \frac{x(1+s)}{2} }{ 1 - \frac{x(1+s)}{2} } - \dfrac{ \frac{x(1-s)}{2} }{ 1 - \frac{x(1-s)}{2} } \right\} = \\ \frac{x}{2s} \cdot \left\{ \dfrac{ (1+s) }{ 1 - \frac{x(1+s)}{2} } - \dfrac{ (1-s) }{ 1 - \frac{x(1-s)}{2} } \right\} = \\ \frac{x}{2s} \cdot \left\{ \dfrac{ 1 }{ \frac{1}{1+s} - x/2 } - \dfrac{ 1 }{ \frac{1}{1-s} - x/2 } \right\} = \\ \left[y = x/2\right] \\ \frac{y}{s} \cdot \left\{ \dfrac{ 1 }{ \frac{1}{1+s} - y } - \dfrac{ 1 }{ \frac{1}{1-s} - y } \right\} = \\ \left[z = 1/y ; \cdot \dfrac{\frac{1}{y}}{\frac{1}{y}} \right] \\ \frac{1}{s} \cdot \left\{ \dfrac{1}{\frac{z}{1+s} - 1} - \dfrac{1}{\frac{z}{1-s} - 1} \right\} = N \\ \frac{1}{s} \cdot \dfrac{ \left[\frac{z}{1-s}-1 - \frac{z}{1+s} + 1 \right]}{[\frac{z}{1+s}-1][\frac{z}{1-s}-1]} = N \\ \frac{z}{s} \cdot (\frac{1}{1-s}-\frac{1}{1+s}) = N\left[\frac{z}{1+s}-1\right]\left[\frac{z}{1-s}-1\right] \\ \text{[ * (1+s) * (1-s)]} \\ \frac{z}{s}(1+s-1+s) = N\left[z-(1+s)\right]\left[z-(1-s)\right] \\ 2z = N \left[ z^2 - 2z + (1-s^2)\right] \\ s^2 = 5 \\ 2z = N \left[ z^2 - 2z - 4 \right] \\ z^2 - (2+2/N)z - 4 = 0 \\ z = \dfrac{ -b \pm \sqrt{b^2-4ac}}{2a} \\ \text{z is rational iff b^2-4ac is a square of a rational number:} \\ ∆ = (2+2/N)^2+16 = 4\left[ (1+1/N)^2+4 \right] = 4[ (N+1)^2/N^2 + 4 ] \\ ∆ = 4\dfrac{ (N+1)^2+4N^2 }{ N^2 } \\ \text{rational iff (N+1)^2+4N^2 is a whole square.}$