Recurring numbers and finite state automata

Today we shall be talking about recurring numbers and we'll be explaining them using finite state automata.

A recurring number is generated by dividing two whole numbers to obtain a decimal whose digits after the point never end. For example, if we divide 1 by 3, we'll get 0.333333333... Remember that division works by dividing a number by the next digit, writing the whole number result as a digit of the answer and using the remainder as a carry, like so:

1 can be written as 1.00000..., which is what we'll do.

 \------------
3/1 . 0 0 0 0

1 divided by 3 is 0 remainder 1, so we write 0 above and put 1 as a carry on the next digit.

  0
 \-----------
3/1 . 10 0 0

10 divided by 3 is 3 remainder 1, so we write 3 above and put 1 as a carry on the next digit.

  0 . 3
 \------------
3/1 . 10 10 0

10 divided by 3 is 3 remainder 1, so we write 3 above and put 1 as a carry on the next digit.

  0 . 3  3
 \-------------
3/1 . 10 10 10

and so on.

But recurring numbers can sometimes be less simple, such as 1/7 which is 0.142857142857142857...:

1 can be written as 1.00000..., which is what we'll do.

 \------------
7/1 . 0 0 0 0

  0
 \-----------
7/1 . 10 0 0

  0 . 1
 \------------
7/1 . 10 30 0

...

  0 . 1  4  2  8  5  7
 \-------------------------
7/1 . 10 30 20 60 40 50 10

...

  0 . 1  4  2  8  5  7  1  4  2  8  5  7
 \-------------------------------------------
7/1 . 10 30 20 60 40 50 10 30 20 60 40 50 10

So why does this happen? Why don't the digits kept changing differently but instead start repeating a sequence? It's because the next digit depends on what remainder the previous digit left, so if the previous digit left a remainder which was left by another previous digit then the new digit and new remainder will be the same as the earlier digit. For example, in this case, the remainder was a 1, but the first remainder left was also a 1, so the sequence will repeat itself:

0 . 1  4  2  8  5  7
 \-------------------------
7/1 . 10 30 20 60 40 50 10

  0 . 1  4  2  8  5  7  1
 \-------------------------
7/1 . 10 30 20 60 40 50 10

  0 . 1  4  2  8  5  7  1  4
 \---------------------------
7/1 . 10 30 20 60 40 50 10 30

...

  0 . 1  4  2  8  5  7  1  4  2  8  5  7
 \-------------------------------------------
7/1 . 10 30 20 60 40 50 10 30 20 60 40 50 10

More technically, this is because the digits are generated using a finite state, the remainder, and when you try to generate an infinite sequence using a finite state, eventually you must get repetition, since you must reuse a previously used state at some point in the infinite sequence.

We can draw this idea using a finite state automaton where the states are the remainders left by a digit and the transition gives the next digit. For example, this is what the finite state automaton for 1/7 is:

Remember, the numbers in the circles are remainders, which are used as carries in front of zeros, and the numbers on the arrows are digits in the result. So we start from a remainder of 1 which results from when we start dividing 1 by 7, and start jumping from remainder to remainder. Now we can either end up with a remainder of 0, in which case the result would terminate and will not be recurring, or it will jump to a remainder which has already been traversed, in which case it will enter an infinite loop, which results in a recurring number. As the transitions show, in the case of dividing by 7, the second case is inevitable, regardless of which non-zero remainder we start with.

Since every number can leave only one of a finite number of remainders when used to divide another number, the result can either be a terminating number or a recurring number and cannot keep on changing forever. Further more, since the number of remainders a number can leave when divided is equal to that number (x/2 can only leave either 0 or 1 as remainders, x/3 can only leave either 0, 1 or 2 as remainders, etc) then there can only be that number of remainders. Since there can only be that number of remainders, and since a remainder of 0 would terminate the number, then the length of the recurring part of a number cannot be longer than one less than the denominator of that number. For example, for all x, x/7 cannot have a recurring part longer than 6 digits. Likewise, for all x, x/100 cannot have a recurring part longer than 99 digits.

Notice that the finite state automaton as used here only works for when we start adding zeros after the point during division. For example, if we divide the following:

\--------------------
7/1 . 1  2  3  0  0  0

then the finite state automaton can only be used when we start using the zeros at the end since the numbers in the automaton assume that the remainders are carried on to zeros. Since even if we use another recurring number, that recurring number can be converted to a fraction and the quotient of two fractions is another fraction, then the finite state automaton can also be used on recurring numbers. For example, if we divide the following:

\--------------------
7/0 . 3  3  3  3  3  3 ...

then we can convert 0.3333... into 1/3, the division can be converted to the fraction (1/3)/7 which can be simplified to 1/(3x7) = 1/21. Now we can use the finite state automaton on 1/21 and reason on when the result should start recurring.

Finally we see that if we divide an irrational number then the result could also be irrational since the state is not finite anymore but will be changing forever with every digit in the divided number.

This is the basis for the finite state automata's pumping lemma, which says that if the number of letters (or digits in this case) generated from a finite state automaton exceeds the number or states in the automaton, then there must be reuse of a previously visited state and thus the letters cannot be forever randomly generated but must follow a regular pattern at that point. In this case we have an even stronger pumping lemma which says that not only will the digits follow a regular pattern after exceeding the number of states in the automaton but will forever repeat the same sequence. This is because there is only one transition going out of each state since only one remainder can be left when dividing a number, so once a state is revisited there is no other path to follow except the previously visited path.

Summary of research paper "Chargaff’s “Grammar of Biology”: New Fractal-like Rules" by Yamagishi & Herai

This is a summary of the research paper http://arxiv.org/ftp/arxiv/papers/1112/1112.1528.pdf. Although it has "grammar of biology" in its title, it's basically about patterns in the frequencies of the 4 nucleotides in DNA: Adenine, Thymine, Cytosine and Guanine.

In case you don't know about it, DNA is a chain of these 4 types of molecules called nucleotides. Each nucleotide is represented by single letter which is the first letter of their name. So "TATA" can be a part of a DNA sequence for example. The DNA is made of 2 strands twisted around each other into a double helix. The two stands must be "complementary" such that if the first nucleotide on one strand is an "A" then the other strand must start with a "T", if it is a "T" then other must be an "A", if it is a "C" then the other must be a "G" and if it is a "G" then the other must be a "C", and the same goes for each nucleotide position in each strand.

Erwin Chargaff had discovered 2 simple patterns regarding the frequencies of the nucleotides in most organisms.

Chargaff's first parity rule says that if you count the number of each nucleotide on each strand, you'll find that the number of A nucleotides on one strand is equal to the number of T nucleotides on the other strand and so on for each complementary nucleotide. This is because of what was said in the previous paragraph.

The second parity rule says that the first rule also applies to the same strand, but only approximately. So the number of A nucleotides on a strand is approximately equal to the number of T nucleotides on the same strand and so on for each complementary nucledotide. It is less understood why this should happen. The problem is that if it were because the number of nucleotides is uniformly random, then the number of A and T nucleotides and the number of G and C nucleotides should not only be approximately equal, but the two groups should also be equal to each other, which is not the case. So the number of A nucleotides is approximately equal to the number of T nucleotides but not to the number of C or G nucleotides.

The second parity rule was later discovered to be a special case of a more general rule which says that on a given strand of DNA, the frequency of a sequence of nucleotides is approximately equal to the frequency of the reverse of the complement of that sequence. For example the number of time that "TAG" appears in a strand of DNA is approximately equal to the number of times that "CTA" appears in the same strand.

The research paper being discussed adds some new rules about the frequencies of the nucleotides.

Let's start from some notation.

• Let w be a nucleotide sequence such as "ATCGAT", S be a DNA strand and S' be the other strand of the DNA.
• |p| is the length of the string p (could be a word or a strand). For example |"ATA"| = 3.
• F(w, S) is the fraction of the number of times w occurs in S over |S|-|w|+1. In other words, it is calculated using a sliding window and the number of times the word is found is divided by the number of times the window is moved. For example F("AA", "AATAAA") = 3/5. (This was confirmed in private conversation with the authors of the paper)
• C(w) is the complementary word of w nucleotide to nucleotide. For example C("ATCG") = "TAGC".
• R(w) is the reverse of w. For example R("ATCG") = "GCTA".

Using this notation, Chargaff's rules can be represented as:
1: F(w, S) = F(C(w), S')
2: F(w, S) ≈ F(R(C(w)), S) (generalized version)

What the authors of the paper did was that they organized all possible words of a certain length into a table which they called a "Math table" such that each row will have a new word, its complement, its reverse and its reverse complement, but each word can only be used once in the table. Since each element of the table is unique, the words in the first column which generate the other columns are called a "generating set" or "G", and each word in "G" is labelled "g". According to the authors of the paper, there is no special way how to determine which words go into G.

For example here is a Math table for words of length 2:

g	C(g)	R(g)	C(R(g))
AA	TT	-	-
AT	TA	-	-
CC	GG	-	-
CG	GC	-	-
AC	TG	CA	GT
AG	TC	GA	CT

By summing the frequencies of each column in the table it was determined that:
Eq1: SUM(F(g, S) for g in G) ≈ SUM(F(C(g), S) for g in G)
Eq2: SUM(F(R(g), S) for g in G) ≈ SUM(F(C(R(G)), S) for g in G)

Note: I'm not sure if the way G is chosen makes a difference or if the blanks in the Math table affect the summation.

The authors of the paper say that there are other identities were discovered using the Math table, but don't mention them.

Since SUM(F(g, S) + F(C(g), S) + F(R(g), S) + F(C(R(g)), S) for g in G) = 100% (assuming R(g) returns blank and hence F(R(g), S) and F(C(R(g), S) give 0 if R(g) is blank in the Math table),

SUM(F(g, S) + F(C(g), S) for g in G) + SUM(F(R(g), S) + F(C(R(g)), S) for g in G) = 100%

Using Eq1 and Eq2, we can turn this equation into

SUM(2F(g, S) for g in G) + SUM(2F(R(g), S) for g in G) ≈ 100%
2SUM(F(g, S) for g in G) + 2SUM(F(R(g), S) for g in G) ≈ 100%
Eq3: SUM(F(g, S) for g in G) + SUM(F(R(g), S) for g in G) ≈ 50%
Or
Eq4: SUM(F(C(g), S) for g in G) + SUM(F(C(R(g)), S) for g in G) ≈ 50%

Eq3 was confirmed with a variety of different species DNA.

Depth First Search and Breadth First Search (graph search series)

I shall be writing a series of posts on graph search algorithms, starting from this one.

Depth first search and breadth first search are among the simplest of algorithms and are generally used as a basis for implementing more sophisticated searches rather than just to be used as is. These algorithms are used as a way to traverse the nodes of trees or general graphs in a systematic way according to how the nodes are connected.

Depth first search starts from the root node, or simply the start node in a general graph, process the node, take a new neighboring node and repeat. When there are no more new neighboring nodes to take, go back to the node that got you to the current node, take another new node and repeat. If you go back to the root then you have traversed all nodes and the process ends.

If "O" is an unprocessed node, "X" is a processed node and "(X)" is the current node, here's what would happen to this tree:

_____+-------O-------+
 +---O---+       +---O---+
 O       O       O       O

     +------(X)------+
 +---O---+       +---O---+
 O       O       O       O

     +-------X-------+
 +--(X)--+       +---O---+
 O       O       O       O

     +-------X-------+
 +---X---+       +---O---+
(X)      O       O       O

     +-------X-------+
 +--(X)--+       +---O---+
 X       O       O       O

     +-------X-------+
 +---X---+       +---O---+
 X      (X)      O       O

     +-------X-------+
 +--(X)--+       +---O---+
 X       X       O       O

     +------(X)------+
 +---X---+       +---O---+
 X       X       O       O

     +-------X-------+
 +---X---+       +--(X)--+
 X       X       O       O

     +-------X-------+
 +---X---+       +---X---+
 X       X      (X)      O

     +-------X-------+
 +---X---+       +--(X)--+
 X       X       X       O

     +-------X-------+
 +---X---+       +---X---+
 X       X       X      (X)

     +-------X-------+
 +---X---+       +--(X)---+
 X       X       X       X

     +------(X)------+
 +---X---+       +---X---+
 X       X       X       X

     +-------X-------+
 +---X---+       +---X---+
 X       X       X       X

For this to work you need enough memory for remembering the path you have took to get to the current node, assuming that there is a natural order for accessing the next nodes from the current node (that is, you will not revisit the same next node from the current node twice).

Breadth first search starts from the root node, or simply the start node in a general graph, and enqueues it into a queue. Then the next node in the queue is dequeued, the node is processed, all of its neighboring nodes are enqueued into the queue and repeat. If the queue is empty because no processed node has any neighboring nodes to add anymore, all the nodes were traversed and the process ends.

If "O" is an unprocessed node, "X" is a processed node and "(X)" is the current node, here's what would happen to this tree:

_____+-------O-------+
 +---O---+       +---O---+
 O       O       O       O

     +------(X)------+
 +---O---+       +---O---+
 O       O       O       O

     +-------X-------+
 +--(X)--+       +---O---+
 O       O       O       O

     +-------X-------+
 +---X---+       +--(X)--+
 O       O       O       O

     +-------X-------+
 +---X---+       +---X---+
(X)      O       O       O

     +-------X-------+
 +---X---+       +---X---+
 X      (X)      O       O

     +-------X-------+
 +---X---+       +---X---+
 X       X      (X)      O

     +-------X-------+
 +---X---+       +---X---+
 X       X       X      (X)

     +-------X-------+
 +---X---+       +---X---+
 X       X       X       X

For this to work you need enough memory for remembering the queue of nodes that are next to process. The breadth first search is great for working on graphs with infinitely long paths as it does not get stuck traversing the same path but checks all the paths simultaneously as they are gradually traversed. The nodes on the queue are called the "fringe" as they are the edges of this ever widening circle of exploration.

Here is the pseudo code. We shall be using a successor function which gives a list of the next nodes from a given node in order to keep the algorithms as generic as possible.

Iterative version of depth first search:

sub depthFirstSearch(startNode, successorFunction, nodeProcessor):
  stack = [[startNode]]
  while stack is not empty:
    currSiblings = stack.pop()
    currNode = currSiblings.pop()
    if currSiblings is not empty:
      stack.push(currSiblings)

    nodeProcessor(currNode)
    
    nextSiblings = successorFunction(currNode)
    if nextSiblings is not empty:
      stack.push(nextSiblings)

Of course depth first search is naturally recursive so we can do it like this:

sub depthFirstSearch(startNode, successorFunction, nodeProcessor):
  sub _depthFirstSearch(currNode):
    nodeProcessor(currNode)
    for each nextNode in successorFunction(currNode):
      _depthFirstSearch(nextNode)

  _depthFirstSearch(startNode)

Breadth first search is more naturally iterative than recursive:

sub breadthFirstSearch(startNode, successorFunction, nodeProcessor):
  queue = [startNode]
  while queue is not empty:
    currNode = queue.dequeue()

    nodeProcessor(currNode)

    nextNodes = successorFunction(currNode)
    if nextNodes is not empty:
      queue.enqueueAll(nextNodes)

However, this is what it would look like recursively:

sub breadthFirstSearch(startNode, successorFunction, nodeProcessor):
  sub _breadthFirstSearch(queue):
    if queue is not empty:
      currNode = queue.dequeue()

      nodeProcessor(currNode)

      nextNodes = successorFunction(currNode)
      if nextNodes is not empty:
        queue.enqueueAll(nextNodes)

      _breadthFirstSearch(queue)

  _breadthFirstSearch([startNode])

Finding the median value using MySQL sql

The median of a finite list of numbers is defined as the number in the middle of the list when the list is sorted, or the average (arithmetic mean) of the two numbers in the middle if the size of the list is even.

Since, as I described in my previous post, averages are meaningless when it comes to something like marks, I've decided to start using medians instead since it would be more useful to know in which half of the class you stand with your mark, and medians are much more intuitive than means.

Here is the SQL to find the median in MySQL (adapted from http://stackoverflow.com/a/7263925)

SET @rownum := -1;

SELECT
   AVG(t.mark)
FROM
(
   SELECT
      @rownum := @rownum + 1 AS rownum,
      results.mark AS mark
   FROM
      results
   ORDER BY results.mark
) AS t
WHERE
   t.rownum IN (
      CEIL(@rownum/2),
      FLOOR(@rownum/2)
   )
;

Here's a brief explanation:

In MySQL we cannot use expressions in LIMIT, so instead we have to simulate a LIMIT by using a counter with user defined variables. Each row in the table will have a row number associated with it starting from 0 in the variable @rownum.

We then choose from these numbered rows the ceiling and floor of "(number of rows - 1)/2" which will be the same middle value if the number of rows is odd or the middle two values if the number of rows is even. The variable will still retain its value after all the rows are numbered so we can use it to know the number of rows.

Since the average of one number is the number itself, we can simply calculate the average of whatever is returned without checking. If the number of rows is odd then we shall find the average of the middle value which will remain the same and if the number of rows is even then we shall find the average of the middle two values will will be the correct median.

Don't forget that if you're using this in PHP you have to use two "mysql_query" calls, one for the first SET and another for the SELECT as you cannot use ";" in queries.

The true meaning of the average (arithmetic mean) of a list of numbers!

For too long we have been averaging numbers without knowing what the average really is. The process of dividing the total by the amount of numbers is so simple that we use it whenever we can without realizing what it actually means to do so.

What the arithmetic mean of a list of numbers is, is the number which is closest to all the other numbers. It is the number which when compared to all the other numbers will give the least error. The fact that it is the number which is least erroneous to all the numbers in the list makes it a good approximation of every number in the list.

Given this definition, should the mean be used as extensively as it is? In an exam result, wouldn't it be more useful to know the percentage of students who passed and failed rather than know the average mark? Or the percentage of students that scored each category of marks (A, B, C, etc)? Just by knowing the single approximate mark of every student will not really let you know how good your mark is when compared to every other mark. Percentages would be more useful.

But I digress. Let's focus on what the arithmetic mean really means.

What does "error" mean? If I say 7 when I should have said 5, what was my error? The most intuitive answer would be 2, which is the absolute difference between the two numbers. Let's see where this takes us.

Error as absolute difference

We want to find a number which has the least error when compared to every number in the list. This is less obvious that one might think as there are many ways to interpret such a statement. What does it mean for a number to have the least error when compared to every number in the list? Two ways I can think of are:

The least maximum error

One way would be to find the number which after computing its error to all the numbers, the maximum error it gives will be the least possible.

So if we have a list [1,3,7], the error the number 5 has to each number is [|1-5|, |3-5|, |7-5|] = [|-4|, |-2|, |2|] = [4, 2, 2]. Now pick the maximum error of these and we have 4. Using this interpretation, 4 is the error 5 has when compared to [1,3,7]. Now we want to find the number which will give the least maximum error.

So since we want to find the number which gives the least maximum error, we are looking for a number "x" such that
max([|1-x|, |3-x|, |7-x|])
will be the least possible.

Let's plot the graphs of each "x" separately, that is, y = |1-x|, y = |3-x| and y = |7-x|.

Each graph is a plot of how the error when compared to each number changes as different "x" are used. It is clear that the lines giving the maximum error are the ones highest up, which are the ones belonging to the largest number in the list (green) and the smallest number in the list (red) but only one of them is the maximum error at any point, depending of whether they have intersected or not. So when x < 4, the maximum error is described by |1-x| and when x > 4, the maximum error is described by |7-x|. When x = 4, they intersect and hence give the same error.

The minimum error of of these maximum errors are where |x-1| and |x-7| intersect, that is, at 4. So 4 is the number which gives the least maximum error. This error would be 3. If you try any other number instead of 4 to represent these 3 numbers, the maximum error you will get will be greater.

In general, we want to find where |max_num-x| and |min_num-x| intersect, as these will obviously always be the lines highest up and the intersection will always be their minimum. We notice that the 2 lines above the intersection are y = max_num-x and y = x-min_num so to find the intersection we put "x" subject of the formula in max_num-x = x-min_num (simultaneous equations) and we have
x = (max_num + min_num)/2
so the number which best approximates the numbers would be (max_num + min_num)/2, which is the number exactly in the middle of max_num and min_num. As you can notice, only the maximum and minimum numbers are taken into consideration using this interpretation which will not give a very representative number of all the numbers.

The least sum of errors

Another way would be to find the number which after computing its error to all the numbers, the sum of all errors it gives will be the least possible.

So if we have a list [1,3,7], the error the number 5 has to each number is [|1-5|, |3-5|, |7-5|] = [|-4|, |-2|, |2|] = [4, 2, 2]. Now add the errors together and we have 4+2+2 = 8. Using this interpretation, 8 is the error 5 has when compared to [1,3,7]. Now we want to find the number which will give the least sum of errors.

So since we want to find the number which gives the least sum of errors, we are looking for a number "x" such that
sum([|1-x|, |3-x|, |7-x|])
will be the least possible.

Let's plot the graphs of each "x" separately, that is, y = |1-x|, y = |3-x| and y = |7-x|, together with their sum.

The blue line is the sum of errors. This looks promising. There is a global minimum at x = 3. So 3 would give the least sum of errors when compared to [1,3,7]. But a little analysis of how absolute differences add up together will show that the minimum will always occur at the minimum of the median number, that is 3 in [1,3,7]. In fact if we should try this on a list with no median number, such as [1,3,5,7], the following graph will emerge:

As you can see there is no single global minimum. There is a plateau which spans between the 2 middle numbers 3 and 5 in [1,3,5,7]. Again, just like in the previous case, the median does not take in account all the numbers and so is not a good representative of all the numbers.

Error as a square of the difference

Absolute errors don't seem to be too promising. But we need to somehow make sure that the differences are always positive. We can't have any negative errors as otherwise they will cancel out with the positive errors. One way to make sure we have positive differences is by squaring the differences, since square numbers are always positive, unless they are complex, which is not a relevant issue here.

We shall now consider the two interpretations of "error when compared to all the numbers" again using this definition of "error".

The least maximum error

We now plot the 3 graphs again but this time using y = (1-x)^2, y = (3-x)^2 and y = (7-x)^2.

So what is the maximum error of these errors? Again it's the highest lines which are composed of y = (max_num-x)^2 and y = (min_num-x)^2 so again we will not get a representative of all the numbers because only the maximum and minimum numbers are considered.

The least sum of errors

What happens if we should add the errors together?

Again, the sum is the blue line, and again there's a peak. But this time it's not just a peak, it's a quadratic equation's turning point. y = (1-x)^2, y = (3-x)^2 and y = (7-x)^2 are all quadratic equations and when you add up quadratic equations you get another quadratic equation which will always have a peak. What's more is that it is not just the median as in the previous case, so what is it?

y = (1-x)^2 + (3-x)^2 + (7-x)^2
y = (1+x^2-2x) + (9+x^2-6x) + (49+x^2-14x)
y = 3x^2 - 22x + 59

So the equation which describes the sum of the errors when compared to a particular "x" is y = 3x^2 - 22x + 59. Where is this equation's minimum? Using the quadratic equation formula x@min = -b/(2a) (derived by using differentiation),

x@min = -(-22)/(2*3) = 11/3

Does 11/3 make you think of anything? It's (1+3+7)/3, which is the arithmetic mean of [1,3,7].

In fact if we use a general list of "n" numbers [a_1, a_2, ..., a_n], the sum of errors when compared with "x" will be:

y = (a_1-x)^2 + (a_2-x)^2 + ... + (a_n-x)^2
y = (a_1^2+x^2-2xa_1) + (a_2^2+x^2-2xa_2) + ... + (a_n^2+x^2-2xa_n)
y = (x^2 + x^2 + ... + x^2) + (-2xa_1 + -2xa_2 + ... + -2xa_n) + (a_1^2 + a_2^2 + ... + a_n^2)
y = nx^2 - 2(a_1 + a_2 + ... + a_n)x + (a_1^2 + a_2^2 + ... + a_n^2)

x@min = -(-2(a_1 + a_2 + ... + a_n))/(2n) = (a_1 + a_2 + ... + a_n)/n

And there you have it, the derivation of the arithmetic mean.

So what is the arithmetic mean? It is the number which gives the least sum of square errors. This seems to be the best interpretation of "least error when compared to all numbers in the list" as it considers all the numbers in the list. In fact square errors are a common occurrence in statistics.

It is interesting to note that if instead of squaring we use 4th powers, or 6th powers, or other even powers which also make the differences positive, the turning points will not be at the same value of "x". But we'll leave the analysis of this observation for another post.

Why multiplying a fraction by 100 gives the percentage

I remember I had this curiosity about why it is that when you multiply a fraction by a number you get that fraction of that number. Why is it that 1/2 × 5 gives half of 5? Why is it that you find the percentage from a fraction by multiplying that fraction by 100? Why is it that multiplication should have this property?

You might want to look at my previous post which explains what fractions mean.

Percentages

As you should know, if for example you have a 10% income tax, that means that out of every 100 units of income you make, 10 units of them are taxes. So a percentage means the number of units you need to take out of every 100 units of a total. This is why it's called "percent", that is, "per hundred", because you are finding the amount of units you need to take our of every hundred units in the total.

However we can also express this statement using fractions instead of percentages. We can just say that 1/10 of your income is taxes. In fact we can convert fractions into percentages by multiplying the fraction by 100, 1/10 × 100 = 10, that is 10%.

Before we understand percentages, we need to understand fractions of totals.

The statement A/B of C means two things:

1. As explained in the last post, it means divide C into B equal parts and take A such parts.
2. It also means A is the number of units to take out of every B units in C.

For example, if we want to take 3/4 of 20,

We can either break 20 into 4 equal parts and take 3 of them:
20 = 5 + 5 + 5 + 5 (4 equal parts)
take 3 of the parts and we have
5 + 5 + 5 = 15

Or we can take 3 from every 4 in 20:
20 = 4 + 4 + 4 + 4 + 4
take 3 from every 4 and we have
3 + 3 + 3 + 3 + 3 = 15

In general, if we want to take A/B of C,
C = C/B + C/B + C/B ... (for B times) (B equal parts, that is, C/B × B which is equal to C)
take A of the parts and we have
C/B + C/B ... (for A times) = C/B × A

Or we can take A from every B in C,
C = B + B + B ... (for C/B times) (that is, B × C/B which is equal to C)
take A from every B and we have
A + A + A ... (for C/B times) = A × C/B

Since C/B × A = A × C/B, we know that the two statements are equal.

Good. So now we return to percentages. The reason why we convert fractions to percentages by multiplying the fraction by 100 is the following:
Given a fraction A/B, when we convert it to a percentage, we are changing the denominator of said fraction to 100 but leaving the fraction equal to A/B, and taking the numerator. So A/B becomes P/100 and P is the percentage.

We are finding a number which when divided by 100 gives the original fraction and therefore the amount of units you need to take from every 100 units of a total such that when you divide the amount you took by the total, you get the original fraction.

For example, if you have a total of 50 units and you want to take 1/10 of the total, the number of units you must take from the total, when divided by 50 must result in 1/10. Likewise, if we change the denominator of the fraction to 100, that is, 10/100, then we say that 10% of 50 units is the number of units we must take such that when it is divided by 50 we get 10/100 (which is equal to 1/10).

Percentages are useful because we would be standardizing the denominator of fractions in order to make them easy to compare. If we wanted to compare 2/4 to 4/16 we can change the denominators of both fractions to 100 (50/100 and 25/100 respectively) and then we will only have to compare the numerators in order to know by how much one fraction is bigger than the other.

So what we're doing is finding another fraction which is of the form P/100. However, P/100 must equal A/B in order to remain the same fraction.

So we have the equation A/B = P/100
We want to find P, so P = A/B × 100 (multiplied both sides by 100)

So if we want to express 2/4 as a percentage,
2/4 = P/100
P = 2/4 × 100
P = 50
So 2/4 = 50/100 or 50%.

I think that the percentage sign "%" can be treated as a symbol representing the constant "1/100". Which means that 50% = 50 × 1/100. This makes sense as in order to go from percentage to fraction form you just change the % back to 1/100 and calculate the expression. 50% = 50 × 1/100 = 1/2.

And this is why percentages work this way.

In general

Now we can generalize this to numbers other than 100. If we use "X" instead of "100",
A/B = P/X
P = A/B × X

By changing the denominator to X, the numerator P will be the amount of units you need to take out of every X units of a total, such that when you divide the amount you took by the total, you get A/B.

So, since P/X is equal to A/B, then just like we can say that P/X means that P is P/X of X, we can also say that P is A/B of X. For example, if 2.5/5 = 1/2, then just like 2.5 is 2.5/5 of 5, 2.5 is also 1/2 of 5.

Why does A equal A/B of B? Understanding what fractions mean.

I believe that the simplest things are often the most complex to understand, because we take them for granted and never question them. But when we do question them, we find that in their simplicity it is very hard to find simpler things into which they can be broken down to. One such simple thing is fractions. Why does the fraction 2/3 mean that 2 is 2/3 of 3? Most of you might be amazed that anyone would ask that. After all, we've been assuming that since we were very young. But challenges are what keep us sharp and what drive us to improve ourselves, so I find the challenge to understand this question inviting.

Notice that I'm assuming that a fraction is made of 2 positive whole numbers. We won't be considering irrational numbers, fractions with other fractions as numerator and denominator or even fractions with negative numbers. General fractions of these kinds will be considered in another post in the future.

Let's start from what a fraction means. 1/B means divide 1 into B equal parts and take one such part. A/B means take A such parts. So 2/5 means divide 1 into 5 equal parts and take two such parts. 6/5 means take six such parts, and so on.

In terms of fractions, "1" is called a "whole". When we divide a whole into B parts, each part is called a "Bth" (for example fourth, fifth, etc) which means 1/B. When we take A of the Bths we say that we have "A Bths" (for example one fourth, two fifths, etc) which means A/B.

Another thing the fraction A/B means is divide A into B equal parts and take one such part. Why is this definition equal to the first definition?

If we divide 1 into B equal parts, each part would be 1/B. But we want to divide A into B equal parts. Since A is A times as much as 1 (for example 2 is two times as much as 1, 3 is three times as much as 1, etc), each of its B equal parts are also A times as much as 1/B. So each part is A × 1/B. For example, if we want to find how big each part of 2 divided into 3 equal parts is, we first see how big 1 divided into 3 equal parts is, which is 1/3, then, since 2 is twice as big as 1, we double 1/3, giving 2 × 1/3.

What is A × 1/B? It's 1/B for A times, that is, A Bths, which is A/B. So we have shown that A × 1/B = A/B and that A/B means both "1 divided into B equal parts and take A parts" and "A divided into B equal parts and take 1 part". So 2/3 means both "1 divided into 3 equal parts and take 2 parts" and "2 divided into 3 equal parts and take 1 part".

Now that we have these two definitions, why does A = A/B of B? Why is it that 2 is 2/3 of 3? First, we must understand what "A/B of C" means.

What does A Bths of C mean? It means divide C into B equal parts and take A of them. Two thirds of four means divide 4 into 3 equal parts, or thirds, and take 2 of them. This implicitly means that A Bths on its own means A Bths of 1. So using our second definition of A/B, we can say that A/B of C is equal to C/B × A.

Does C/B × A equal A/B × C? We'll show this by showing that both of those expressions are equal to (A × C)/B or "the area of a C by A rectangle divided into B equal parts and taking 1 such part". The best way to understand these quantities is through a graphical representation.

The diagram on the left represents A/B × C, that is, a length A divided into B equal parts, extended into a rectangle C long and take one such part. The diagram on the right represents C/B × A, that is, a length C divided into B equal parts, extended into a rectangle A long and take one such part.

Since both rectangles are A by C with the difference that one is a rotated version of the other, and both are divided into B equal parts, we can save that both rectangles are equal to A × C and we are taking one Bth of such a rectangle. So C/B × A = A/B × C = (A × C)/B.

Great, so now we can say that A/B of C is equal to A/B × C, which means that we can just replace the "of" with a "×". So now we have a good understanding of what A/B of C means. Now we move to why A is A/B of B.

What does "A/B of B" mean? It means "divide B into B equal parts and take A such parts" or B/B × A. What is a Bth of B? It is 1/B × B. 1 divided into B equal parts and take B such parts. But then you would be taking all the parts which form 1 again. So a Bth of B is 1, therefore B/B = 1 (unless B is 0 in which case dividing 1 into 0 equal parts will not make sense). So B/B × A = 1 × A which we know equals A.

Great! So now we know that A/B of B is A, that A/B of C means A/B × C, that A/B × C = C/B × A = (A × C)/B and that A/B means both "1 divided into B equal parts and take A such parts" and "A divided into B equal parts and take 1 such part". Next we'll see how these are applied to percentages.