Posted by Here’s an odd little bit of math for you this Sunday. It’s defined in terms of recurrence. Recurrence happens when a function is defined in terms of itself. This happens more than you might think – one famous example is the Fibonacci sequence, which is informally defined by saying “To get the next term in the sequence, add the previous two terms together. The first two terms are 1 and 1.” And so you can calculate that the sequence is {1, 1, 2, 3, 5, 8, 13, 21…} and so forth. That sequence turns out to show up in various odd places in math and science, and recursively defined sequences are actually pretty common in physics. This one isn’t, as far as I know. It seems to have been discovered in 2003 by students at Stephen Wolfram’s NKS Summer School – more on that later. The sequence is defined thus:
This needs an initial value along the lines of the Fibonacci sequence “The first two terms are 1 and 1″, and in this case the initial value for the sequence is a(1) = 7. Thus a(2), the second term of the sequence, is equal to a(1) + gcd(2, a(1)).
Here “gcd” refers to the greatest common divisor function. It gives the largest integer that evenly divides the numbers you feed into the function. For instance gcd(18, 12) = 6, because both 18 and 12 can be divided evenly by 6. They can also both be divided by several other numbers, but 6 is the greatest common divisor. So since a(1) = 7 and gcd(2,7) is 1, a(2) = 7 + 1 = 8.
If we calculate the first 50 terms in the sequence, we’ll find that they are: 7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 141, 144, 145, and 150. If we look at the difference between successive terms, ie, between 7 and 8, between 8 and 9, between 94 and 141 and so forth, we find this daughter sequence: {1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1}
It appears to be composed mostly of 1s, with a few others thrown in for good measure. But all the ones thrown in seem to be prime numbers. I won’t bore you by printing out some absurd number of terms in the sequence, but it will continue to be true. Eric Rowland proved recently that this sequence generates only 1s and primes. The length of the strings of 1s tends to grow larger as you go out, and the primes generated tend to be higher and higher, however it is not yet known whether this sequence eventually generates all the primes. The behavior of this sequence for initial conditions other than a(1) = 7 is not entirely explored. For some other conditions the sequence strictly generates 1s and primes, for others it generates composite numbers before possibly settling down into 1s and primes behavior – but this has not yet been proved.
Here’s a figure (from Rowland’s paper) which plots the jth occurrence of a non-1 value on the x-axis with the n required to get that value on the y-axis. Lots of regularity, and lots of 1s. Fortunately there’s computational shortcuts you can take, as the length of the sequences of 1s is predictable in advance:
There’s not much practical use for this. If you want to generate a list of primes, there’s vastly more efficient ways. Nonetheless, it’s an interesting fact. I suggest reading the Rowland paper for more info, as it’s not technically difficult at all.
Now about the fact that this was discovered at the NKS School. Stephen Wolfram is a brilliant guy who most physics and math types think went off the rails with his idea that pretty much everything in physics is really computational in nature. I tend to agree with his critics, not because I (or they) have anything against computation but because so far the idea doesn’t really make any predictions and therefore isn’t testable. But of course computation is an interesting study in its own right and for all we know it could eventually turn out to have deep relevance in physics. To his credit though, it is certainly possible to discover interesting things by looking at the behavior of simple computational systems. This is one of those interesting things.
August 22, 2010
August 22, 2010
August 22, 2010
August 22, 2010
August 23, 2010
August 23, 2010
August 25, 2010
November 4, 2010