Hofstader’s Chaotic Sequence
[This article was first published on Playing with R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
About a year ago I was reading Godel, Escher, Bach by Douglas Hofstadter. In a section on recursion he presents a sequence that he calls “A Chaotic Sequence” defined as:Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Q(n) = Q(n – Q(n – 1)) + Q(n – Q(n – 2)) for n > 2
Q(1) = Q(2) =1
It’s similar to a Fibunacci sequence in that it references earlier values to calculate new ones. But rather than simply adding the previous two values it uses the previous two values as an index to see how far back in the sequence to find the numbers to add. The results are interesting.
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, …
The next number would be 11 (found by adding the 5 that’s found 10 numbers back to the 6 that’s found 9 numbers back).
Recreating this sequence in R is quite simple.
q = c()
q[1] = q[2] = 1
n = 3
while(n < 100){
q[n] = q[n - q[n-1]]+q[n - q[n-2]]
n = n+1
} The first 100 values of the sequence are listed and plotted below.
It's clear that the values are increasing.
Looking at the first 10,000 values we again see that the values are increasing with periodic increases in variance.
If we look at the first difference of the values we can see the periodic variance more pronounced.
Now looking at the first 150,000 values we can see that the pattern continues... it's almost like a fractal.
> q
[1] 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 12
[22] 12 12 16 14 14 16 16 16 16 20 17 17 20 21 19 20 22 21 22 23 23
[43] 24 24 24 24 24 32 24 25 30 28 26 30 30 28 32 30 32 32 32 32 40
[64] 33 31 38 35 33 39 40 37 38 40 39 40 39 42 40 41 43 44 43 43 46
[85] 44 45 47 47 46 48 48 48 48 48 48 64 41 52 54
It's clear that the values are increasing.
Looking at the first 10,000 values we again see that the values are increasing with periodic increases in variance.
If we look at the first difference of the values we can see the periodic variance more pronounced.
plot(c(1:(length(q)-1)),diff(q), type='l')
Now looking at the first 150,000 values we can see that the pattern continues... it's almost like a fractal.
To leave a comment for the author, please follow the link and comment on their blog: Playing with R.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.