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

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE
    html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-US">
<head>
<title>Project Euler #137: Fibonacci Golden Nuggets</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="author" content="Shlomi Fish" />
<meta name="description" content="Analysis of Project Euler Problem No. 137" />
</head>
<body>

<h1>Project Euler #137: Fibonacci Golden Nuggets</h1>
<script type="text/javascript" src="http://www.shlomifish.org/js/MathJax/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<p>
<a href="http://projecteuler.net/problem=137">Link to Project Euler problem
No. 137</a>
</p>

<p>
\[

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\}

\]
</p>

Therefore:

[ Given limits according to the |q| &lt; 1 ]
</p>

<p>
\[

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] \\

ys \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] \\

s \cdot \left\{ \dfrac{1}{\frac{z}{1+s} - 1} - \dfrac{1}{\frac{z}{1-s} - 1} \right\} = N \\

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 \\

sz \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)]} \\

    sz(1+s-1+s) = N\left[z-(1+s)\right]\left[z-(1-s)\right] \\

    2 s^2 \cdot z = N \left[ z^2 - 2z + (1-s^2)\right] \\

    s^2 = 5 \\

    10z = N \left[ z^2 - 2z - 4 \right] \\

    z^2 - (2+10/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+10/N)^2+16 = 4\left[ (1+5/N)^2+4 \right] = 4[ (N+5)^2/N^2 + 4 ] \\

    ∆ = 4\dfrac{ (N+5)^2+4N^2 }{ N^2 } \\

    \text{rational iff (N+5)^2+4N^2 is a whole square.}

\]
</p>


</body>
</html>
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.