We've done a variation on this puzzle before, but then of course there wasn't a cool XKCD comic.

The sequence can be defined in this way:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

And the conjecture is that no matter what positive starting integer you start from the sequence of numbers will always reach one. I.e., starting from 13 gives the following sequence:

13 40 20 10 5 16 8 4 2 1

For odd numbers we do the following: 3n + 1, where n is the current integer in the sequence. Is the three arbitrary, or does the conjecture not work for other odd values? I.e. if we take the formula as k.n + 1 does every positive integer still eventually reduce to 1?

Three and five are just two values of course.

How far can you check? What bounds are you putting on the calculations? And, how many of your friends have called whilst you've been doing it?

I've always found probabilities and randomness counter intuitive in many ways, and I'm sure I'm not alone. Getting good quality random data out of computers has always been difficult. Normally computer programmers have good access to various pseudo-random number generators (or PRNGs), but their quality varies a lot. These days it's possible to download good quality random numbers from the internet, and one of the Bangspace projects I'm interested involves building a random number source.

A question that comes up of course is how do you tell if a number is random? Of course you can't. If you say “pick a number between one and ten” and I say 3 is that random? Can you tell? Unfortunately you can't. And if that is true what does it mean to talk about the quality of random numbers?

We can only really tell something about random data when there is a lot of it, and the way to tell is to examine the data and look for patterns. If we find any sort of pattern then the data probably isn't really random. It's more or less the case that the easier it is to spot a pattern the less random the data is, or at least the lower the quality of the random data. For example, with a PRNG the only thing that you need to know to establish every number in a sequence is that starting seed for the generator. Every sequence that starts with the same seed will always contain the same numbers, and PRNGs normally don't have that many possible seeds (32 bits is very common, and whilst four billion sounds like a lot of starting positions, it isn't really for a modern computer).

Let's say we have a megabyte of data. A very simple test is that the number zero should only be present, on average, in one out of 256 bytes of data* [*The division of the data into bytes is entirely arbitrary and the same test works in the same way if you split it into 4 bit nibbles, or 16 bit words or anything else — the difference will be in the expected frequency (1/16 for nibbles, 1/65536 for words where it is 1/256 for bytes).].

As an aside, the program is almost certainly going to do a linear scan of the data. If it is to run in sub-linear time then that means it takes the program less time to run than it does to scan all of the data.

Of course what is true for zeros in the file should be true for every other number as well.

Once we have this we can use all of this data together to do a further test on the randomness numbers.

Finally, have a think about doing this in sub-linear time as well.

Over here at ! ¹ [1Web site to follow once we work out the DNS problems.] Ben has been trying to get a film night together to watch the classic old geek film Tron.

Google haven't been quite as slack as we have, and they've worked out a cool game AI programming contest inspired from the bike chase scene² [2It always seems to be the bike chase sequence that gets turned into computer game. There was a particular cool one up at BarCamp Chiang Mai where you got to sit on real bikes and play.].

The competition site is over here and you can enter in a wide variety of programming languages. There's a lot of good information about strategies to pursue in the forums and it's pretty easy to grab some examples and run them off against each other on your local machine.

So, who has some bright ideas for strategies? and who is going to throw some code at this and have a play?

I'm sure everybody who has ever played around with computer programming has at one point or another written some code that draws the Mandelbrot set. It turns out that there's a cool way to calculate π in there too.

The Mandelbrot

If you've not implemented complex numbers before they're fairly simple. A complex number is a binary tuple where the first number is real and the second imaginary, (x, yi). i is the square root of -1. Squaring these numbers is fairly simple:

let sqc (r, i) = ( r * r - i * i, 2 * r * i )

And adding them is even simpler:

let add (r1, i1) (r2, i2) = (r1 + r2, i1 + i2)

The basics of the sequence are to convert the x and y screen position into a complex number over the range -1 to 1 on each axis and then keep squaring and adding:

let step o v = add o (sqc v)

Where o is the original number and v is the result of the last iteration step. The steps are always started with a point at the origin, so at step 0 the value is 0, and at step 1 the value is the complex number we're calculating for.

The normal way to determine if a given location is outside the Mandelbrot is to keep doing the calculation step until the distance from the origin is more than 2 — once we're more than 2 away from the origin then we know that the calculation will keep producing ever bigger numbers. Inside the set the iteration will never complete as the calculation goes into an infinite loop. The distance from the origin is done in the obvious way using Pythagoras' theorem (but now we're not taking the y as a complex number, it's simply a distance along the axis):

let length (r, i) = sqrt (r * r + i * i)

Calculate π

The calculation involves using complex numbers where the real component is -0.75 and is really simple. You decide how accurately you want to calculate π, say we want ±0.2 (the error term), we then do the steps from the Mandelbrot counting how many steps we need until the distance goes to 2 or more. π is the number of steps times our error term takes to get to a distance of 2 or more.

Doing the calculation we get 15 steps so π is 15 × 0.2 ±0.2. We can reduce the error term to get more accurate results.