An Old Problem in Disguise

Here is a well known mathematical problem stated in a slightly different way than usual. See if you can find out which problem I am talking about.

Start with any binary number ending in a 1, e.g.

100101101

Now shift this number one place to the left, filling the rightmost digit with a 1

1001011011

then add this number to the original number

100101101
   1001011011
   ----------
   1110001000

Finally eliminate all trailing zeros

1110001

Now repeat the whole process until you reach the number 1. The question is, will you always end up at the number 1, irrespective of the number you started with?

You probably guessed it by now that this is the well known Collatz problem. In its standard form the Collatz conjecture reads

Given a starting number x₀ and the recursion






the sequence x_n will always reach the number 1.

I have always been fascinated by this problem, but never so seriously that I would have started reading up on it and following the newest results. Only recently I started pondering over it and came up with the representation in the beginning. Naive that I was, I thought I could see some patterns in the binary representation of the problem. Of course I was in no way the first person to think of this an some further reading on Wikipedia revealed that this is one of the standard alternative representations of the problem. Some more extended Google search revealed this online script for calculating the Collatz number sequence in binary form.

I like the binary representation because it somehow reminds me of cellular automata. In a cellular automaton the state of a cell in the next generation is determined by the states of the cells in a given neighbourhood in the previous generation. Although it looks similar, the binary Collatz problem doesn't map in a straightforward way onto a cellular automaton. This is because the addition of the two binary numbers can cause non-local changes due to the carry over. It turns out, however, that there is a way of translating the Collatz problem into a cellular automaton.

There are a few patterns that one can identify in the binary representation. If a number x ends on k ones then there will be k successive steps where the 3n+1 operation just adds one zero at the end. This means that the number will grow from its original value x to


On the other hand, if x ends in k alternating ones and zeros, then the next 3n+1 operation will turn this sequence into zeros and the result will be


These quick investigations have certainly sparked my interest in the Collatz conjecture again, and I am now looking forward to reading a bit more in depth on the problem.

NetPNM ... or "A complete image class in C++ in less than 70 lines"

I really love computer graphics and I like creating images using mathematical algorithms. Of course there are many programs out there that let you do that but sometimes you just want to write your own code. My preferred language for this is C++. But then the question arises how to write a picture to disk without linking to some complicated library.

The solution comes in the form of the NetPBM (or portable any map) format, probably the simplest image format out there. Here I will present a very simple but complete image class, including a struct to hold RGB colour triplets and a function for writing the image to a file.

All this will take less than 70 lines of code. In these 70 lines I will even get to write a main function that will fill an image with some colours and save it to disk.

First, let's include some headers

#include <boost/scoped_array.hpp>
#include <iostream>
#include <fstream>
#include <cmath>

I like using the boost smart pointers. This eliminates many destructors and rids me of the worry about memory management.

Next comes a struct to hold RGB colours. It comes with a default constructor and a convenience constructor that takes the three colour values. Colours are stored in 8 bit unsigned chars.

struct Colour
{
    Colour() {}
    Colour(unsigned char r_, unsigned char g_ , unsigned
char b_)
      : r(r_), g(g_), b(b_) {}
    unsigned char r, g, b;
};

Now comes the image class. Internally it holds a smart pointer to an array of colours and two ints specifying the width and the height of the image.

I like to use typedefs for the smart pointers to make it more clear what type data the array holds.

class Image
{
  private:
   typedef boost::scoped_array<Colour> pColour;
    int width, height;
    pColour data;

Next we have two constructors, one default constructor creating an empty image and one constructor creating an image of given size.

public:
    Image() : data(0), width(0), height(0) {}
    Image(int width_, int height_)
      : width(width_), height(height_), data(new 
Colour[width_*height_]) {}

We have a default constructor, so we also need a way to change the size of the image after construction. For this I will write a function called resize. Note that the boost::scoped_array takes care of deallocating the array should it already contain data.

void resize(int width_, int height_)
    {
      width = width_;
      height = height_;
      data.reset(new Colour[width*height]);
    }

We also need some way of accessing the image data. Being a good boy, I will write a const and a non-const accessor.

Colour& at(int x, int y) { return data[x + width*y]; }
    const Colour& at(int x, int y) const { return 
data[x + width*y]; }

So much for the basic functionality. I promised a function that writes the image to a file. It turns out that the netpbm format in its ascii version is so simple that this function will only take about 10 lines of code. The file is completely in ASCII format, so it is readable with any text editor. It starts with the "magic number" P3 followed by any number of comment lines (starting with #). The next line contains the size of the image
As two numbers width and height. The last line of the header contains the bit depth of the image, normally 255. After that we just write all the R, G and B values in ASCII format separated by whitespace.

void write(std::ostream &os)
    {
      // writing the header
      os << "P3\n"
         << "# created using ctidbits by themathsgeek 
(themathsgeek.blogspot.com)\n"
         << width << " " << height << "\n"
         << "255\n";
      for (int i=0; i<width*height; ++i)
      {
        Colour c = data[i];
        os << int(c.r) << " " << int(c.g) << " " << 
int(c.b) << "\n";
      }
    }
   
};

That's it (the last bracket closes the class definition). Now we are ready to test our class.

int main()
{
  Image img(800,600);
  for (int x=0; x<800; ++x)
    for (int y=0; y<600; y++)
    {
      float r = cos(sqrt(x*x + y*y)/50.0);
      float g = sin(x/50.0);
      float b = cos(y/50.0);
      Colour c( (unsigned char)(255*(0.5*r + 0.5)),
                (unsigned char)(255*(0.5*g + 0.5)),
                (unsigned char)(255*(0.5*b + 0.5)));
      img.at(x,y) = c;
    }

  std::ofstream os("test.pnm");
  img.write(os);
  os.close();
}

The pnm format is a little bit bulky in terms of memory but you would normally convert it to some other format before storing or uploading anyway, so that doesn't really matter. On Linux you can use ImageMagick convert to quickly convert into other formats. On Windows you can use Photoshop or Paint Shop Pro.

C++ Binary Stream Manipulator

I would consider myself an enthusiastic C++ programmer. I don't know all the internals of the STL library or all the C++ standard but I know how template programming works and frequently make use of the boost libraries.

Whenever I program any little project, I go to some length to write some of the code in such a general way that I might be able to re-use it later. In a current project I want to write out numbers to std::cout (or any stream for that matter) in binary format. Instead of just writing a little function which does the trick, I decided that I want to have a manipulator, much the same as the hex or oct manipulator of the STL. So what I want to be able to write in my code is

std::cout << binary << x;

and then x would be written in binary format.

Let' start with the easier task. So first I want to be able to write

std::cout << toBinary(x);

Somehow my sense of programming style commands me not to take the obvious route and create a temporary string object which is then passed to the << operator. I want to write the binary directly to the stream. But then I also want to be able to use toBinary like this

std::string s = toBinary(x);

This means that toBinary can't be a straightforward function. Instead it is a class. I will derive it from an abstract base class like this

class toBinary : public stream_formatter {
  private:
    unsigned long val;
  public:
    toBinary(unsigned long val_) : val(val_) {}
    virtual std::ostream& toStream(std::ostream& os) const
    {
      unsigned long tmp = val;
      unsigned long tmp2 = 0;
      int length = 0;
      while (tmp != 0)
      {
        tmp2 = (tmp2<<1) | (tmp&1);
        tmp = tmp>>1;
        ++length;
      }
      if (length==0)
      {
        os << '0';
        return os;
      }
      
      while (length>0)
      {
        os << (tmp2&1)?'1':'0';
        tmp2 = tmp2>>1;
        --length;
      }
      return os;
    }
};

Now we can overload the << operator for this class

std::ostream& operator<<(std::ostream& os, const stream_formatter &conv)
{
  return conv.toStream(os);
}

This completes my first task, I can write std::cout << toBinary(x); In order to be able to assign a toBinary object to a string, I add the typecast operator to the toBinary class

operator const std::string()
    {
      std::ostringstream os;
      this->toStream(os);
      return os.str();
    }

This does the trick and now I can write std::string s = toBinary(x); But what about my original quest? I thought that should be relatively straightforward. Alas, it isn't. After a little search on Google, I found this tutorial on how to write your own manipulators. The tutorial tells you how to write a manipulator that modifies the value of a number. It doesn't tell you how to write a completely new output handler from scratch. It turns out that it involves a little more inside knowledge of the STL than I thought.

I will keep trying and I will report here, when I know more.

My favourite maths joke

Here is my favourite maths joke. It's really a joke about mathematicians and not about maths.

Two men are travelling in a hot air balloon. The wind suddenly freshens up and the get carried away inside a cloud. Once the wind dies down the two men are properly lost. Fortunately they see a man walking along a road below them. As they are heading for the man they call towards him "Excuse us Sir, could you please tell us where we are?"
The man stops dead in his track and looks at the two travellers, but he doesn't answer. The balloon continues to fly towards the man on the road until it is straight above him. Still no answer. The balloon flies on and, just when it is almost too far away and the two travellers had almost given up any hope of getting an answer, the man on the road shouts to them: "Dear Sirs! You are located in a basket beneath a hot air balloon."
The travellers look at each other in astonishment, until one of them says "That man was a mathematician." "How do you know that?" asks the other. "Well, there are three reasons
a) He took a very long time to come up with a response.
b) His answer was absolutely correct.
c) What he said did not help us in any way."

Fractal Bubbles

In the past weeks I have started playing around with the good old fractal generator. Of course we all know the mother of all fractals, the Mandelbrot set (at least my fellow geeks will know it). The Mandelbrot set is based on the iteration

in the complex plane. There are a lot of other fractals with different iteration formulas out there, but I always thought they looked similar to the original.

But then I found Gnofract, and it opened my eyes. Instead of changing the formula, why not change the colouring method. Here is my first example of a fractal so generated. I call it "Bubbles" because it looks like lots of bubbles floating in space.

Bubbles

P.S. If you click on the image, the link will take you to Zazzle. If you really like the picture, and/or if you like this blog so much that you want to support it financially, feel free to purchase products from my Zazzle gallery.

Welcome!

Hi and welcome to my blog. It's called "The Maths Geek" because I am one. It could have been called "The Math Geek" but, firstly, that name was already taken and, secondly, I prefer the British spelling over the American one. And in Britain we say "maths" and not "math".

There! I started my blog nit-picking on some grammatical issue. This qualifies me, at least partially, as a geek.

So read on and enjoy.