Help for Tune Smithy Koch snowflake icon.gif

Self Similar Sloth Canon Number Sequences

From Tune Smithy

(Difference between revisions)
Jump to: navigation, search
(Could this be useful for Tune Smithy for the future?)
(A consequence of this construction of interest to mathematicians)
Line 136: Line 136:
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.
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 you had an enumeration of all possible sloth canon sequences self similar at n = 2 and with first number 0.
+
A more rigorous way to show this:
-
Then - the first number is 0 so the sequence goes
+
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).
-
0, *, *, *, *, ...
+
-
We can't deduce anything yet.
+
So - we have already said the fist 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 second sequence in our enumeration, say,  
+
Now set the 2nd number to any number different from the second number in the 1st sequence in our enumeration, say, 3
0, 3,  *, *, *, ...
0, 3,  *, *, *, ...
Line 150: Line 149:
0, 3, 3, *, 3, *, *, *, 3, *, *, *, *, *,
0, 3, 3, *, 3, *, *, *, 3, *, *, *, *, *,
-
Now set the 4th number in our sequence to anything that differs from the 4th number in the 3rd sequence in our enumeration:  
+
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, *,
0, 3, 3, 5, 3, *, 5, *, 3, *, *, *, 5, *,
Line 162: Line 161:
In this way we get a new sequence which is nowhere in our enumeration. So the enumeration is incomplete.
In this way we get a new sequence which is nowhere in our enumeration. So the enumeration is incomplete.
-
So usual diagonalization argument, it's impossible to enumerate the sequences, so there are uncountably many of them.
+
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 the case of n = 2 and first number set to 0.

Revision as of 01:20, 22 January 2013

The Norwegian 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

Contents

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.

There are several more in the database. 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, ...
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).

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 many other sloth canon integer sequences.

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 that one: 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 is - that 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 one more in this short fragment:

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

This construction shows that there are uncountably many such sequences.

With the Tune Smithy construction 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 fist 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 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 8th 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 the case of n = 2 and first number set to 0.

Personal tools
Namespaces
Variants
Actions
Navigation
How to use the wiki
More
Toolbox