Saturday, April 30, 2011

Hofstader's Chaotic Sequence

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:

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.

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

No comments:

Post a Comment