Given a sequence of integers, a common mathematical task is to try to find a short “closed” form for the sequence. For example, a closed form for (2,6,12,20,…) is n*(n+1), a closed form for (-1,1,-1,1,-1,…) is (-1)^n, and a closed form for (1,1,2,2,3,3,…) is floor((n+1)/2) (where the floor function rounds down).
The last two are interesting because they are not continuous. This means that if you interpreted the ‘closed form’ as a function of real numbers and plotted it on a graph, you would not see a smooth continuous line. In the case of floor((n+1)/2), you would see horizontal lines each two units long, and each one one unit higher than the previous:
In the case of (-1)^n, I don’t think there’s any kind of continuity whatsoever. You might be able to say that the function is defined when n is rational, but I think that’s as far as it goes.
For some reason that I can’t properly justify, I don’t like this. I like it when an integer sequence can be generated by a continuous smooth curve. Any finite sequence can be generated by a polynomial with a degree that is at most one less than the length of the sequence, which is exactly what my sequences-to-functions app does. For example, the sequence (1,2,3,4,1) can be generated by the polynomial (-1/6)x^4 + (5/3)x^3 – (35/6)x^2 + (28/3)x – 4:
Of course, the next value generated by the polynomial is not 2, as the sequence suggests, but -14. In general any polynomial generated by a sequence like this will rocket upward or downward at either end. So you can’t get any kind of periodic behavior out of polynomials. I started investigating using the sine function for periodic behavior back in high school when I first encountered the double-counting sequence (1,1,2,2,3,3,…).
The sine curve can help when we note that the double counting sequence can be written as the sum of two other simpler sequences:
0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, ... + 0.5, 0.0, 0.5, 0.0, 0.5, 0.0, 0.5, 0.0, ... ------------------------------------------------------- 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0, ...
The first of these is simply f(x) = x/2, and the second is a simple alternation between 0 and 0.5. The sine curve is great at alternating, so all we need is to stretch and pull it to make everything line up correctly:
This was as far as I thought about the issue in high school, and aside from a brief resurfacing in college calculus, it didn’t come to mind again until recently when a friend of mine started taking calculus. Only then did I realize that there are glaring questions here: What other sequences can we produce with these tools? What periods can they have? Would anybody like a beer?
So I’ve thought about these questions some during my spare moments the last few weeks, and have a few answers so far. The first thing I noted was that, for a given period, there is a canonical sequence that we may as well call a “basis”, from which any periodic sequence can be constructed. The simplest for a period P is simply P-1 zeros followed by a single one. For example, with P = 5, the canonical sequence (call it ‘the 5-basis’) would be (0,0,0,0,1,0,0,0,0,1,0,…). This is sufficient to create any period-5 sequence by simply shifting back and forth and multiplying. If our canonical sequence is called f(n), and we want to create the sequence (1,9,6,2,5,1,9,6,2,5,1,…), we can do each of the five numbers individually and then add them together:
g(n) = f(n+4) + 9*f(n+3) + 6*f(n+2) + 2*f(n+1) + 5*f(n) 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, ... 0, 9, 0, 0, 0, 0, 9, 0, 0, 0, 0, ... 0, 0, 6, 0, 0, 0, 0, 6, 0, 0, 0, ... 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, ... + 0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, ... ---------------------------------------- 1, 9, 6, 2, 5, 1, 9, 6, 2, 5, 1, ...
So finding a basis function gives us a lot. It also gives us the repeated counting function for its period (for period P, start with f(x) = x/P and then subtract off appropriate amounts using P-1 fractional multiples of the basis). The next question then is what basis functions can we construct from the sine function? The basis for P=2 is not hard, since the most obvious characteristic of the sine function is that it alternates between two values. P=4 also turns out to be pretty easy, because the sine function also has a clean period-4 version, which isn’t a basis function but can easily produce a basis function when combined with the 2-basis:
| f(n) = (1+sin(πn – 1/2))/2 | = 1, 0, 1, 0, 1, 0, 1, 0, 1, … |
| g(n) = sin(πn/2) | = 1, 0,-1, 0, 1, 0,-1, 0, 1, … |
| h(n) = (f(n) + g(n))/2 | = 1, 0, 0, 0, 1, 0, 0, 0, 1, … |
The 4-basis can be used to create a period-4 counting loop:
This was as far as I got at first — I wasn’t sure if I could use the sine function to create a basis for any periods other than 2 and 4. Eventually I weasled out a period-3 basis using a single sine wave:
Which we can of course use to make a triple-counting function:
And most recently using all sorts of shameful tricks I found a basis for period-5:
I haven’t yet figured out if the witchcraft that was involved can be used for higher prime periods, of if there is any hope for aperiodic sequences like (1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,…). But I do know that if you multiply the 3-basis with the 5-basis you get a 15-basis, and so I have no choice but to conclude with a graph for a period-15 sequence of random integers from 0 to 10:
Comments