Re: Closed form of the Hofstadter G-Sequence
- From: torteloni@xxxxxxxxxxxxxx
- Date: Sun, 25 Jan 2009 09:50:02 -0800 (PST)
On 22 Jan., 08:01, hagman <goo...@xxxxxxxxxxxxx> wrote:
If you do not want the exact details but rather just want to know
the PHI comes from, have a look at the recursion
G(n) = n -G(G(n-1))
IF G(n) is approximately c*n for some constant c, then this implies
c*n ~ n - c*c*(n-1)
and dividing by n suggests c = 1 - c^2.
For the exact proof by induction, I think the assumption that
[(n+1)/PHI] is not the same as n-[([n/PHI]+1)/PHI] leads to
an impossibly good rational approximation of PHI.
Thanks for this hint. This already helps me a lot (and is a really
interesting idea I think). Do you have any more idea for me how that
closed form can be proved? Or do you have any idea for helpful
literature about that? The only literature references I found are in
"Gödel, Escher, Bach" (but there is not too much information in it)
and some English science magazines - and most of them I cannot get as
a German pupil....
- Prev by Date: Re: Optimising files on a DVD -any algorithm better than brute-force approach?
- Next by Date: Re: ---- ---- --- A question in trigonometry
- Previous by thread: Re: Closed form of the Hofstadter G-Sequence
- Next by thread: Defn "Strongly Continuous Vector Valaued Function"