Pensieve header: Sep 25: Further ways to compute Fibonacci.

Topics (in no particular order). Whatever you may suggest; whatever comes to my mind; the Fibonacci numbers; the Jones polynomial; a more efficient Jones algorithm; a riddle on spheres; Khovanov homology; Γ-calculus; the Hopf fibration; Hilbert’s 13th problem; non-commutative Gaussian elimination; free Lie algebras; the Baker-Campbell-Hausdorff formula; wacky numbers; an order 4 torus; the Schwarz Lantern; knot colourings; the Temperley-Lieb pairing; the dodecahedral link; sound experiments; barycentric subdivisions; a Peano curve; braid closures and Vogel’s algorithm; the insolubility of the quintic; phase portraits; the Mandelbrot set; shadows of the Cantor Aerogel; quilt plots; some image transformations; De Bruijn graphs; the Riemann series theorem; finite type invariants and the Willerton fish.

Possible (Smallish) Projects

Get some neat things out of DBN: Classes: 2015-16: MAT 475 Problem Solving Seminar: Quiz 1:

Rasterize[
Import["http://drorbn.net/AcademicPensieve/Classes/16-475-ProblemSolving/Quiz-01.pdf"][[1]],
ImageResolution ->120
] // ImageCrop

Further ways to compute Fibonacci

The Naive Way

f0[0]=f0[1]=1; f0[n_] := f0[n-1]+f0[n-2];

Table[Timing[n->f0[n]], {n,20,30}] // MatrixForm

The Naive Way, Corrected

f1[0]=f1[1]=1; f1[n_] := (f1[n] = f1[n-1]+f1[n-2]);

Timing[f1[100]]

“prev”, “cur”, and “While”.

f2[n_] := (
{k,prev,cur}={1,1,1};
While[k<n, {prev, cur} = {cur, prev+cur}; ++k];
cur
)

f2[100]

f3[n_] := Module[{k,prev,cur},
{k,prev,cur}={1,1,1};
While[k<n, {prev, cur} = {cur, prev+cur}; ++k];
cur
]

f3[40]

“prev”, “cur”, and “For”.

For[k=cur=prev=1, k<100, ++k, {prev, cur} = {cur, prev+cur}]; cur

“prev”, “cur”, and “Do”.

{prev, cur}={1,1};
Do[{prev, cur} = {cur, prev+cur},99];
cur

A “While” loop for {(Subscript[f, 1]), (Subscript[f, 2]), ...} (using negative indices)

f6[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, fs=Append[fs, fs[[-1]]+fs[[-2]]]];
Last[fs]
]

f6[100]

f7[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, fs=Append[fs, fs[[-1]]+fs[[-2]]]];
fs
]

f7[20]

f8[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, AppendTo[fs, fs[[-1]]+fs[[-2]]]];
fs
]

f8[10]

A “While” loop for {(Subscript[f, 1]), (Subscript[f, 2]), ...} (using “Total” and “Most”)

f9[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, AppendTo[fs,1+Total@Drop[fs,-1]]];
fs
]

f9[10]

f10[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, AppendTo[fs,1+Total@Most@fs]];
fs
]

f10[10]

“Series” and (1/(1-x-(x^2)))

Series[(1/(1-x-(x^2))),{x,0,10}]

“SeriesCoefficient” and (1/(1-x-(x^2)))

A Sum of Binomial Coefficients

Solve for an “explicit” formula, then use it.

Using “MatrixPower”

Using (Subscript[f, 2n])=(Subscript[f, n]^2)+(Subscript[f, n-1]^2) and (Subscript[f, 2n+1])=(Subscript[f, n])((Subscript[f, n+1])+(Subscript[f, n-1]))

A “categorified” version (using lists)

A “categorified” version (using strings)

“ReplaceRepeated” on (({{n}, {(Subscript[f, n-1])}, {(Subscript[f, n])}})).

“NestWhile” on (({{n}, {(Subscript[f, n-1])}, {(Subscript[f, n])}})).

“Nest” on (({{(Subscript[f, n-1])}, {(Subscript[f, n])}})).

Other Items

Continue looking at Charlene’s project? (Probably not; enough Fibonacci!)
A look at Etienne’s project? (Maybe)