Reading by doing. ‘Thinking Better’ the book by Marcus du Sautoy

Have you heard about a new book Thinking Better: The Art of the Shortcut in Math and Life by Marcus du Sautoy? If not, you may consider given it a try, since this book is very engaging. The book is about various topics in mathematics and how they provide shortcuts that can be used in different fields of daily life to find solutions to seemingly daunting problems. These shortcuts speed up the computations and free time for you to do other things. Each chapter of the book starts with a puzzle that the reader is asked to solve. Then the main content of the chapter is related to the puzzle, while the solution is provided in the end.

I’ve already read The Music of the Primes that was also written by Marcus and thoroughly enjoyed it. What makes this book to stand out in comparison to The Music of The Primes is that it’s focused on practical advise that could be actioned by readers. But what I find most compelling about this book is that reading it is not enough to get the most out of the content, there is also a need to play with the content of each chapter, carefully examining it. Otherwise the subtle details and insight could be lost and not understood properly.

Marcus tries to present his ideas in a way that is accessible to a reader who is not supposed to be a math expert. That is why it seems his approach is to use as little of math terminology and formulas as possible. Even the word ‘formula’ doesn’t show up until page 20 into the book. This approach to writing popular science books is not new and it tries to achieve a trade off between a number of readers who may be frightened by the mathematical notation, and the number of readers who could be disappointed by the lack of it. Which brings me to the main point of this post. Even though Marcus doesn’t shy away from writing down some equations to exactly convey his ideas, there are places in the book where additional mathematical details could clarify his point even better. I also suggest to name the math objects as they are used in mathematics. There is no harm in doing that just like Steven Strogatz did in The Joy of x or John Derbyshire in the Unknown Quantity books. Proper math notation doesn’t frighten, but could actually help readers understand concepts better.

For example, in the first chapter of the book, on page 20 the following sequence is introduced

1, 3, 6, 10, 15, 21 …

Which as Marcus explains is a sequence of triangular numbers and the general formula to get the nth triangular number is

1/2 * n * (n + 1)

What I think is missing here is the fact that Marcus stops short of explaining that there is a general formula to find the sum of members of a finite arithmetic sequence. This is important, since each nth number in the triangular numbers sequence is a sum of the nth numbers of the arithmetic sequence that Marcus mentions on page 2, talking about Gauss’s school lesson

1, 2, 3, 4, 5, 6 …

Notice that this sequence is arithmetic, since the difference between each consecutive member and the previous one is constant. In this particular case it equals to 1.

For example, that general formula is

Sumn = 1/2 * n * (a1 + an), where a1 is the first member, which in the case of natural number sequence is 1; an stands for the last number until which we want to sum and n stands for the number of members starting from the first to the last we want to sum. Then substituting these values into the general formula we arrive at the formula Marcus mentioned in the book

nthtriangular number = 1/2 * n * (1 + n)

What this gives a reader is that now it’s possible to use this general formula to calculate sums of other arithmetic sequences, for example the sequence of odd numbers.

1, 3, 5, 7, 9, 11, 13, 15 …

Let’s calculate the sum of first 8 members of this sequence, a1 = 1, an = 15, n = 8, then

Sumn = 1/2 * n * (a1 + an) = 1/2 * 8 * (1 + 15) = 64

One additional, example where this general formula could have been mentioned by Marcus was on page 28, where he explains how to calculate the number of handshakes in a population of a city having N people. It goes like this. Imagine these N people standing in a line. Then the first person can make N – 1 handshakes ( minus one, since he cannot shake his own hands). Then the second one can make N – 2 handshakes, continuing in similar fashion until the last person who can make no handshakes, since everyone already handshaked him. Then Marcus mentions that the sum of handshakes is the sum from 1 to N – 1, which is the sum that Gauss was asked to perform in his math class:

1/2 * (N – 1) * N

It seems to me a reader can be very confused at this point, since it’s not that clear that this is the sum Gauss was tasked to perform. This is because Gauss was asked to calculate the sum of the first nth natural numbers,

1, 2, 3, 4, 5, 6 …

As was mentioned earlier the general formula for this sum is Sumn = 1/2 * n * (a1 + an) and in this particular case it’s

Sumn = 1/2 * n * (1 + n), Then, one may ask, where does the 1/2 * (N – 1) * N comes from?

To get out of the confusion state, two things could be helpful. First, it’s a diagram of people standing in line waiting to be handshaked, and a little bit more details on how the 1/2 * (N – 1) * N formula was derived.

Looking at the diagram with four people in line we can see that the total number of handshakes is 3 + 2 + 1 + 0 = 6. Now, if we take N people in line as in the book’s example, then the first person in line is a1 = N – 1 , and the last person in line an = N – N, and the total number of people in line is N. Then substituting these numbers into the general formula for the sum of arithmetic sequence we got:

Sumn = 1/2 * n * (a1 + an) = 1/2 * (N – 1 + N – N) * N = 1/2 * (N – 1) * N

This is how the formula in the book was derived.

This post is not the last one, since I have not finished reading the book yet. There are more to come.

What the hack is Rule 30? Cellular Automata Explained

Introduction

If you ask the same question, what is this Rule 30, then you are not alone. This rule is related to one-dimensional Cellular Automata introduced by Stephen Wolfram in 1983 and later described in his A New Kind Of Science book. Even though, I skimmed through this book previously, I was never able to understand what was it all about. It had some neat diagrams, but I didn’t try to understand how the diagrams where generated. This changed a day ago when I watched an interesting interview that Lex Fridman had with Stephen Wolfram, where they discussed among other things Rule 30, which was the one that Wolfram described first. This rule is capable of generating a complex behavior even though the rule itself is very simple to define.

Elementary Cellular Automaton

The Elementary Cellular Automaton consists of a one-dimensional array of cells that can be in just two sates, namely, black or white color. The cellular automaton starts from initial state, and then transition to the next state based on a certain function. The next state of the automaton is calculated based on the color of current cell and its left and right neighbors’ colors. By the way, that transition function, gives its name to the cellular automaton rule, just like Rule 30.

Rule 30 transition function

Current Sate111110101100011010001000
Next state00011110

Where, for example, the binary digits ‘111’ in the first column indicate the black color of the left, current and right cells, and the values, ‘0’ or ‘1’ indicate what will be the color of the current cell in the next state (iteration) of the automaton. If we write down all the the binary values of the next state together as a single 8 digit binary number, which is 00011110 and convert it to a decimal number we get 30, and hence the name of the Rule 30. In a Boolean form this transition function is

(left, current, right) -> left XOR (current OR right)

We’ll use this function later in the C++ implementation of the Rule 30.

This is how the output from Rule 30 looks like after 20 and 100 steps respectively.

source: WolframAlpha

How to generate Rule 30?

It is easy to implement the Rule 30 using a 64 bit integer in C++. The only drawback is that we can get only 32 steps with the implementation below taken from Wikipedia.

Note: If this is a little bit to much for you now, then skip to the next part where we’ll use WolframAlpha to program it for us.

In the code below a 64 bit integer is used to generate an initial state using a bit mask in line 6. Then the outer for loop generates 32 steps of the Rule 30 by applying the transition function in line 19. The inner loop generates the black (using character ‘1’) and white (using character ‘-‘) colors using state bit mask.

#include <stdint.h>
#include <iostream>

int main() {
 // This is our bit mask with the 32 bit set to '1' for initial state
  uint64_t state = 1u << 31;

  for (int i = 0 ; i < 32 ; i++) {

    for (int j = sizeof(uint64_t) * 8 - 1 ; j  >=  0 ; j--) {
      // Here we decide what should be the color of the current cell based on the current state bit mask.
     // Bitwise operator is used to accomplish this efficiently
      std::cout << char(state  >>  j & 1 ? '1' : '-');
    }
    std::cout << '\n';
    
    // This is just the (left, current, right) -> left XOR (current OR right) functioned mentioned previously
   // Bitwise operators  are used to accomplish this efficiently
    state = (state >> 1) ^ (state | state << 1);
  }
}

It is possible to run this code in the online C++ compile. Just click on the link and then click on the green Run button at the top of the screen. The result looks similar to below.

The full output for 32 steps looks like this

--------------------------------1-------------------------------
-------------------------------111------------------------------
------------------------------11--1-----------------------------
-----------------------------11-1111----------------------------
----------------------------11--1---1---------------------------
---------------------------11-1111-111--------------------------
--------------------------11--1----1--1-------------------------
-------------------------11-1111--111111------------------------
------------------------11--1---111-----1-----------------------
-----------------------11-1111-11--1---111----------------------
----------------------11--1----1-1111-11--1---------------------
---------------------11-1111--11-1----1-1111--------------------
--------------------11--1---111--11--11-1---1-------------------
-------------------11-1111-11--111-111--11-111------------------
------------------11--1----1-111---1--111--1--1-----------------
-----------------11-1111--11-1--1-11111--1111111----------------
----------------11--1---111--1111-1----111------1---------------
---------------11-1111-11--111----11--11--1----111--------------
--------------11--1----1-111--1--11-111-1111--11--1-------------
-------------11-1111--11-1--111111--1---1---111-1111------------
------------11--1---111--1111-----1111-111-11---1---1-----------
-----------11-1111-11--111---1---11----1---1-1-111-111----------
----------11--1----1-111--1-111-11-1--111-11-1-1---1--1---------
---------11-1111--11-1--111-1---1--1111---1--1-11-111111--------
--------11--1---111--1111---11-11111---1-11111-1--1-----1-------
-------11-1111-11--111---1-11--1----1-11-1-----11111---111------
------11--1----1-111--1-11-1-1111--11-1--11---11----1-11--1-----
-----11-1111--11-1--111-1--1-1---111--1111-1-11-1--11-1-1111----
----11--1---111--1111---1111-11-11--111----1-1--1111--1-1---1---
---11-1111-11--111---1-11----1--1-111--1--11-1111---111-11-111--
--11--1----1-111--1-11-1-1--11111-1--111111--1---1-11---1--1--1-
-11-1111--11-1--111-1--1-1111-----1111-----1111-11-1-1-111111111

Compare the image above to the one generated using WolframAlpha symbolic language in the Wolfram Notebook.

Using WolframAlpha to generate Rule 30

WolframAlpha is a computational knowledge engine developed by Wolfram Research. It is embedded in Mathematica symbolic language and it has a declarative programming style. Which means that you specify what you want to be done instead of how it should be done.

For example, to generate Rule 30 and visualize it one simple writes

ArrayPlot[CellularAutomaton[30, {{1},0}, 64]]

where CellularAutomaton function generates 64 states of the automaton, starting with a one black cell in accordance with the Rule 30 generation function, and ArrayPlot function prints the result.

And the output is

Please follow the this link to the Wolfram Notebook where the various Elementary Cellular Automata Rules are generated.

Summary

Playing with cellular automat rules seems like an interesting game to play, plus doing it using WolframAlpha language is a piece of cake.