Help for Tune Smithy

# Self Similar Sloth Canon Number Sequences

(Difference between revisions)
 Revision as of 22:02, 21 February 2013 (view source) (→What does it mean to say that these sequences make a sloth canon?)← Older edit Revision as of 22:04, 21 February 2013 (view source) (→What does it mean to say that these sequences make a sloth canon?)Newer edit → Line 31: Line 31: There are several more sequences in the database that can be made as Tune Smithy seeds in the same way. So:
There are several more sequences in the database that can be made as Tune Smithy seeds in the same way. So:
[https://oeis.org/A000120 number of 1's in binary expansion of n (or the binary weight of n)] 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, ... [https://oeis.org/A000120 number of 1's in binary expansion of n (or the binary weight of n)] 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, ... - {{#ev:youtube|CKcMD56EFw8|480}} - that's the Tune Smithy sloth canon for the seed 0, 1. + {{#ev:youtube|CKcMD56EFw8|480}}
+ - that's the Tune Smithy sloth canon for the seed 0, 1. [https://oeis.org/A053735 Sum of digits of (n written in base 3)] 0, 1, 2, 1, 2, 3, 2, 3, 4, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, 3, 4, 5, 4, 5, 6, 1, 2, ... [https://oeis.org/A053735 Sum of digits of (n written in base 3)] 0, 1, 2, 1, 2, 3, 2, 3, 4, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, 3, 4, 5, 4, 5, 6, 1, 2, ... - {{#ev:youtube|gBINnRylfis|480}}- that's the Tune Smithy sloth canon for the seed 0, 1, 2 + {{#ev:youtube|gBINnRylfis|480}}
+ - that's the Tune Smithy sloth canon for the seed 0, 1, 2 [https://oeis.org/A006287 Sum of squares of digits of ternary representation of n] 0, 1, 4, 1, 2, 5, 4, 5, 8, 1, 2, 5, 2, 3, 6, 5, 6, 9, 4, 5, 8, 5, 6, 9, 8, 9, 12, 1, 2, ... [https://oeis.org/A006287 Sum of squares of digits of ternary representation of n] 0, 1, 4, 1, 2, 5, 4, 5, 8, 1, 2, 5, 2, 3, 6, 5, 6, 9, 4, 5, 8, 5, 6, 9, 8, 9, 12, 1, 2, ... - {{#ev:youtube|6DFGCdl2QGM|480}} - that's the Tune Smithy sloth canon for the seed 0 1 4 + {{#ev:youtube|6DFGCdl2QGM|480}}
+ - that's the Tune Smithy sloth canon for the seed 0 1 4 However there are many self similar, "sloth canon" sequences in the [https://oeis.org/wiki/Welcome On-Line Encyclopedia of Integer Sequences] that can't be made using the Tune Smithy method. For a list of some of them see [http://oeis.org/selfsimilar.html Some Self-Similar Integer Sequences] However there are many self similar, "sloth canon" sequences in the [https://oeis.org/wiki/Welcome On-Line Encyclopedia of Integer Sequences] that can't be made using the Tune Smithy method. For a list of some of them see [http://oeis.org/selfsimilar.html Some Self-Similar Integer Sequences]

## Revision as of 22:04, 21 February 2013

The Danish composer Per Nørgård uses an endless self similar (fractal like) strict sloth canon structure in some of his compositions such as his Symphony number 2. He first discovered his sequence in 1959, so long before I got the idea of making sloth canon sequences for Tune Smithy.

Interestingly, his sequence is constructed in a different way from the Tune Smithy sloth canons. It is a strict sloth canon, but has other properties that the Tune Smithy sloth canons don't have, and if you try to make it from a Tune Smithy seed, it just doesn't work.

This is his sequence on the on-line encyclopedia of integer sequences The Danish composer Per Nørgård's "infinity sequence", invented in an attempt to unify in a perfect way repetition and variation 0, 1, -1, 2, 1, 0, -2, 3, -1, 2, 0, 1, 2, -1, -3, 4, 1, 0, -2, 3, 0, 1, -1, 2, -2, 3, 1, ...

His explanation of how it is constructed: the infinity series - Construction by the projection of intervals

A youtube video of his second symphony: Per Nørgård's Second Symphony

## What does it mean to say that these sequences make a sloth canon?

It means that if you take every nth number from the original sequence for suitable n, you get the same sequence again.

So for instance with the fractal tune generated from the 0 1 0 seed in Tune Smithy, if you take every third number in the sequence you get the original sequence again:

This is the Tune Smithy 0 1 0 generated sequence

Number of 1's in ternary (base 3) expansion of n. 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 1, 2, 3, 2, 1, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2,...

So if we underline every third number we get the original sequence again. Numbers highlighted in bold: 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 1, 2, 3, 2, 1, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 0,....

All the Tune Smithy sloth canon type fractal tunes work that way. This is what makes it possible to use them to make sloth canons.

Here is the same sequence played as a sloth canon in Tune Smithy

There are several more sequences in the database that can be made as Tune Smithy seeds in the same way. So:
number of 1's in binary expansion of n (or the binary weight of n) 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, ...

- that's the Tune Smithy sloth canon for the seed 0, 1.

Sum of digits of (n written in base 3) 0, 1, 2, 1, 2, 3, 2, 3, 4, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, 3, 4, 5, 4, 5, 6, 1, 2, ...

- that's the Tune Smithy sloth canon for the seed 0, 1, 2

Sum of squares of digits of ternary representation of n 0, 1, 4, 1, 2, 5, 4, 5, 8, 1, 2, 5, 2, 3, 6, 5, 6, 9, 4, 5, 8, 5, 6, 9, 8, 9, 12, 1, 2, ...

```- that's the Tune Smithy sloth canon for the seed 0 1 4
```

However there are many self similar, "sloth canon" sequences in the On-Line Encyclopedia of Integer Sequences that can't be made using the Tune Smithy method. For a list of some of them see Some Self-Similar Integer Sequences

## This is not the same thing as a fractal sequence

Confusingly, the word "fractal" has already been applied to a different type of number sequence, one which has a different type of self similarity. See Fractal Sequence.

So, not sure what to call this type of sequence. Calling it a self similar sequence doesn't distinguish it from the fractal sequence as that is also self similar in a different way (by removing the first occurrence of each number in the sequence).

For now, let's just call them "sloth canon sequences" because when you turn them into music, you get sloth canons if you add extra instruments to play every nth note, and every n2th note and so on.

### Another way of looking at the Tune Smithy sloth canon sequences

The idea here is to generalize the result above that the 0 1 0 seed gives you the sequence of the number of 1's in ternary (base 3) expansion of n

We can find a similar definition for any of the Tune Smithy sequences if we use weighted digit sums - the same idea as a Checksum

We can turn any Tune Smithy seed into a suitable weighted sum such that the weighted sum of the digits of n to an appropriate base gives the nth number in the sloth canon sequence for that seed.

### Example to show how it works

So given any Tune Smithy seed, beginning with 0, say 0 2 -1.

The idea is - first you set the base for your number system to the length of the seed, here 3.

Then you have to choose appropriate weights for each digit, so here, first digit 0, it doesn't matter what weight you give it as it always multiplies out to give 0. Then we want to evaluate 1 as 2, as a weighted sum (the second number in the seed), so give it the weight 2. Then we want to evaluate 2 as -1 as a weighted sum, so we give the weight -0.5.

So our weights for the digits are

1, weight = 2
2, weight = -0.5

Now if we find the weighted sum of the digits of n expressed to base 3, we will get the endless tune smithy sloth canon sequence
0, 2, -1, 2, 4, 1, -1, 1, -2,...

So for instance the number 7 (decimal) is 21 (base 3).

The weighted sum of the digits for its digits is 2*-0.5 + 1*2 = 1.

Since we are counting starting from 0, then this is the 8th number in the sloth canon sequence, and as we can confirm, the 8th number in this sequence is 1.

### Generalization of the Tune Smithy construction

You can make all the Tune Smithy sloth canons using weighted digit sums in this way, because you just need to choose an appropriate base and a weight for each digit. It is easy to seee that the sloth canon construction method for Tune Smithy gives exactly the same result as this weighted sum approach.

Doing it this way though shows that the result isn't limited to integer sequences. It also generalizes to sequences of rationals (fractions) and reals (with infinite decimal expansions like PI) and even complex numbers (using square root of -1) (indeed, for mathematicians, you can also generalize to any field or ring for the weights).

### More digit sum sloth canon sequences in the OEIS

A007953: Digital sum (i.e. sum of digits) of n 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 3, 4, 5, 6, 7, 8, 9, 10,

A003132: Sum of squares of digits of n 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 4, 5, 8, 13, 20, 29, 40, 53, 68, 85, 9, 10, 13, 18, 25, 34, 45, 58, 73, 90, 16,...

A053737 Sum of digits of (n written in base 4) 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6, 4,

## Sums of digits modulo the base

Note, these can't yet be played in Tune Smithy, at least not in an easy way, though it would be straightforward to add the option to take the modulus and so play them.

Of course it makes no difference to the sloth canon property if you take the modulus:

## What about the other sloth canon integer sequences

As we see from the The Danish composer Per Nørgård's "infinity sequence" then there are other sloth canon integer sequences, and in fact there are many others.

Another simple example is this one: Write n in ternary, sort digits into increasing order 0, 1, 2, 1, 4, 5, 2, 5, 8, 1, 4, 5, 4, 13, 14, 5, 14, 17, 2, 5, 8, 5, 14, 17, 8, 17, 26, ...
It's a sloth canon sequence - if you take every third number you get the original sequence again 0, 1, 2, 1, 4, 5, 2, 5, 8, 1, 4, 5, 4, 13, 14, 5, 14, 17, 2, 5, 8, 5, 14, 17, 8, 17, 26,...
But it's not a tune smithy type sloth canon, you can't get it using the seed 0 1 2.

We've already seen the Tune Smithy sloth canon sequence for 0 1 2: Sum of digits of (n written in base 3) 0, 1, 2, 1, 2, 3, 2, 3, 4, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, 3, 4, 5, 4, 5, 6, 1, 2, ...
- that's the Tune Smithy sloth canon for the seed 0, 1, 2, and as you can see it is a completely different sequence, just the first four numbers are the same (as they have to be of course).

So, there are lots of particular examples of that type on this page: Some Self-Similar Integer Sequences

But, are there any other methods of constructing infinitely many sloth canon sequences? Is there any way to classify all the sloth canon sequences?

## General way to make any infinite sloth canon sequence

The observation that makes it possible to generalize this construction is that a sloth canon sequence is under determined, and it doesn't matter what you put in the gaps.

So suppose the first three numbers are 0 1 2, and you want it to be the same when you take every 3rd number. Then so far these numbers are fixed:

0, 1, 2, 1, *, *, 2, *, *, 1, *, *, *, *, *, *, *, *, 2, *, *, *, *, *, *, *, *, 1, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *

So - in fact infinitely many numbers are already fixed, but they get sparser as you go along the sequence.

We can proceed now by putting anything we like in the next available gap, and fill in any of the numbers that are implied by the sloth canon structure - just two more 15's are needed in this short fragment but there are of course infinitely many of them in the complete sequence:

0, 1, 2, 1, 15, *, 2, *, *, 1, *, *, 15, *, *, *, *, *, 2, *, *, *, *, *, *, *, * 1, *, *, *, *, *, *, *, *, 15, *, *, *, *, *, *, *, *, *, *, *, *

Then can put anything in the next gap and so continue the process.

0, 1, 2, 1, 15, -22, 2, *, *, 1, *, *, 15, *, *, -22, *, *, 2, *, *, *, *, *, *, *, * 1, *, *, *, *, *, *, *, *, 15, *, *, *, *, *, *, *, *, -22, *, *, *

Obviously you can keep going like that and the result will be a sloth canon sequence, no matter what you do.

Also the other way around, any sloth canon sequence can be constructed in this way because we are just using the rules that define the sloth canon to construct it.

## Could this be useful for Tune Smithy for the future?

As described so far, the construction is so general you have to keep making choices as you go along the sequence, so it is a bit to general to be useful for algo comp as it stands.

However, you could use it with a randomizing element - randomly choose the under-determined numbers as you go along.

Or, another idea, you could start with the Tune Smith sloth canons (or maybe some other sloth canon sequence as your starting point) - then have some way for the user to adjust any of the numbers that can be adjusted without disturbing the sloth canon, and Tune Smithy then automatically adjusts all the numbers that get changed as a result of it.

Quite a lot of work so probably won't do that any time soon. But nice idea for FTS for the future when I have more time :).

## A consequence of this construction of interest to mathematicians - there are uncountably many sloth canon integer sequences of any similarity period n

With the Tune Smithy construction method, you can make only countably many sloth canon integer sequences, because you can enumerate all the possible Tune Smithy strict sloth canons by enumerating all possible finite seeds.

But the sequence generated by this more general process can't be enumerated, because you have infinitely many choices you can make while constructing the sequence using the method just described. You can choose any number you like at each stage in the process.

So there are uncountably many such sequences. Indeed, there are uncountably many for any repetition length n >= 2 as well.

A more rigorous way to show this:

Suppose there exists an enumeration of all possible sloth canon sequences self similar at n = 2 and with first number 0. (Or if you are a constructivist mathematician, you say, suppose you can construct such an enumeration, it doesn't matter, the reasoning is the same).

So - we have already said the first number is going to be 0. But so far the other numbers might be anything.

Now set the 2nd number to any number different from the second number in the 1st sequence in our enumeration, say, 3, giving:

0, 3, *, *, *, ...

This then determines some more of the numbers like this:

0, 3, 3, *, 3, *, *, *, 3, *, *, *, *, *,

Now set the 4th number in our sequence to anything that differs from the 4th number in the 2nd sequence in our enumeration:

0, 3, 3, 5, 3, *, 5, *, 3, *, *, *, 5, *,

Similarly, set the 6th number in our sequence to anything that differs from the 6th number in the 4th sequence in our enumeration:

0, 3, 3, 5, 3, 7, 5, *, 3, *, 7, *, 5, *,

and so on.

In this way we get a new sequence which is nowhere in our enumeration. So the enumeration is incomplete.

So usual diagonalization argument, we have shown it is impossible to do it, no such enumeration can exist, so there are uncountably many of these sequences - even in this simplest case of n = 2 and first number set to 0.

Of course you can use the same argument for any n.

## The Maths

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

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

Then 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?

You can contact me at support (at) robertinventor (dot) com

## Musical Examples

You can play any of the sequences in the OEIS database using their Music page and enter in the sequence name

You can find recordings of Per Nørgård's symphony number 2, which makes use of his "infinity sequence", on youtube such as this recording: Per Nørgård's Second Symphony

For some midi examples of the Tune Smithy type sequences, worked up as actual sloth canons, Tune Smithy Sloth Canons

Here are some of the Tune Smithy fractal tunes using various sloth canon sequences applied to various tuning systems:

For instance the first one uses a sloth canon sequence constructed from the seed 0, 1, 2, 0, 6, 0 using the tune smithy construction method.

This means you can think of the numbers as the weighed sum of the digits in a base 6 expansion with weight
1, weight 1
2, weight 1
3, weight 0
4, weight 1.5 (so the '4' is counted as 6 after weighting(
5, weight 0

and here is the result (it is somewhat "obfuscted" as it is played on a non linearly ordered, microtonal tuning that repeats at the fourth, 4/3, but that makes no difference to the sloth canon properties, it is still a sloth canon type melody, if you take every sixth note in the tune you get the original tune again.):