Help for Tune Smithy Koch snowflake icon.gif

Self Similar Sloth Canon Number Sequences

From Tune Smithy

Revision as of 11:31, 24 January 2013 by WikiSysop (Talk | contribs)
Jump to: navigation, search

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

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. This is what makes it possible to use them to make sloth canons.

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,

similarly: A053737 Sum of digits of n written in base 5, A053827 Sum of digits of n written in base 6, A053828 Sum of digits of n written in base 7, A053829 Sum of digits of n written in base 8, A053830 Sum of digits of n written in base 9 , A053831 Sum of digits of n written in base 11, A053832 Sum of digits of n written in base 12, A053833 Sum of digits of n written in base 13, A053834 Sum of digits of n written in base 14, A053835 Sum of digits of n written in base 15, A053836 Sum of digits of n written in base 16,

A173528 a(n) = 1 + sum of digits of n-1 written in base 8, A173525 1+A053824(n-1), where A053824 = sum of digits in base 5,

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

A053838 (Sum of digits of n written in base 3) modulo 3. 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1, 2, 0, 1, 2, ... A053839 (Sum of digits of n written in base 4) modulo 4, A053840 (Sum of digits of n written in base 5) modulo 5, A053841 (Sum of digits of n written in base 6) modulo 6, A053842 (Sum of digits of n written in base 7) modulo 7, A053843 (Sum of digits of n written in base 8) modulo 8, A053844 (Sum of digits of n written in base 9) modulo 9,

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 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 an integer sequence f(n) is a map from the non negative integers to the integers. So the first term in the sequence is f(0).

Definition of a sloth canon sequence

A sloth canon sequence as an integer sequence f(n) (mapping from natural numbers to 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, there are uncountably many 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.

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

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 the lemma above, we see that w(n) = f(n) for all n.

QED

Definition of a Per Nørgård sequence

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

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

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) )

Lemma 3, A Per Nørgård sequence can be obtained from binary numbers by a sort of alternating digit sum (WORK IN PROGRESS)

See A004718, and 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.

We need to prove that this construction satisfies the rules 1. and 2. above.

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

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

Lemma 4. 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 5. The even numbered members of a Per Nørgård sequence are the inversion of its odd numbered members. (WORK IN PROGRESS)

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

OEIS Music page

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:

Play & Create Tunes as intricate as snowflakes - Videos

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.):


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