The mathematics of sloth canon number sequences and Per Nørgård’s infinity series

This describes the maths behind the sloth canon number sequences described in my Self Similar Sloth Canon Number Sequences article

It simplifies the proofs here to use a 0 based notation. So we define an integer sequence f(n) as a map from the non negative integers to the integers. The first term in the sequence is f(0).

Sloth Canon Sequences

Definition of a sloth canon sequence

A sloth canon sequence is an integer sequence f(n) (mapping from positive integers to the integers) with similarity repeat interval r satisfying the functional equation:

f(n*r) = f(n).

Let’s call this the sloth canon similarity rule.

Observation, a sloth canon sequence can be used to construct musical sloth canons

To see this, if the first voice in the sloth canon is f(n), the sequence f(n*r) is identical to the sequence f(n) so giving the second voice in the sloth canon.

We also have f(n*r2) = f(n*r) = f(n) so f(n*r2) is also identical to the sequence f(n), so giving the third voice in the canon, and so continuing in this way, the sequence f(n*rm) is also identical to the sequence f(n) for any m.

When converted into musical notes, the result is an endless musical canon with as many voices as desired, each playing the same melody line at different speeds, i.e. a sloth canon.

Observation, there are uncountably many possible sloth canon sequences

Any choice for any of the numbers k with k%r !=0 leads to a sloth canon sequence, so there are uncountably many such sequences.

Tune smithy sequences

Definition of a tune smithy sequence

Let’s define a tune smithy sequence f(n) as a sloth canon sequence with the additional property that for any k>0, and any i with i>0 and i<r, then f(k*r+i)-f(k*r) = f(i)-f(0). In other words it is made by adding the same “seed” phrase to each of the multiples of r, and expanding the result out to make a sloth canon sequence. We can call this the seed similarity rule.

Lemma 1, A tune smithy sequence is completely determined by its values for f(i) for i<r

Proof, by induction: suppose it is already determined for all values i<=kr for integer k, then you get the values for i<(k+1)*r by the seed similarity rule, and the value for (k+1)*r by the sloth canon similarity rule).

Observation, there are only countably many tune smithy sloth canon sequences

It follows that there are only countably many tune smithy sequences because you can enumerate all possible finite sequences.

Tune smithy sequences are weighted digit sums

Lemma 2, all tune smithy sequences are weighted digit sums, and vice versa all weighted digit sums are tune smithy sequences

In detail: any tune smithy sequence f(n) with f(0)=0 and with similarity repeat r can be expressed as a weighed digit sum of the digits of n written to base r by suitable choice of weights w(i) for i<r. Also vice versa, any weighted digit sum defines a tune smithy sloth canon sequence.

Proof

First suppose w(n) is a weighted digit sum of n expressed to base r.

1. w(n*r)) = w(n)
Immediate, because the base r expression for n*r is obtained from the expression for n by adding a 0 at the end.

2. w(k*r+i) = w(k*r) + w(i) (for i<r)
Immediate, because you get the base r expression for k*r+i by changing the trailing 0 to an i.

So w(n) is a tune smithy sloth canon sequence.

Conversely, suppose f(n) is a tune smithy sequence with f(0) = 0 and similarity repeat r.

We need to convert it to a weighted digit sum. To do this set w(i) = f(i)/i for i<r. Then since w(i) satisfies 1 and 2 above, then w(i) is a tune smithy sloth canon seuqence, and since f(n) is completely determined by its values for i<r by lemma 1, and since w(n) = f(n) for n<r, we see that w(n) = f(n) for all n.

QED

The Per Nørgård sequences

The infinity sequence is discussed here on the composer’s website: infinity series The result are stated without proof, so the idea in this section is just to present the proofs of the results.

Definition of the Per Nørgård sequence

Following the example of the OEIS entry, it is easier to define the sequence using the binary digit definition, then derive the original definition from it as a consequence.

Definition, The Per Nørgård sequence is obtained from binary numbers by a special type of alternating digit sum

See A004718, and on the composer’s website: Construction by binary numbers

Write n in binary and read from left to write, starting with 0 and interpreting 1 as “add 1” and 0 as “change sign”. For example 19 = binary 10011, giving 0 -> 1 -> -1 -> 1 -> 2 -> 3, so a(19) = 3.

Some immediate consequences of this, again stated on the composer’s website, see:Is Per Nørgård’s infinity series unique?

Lemma 3. The even numbered members of a Per Nørgård sequence give the sequence inverted.

i.e. f(2k) = – f(k) for k>0. This follows because you obtain the binary expansion for f(2k) by adding a 0 to the end which changes the sign.

Lemma 4. The odd numbered members give the sequence incremented by 1 (transposed)

i.e. f(2k+1) = f(k)+1. This follows because you obtain the binary expansion for f(2k+1) by adding a 1 to the end which adds 1 to the sum.

Observation (not actually needed in what follows, just of interest

The lemmas f(2k) = – f(k) and f(2k+1) = f(k)+1 recursively define f(n) for all n

That’s because because any integer n can be reduced to 0 by subtracting 1 whenever it is odd, and dividing by 2 whenever it is even. So reversing the process, any n can be obtained by repeated application of either doubling or adding 1.

Lemma 5. a Per Nørgård sequence is a sloth canon sequence with similarity repeat 4.

We need to show that f(4*n) = f(n)

Proof: Immediate because you get the binary expansion for 4*n by adding two 0s to the binary expansion for n, which has the same alternating digit sum.

lemma 6. This new definition is equivalent to the original definition of the sequence.

The Per Nørgård infinity sequence is a sequence f(n) with the property that

1. f(0) = 0 and f(1) = 1
2. f(2(k+1)) – f(2k) = – (f(k+1) – f(k) ).
3. f(2(k+1)+1) – f(2k+1) = f(k+1) – f(k).

2. and 3. can also be rephrased as
2. f(2k+2) – f(2k) = – (f(k+1) – f(k) ).
3. f(2k+3) – f(2k+1) = f(k+1) – f(k).

This is a recursive definition that defines f(n) for all n.

So, for instance,

f(2)-f(0) = -( f(1)-f(0))
f(3)-f(1) = f(1)-f(0)

f(4)-f(2) = – (f(3) – f(2) )
f(5)-f(3) = (f(3) – f(2) )

We need to prove that our new binary expansion based definition satisfies these two rules, 2. and 3. of his original definition (1. is immediate).

By application of lemmas 3 and 4 we have:

2. f(2*(k+1)) – f(2*k)
= – f(k+1) + f(k)

3. f(2*(k+1)+1) – f(2*k+1)
= f(k+1)+1 – (f(k)+1)
= f(k+1) – f(k)

So what we have is indeed the Per Nørgård infinity sequence.

QED

This still leaves the question – why are there so many sloth canon sequences in the OEIS database?

This doesn’t explain why so many of the sequences in the database have this property. Though uncountably many sequences of this form exist, they are still a very special type of sequence. You have to get it right at infinitely many places along the sequence. If you get just one of those numbers wrong, it is no longer a sloth canon sequence.

So, there must be some reason why there are so many sequences of this type in the database, it can’t be just chance.

If it was just chance, you would expect to get only the ones constructed to be sloth canons, or the ones constructed using a process that is known to generate sloth canons. Of processes known to always generate sloth canon sequences, so far we only have the weighted digit sums (because those always create sloth canon sequences as described above).

It would be interesting to know what other mathematical constructions lead to sloth canon sequences, and why there are so many diverse sequences of this type in the database.

Does anyone know of any other mathematical ways of generating number sequences that always give you a sloth canon? Can all the sequences in the OEIS database be explained by such methods?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s