tag:blogger.com,1999:blog-41452548900406951922024-03-13T19:28:51.299-07:00The Maths GeekThe Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-4145254890040695192.post-67163370252988058812011-06-23T04:39:00.000-07:002011-06-23T04:39:46.529-07:00Non-Vedic Maths: Half and five for the odds<p>In my series of <a href="http://themathsgeek.blogspot.com/2011/05/non-vedic-maths-introduction.html">Non-Vedic maths</a> I will present mental arithmetic techniques that allow you to speed up your number-crunching. In contrast to Vedic maths, I will also explain why these techniques work. I believe that being able to add and multiply quickly does not make a good mathematician. But understanding how things work and being able to develop your own techniques is more important.
</p><p>Enough already! I'm repeating myself!
</p><p>Today's technique teaches how to multiply any number by 5, 50, 500 etc. The technique is based on the simple fact that
</p>
<pre>5 = 10/2
</pre>
<p>In this way multiplication by 5 is the same as multiplication by 10 and the division by 2. By using a technique for quickly dividing by 2 the method is accelerated further.
</p><p>So let's start with an example. Say you want to multiply 3465 by 5. We start with multiplying by 10, i.e. adding a zero at the end
</p>
<pre>3465 × 5 = 34650 / 2
</pre>
<p>Dividing by two can be done in two ways. If you know your multiples of two up to 9×2=18 by heart then the traditional method is probably best. Just divide every digit from left to right including the carry over from the remainder. Note that the carry over is either 0 or 1, so the largest number that you will ever have to divide is 19. In our example we get
</p>
<pre>34650 / 2 = 17325
</pre>
<p>This is our result!
</p><p>Some people are not as comfortable or quick with dividing numbers above 10 by 2. For these people the following alternative method might be faster. First divide every digit by 2 and forget about the remainder or carry over,
</p><p><br />
</p>
<pre>34650
12320
</pre>
<p>Next we shift the number to divide one place to the right (this was our original number) and replace every even digit with 0 and every odd digit with 5.
</p>
<pre>3465
5005
</pre>
<p>This second step effectively accounts for the carry overs that we missed in the first step. Now add the results of these two operations together
</p>
<pre>12320
5005
-----
17325
</pre>
<p>Because all the digits of the first number result from division of numbers less than ten, none of the digits can be larger than 4. For this reason we never have to worry about carry-overs when adding the two numbers.
</p><p>For a slightly more mathematical explanation to what we have done here, let's write 34650/2 in the following way
</p>
<pre>34650/2 = (24640 + 10010)/2
= 24640/2 + 10010/2
= 12320 + 5005
= 17325
</pre>
<p>To summarise, in order to multiply a number by five
</p>
<ul><li> append a zero at the right of the number
</li><li> divide every digit by two, ignoring any remainders
</li><li> add five to every digit to the right of an odd digit of the number that you got after the first step.
</li></ul>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com2tag:blogger.com,1999:blog-4145254890040695192.post-85135824589557764132011-06-15T04:52:00.000-07:002011-06-15T04:52:35.356-07:00Catalan's theorem and Pillai's conjectureNumber theory always surprises by the seemingly simple questions which turn out to be extremely hard or maybe even impossible to answer. One such question concerns perfect powers of the type
<br />
<span class="texhtml"><i>x</i><sup><i>n</i></sup></span>
<br />
where both <span class="texhtml"><i>x</i></span> and <span class="texhtml"><i>n</i></span> are natural numbers. Can we say, which numbers can be expressed as perfect powers? If we don't further restrict <span class="texhtml"><i>n</i></span> then the answer is simple. Any number <span class="texhtml"><i>x</i></span> can be represented as <span class="texhtml"><i>x</i><sup>1</sup></span>. So that means the set of numbers that can be represented as perfect powers is the complete set <img alt="\mathbb{N}" class="tex" src="http://3.bp.blogspot.com/-O2S_2V4UueM/TfiaEX5KV4I/AAAAAAAAAGQ/l7yuURID65I/s1600/natural_numbers.png" />. So this question is boring.
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-UX3D9KEDI2Q/TfibZUQ_5GI/AAAAAAAAAGk/40YX3VVFICs/s1600/powers100.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://4.bp.blogspot.com/-UX3D9KEDI2Q/TfibZUQ_5GI/AAAAAAAAAGk/40YX3VVFICs/s1600/powers100.png" /></a></div>
<br />
But what if we exclude these trivial powers and say that n must be greater than 1? The list of these numbers is the sequence <a href="http://oeis.org/A001597">A001597</a> in OEIS. On the right is a plot of the first 100 of these numbers <span class="texhtml"><i>a</i><sub><i>n</i></sub></span>. As you can see, the numbers seem to grow more than linearly. In fact for large numbers they seem to grow with <span class="texhtml"><i>n</i><sup>2</sup></span>. This seems to suggest that the gaps between two consecutive numbers also needs to grow. This is intuitively right. As the numbers grow, there are less and less candidates that could produce perfect powets.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-_mQr_4FqBZg/TfibkCuDOuI/AAAAAAAAAGo/GMwClyo-n9I/s1600/powerdiff1000.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-_mQr_4FqBZg/TfibkCuDOuI/AAAAAAAAAGo/GMwClyo-n9I/s1600/powerdiff1000.png" /></a></div>
But how large are the gaps exactly? More interestingly, as the gaps grow larger, do we still encounter some small gaps? The plot on the left shows the differences <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> between two consecutive elements of the sequence plotted against the smaller number for the first 1000 or so numbers
<br />
<span class="texhtml"><i>g</i><sub><i>n</i></sub> = <i>a</i><sub><i>n</i> + 1</sub> − <i>a</i><sub><i>n</i></sub></span>,
<br />
i.e. we're plotting <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> against <span class="texhtml"><i>a</i><sub><i>n</i></sub></span>. It can be seen that most of the <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> seem to lie close to a curve given by
<br />
<img alt="G(x)= 2 \sqrt{x} + 1" class="tex" src="http://1.bp.blogspot.com/-WDtqtVcsrwk/TfiaE5dCr4I/AAAAAAAAAGY/wOxrfVnILAU/s1600/pillai_limit.png" />
<br />
which also limits the <span class="texhtml"><i>g</i><sub><i>n</i></sub></span>. This simple form is amazing at first, however it becomes quite clear when one looks at just the square numbers <span class="texhtml"><i>x</i><sup>2</sup></span>. If <span class="texhtml"><i>a</i><sub><i>n</i></sub></span> is a square number then <img alt="(\sqrt{a_n}+1)^2" class="tex" src="http://2.bp.blogspot.com/-bJ38OP9xM0Q/TfiaEkg-b4I/AAAAAAAAAGU/NJxzkJ9kVsU/s1600/next_square.png" /> is also a perfect square. The difference between the two numbers is <img alt="2 \sqrt{a_n}+1" class="tex" src="http://1.bp.blogspot.com/-PoZiaIMbqaU/TfiaFIpZslI/AAAAAAAAAGc/n7OevVAMDbY/s1600/square_diff.png" />. Only few numbers seem to depart from this behaviour and have a lot smaller values. This always happens when there is at least perfect power, that is not a square, between two perfect squares.
<br />
So we have an upper bound for the <span class="texhtml"><i>g</i><sub><i>n</i></sub></span>. But is there a lower bound for the <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> that increases with <span class="texhtml"><i>n</i></span>. Or does <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> always have excursions to small numbers? Let's look first at the smallest possible value <span class="texhtml"><i>g</i><sub><i>n</i></sub> = 1</span>.
<br />
Catalan's theorem makes a statement about this particular case. It says that there is only one <span class="texhtml"><i>n</i></span> for which <span class="texhtml"><i>g</i><sub><i>n</i></sub> = 1</span>, or in the full notation
<br />
<span class="texhtml"><i>x</i><sup><i>n</i></sup> − <i>y</i><sup><i>m</i></sup> = 1</span> has only one solution, which is <span class="texhtml">3<sup>2</sup> − 2<sup>3</sup> = 1</span>
<br />
Until 2002 this was Catalan's conjecture but then it was proven by Preda Mihăilescu. Long before this proof Pillai generalised the the Catalan conjecture and speculated about the solutions of the equation
<br />
<span class="texhtml"><i>x</i><sup><i>n</i></sup> − <i>y</i><sup><i>m</i></sup> = <i>c</i></span> for <span class="texhtml"><i>c</i> > 1</span>
<br />
The graph above seems to suggest that for <span class="texhtml"><i>c</i> = 2</span> there is also just one solution
<br />
<span class="texhtml">3<sup>3</sup> − 5<sup>2</sup> = 2</span>
<br />
but to my knowledge this has not been proven. Pillai's conjecture now states that for any value of c, the above equation only has a finite number of solutions. This means that the gaps in the sequence of perfect powers not only grow, but there is some increasing lower bound for the gaps as well. Erdos went one step further and conjectured that this lower bound is given by
<br />
<span class="texhtml"><i>g</i><sub><i>n</i></sub> < <i>n</i><sup><i>k</i></sup></span>
<br />
where <span class="texhtml"><i>k</i></span> is a fixed constant which is greater than one.
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-YwnRd5gzINI/Tfib3Syo2FI/AAAAAAAAAGs/ErNqC5_zPoI/s1600/powerdiff_log.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://1.bp.blogspot.com/-YwnRd5gzINI/Tfib3Syo2FI/AAAAAAAAAGs/ErNqC5_zPoI/s1600/powerdiff_log.png" /></a></div>
From the plot of the first million gaps this does not immediately seem obvious. The figure shows the plot of the gaps <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> against <span class="texhtml"><i>n</i></span> for <span class="texhtml"><i>n</i></span> up to <span class="texhtml">10<sup>6</sup></span> on a double-logarithmic scale. Although the lower bound does seem to grow, the value of the parameter <span class="texhtml"><i>k</i></span> of the Erdos formula, of roughly 0.22 (green line), is determined by a single outlier at <span class="texhtml"><i>a</i><sub>384026</sub> = 143384152921</span> and <span class="texhtml"><i>g</i><sub>384026</sub> = 17</span>. Almaost all other values of <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> lie well above the Erdos curve. Only one other point comes close to the limiting curve at <span class="texhtml"><i>g</i><sub>745174</sub> = 24</span>
<br />
One more interesting feature that can be seen are strange lines in the plot that slope at a slightly lower exponent of about <span class="texhtml">2 / 3</span>. This suggests that there is some hidden structure in the seemingly random behaviour of the <span class="texhtml"><i>g</i><sub><i>n</i></sub></span>. Another feature, which I noticed when plotting the <span class="texhtml"><i>g</i><sub><i>n</i></sub></span> is that there seem to be islands of regularity.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-1RmNB3PiALI/TficG3Kvh8I/AAAAAAAAAGw/PEf7jkP6Cf4/s1600/powerdiff_detail.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-1RmNB3PiALI/TficG3Kvh8I/AAAAAAAAAGw/PEf7jkP6Cf4/s1600/powerdiff_detail.png" /></a></div>
If we zoom in to the region from <img alt="7.4\times10^{11}" class="tex" src="http://1.bp.blogspot.com/-lNjLLpW5_Zk/TfiaD9yg48I/AAAAAAAAAGM/bvVlPL4d9EI/s1600/lower_limit.png" /> to <img alt="7.6\times 10^{11}" class="tex" src="http://1.bp.blogspot.com/-dZwuEA7OjAo/TfiaFT4owdI/AAAAAAAAAGg/p5JYhaiEvoE/s1600/upper_limit.png" /> we get the following plot. Most points are again crowded around the upper limit but the others have the very regular shape of two parabolas intersecting each other.
<br />
As you can see, even formulas that seem simple can have surprisingly rich behaviour and open up very difficult problems.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-72030386842379486432011-06-11T11:35:00.000-07:002011-06-11T11:36:09.776-07:00Is the bitcoin "Black Friday" really a crash?I have been following the development of the internet currency bitcoin for the last few days. I heard a lot of people talking about it, so I thought it might be an interesting option for an online currency. The value of a bitcoin has been steadily increasing over the last few weeks up to a record high of over 30$. Yesterday saw a development in the value of a bitcoin that made the media speak of a "Black Friday". I won't go into the discussion about the morality of this online currency as there have been reports that the drug trade is turning to bitcoins as a payment. But here I want to ask the question: <b>Was the "Black Friday" really a crash?</b><br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-fcTZhZoTCzY/TfOvmYMn9TI/AAAAAAAAAGI/dpfQDs9QDVU/s1600/bitcoin.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="328" src="http://2.bp.blogspot.com/-fcTZhZoTCzY/TfOvmYMn9TI/AAAAAAAAAGI/dpfQDs9QDVU/s400/bitcoin.png" width="400" /></a></div>From the data I got from the <a href="https://www.mtgox.com/">mtgox.com</a> API, I plotted the graph above. Naturally, we should plot any kind of exponential growth on a semi-logarithmic scale. The origin is some arbitrary point in the past, roughly 1000 hours before the time of writing this post. Older data is averaged over larger intervals, because it is not available any more as real-time data. One can see that, on average, the value of the currency has doubled every 7 days. I have also plotted an upper resistance and a lower support that both grow at this constant average growth rate.<br />
<br />
You can see that the value of a bitcoin has kept to this channel between its resistance and its support for almost 1000 hours. And even today it only made a<b> very short excursion below the support curve</b>. Note that it could have made this kind of excursion 200 hours ago as well. The averaged nature of the data for that time period makes it impossible to judge exactly what happened then.<br />
<br />
To be speaking of a "Black Friday" is therefore<b> very premature</b>. All that happened was that the over-exponential growth of the last few days has been compensated for. Of course it has to be seen wether the support will hold. But even if it doesn't, there is a good chance of a <a href="http://www.investopedia.com/terms/s/sidewaystrend.asp">sideways trend</a> to follow the rapid growth of the currency.<br />
<br />
My conscience dictates that I write a <b>warning and disclaimer</b> at the end of this post. I am not endorsing the bitcoin currency and I am not encouraging to invest or to trade in bitcoins. Please be<b> very careful as to where you invest your money</b> and don't take any online article as the ultimate truth about the matter.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-80070589893925448512011-06-02T04:24:00.000-07:002011-06-02T04:24:43.945-07:00Binary Trees in SQL: The Adjacency List<div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-M2cqsC7mzGs/Tedyfi7ICbI/AAAAAAAAAF8/pbToca0_pmc/s1600/Binary_tree.png" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="183" width="220" src="http://4.bp.blogspot.com/-M2cqsC7mzGs/Tedyfi7ICbI/AAAAAAAAAF8/pbToca0_pmc/s400/Binary_tree.png" /></a></div><br />
When learning to program, a key skill is to know you data structures. For every task there is the ideal data structure that makes the task easy and straightforward to implement. But then we are thrown into <i>the real world</i>. In this real world we are told to finish a piece of code with the restriction that the data has to be stored in a SQL database. Most of the time we think of databases essentially being arrays in which the data is stored in a tabular way. In the back of our head we know that a more sophisticated data structure would be more fit for the task, but we don't have the time or can't be bothered to think about these luxuries in more detail. One prime example is the tree data structure. Wouldn't it be great if there was a simple, straightforward way to implement trees in SQL?<br />
<br />
I am going to show how this can be done. As it turns out there is more than one solution to the problem. In this post I will be writing about the first and maybe the most intuitive approach, the adjacency list. In the end this approach will turn out to be OK but not ideal for all applications. In two following posts I will then present more stable approaches to the problem, the <b>nested set</b> and the <b>binary heap</b>.<br />
<br />
<h3>Adjancency List</h3><br />
The adjacency list is probably the implementation of a binary tree that is the easiest to understand and the one that most people would come up with if asked to implement a tree structure. Every entry in the tree connects two elements by a parent child relationship. We want to keep things neat and tidy, so we make sure that we separate data from structure. What this means is that we have a table with all the data, somewhat like this<br />
<br />
<pre>CREATE TABLE people (id INTEGER PRIMARY KEY NOT NULL, name VARCHAR(30));
</pre><br />
Now we define the table that will hold the structure of the tree. Every entry in this tree will link a child node to a parent node and therefore has two references to our data table<br />
<br />
<pre>CREATE TABLE bintree (parent INTEGER, child INTEGER NOT NULL, rel CHAR(1));
</pre><br />
You will notice an extra column 'rel' in this table which can hold the two values 'L' or 'R'. Because we are storing a binary tree, each node is either the left or the right node of it's parent. By specifying the relation to it's parent we can perform proper binary searches in the table. Keeping the two tables separate allows us to create the tree structure for the data relatively independently of the data itself. We could also sort the same data set in two or more trees for different sorting criteria. <br />
<br />
Now let's start populating our tables with data. When we insert a piece of data into our data table, we must also insert the relationship to the other data sets into the tree table. The next two insert statements do the job.<br />
<br />
<pre>INSERT INTO people VALUES (1,'John'),(2,'Ben'),(3,'Sue');
INSERT INTO bintree VALUES (-1,1,''),(1,2,'L'),(1,3,'R');
</pre><br />
But note how we have to take care that we retain the tree structure. The parent must exist and it can have a maximum of one left and one right child node. Only the root node does not have a parent which is denoted by a <i>-1</i> in the parent column. This constraint can be tested using check statements, but I will not go into the details of that in this post. Deleting a leaf node from the tree is also done using two simple drop statements, for example to remove <i>Ben</i> from the tree we execute the following<br />
<br />
<pre>DELETE FROM people WHERE id=2;
DELETE FROM bintree WHERE child=2;
</pre><br />
We have to ensure manually that the node deleted in this way doesn't have any children of its own. If it does, the children will end up <b>orphaned and unreachable</b>. Checking this can again be done using check statements. The real problem arises when you try to delete <b>a node and all it's children</b>. The only way to achieve this is by going through all the elements which are reachable from the node and delete them individually. This can be quite time consuming if you have a larger database. <br />
<br />
Another common task is to find out if one node A is the ancestor of another node C. Again, a number of SQL statements have to be issued. Starting from the child node C, we find it's parent<br />
<br />
<pre>SELECT parent FROM bintree WHERE child=[C]
</pre><br />
If this returns the ancestor A then we know that the two nodes are related by an ancestor-descendant relationship. If the statement returns nothing, then we have reached the root of the tree telling us that the two nodes are not related. If we get any other node then we issue the same command again, but with the new node as the child node. We continue this way until we have either found the ancestor or reached the root node. The PHP code for this algorithm is as follows<br />
<br />
<pre>// a function that returns true if $parent is an ancestor of child and false otherwise
function isAncestor($parent,$child) {
$node = $child;
while ($node != -1) {
$query="SELECT parent FROM bintree where child=".$node;
$result=mysql_query($query); // should return exactly one result
$node=mysql_result($result,0,"parent");
if ($node==$parent) return true;
}
return false;
}
</pre><br />
As you can see, the adjacency list layout for storing trees is not the ideal method. Some simple operations take multiple SQL queries and the consistency of the tree is not automatically ensured. Apart from orphaned nodes we have to avoid cyclic dependencies, where one node ends up to be it's own ancestor. In another post I will write about alternative methods that will alleviate some of these problems.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-55213314498045067952011-06-01T09:15:00.000-07:002011-06-02T03:53:30.719-07:00Two Ladders Puzzle: Answer<div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-MaSk2Z6wCTs/TeZnyXU2r1I/AAAAAAAAAF0/Q5BojMV9bNg/s1600/Ladders_Solution.png" imageanchor="1" style="margin-right:1em; margin-bottom:1em"><img border="0" height="246" width="400" src="http://4.bp.blogspot.com/-MaSk2Z6wCTs/TeZnyXU2r1I/AAAAAAAAAF0/Q5BojMV9bNg/s400/Ladders_Solution.png" /></a></div><p>Previously I posted the <a href="http://themathsgeek.blogspot.com/2011/05/two-ladders-puzzle.html">Two Ladders Puzzle</a> in which two ladders lean against opposite walls. The length of the ladders is given and so is the height of the point where they intersect. The task was to find the distance between the walls. The problem can be solved using Pythagoras and the law of similar triangles, so really it can classify as an easy problem. Nonetheless, the answer requires the solution of a quartic equation. We begin by naming the lengths of the ladders <span class="texhtml"><i>a</i></span> and <span class="texhtml"><i>b</i></span> and the, as yet unknown heights at which the ladders lean against the walls by <span class="texhtml"><i>x</i></span> and <span class="texhtml"><i>y</i></span>. Also let's divide the distance between the two walls into the parts <span class="texhtml"><i>m</i></span> and <span class="texhtml"><i>n</i></span>. We now have 5 unknowns, so we need 5 equations. The easy one is<br />
</p><p><span class="texhtml"><i>m</i> + <i>n</i> = <i>d</i></span> <br />
</p><p>Then we have Pythagoras for the two ladders<br />
</p><p><span class="texhtml"><i>a</i><sup>2</sup> = <i>d</i><sup>2</sup> + <i>x</i><sup>2</sup></span> <br />
</p><p><span class="texhtml"><i>b</i><sup>2</sup> = <i>d</i><sup>2</sup> + <i>y</i><sup>2</sup></span> <br />
</p><p>Finally we have the similar triangles<br />
</p><p><img class="tex" alt="\frac{d}{x} = \frac{n}{h}" src="http://4.bp.blogspot.com/-eiQA1Vpn_rQ/TeZkQY8ShjI/AAAAAAAAAFk/bjE3raz6L68/s1600/ladder_ratiox.png" /> <br />
</p><p><img class="tex" alt="\frac{d}{y} = \frac{m}{h}" src="http://2.bp.blogspot.com/-o9Em_FsaY1A/TeZkQnDlVxI/AAAAAAAAAFo/TANg4yns9ME/s1600/ladder_ratioy.png" /> <br />
</p><p>If we add these two equations, we get the sum <span class="texhtml">(<i>m</i> + <i>n</i>) / <i>h</i></span> on the right hand side. But <span class="texhtml"><i>m</i> + <i>n</i> = <i>d</i></span> and thus we can eliminate d to obtain the nice intermediate result<br />
</p><p><img class="tex" alt="\frac{1}{h} = \frac{1}{x} + \frac{1}{y}" src="http://3.bp.blogspot.com/-6zXxrE9jE1w/TeZkPq6E7hI/AAAAAAAAAFY/wbiV63bdSDM/s1600/ladder_harmonic.png" /> <br />
</p><p>This means that <span class="texhtml"><i>h</i></span> is the <b>harmonic mean</b> of <span class="texhtml"><i>x</i></span> and <span class="texhtml"><i>y</i></span>, independent of the values of <span class="texhtml"><i>a</i></span>,<span class="texhtml"><i>b</i></span> or <span class="texhtml"><i>d</i></span>.<br />
</p><p>The rest of the solution will become a tiny bit messy. Instead of looking for a solution of <span class="texhtml"><i>d</i></span>, we can look first for the values of <span class="texhtml"><i>x</i></span> or <span class="texhtml"><i>y</i></span>. Then we can use Pythagoras to find <span class="texhtml"><i>d</i></span>. To do this we subtract the two Pythagorean equations to eliminate <span class="texhtml"><i>d</i></span> <br />
</p><p><span class="texhtml"><i>x</i><sup>2</sup> − <i>y</i><sup>2</sup> = <i>a</i><sup>2</sup> − <i>b</i><sup>2</sup></span> <br />
</p><p>Solving the harmonic equation for <span class="texhtml"><i>y</i></span> we get<br />
</p><p><img class="tex" alt="y = \frac{hx}{x-h}" src="http://2.bp.blogspot.com/-2dwQZpc6m3Q/TeZkP2IE_YI/AAAAAAAAAFc/gntJyHy-gnk/s1600/ladder_harmonicy.png" /> <br />
</p><p>With this we can eliminate <span class="texhtml"><i>y</i></span> from the above difference of squares<br />
</p><p><img class="tex" alt="x^2-\frac{h^2 x^2}{(x-h)^2} = a^2-b^2" src="http://2.bp.blogspot.com/-L4NiSgxcf5o/TeZkQMtEg6I/AAAAAAAAAFg/64MGY14J1I0/s1600/ladder_quartic.png" /> <br />
</p><p>Obviously this is a fourth order equation for <span class="texhtml"><i>x</i></span>. I know this is not really a nice result so we will have to get some help for solving it. So let's insert the values and stick it into WolframAlpha. Of course there are four possible solutions. We get one positive, one negative and two complex solutions. Only the positive solution of <img class="tex" alt="x \approx 3.03692" src="http://4.bp.blogspot.com/-POQhCsYujvY/TeZkQ-Iqs7I/AAAAAAAAAFw/-UUzKjp_QrM/s1600/ladder_solu_x.png" /> is relevant. Now we can use the first Pythagoras to find the value for <span class="texhtml"><i>d</i></span> <br />
</p><p><img class="tex" alt="d \approx 2.60329" src="http://2.bp.blogspot.com/-9HNKvGhJ3lQ/TeZkQ4PAUxI/AAAAAAAAAFs/ireBM4dNXHI/s1600/ladder_solu_d.png" /> <br />
</p>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com1tag:blogger.com,1999:blog-4145254890040695192.post-19574919641985708942011-05-27T05:40:00.000-07:002011-05-27T05:42:23.309-07:00Tutorial: Midpoint rule<p>In a previous post I spoke about the trapezium rule for integrating functions numerically. The trapezium rule could find the value of an integral with second order accuracy. In this post I will present an alternative method, the midpoint rule. The geometric interpretation of the midpoint rule appears to be more crude than the trapezium rule. Nonetheless, it turns out that the midpoint rule also has second order accuracy.<br />
</p><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-tI5wJUDoulE/Td-YvadP7sI/AAAAAAAAAFQ/Ap5udGnmm6w/s1600/Midpoint.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="241" src="http://4.bp.blogspot.com/-tI5wJUDoulE/Td-YvadP7sI/AAAAAAAAAFQ/Ap5udGnmm6w/s320/Midpoint.png" width="320" /></a></div><p>Like the trapezium rule, we divide our interval <span class="texhtml">[<i>a</i>;<i>b</i>]</span> into <span class="texhtml"><i>N</i></span> equal sections of width <span class="texhtml"><i>h</i> = (<i>b</i> − <i>a</i>) / <i>N</i></span>. The area of each section is now approximated by the area of the rectangle of width h and whose height is given by the function value at the centre of the section. The centre of the nth section is given by <br />
<span class="texhtml"><i>x</i><sub><i>n</i> + 1 / 2</sub> = <i>a</i> + (<i>n</i> + 1 / 2)<i>h</i></span>.<br />
</p><p>Here <span class="texhtml"><i>n</i> = 0,1,...,<i>N</i> − 1</span>. As before, we define <span class="texhtml"><i>f</i><sub><i>n</i> + 1 / 2</sub> = <i>f</i>(<i>x</i><sub><i>n</i> + 1 / 2</sub>)</span>. The area of the <span class="texhtml"><i>n</i></span>th rectangle is then given by <span class="texhtml"><i>h</i><i>f</i><sub><i>n</i> + 1 / 2</sub></span>. And the value of the integral is given by <br />
</p><p><img class="tex" alt="\int_a^b f(x)\;dx = h( f_{1/2} + f_{3/2} + \ldots + f_{N-1/2}) = h\sum_{k=0}^{N-1}f_{k + 1/2}" src="http://2.bp.blogspot.com/-FBU2dQpSbmo/Td-WubLEhOI/AAAAAAAAAFI/WTNWBuiJKBg/s1600/midpointrule.png" /> <br />
</p><p>This is the final form for the midpoint rule. As with the trapezium rule, the accuracy of the integral can be increased by increasing N, i.e. decreasing the step size h. Again we can plot the error of the numerical integral against the number of steps on a logarithmic scale. </p><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-BtU5EXaPNME/Td-W05dKj4I/AAAAAAAAAFM/P3jDtvztV_c/s1600/midpoint.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="http://1.bp.blogspot.com/-BtU5EXaPNME/Td-W05dKj4I/AAAAAAAAAFM/P3jDtvztV_c/s400/midpoint.png" width="400" /></a></div><p>In figure the error of the integral <br />
<br />
<img alt="\int_0^1\sin(\pi x) dx = \frac{2}{\pi} " class="tex" src="http://2.bp.blogspot.com/-R9PXo57pMOU/TcQSNpORmjI/AAAAAAAAAB8/4ao7UXKy-X4/s1600/integral_example.png" /><br />
<br />
when evaluated with the midpoint and the trapezium rule is plotted. Clearly, the midpoint rule has a second order error, as has the trapezium rule. At first sight this is somewhat surprising since the midpoint rule makes no attempt to incorporate the change in the function value over the sections into the approximation.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-0bw66HtzguU/Td-abdwJYnI/AAAAAAAAAFU/850WdUNof7w/s1600/Midpoint2.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="258" src="http://1.bp.blogspot.com/-0bw66HtzguU/Td-abdwJYnI/AAAAAAAAAFU/850WdUNof7w/s320/Midpoint2.png" width="320" /></a></div>To understand the accuracy of the approximation, we have to re-interpret the midpoint formula <span class="texhtml"><i>h</i><i>f</i><sub><i>n</i> + 1 / 2</sub></span> as the area of a trapezoid that intersects the function graph at the midpoint an which has a slope identical to the derivative of the function at that point. It is a simple, but very useful, geometric fact that the area of a trapezoid is the same as the area of a rectangle whose height is the average of the trapezoid's height.<br />
</p><p>Looking at the error curves a bit more closely, we can observe that the error of the midpoint rule is always slightly smaller than that of the trapezium rule. In fact when we divide the two error curves in the region where they decrease with N^2, we get an almost constant error ratio of about 1/2. This will lead us to improve the two methods. But this will be the subject of another post.<br />
</p>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-79585876901464719342011-05-25T10:16:00.000-07:002011-05-25T10:19:06.010-07:00Two Ladders PuzzleThis puzzle is an old favourite of mine. It looks quite straightforward but it's not as easy as one might expect.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-u3OV_FJQhgw/Td04_8Cl0vI/AAAAAAAAAE8/f7fYP1PJWjc/s1600/Ladders.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="206" src="http://2.bp.blogspot.com/-u3OV_FJQhgw/Td04_8Cl0vI/AAAAAAAAAE8/f7fYP1PJWjc/s320/Ladders.png" width="320" /></a></div><br />
Two ladders are leaning against opposite walls in an alleyway. The bottom of each ladder is placed on the ground in the opposite corner. One ladder is 4m long, the other is 3m long. The height at which the two ladders meet is 1m.<br />
<br />
<span style="clear: both;"><br />
<strong>Question: How far are the walls apart?</strong><br />
</span>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com6tag:blogger.com,1999:blog-4145254890040695192.post-67227660265333756372011-05-20T04:13:00.000-07:002011-05-25T04:31:52.700-07:00Short Thoughts: If a tree falls in the forest...<div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-TaqslOhuTOY/TdZMiaO7_rI/AAAAAAAAAEs/Lmfag1F0UGw/s1600/fallentree.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="240" src="http://3.bp.blogspot.com/-TaqslOhuTOY/TdZMiaO7_rI/AAAAAAAAAEs/Lmfag1F0UGw/s320/fallentree.jpg" width="320" /></a></div>...does it make a sound. This seems to be a deep philosophical question, but is it really? It just depends on what your definition of sound is. If you define sound as pressure waves in air then the answer is clearly YES. The pressure waves are there, and might influence other objects in the forest.<br />
<br />
If, on the other hand, you define sound as through the experience of a human being, then you are linking it to the perception of an individual. In this sense the answer is NO. The tree does not make a sound because there is no one whose brain activity is changed in such a way that she would call it a sound.<br />
<br />
I find this definition problematic. What if you had a sound recording device? You could record the sound and play it back later. If no one was present when the device made its recording then where did the sound come from. Did the recording device create the sound from scratch? Or did the tree suddenly make a sound the moment you observe the sound through the recording device? In this way the question resembles the observer problem in quantum mechanics.<br />
<br />
But if you go down this route then you have to be consistent and follow this argument through to its end. You should not allow anything to exist unless you are observing it. So the final answer to the question must be:<br />
<br />
<b>If a tree falls in the forest and no one is there to hear it then the tree didn't exist in the first place.</b>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-63596607536813385292011-05-18T05:35:00.000-07:002011-05-18T05:40:25.300-07:00Non-Vedic Maths: One more here, one more there, do I care?<b>Multiplying two numbers whose last digits add up to powers of 10</b><br />
<br />
This is my first post in the series of <a href="http://themathsgeek.blogspot.com/2011/05/non-vedic-maths-introduction.html">Non-Vedic maths</a>, where I will be explaining speed calculation techniques. These techniques are NOT based on the ancient Indian Vedas but can be derived using elementary maths. <br />
<br />
In this first instalment of the series I will be looking at how to multiply two numbers whose last digits add up to powers of 10 and whose leading digits are identical. To explain the method let us first look at two digit numbers. As an example, we multiply 63 with 67. For this method to work the first digit has to be the same for both numbers and the last digits have to add up to 10. Then we can write our to numbers as<br />
<br />
<span class="texhtml">10<i>a</i> + <i>b</i></span> and <span class="texhtml">10<i>a</i> + <i>c</i></span> <br />
<br />
where <span class="texhtml"><i>b</i> + <i>c</i> = 10</span> and <span class="texhtml"><i>a</i></span> is the leading digit. In our example we have <span class="texhtml"><i>a</i> = 6</span>, <span class="texhtml"><i>b</i> = 3</span> and <span class="texhtml"><i>c</i> = 7</span>. Multiplying the two numbers gives<br />
<br />
<br />
<img alt="\begin{alignat}{1}
(10a+b)(10a+c) &= 100a^2 + 10(ab + ac) + bc\\
&= 100a^2 + 10a(b+c) + bc\\
&= 100a^2 + 100a + bc\\
&= 100a(a+1)+bc
\end{alignat}" class="tex" src="http://1.bp.blogspot.com/-RuLhid4SEk8/TdOuaoUsYpI/AAAAAAAAAEg/PklUvEQYah8/s1600/onemore_theory.png" /> <br />
<br />
<br />
In the third step we used that b+c=10. The product bc will always be less than 100 so the digits will not interfere with the first term, which is a multiple of 100. In our example we have <br />
<br />
<span class="texhtml">63 * 67 = 100 * 6 * 7 + 3 * 7 = 100 * 42 + 21 = 4221</span> <br />
<br />
The rule that can be extracted from this is: <br />
<br />
<b>Take the first digit and multiply with one more than itself. Multiply the last two digits. The final answer is made up of the two results by joining the results together.</b> <br />
<br />
We can represent this graphically in the following way.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-EVJoJZ3FmQU/TdO60kJcOaI/AAAAAAAAAEk/ARI0DNZCsD4/s1600/onemore.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-EVJoJZ3FmQU/TdO60kJcOaI/AAAAAAAAAEk/ARI0DNZCsD4/s1600/onemore.png" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"><br />
</div><br />
<br />
The method clearly also works if a is not a single digit number, but it can have any number of digits. If we wanted to multiply 116 with 114 we will get<br />
<br />
<span class="texhtml">100 * 11 * 12 + 6 * 4 = 13200 + 24 = 13224</span>.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-hBxgvqkV49o/TdO60zVmB0I/AAAAAAAAAEo/uANOh6556CU/s1600/onemore2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-hBxgvqkV49o/TdO60zVmB0I/AAAAAAAAAEo/uANOh6556CU/s1600/onemore2.png" /></a></div><br />
<br />
The method can be generalised if the trailing two digits add up to 100 or the trailing three digits add up to 1000 and so on. The maths is similar to the previous case.<br />
<br />
<img alt="\begin{alignat}{1}
(100a+b)(100a+c) &= 100a^2 + 100(ab + ac) + bc\\
&= 10000a^2 + 100a(b+c) + bc\\
&= 10000a^2 + 10000a + bc\\
&= 10000a(a+1)+bc\end{alignat}" class="tex" src="http://2.bp.blogspot.com/-AV8U8SRwJNI/TdOuZ0Rf1mI/AAAAAAAAAEY/lq6nVFrWnoA/s320/onemore2_theory.png" /> <br />
<br />
Again, <span class="texhtml"><i>b</i><i>c</i></span> will always be less than 10000 because each of them is less than 100. To see an example, lLet's multiply the numbers 436 and 464. Here the last two digits add up to 100 and the leading digit is the same in both numbers.<br />
<br />
<img alt="\begin{alignat}{1}
436 * 464 &= 10000*4*5 + 36*64\\
&= 10000*20 + 2304\\
&= 202304
\end{alignat}" class="tex" src="http://4.bp.blogspot.com/-CUszLOH-P40/TdOuaGLo5VI/AAAAAAAAAEc/mWnlxpHbR6Q/s1600/onemore_example.png" /> <br />
<br />
Of course one has to multiply two digit numbers, which can be a little more complicated. In another post I will present methods that can make this multiplication easier.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-4968083529848162902011-05-18T05:33:00.000-07:002011-08-08T04:17:04.690-07:00Non-Vedic Maths: An IntroductionIn the past I have repeatedly been confronted with people who promote Vedic Mathematics. Vedic Maths is a system of mathematical procedures that is supposed to help you master mathematics. The people promoting this system claim that it is based on the old Indian Vedic Sutras which date back over 4000 years. A little study of the subject reveals a slightly different story. Vedic mathematics was first presented by an Indian mathematician called Bharati Krishna Tirthaji Maharaja, in the early part 1900s.<br />
<br />
He claimed to have found uncovered the system by intensely studying the old Vedas. However, most scholars, that are not directly involved in promoting the system, agree that <b>the Vedas do not actually contain any of the "Vedic mathematics" sutras</b>. It is, therefore, much more likely that a Tirthaji invented the methods himself, or even copied them from other sources. Another argument against the origin from the Vedas is that the techniques described in Vedic maths heavily rely on the decimal number system. But this system was not invented until much later, after the Vedas were written down.<br />
<br />
The Vedic maths system claims to provide calculation strategies which are creative and useful. But they don't really promote a deeper understanding of mathematics. All that these methods really do, is to provide the student with some shortcuts for performing standard calculations in their head. It is interesting to note that the mathematics behind the system is not very sophisticated and was certainly known at the time that a Tirthaji developed these methods.<br />
<br />
So, quite clearly, Vedic maths does not date back to Vedic times and cannot be extracted from the Vedas. It is a modern invention that uses the claim of dating back to ancient times in order to promote itself. But all this doesn't answer the crucial question, is the Vedic maths system useful? As I said before, the methods provided do not really promote analytical thinking and, in todays world of computers and pocket calculators, they are not needed in everyday life, and they will not help the student in their future job. To make matters worse, the Vedic mathematics system does not explain why or how the techniques work. So the student is left with learning the methods by heart and repeat blindly. If you believe that education should involve more than pure repetition of facts, and you don't want your children to grow up being parrots, then avoid the Vedic maths system. For two more passionate articles against the system, you can read <a href="http://www.openthemagazine.com/article/art-culture/the-fraud-of-vedic-maths">The Fraud of Vedic Maths</a> or <a href="http://pd.cpim.org/2001/aug19/aug192k1_education1.htm">Stop this Fraud on our Children!</a><br />
<br />
Arithmetic shortcuts do have their use however, and that is to <b>impress your friends</b>. If you can find the result of a complex product or sum before your friends can get out their iPhones and start the calculator app, then they will be truly impressed. And if you can still pull this feat after a few pints in the pub, you will be considered the maths genius for the rest of your life. For this reason alone, I will start a series of posts under the heading "Non-Vedic Maths". This series will present mathematical parlour tricks and shortcuts for everyday calculations to impress your friends. I will also go the extra mile and explain <b>why the techniques work</b>. But be warned: learning these methods will not help you in any other way, and you will most certainly be branded a geek by everyone around you.<br />
<br />
<a href="http://themathsgeek.blogspot.com/2011/05/non-vedic-maths-one-more-here-one-more.html">Read on for the first technique.</a><br />
<div><br />
</div>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com2tag:blogger.com,1999:blog-4145254890040695192.post-25287606512218797042011-05-16T05:26:00.000-07:002011-05-16T05:26:05.131-07:00Collatz: Bringing some order into the chaos<p>I recently wrote that I was rekindling my interest in the Collatz problem. I still haven't had the time to read any literature but I came up with an interesting transformation to the problem that seems to unearth some structure which is maybe not directly obvious. For regular readers of this blog, you might see the similarities with this transformation and the formula I posted earlier on calculating the points for interval halving using a closed formula. It really was the Collatz problem that inspired that formula. To the uninitiated, the Collatz problem is based on the sequence<br />
<img alt="x_{n+1} = \begin{cases}
x_n/2 & x_n \text{ even}\\
3x_n + 1 & x_n \text{ odd}
\end{cases}" class="tex" src="http://4.bp.blogspot.com/-ZWyAoY4SuRU/TbmA93xN87I/AAAAAAAAAA4/1gsoehCi01k/s1600/32de0020ebcdcc093642c7aef4436808.png" style="border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-style: none; border-width: initial; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; vertical-align: middle;" /><br />
<br />
The question is whether, for any positive integer starting value, the sequence will always reach the value 1. <br />
</p><p>One can reverse the problem in the following way. Define the set C in the following way<br />
</p><p><img class="tex" alt="
\begin{alignat}{2}
&1 \in C\\
&\text{if } x \in C \quad\text{ then }\quad2x \in C\\
&\text{if } x \in C \quad\text{ and }\quad x \text{ mod } 3 = 1 \quad\text{ then }\quad\frac{x-1}{3} \in C
\end{alignat}" src="http://2.bp.blogspot.com/-Q4KCW6GBdK8/TdEQNyCPaYI/AAAAAAAAADE/_TdSVs2ys10/s1600/collatz_invers.png"><br />
</p><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-9zf2uCxH0zw/TdERiVFphXI/AAAAAAAAADk/b5CF13DwYMU/s1600/collatz_graph.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em; clear:left; float: left;"><img border="0" src="http://3.bp.blogspot.com/-9zf2uCxH0zw/TdERiVFphXI/AAAAAAAAADk/b5CF13DwYMU/s1600/collatz_graph.png" /></a></div><p>The problem then transforms to the question, whether <span class="texhtml"><i>C</i></span> contains all positive integers, in other words: is <img class="tex" alt="C=\mathbb{N}" src="http://4.bp.blogspot.com/-uoNydTOFMMc/TdEQXV8jVXI/AAAAAAAAADM/UnRizAmNumk/s320/CinN.png">? In this form the problem can be represented as a tree with 1 at its root, every element <span class="texhtml"><i>x</i></span> has at most two children. One child is always <span class="texhtml">2<i>x</i></span>, the other child is <span class="texhtml">(<i>x</i> − 1) / 3</span> if that number is an integer.<br />
</p><p>Every odd number <span class="texhtml"><i>x</i></span> trivially has an infinite number of descendants of the form <span class="texhtml">2<sup><i>k</i></sup><i>x</i></span>. I will call the set of these numbers the tower of <span class="texhtml"><i>x</i></span>.<br />
</p><p><b>Definition:</b> The tower <span class="texhtml"><i>T</i><sub><i>x</i></sub></span> of an odd number <span class="texhtml"><i>x</i></span> is the set <img class="tex" alt="T_x=\{2^k x | k=0,1,2,\ldots\}" src="http://4.bp.blogspot.com/-Wq0xImc186g/TdESJBVUqMI/AAAAAAAAADo/LUX8kzvYLL4/s400/TowerDef.png">. <span class="texhtml"><i>x</i></span> is called the base of the tower.<br />
</p><p>We also define the children of <span class="texhtml"><i>T</i></span> in the natural way, as a set of towers which are based on those children of the elements of <span class="texhtml"><i>T</i></span> which are not elements of <span class="texhtml"><i>T</i></span> themselves.<br />
</p><p><b>Definition:</b> The children <span class="texhtml"><i>C</i><sub><i>T</i></sub></span> of a tower <span class="texhtml"><i>T</i></span> is the set<br />
</p><p><img class="tex" alt="C_T = \{T_y | y = (x-1)/3 \quad\text{ where }\quad x \in T\quad\text{ and }\quad x \text{ mod } 3 = 1 \}" src="http://4.bp.blogspot.com/-4NWmccHNG0E/TdETIZbz1II/AAAAAAAAADw/0tbzFOjEfyQ/s1600/ChildrenDef.png"><br />
</p><p>It's easy to show that every tower either has no children, if the base is a multiple of 3, or an infinite number of children otherwise.<br />
</p><p>I would like to find a way to map each tower onto a single number, i.e. every element <span class="texhtml"><i>x</i></span> of <span class="texhtml"><i>T</i><sub><i>x</i></sub></span> should be mapped onto the same value. To do this I take the largest power <span class="texhtml"><i>k</i><sub><i>x</i></sub></span> of 2 that is smaller or equal to <span class="texhtml"><i>x</i></span>: <img class="tex" alt="2^{k_x} \le x < 2^{k_x+1}" src="http://3.bp.blogspot.com/-PXegTMCglZI/TdETolFzvZI/AAAAAAAAAEA/VUH3h9ymZaI/s1600/xinterval.png">. We now define<br />
</p><p><img class="tex" alt="t_x := 2^{-k_x} x - 1" src="http://4.bp.blogspot.com/-MS3LmFnfh-o/TdEToe9PC5I/AAAAAAAAAD4/qxiK0fG6QMg/s1600/tDef.png"><br />
</p><p>The values of <span class="texhtml"><i>t</i><sub><i>x</i></sub></span> lie between 0 and 1 and are rational numbers of the form <br />
</p><p><img class="tex" alt="t_x = \frac{p}{2^k}" src="http://4.bp.blogspot.com/-iHRufpbq5V4/TdEToUQgFbI/AAAAAAAAAD8/OivelfFPQJ0/s1600/tfrac.png">.<br />
</p><p>It is clear that <span class="texhtml"><i>k</i><sub>2<i>x</i></sub> = <i>k</i><sub><i>x</i></sub> + 1</span> and therefore <span class="texhtml"><i>t</i><sub>2<i>x</i></sub> = <i>t</i><sub><i>x</i></sub></span>. This means, all the elements of a tower are uniquely mapped onto a single value. We can, therefore, identify these values with the towers they originate from and we will refer to the towers <span class="texhtml"><i>T</i></span> by their <img class="tex" alt="t_T := t_x, x \in T" src="http://1.bp.blogspot.com/-Pu-6DyQxzOU/TdEUazUTZZI/AAAAAAAAAEM/_DgLiszYY9s/s1600/tTDef.png">. <br />
</p><p>The next question that arises is, given an tower <span class="texhtml"><i>t</i><sub><i>T</i></sub></span> what do the children of a tower look like. As an example, the children of <span class="texhtml"><i>t</i><sub>7</sub> = 3 / 4</span> are plotted in the figure on the right. The values of the first few of these children are given in the following table.<br />
</p><table><caption>
Children of t = 3/4
</caption><tbody>
<tr><td> Fraction </td><td> Decimal</td></tr>
<tr><td> 1 / 8 </td><td> 0.125 </td></tr>
<tr><td> 5 / 32 </td><td> 0.15625 </td></tr>
<tr><td> 21 / 128 </td><td> 0.16406 </td></tr>
<tr><td> 85 / 512 </td><td> 0.16602 </td></tr>
<tr><td> 341 / 2048 </td><td> 0.16650</td></tr>
</tbody></table><p>It can be seen, and easily proved, that if <span class="texhtml"><i>p</i> / 2<sup><i>k</i></sup></span> is a child of any <span class="texhtml"><i>t</i></span>, then so is <span class="texhtml">(4<i>p</i> + 1) / 2<sup><i>k</i> + 2</sup></span>. This results in an geometric series that converges to <br />
</p><p><img class="tex" alt="(3p+1)/(3\times 2^k)" src="http://4.bp.blogspot.com/-YG9OXt7I-I0/TdEUarEzENI/AAAAAAAAAEI/COpwk0GcHNw/s1600/converge.png"><br />
</p><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-wKVxLsSFt8w/TdEVqbiVozI/AAAAAAAAAEQ/_C1nVMFgbb0/s1600/collatz_children.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="300" width="400" src="http://2.bp.blogspot.com/-wKVxLsSFt8w/TdEVqbiVozI/AAAAAAAAAEQ/_C1nVMFgbb0/s400/collatz_children.png" /></a></div><p>The figure above plots the children of the first 1000 towers against the values of the towers themselves. Interestingly a clear structure emerges. The sequences of the children all seem to converge against two straight line segments. These line segments can be represented by the function<br><br />
</p><p><img class="tex" alt="y = \begin{cases}
\frac{1}{3}( 4x + 1) & \quad \text{for } x< \frac{1}{2}\\
\frac{1}{3}( 2x - 1) & \quad \text{for } x> \frac{1}{2}
\end{cases}" src="http://3.bp.blogspot.com/-3tXRiK2jy6s/TdEUaWS2dfI/AAAAAAAAAEE/TW4G91cPoew/s1600/childrenLinear.png"><br />
</p><p>When I first plotted this graph and discovered this very simple structure hidden in the Collatz problem, I was utterly amazed. Of course I don't know enough to decide if this structure could hold the key to unravelling the problem but it certainly gives me hope. <br />
</p><p>Finally, an apology to all those who know more about the problem. These things probably have been discovered already. I have not supplied any references and most likely got the terminology wrong. If so, I will be happy to be corrected.<br />
</p>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com1tag:blogger.com,1999:blog-4145254890040695192.post-88123732407250373172011-05-11T07:07:00.000-07:002011-05-25T04:34:17.196-07:00The Three Wise Men Puzzle: AnswerThis is the answer to the <a href="http://themathsgeek.blogspot.com/2011/05/three-philosophers-puzzle.html">"Three Wise Men Puzzle"</a> posted earlier.<br />
<br />
To understand the reason the men stop laughing we follow the thoughts of one of the philosophers, let's call him A. A sees the other two men, B and C laughing. Assuming that he doesn't have a mark on his forehead, he thinks that B is laughing at C and vice versa. But he must also assume that B is unaware of his own mark on the forehead. If A had no mark, what does B think C is laughing about? In other words, if A's assumption was true, B should quickly realise that C is laughing at B and therefore B should stop laughing. But after enough time has passed, and B hasn't stopped, A must assume that he himself has a spot on his forehead.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-11134446326352702812011-05-11T06:57:00.000-07:002011-05-11T07:25:52.605-07:00Successive Interval Halving<p>In a previous post I talked about the trapezium rule for approximating integrals. One nice feature was that one can successively increase the resolution without having to evaluate the function at points at which it has already been evaluated once. The formula I gave was <br />
</p><p>If one uses this method from the onset, this will result at the function being evaluated at the following points<br />
</p><table><tr> <td> Step <span class="texhtml"><i>i</i></span> </td><td> <span class="texhtml"><i>y</i> = (<i>x</i> − <i>a</i>) / (<i>b</i> − <i>a</i>)</span> <br />
</td></tr>
<tr> <td> 0 </td><td> 0<br />
</td></tr>
<tr> <td> 1 </td><td> 1<br />
</td></tr>
<tr> <td> 2 </td><td> 1/2<br />
</td></tr>
<tr> <td> 3 </td><td> 1/4<br />
</td></tr>
<tr> <td> 4 </td><td> 3/4<br />
</td></tr>
<tr> <td> 5 </td><td> 1/8<br />
</td></tr>
<tr> <td> 6 </td><td> 3/8<br />
</td></tr>
<tr> <td> 7 </td><td> 5/8<br />
</td></tr>
<tr> <td> 8 </td><td> 7/8<br />
</td></tr>
</table><p>and so on. A few days ago I was creating a demonstration and I wanted to create a longer table with these values. I didn't want to create it by hand so I was looking for a closed formula that produces the values in the second column from those in the first column. After some pondering over the problem I came up with the following formula<br />
</p><p><img class="tex" alt="y=(2n+1) 2^{-\lfloor\log_2(2n+1)\rfloor} - 1" src="http://4.bp.blogspot.com/-95TBYjXSXE0/TcqVYE2OylI/AAAAAAAAADA/E6aauIxigZk/s1600/interval_halving.png" /> <br />
</p><p>Here the <img class="tex" alt="\lfloor.\rfloor" src="http://4.bp.blogspot.com/-de3S-eWORoI/TcqVX8cKD2I/AAAAAAAAAC8/j4C-aUuI380/s1600/floor_function.png" /> denotes the floor function, i.e. the largest integer that is smaller or equal the argument. This formula will produce all the numbers in the table, including the zero, but not the one. The one, therefore, still has to be added by hand. Usually I would advise against using logarithms and exponentials in numerical algorithms but, because they are to the base 2, they can be implemented by bit shifting operations.<br />
</p><p>There is actually an interesting relation between <span class="texhtml">2<i>n</i> + 1</span> and <span class="texhtml"><i>y</i></span> when we write them as binary numbers. In fact, if we write <span class="texhtml">2<i>n</i> + 1</span> as binary and place a decimal point after the leading 1 we get <span class="texhtml"><i>y</i> + 1</span>. Here is an example<br />
</p><table><tr> <td>2n+1 </td><td> <span class="texhtml">10011101<sub>2</sub></span> <br />
</td></tr>
<tr> <td>y+1 </td><td> <span class="texhtml">1.0011101<sub>2</sub></span> <br />
</td></tr>
<tr> <td>y </td><td> <span class="texhtml">0.0011101<sub>2</sub></span> <br />
</td></tr>
</table>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-50280493718623084882011-05-10T05:56:00.000-07:002011-05-10T06:05:01.029-07:00Wolfram's Target AudienceI am hooked on to <a href="http://www.wolframalpha.com/">Wolfram Alpha</a>. I really think that it rocks and I can't live without it. Some days ago I wanted to bake a bread with my new bread baking machine. But I don't have any scales in the house to weigh the ingredients and the recipe tells me to use 250g of rye flour. But I do have a metric measuring cup. So I typed in <a href="http://www.wolframalpha.com/input/?i=density+of+rye+flour">density of rye flour</a> and I get <i>540 g/dm^3 (grams per cubic decimeter) </i>as answer. I know that a decimeter^3 is the same as a litre so a simple division tells me that I need 0.46l or 460ml of rye flour.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-_9Vx86M7Q8k/Tckd0trw4lI/AAAAAAAAAC4/u6SgaIApEEU/s1600/Mathematica.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-_9Vx86M7Q8k/Tckd0trw4lI/AAAAAAAAAC4/u6SgaIApEEU/s1600/Mathematica.png" /></a></div>Yesterday I was using it for some more mathematical purpose when my eye fell on this ad for the Mathematica software. They use the slogan "One software to rule them all" a modification of a quote from "Lord of the Rings". Of course, my first reaction was "Wow, these guys are cool!" Then I calmed down a bit and started thinking about Wolfram's marketing strategy. My first thought was then replaced by the more sobering thought "Wow, these guys really know their target audience!" I am not really a fan of marketing people because I think that targeted marketing aims at manipulating people. But funnily enough, in this case, I don't mind. Maybe, deep down, I think that the people who devised this ad had as much fun creating the ad as I have looking at it. But maybe that is exactly what they want me to believe. Maybe the marketing department of Wolfram are just a scheming bunch of cold blooded guys who know exactly what a geek like me would fall for. Maybe they hid the <a href="http://en.wikipedia.org/wiki/Easter_egg_(media)">Easter eggs</a> in Wolfram Alpha just to attract those nerds who have nothing better to do than to sit in front of the computer, trying to tease clever answers out of a machine.Well, they have succeeded. I think Mathematica is a great software I have had the pleasure to work with and I think, by making Wolfram Alpha and the Wolfram Integrator available to everyone, they have become more likeable. And yes, I will still waste my time by looking for Easter eggs that have not been posted on the internet yet.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-16192683620348606022011-05-09T07:59:00.000-07:002011-05-11T07:11:39.255-07:00Three Philosophers Puzzle (Three Wise Men Puzzle)Here is a logic problem which I was told some years ago and I found it quite interesting at the time. I tried finding a reference to this problem on the internet but wasn't really successful.<br />
<br />
EDIT: Thanks to one of the readers, who pointed out that the puzzle is actually well known and is called the "Three Wise Men Puzzle". A variation of the puzzle is the "Muddy Children Problem".<br />
<br />
The problem goes like this:<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: left; clear:left; float:left; display:block;"><tbody>
<tr><td style="text-align: center;"><a href="http://3.bp.blogspot.com/-3iTN2QKtjcc/Tcf_gyzpVkI/AAAAAAAAAC0/oFA0ucBD988/s1600/ThreePhilosophers.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" src="http://3.bp.blogspot.com/-3iTN2QKtjcc/Tcf_gyzpVkI/AAAAAAAAAC0/oFA0ucBD988/s1600/ThreePhilosophers.jpg" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The Three Philosophers - by Giorgione</td></tr>
</tbody></table>Three philosophers are sitting in the shade of a tree discussing deep philosophical problems. They talk and talk and, of course, they don't reach an agreement or come any closer to a solution. After some hours of talking the afternoon sun makes the three men grow tired and they finally decide to take a nap. While the philosophers are sleeping a young boy from the local village passes by. He looks at the men and decides to play a prank on them. The boy takes some white paint and on each of their foreheads he paints a white spot that resembles bird droppings. After some time the philosophers wake up again and, looking at the others, they all burst out into laughter. Of course each of them thinks that a bird has relieved itself on their colleagues foreheads but none of them is aware that, he too, has a white spot on their forehead. In this way they keep on laughing, but they don't let the others know of their plight. But suddenly they all stop laughing, suddenly realising that they too must have the mark on their forehead.<br />
<br />
<b>Question:</b> How, just by using logic, did they arrive at this conclusion?<br />
<br />
<b><a href="http://themathsgeek.blogspot.com/2011/05/three-wise-men-puzzle-answer.html">The answer can be found here.</a></b>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-38093204525802137362011-05-06T08:46:00.000-07:002011-05-10T05:58:46.382-07:00Tutorial: Trapezium MethodA subject I am particularly interested in is everything to do with numerical and mathematical algorithms. For this reason I decided that I am going to start a series on numerics. A second series will be on algorithms and discrete maths. The topics I am going to cover will not necessarily be published in any logical order as I will write about stuff that comes to my mind. But I will provide a page <a href="http://themathsgeek.blogspot.com/p/index-to-tutorials-and-series.html">here</a> which will act as a kind of index. In this way I hope that, after some time, I will be able to provide a tutorial on the subjects together with the odd little gem strewn in between. <br />
<br />
<h3>Trapezium Method of Numerical Integration<br />
</h3>When evaluating an integral using the trapezium rule the function <span class="texhtml"><i>f</i></span> to be integrated is evaluated at discrete points <span class="texhtml"><i>x</i><sub><i>i</i></sub></span> between the integration boundaries <span class="texhtml"><i>a</i></span> and <span class="texhtml"><i>b</i></span> <br />
<br />
<span class="texhtml"><i>x</i><sub><i>i</i></sub> = <i>a</i> + <i>h</i><i>i</i></span> <br />
<br />
where the interval size <span class="texhtml"><i>h</i></span> is given by<br />
<br />
<img alt="h = \frac{b-a}{N}" class="tex" src="http://3.bp.blogspot.com/-Gs4ENQiN8PE/TcQQoKsoNpI/AAAAAAAAABM/FHg1gH2obOA/s1600/interval.png" />,<br />
<br />
<span class="texhtml"><i>N</i></span> is the number of intervals and <img alt="i=0\ldots N" class="tex" src="http://1.bp.blogspot.com/-rHZBysHGMRQ/TcQQ3kkA4zI/AAAAAAAAABU/USrgNMq_Hv4/s1600/irange.png" />. I will also refer to <span class="texhtml"><i>N</i></span> as the resolution. In practice <span class="texhtml"><i>N</i></span> is often chosen to be a power of 2. There is no particular reason for this other than the fact that one commonly increases the resolution by a factor of 2 when improving the accuracy. <br />
<br />
Let's abbreviate the notation by defining the discrete function values<br />
<br />
<img alt="f^N_i = f(x_i)" class="tex" src="http://3.bp.blogspot.com/-OPSBepzM3wg/TcQRFL2sp7I/AAAAAAAAABc/I7v2FmCn-QI/s1600/fdiscrete.png" /> <br />
<br />
Here I used the upper index <span class="texhtml"><i>N</i></span> to clarify that the discrete function values depend on the resolution. With this definition we can now write the trapezium approximation <span class="texhtml"><i>T</i><sub><i>N</i></sub></span> of resolution <span class="texhtml"><i>N</i></span> to the integral as<br />
<br />
<img alt="\int_a^b f(x) dx \approx \frac{1}{2h}\left( f^N_0 + 2 \sum_{i=1}^{N-1} f^N_i + f^N_N \right) =: T_N" class="tex" src="http://2.bp.blogspot.com/-1sYThB7PSQw/TcQRXQluaYI/AAAAAAAAABk/_qqKJ1QHceg/s1600/trapezoid_def.png" /> <br />
<br />
What this means geometrically is explained in the following graph. The integral of a function is the area below the graph of that function. The trapezium rule approximates this area by adding the areas of the trapezoids created by the x-axis and the function values at the discrete points. Each trapezoid has the area <br />
<br />
<img alt="\frac{1}{2h}\left( f_i + f_{i+1} \right)" class="tex" src="http://2.bp.blogspot.com/-KdrppJLl1tU/TcQR3kwR65I/AAAAAAAAABs/1oyfaefBvUU/s1600/trapezoid_single.png" /> <br />
<br />
Summing these areas up, one obtains the above formula. Let's do an example. We want to integrate the function <span class="texhtml">sin(π<i>x</i>)</span> between the limits 0 and 1. Using N=4 we get<br />
<br />
<img alt="T_4 = \frac{1}{8}\left( 0 + 1.41421 + 2.00000 + 1.41421 + 0 \right) = 0.60355" class="tex" src="http://2.bp.blogspot.com/-TSQoZBjr_0g/TcQSDCq_wmI/AAAAAAAAAB0/UIpr-Odl0t0/s320/trapezoid_four.png" /> <br />
<br />
Comparing this with the exact solution<br />
<br />
<img alt="\int_0^1\sin(\pi x) dx = \frac{2}{\pi} " class="tex" src="http://2.bp.blogspot.com/-R9PXo57pMOU/TcQSNpORmjI/AAAAAAAAAB8/4ao7UXKy-X4/s1600/integral_example.png" /> <br />
<br />
We see that, with this crude approximation, the error is about <img alt="\varepsilon=0.03307" class="tex" src="http://4.bp.blogspot.com/-IB7R8PGolWA/TcQSibWYQSI/AAAAAAAAACE/sBbAoJPjo3w/s320/error_four.png" /> <br />
<br />
Of course one expects this approximation to get better as <span class="texhtml"><i>N</i></span> increases and thus <span class="texhtml"><i>h</i></span> decreases. In fact, one can show that, for sufficiently smooth functions<br />
<br />
<img alt="\int_a^b f(x) dx = T_N + O(h^2)" class="tex" src="http://2.bp.blogspot.com/-VMahTiUzpL4/TcQSwXzCwYI/AAAAAAAAACM/m0NY85oSOqo/s1600/trapezoid_order.png" />.<br />
<br />
The above equation means that the error in the trapezium approximation decreases quadratically with the number of steps.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-0JYFAJKdbW0/TcQV1Qhf4LI/AAAAAAAAACc/ZOfeUIUkByM/s1600/trapezoid.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="240" src="http://3.bp.blogspot.com/-0JYFAJKdbW0/TcQV1Qhf4LI/AAAAAAAAACc/ZOfeUIUkByM/s320/trapezoid.png" width="320" /></a></div>Let's see this on our example. In the diagram I plotted the error against the resolution on a double logarithmic plot. Up to <span class="texhtml"><i>N</i> = 1<i>e</i>6</span> the curve is almost a straight line with a slope of -2. To show this the green line is the function <img alt="\varepsilon \propto N^{-2}" class="tex" src="http://2.bp.blogspot.com/-616EyrJmH-E/TcQXjApPFfI/AAAAAAAAACs/eRH4z8ynaxs/s320/error_order.png" />. This means that, in order reduce the error by a factor of four, one has to double the resolution.<br />
<br />
One interesting feature of the trapezium rule is the fact that it makes the doubling of the resolution easy for us. When going from <span class="texhtml"><i>N</i></span> to <span class="texhtml">2<i>N</i></span>, one does not have to evaluate the function at all the <span class="texhtml">2<i>N</i></span> points. Instead one can use the result <span class="texhtml"><i>T</i><sub><i>N</i></sub></span> of the previous approximation. The rule is<br />
<br />
<img alt="T_{2N} = \frac{1}{2} T_N + \frac{1}{2h} \sum_{i=1,3,\ldots}^{2N-1}" class="tex" src="http://4.bp.blogspot.com/-5ZzJUs7QiHo/TcQU6E1Nf9I/AAAAAAAAACU/ZQ4IfaC402U/s320/trapezoid_refine.png" /> <br />
<br />
This formula makes it easy to successively increase the resolution until the required accuracy is achieved. <br />
<br />
Finally I'd like to comment on the behaviour of the error when <span class="texhtml"><i>N</i></span> gets really large. In the figure above you can see that the error levels off at about <span class="texhtml">2 × 10<sup> − 7</sup></span> when <span class="texhtml"><i>N</i></span> increases above 2000. This error is above the numerical accuracy, which is about <span class="texhtml">10<sup> − 8</sup></span> in my calculations. When <span class="texhtml"><i>N</i></span> increases further the error starts to increase again until, in the end it is even larger than before. The reason for this large error is that the individual terms in the sum become very small. Adding many small values up results in a loss of accuracy due to rounding errors.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com1tag:blogger.com,1999:blog-4145254890040695192.post-49677113931188270772011-04-28T05:44:00.001-07:002011-05-16T05:27:08.249-07:00An Old Problem in DisguiseHere 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.<br />
<br />
Start with any binary number ending in a 1, e.g.<br />
<br />
<pre>100101101
</pre><br />
Now shift this number one place to the left, filling the rightmost digit with a 1<br />
<br />
<pre>1001011011
</pre><br />
then add this number to the original number<br />
<br />
<pre>100101101
1001011011
----------
1110001000
</pre><br />
Finally eliminate all trailing zeros<br />
<br />
<pre>1110001
</pre><br />
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?<br />
<br />
You probably guessed it by now that this is the well known Collatz problem. In its standard form the Collatz conjecture reads<br />
<br />
Given a starting number <span class="Apple-style-span" style="font-family: serif; font-size: 13px; line-height: 19px;"><i>x</i><sub>0</sub></span> and the recursion<br />
<br />
<span class="Apple-style-span" style="font-family: sans-serif; font-size: 13px; line-height: 19px;"><img alt="x_{n+1} = \begin{cases}
x_n/2 & x_n \text{ even}\\
3x_n + w & x_n \text{ odd}
\end{cases}" class="tex" src="http://4.bp.blogspot.com/-ZWyAoY4SuRU/TbmA93xN87I/AAAAAAAAAA4/1gsoehCi01k/s1600/32de0020ebcdcc093642c7aef4436808.png" style="border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-style: none; border-width: initial; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; vertical-align: middle;" /></span><br />
<br />
<br />
<br />
<br />
the sequence <span class="Apple-style-span" style="font-family: serif; font-size: 13px; line-height: 19px;"><i>x</i><sub><i>n</i></sub></span> will always reach the number 1.<br />
<br />
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 <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Wikipedia</a> revealed that this is one of the standard alternative representations of the problem. Some more extended Google search revealed <a href="http://www.antiquark.com/math/collatz_bin.html">this online script</a> for calculating the Collatz number sequence in binary form.<br />
<br />
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.<br />
<br />
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<br />
<span class="Apple-style-span" style="font-family: sans-serif; font-size: 13px; line-height: 19px;"><img alt="\left(\frac{3n+1}{2}\right)^k x" class="tex" src="http://3.bp.blogspot.com/-Tz2hbQjzyLw/Tbl-_pdVCBI/AAAAAAAAAAo/mrQER0w-FAw/s1600/3c6ed80f6be822a3a32c3f92c04a71b5.png" style="border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-style: none; border-width: initial; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; vertical-align: middle;" /></span><br />
<br />
<span class="Apple-style-span" style="font-family: sans-serif; font-size: 13px; line-height: 19px;"></span>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<br />
<span class="Apple-style-span" style="font-family: sans-serif; font-size: 13px; line-height: 19px;"><img alt="\frac{3n+1}{2^k}" class="tex" src="http://3.bp.blogspot.com/-uVeUO10KQmM/Tbl_LguFjCI/AAAAAAAAAAw/wGtiUu_LpbU/s1600/7efea4ce0a6e1e90f4badcd05cc655a3.png" style="border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-style: none; border-width: initial; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; vertical-align: middle;" /></span><br />
<br />
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.<br />
<div><br />
</div>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-53463317244184848352011-04-21T11:16:00.000-07:002011-05-10T05:57:55.394-07:00NetPNM ... 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.<br />
<br />
The solution comes in the form of the <a href="http://en.wikipedia.org/wiki/Netpbm_format">NetPBM</a> (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.<br />
<br />
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.<br />
<br />
First, let's include some headers<br />
<br />
<pre>#include <boost/scoped_array.hpp>
#include <iostream>
#include <fstream>
#include <cmath>
</pre><br />
I like using the boost smart pointers. This eliminates many destructors and rids me of the worry about memory management.<br />
<br />
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.<br />
<br />
<pre>struct Colour
{
Colour() {}
Colour(unsigned char r_, unsigned char g_ , unsigned
char b_)
: r(r_), g(g_), b(b_) {}
unsigned char r, g, b;
};
</pre><br />
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.<br />
<br />
I like to use typedefs for the smart pointers to make it more clear what type data the array holds.<br />
<br />
<pre>class Image
{
private:
typedef boost::scoped_array<Colour> pColour;
int width, height;
pColour data;
</pre><br />
Next we have two constructors, one default constructor creating an empty image and one constructor creating an image of given size.<br />
<br />
<pre>public:
Image() : data(0), width(0), height(0) {}
Image(int width_, int height_)
: width(width_), height(height_), data(new
Colour[width_*height_]) {}
</pre><br />
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.<br />
<br />
<br />
<pre>void resize(int width_, int height_)
{
width = width_;
height = height_;
data.reset(new Colour[width*height]);
}
</pre><br />
We also need some way of accessing the image data. Being a good boy, I will write a const and a non-const accessor.<br />
<br />
<pre>Colour& at(int x, int y) { return data[x + width*y]; }
const Colour& at(int x, int y) const { return
data[x + width*y]; }
</pre><br />
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<br />
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.<br />
<br />
<pre>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";
}
}
};
</pre><br />
That's it (the last bracket closes the class definition). Now we are ready to test our class.<br />
<br />
<pre>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();
}
</pre><br />
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.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-63867512373606207842011-04-19T06:25:00.000-07:002011-05-10T05:57:15.138-07:00C++ Binary Stream ManipulatorI 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.<br />
<br />
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<br />
<br />
<pre>std::cout << binary << x;</pre><br />
and then x would be written in binary format.<br />
<br />
Let' start with the easier task. So first I want to be able to write<br />
<br />
<pre>std::cout << toBinary(x);</pre><br />
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<br />
<br />
<pre>std::string s = toBinary(x);</pre><br />
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<br />
<br />
<pre>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;
}
};
</pre><br />
Now we can overload the << operator for this class<br />
<br />
<pre>std::ostream& operator<<(std::ostream& os, const stream_formatter &conv)
{
return conv.toStream(os);
}
</pre><br />
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<br />
<br />
<pre>operator const std::string()
{
std::ostringstream os;
this->toStream(os);
return os.str();
}
</pre><br />
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, <a href="http://stackoverflow.com/questions/799599/c-custom-stream-manipulator-that-changes-next-item-on-stream">I found this tutorial</a> 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. <br />
<br />
I will keep trying and I will report here, when I know more.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com1tag:blogger.com,1999:blog-4145254890040695192.post-49090924535464116082011-04-18T07:58:00.001-07:002011-05-10T05:56:53.402-07:00My favourite maths jokeHere is my favourite maths joke. It's really a joke about mathematicians and not about maths.<br />
<blockquote><br />
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?"<br />
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."<br />
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<br />
a) He took a very long time to come up with a response.<br />
b) His answer was absolutely correct.<br />
c) What he said did not help us in any way."</blockquote>The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-86776349963587029682011-04-14T08:07:00.001-07:002011-05-10T05:56:43.357-07:00Fractal BubblesIn 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<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-j0EPE0O7e7k/TacMbE1JcbI/AAAAAAAAAAU/3_OhI2id23o/s1600/mandelbrot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-j0EPE0O7e7k/TacMbE1JcbI/AAAAAAAAAAU/3_OhI2id23o/s1600/mandelbrot.png" /></a></div>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.<br />
<br />
But then I found <a href="http://gnofract4d.sourceforge.net/">Gnofract</a>, 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.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://www.zazzle.com/mathbeauty/gifts?cg=196559611247305494" style="margin-left: auto; margin-right: auto;"><img border="0" src="http://2.bp.blogspot.com/-1Z7IdFFBk4Q/TacMAfsMg9I/AAAAAAAAAAQ/frQgc0JGpu0/s1600/Bubbles.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="http://www.zazzle.com/mathbeauty/gifts?cg=196559611247305494">Bubbles</a></td></tr>
</tbody></table>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.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0tag:blogger.com,1999:blog-4145254890040695192.post-52008800870742470382011-04-14T07:54:00.000-07:002011-05-10T05:56:33.214-07:00Welcome!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".<br />
<br />
There! I started my blog nit-picking on some grammatical issue. This <a href="http://www.matthewbarr.co.uk/geek/">qualifies me</a>, at least partially, as a geek.<br />
<br />
So read on and enjoy.The Maths Geekhttp://www.blogger.com/profile/03425659585009977962noreply@blogger.com0