Tagged: Algorithms

Fun With Sequences

I like sequences that have non-conventional definitions. For example, there is the very non-equational Look and Say Sequence made famous by Conway:

\{1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131211, \ldots \}

This starts with the seed value 1, and each successive term is generated by looking at the previous term, saying the numbers appearing there out loud, and writing down the numbers you find yourself saying. For instance, the term ‘111221’ becomes “Three ones, two twos, one one”, which transliterates to ‘312211’.

Despite this crazy generating rule, there is actually a lot of structure to be found in this sequence. Conway found that certain strings of digits, once created, never interacted with those to their left or right again, instead going through an internal ‘life cycle’, growing and changing until it reached a point where it was a string of several such atomic strings joined together; each of these then went off in their own life cycle like some strange numerical mitosis. Conway actually named these atomic strings after the elements, since he found 92 such atomic strings containing the numbers 1, 2, and 3 alone, and two ‘transuranic’ strings for each other natural number.

Conway also found that the ratio of the length of successive terms approaches a constant, and gave a degree-71 polynomial of which this constant is the only real root.

The Look and Say Sequence is surprisingly fruitful, given how non-mathematical its rule seems.

Continue reading

Advertisements

Complete Word Tours

Suppose we were to take a finite alphabet \mathbb{A}_n of n letters, say \{ 0, 1, \ldots, n-1\}, and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:

\{00, 01, \ldots, 0(n-1), 10, 11, \ldots, (n-1)(n-1)\}

and there are n^2 many of these. Let’s denote the set of length-m words using the alphabet \mathbb{A}_n by \mathbb{W}^m_n.

What I am interested in now is “For a given n and m, what is the minimum length string of letters I can write down and still be sure that every word in \mathbb{W}^m_n appears somewhere in it as a substring?”. Why might I be interested in such a thing? Because I really should be working on my PhD, that’s why.

Example:

01100

contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of \mathbb{W}^2_2 appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,

0011101000

and

0201221100

are examples of optimal tours through \mathbb{W}^3_2 and \mathbb{W}^2_3 respectively, as they both have this property that each letter added after the first m adds a previously unseen word.

Notice I’ve introduced the terminology tour for any string \tau that contains all words in a given \mathbb{W}^m_n, with optimal tour being the tour \tau^m_n that is of minimum possible length for that m and n.

Continue reading

Avian Flow: Continuum Boid Dynamics

I’m excited for this, if only because of the enormous amount of humorous nomenclature that will come of it. Ok, here we go.

Have you ever heard of Boids? Boids (‘Birds’ with a Brooklyn accent) refers to a certain type of algorithm for simulating the flocking of large numbers of animals – for example, the eponymous birds. The word refers both to the algorithm itself and to the individual elements being simulated, which are rendered onscreen and whose motion through simulated space evolves according to a set of three rules. The particular details of the algorithm may vary from implementation to implementation, but these three main features of the Boids’ are usually the same.

Boids, as entities, possess a position and a velocity, and obey the following physical principles:

  1. Alignment. Boids wish to conform to the flight paths of their neighbours, and so will rotate to align their own velocity with the average velocity of neighbouring boids which are sufficiently close.
  2. Cohesion. Boids like to fly in groups, and they like to be as close to the centre of the group as possible. For this reason they also steer towards the mean position of those sufficiently close neighbours.
  3. Separation. Boids don’t, however, like to collide, so they will actively avoid any of their neighbours that come too close.

If you want to have a look at an actual implementation and some wonderful, in-depth visualisations of all of these things, then you can do no better than this post over at Harry Brundage’s blog. Seriously, go over there and have a play. I’ll wait here.

Neat, huh? But why should we care? Why am I talking about boids? Well, the first thing that came into my head when I learned of boids was:

Why not make this a continuous system?

Continue reading