Conservatives, Liberals and Logic

These days, “How can they be so illogical?”, is one of the most common questions I hear people asking in exasperation. Sometimes, “illogical” is replaced with “dumb”, “stupid” etc, but the intent is really to question the “abilities of deduction”. The other variants of this question are “How can they be so evil?”, “How can they be so wrong and not know it?” and so on. In this post, I am only going to talk about the “illogical” nature of “them”. 

I really find that question funny, because most of the time, people asking that question really don’t know what “Logic” means. Let’s revisit something that all of us have learned in middle school.

Logic helps us decide, given a set of premises, if the conclusion of inferences is correct. In other words, it helps us appraise an argument. Using logic, we can objectively assess an argument as either valid or invalid.

We all learned Geometry in school. Euclid constructed the most beautiful edifice in human knowledge, by starting with extremely simple postulates and using them to prove theorems of  increasing complexity. Everything about Euclid’s geometry is absolutely logical.

Except his postulates. They have no logical proof. They are taken as “self evident truths”. For example, one postulates roughly states that it is possible to draw a straight line from any one point to another. There is no way to prove this statement. We assume it to be true and use it for logically proving other theorems. As long as these “axioms” feel trivially true, everyone will be comfortable using them as the starting point.

But what if the axiom doesn’t feel trivially true? That indeed was the problem with Euclid’s 5th, and last postulate about parallel lines. This is a big topic, and I can refer you to Euclid’s Window. By changing the fifth postulate, mathematicians were able to come with completely new Geometries, that are very different but as logical as Euclidean Geometry. As it turns out, they are far more than mathematical curiosities, and the space in which our stars and galaxies operate, indeed follows non-Euclidean Geometry.

What does all this have to do with conservatives and liberals and their logical or illogical arguments? The point is, if the starting premise is different, then the logical argument would lead to a very different conclusion. Duh, you say. OK. So here is the crux. There is simply NO way to logically choose a premise. That whole thing - the inferences, the deductions - that whole logic thing, is what comes afterwards. 

So, it’s totally possible that “they” are making a very logical argument, but “their” premises are vastly different than yours. Here is what you probably don’t want to hear - “their” premises are not worse or better than your premises - they are just different premises.

This is not just a semantic jugglery. This is also not an attempt to whitewash by saying, “everyone is correct”. No. There indeed are a lot of stupid people who make illogical arguments. Their premises are contradictory in nature, and/or their inferences do not follow the rules of Logic. But questions such as “What ought to be” come down to morality, and cannot be settled by logic. Our moral code is driven by our intuitions, which are the result of our evolution by natural selection. Again, a big contentious topic and I can refer you to The Righteous Mind.

This is also not to say that all debates with “them” are on morality. Not at all. For example, when it comes to public policy, effectiveness (usefulness v/s harm) can often be debated objectively, using data analysis. That’s another big topic, as statistical interpretations can also get clouded by confirmation bias and frankly, dishonest intentions.

So now what? How can you convince “them” that “their” argument is illogical? Seriously, if you are still asking that question, you need to read this post again. Instead of looking at the argument, why not look at the premise of that argument? Why not examine it to see if it can be derived from even more fundamental premises, or is it truly subjective?

More importantly, why the need to prove to “them” that “they” are morally wrong? If Mathematics can have internally consistent theories that contradict each other, what’s wrong in a society of humans who hold very contradictory but logical views? Of course it’s not comfortable, but that diversity of thoughts and opinions, you know the thing that we say we celebrate - how about actually celebrating that?

Here’s Looking at Euclid

Book Review : Here’s Looking at Euclid

Author : Alex Bellos

My Rating : 4 out of 5 stars

The complete title of the book is “Here’s Looking at Euclid : A surprising excursion through the astonishing world of math”.

On the back cover of the book, there is a large paragraph praising this book, written by none other than Martin Gardner. That caught my attention. There is also a chapter in the book related to toys and puzzles based on mathematics, in which the author describes his meeting with Martin Gardner, and about his influence on recreational mathematics. This book seems to be in the same tradition that Gardener was instrumental in popularizing. Blending Math, History, Mind bending puzzles, and much more in an entertaining package.

This book too is fun to read, although it starts slow. The initial chapters were a bit of a drag for me. I was also irritated by the constant reference of Amazonian native tribes as “Indians”. This is not about political correctness, it’s just flat out wrong. Especially for someone who has taken the trouble to travel to India to personally research about ancient Hindu mathematics. Even setting that aside, it took a few chapters for the book to pick up speed for me.

Luckily, as the book progressed, it became a lot more entertaining and informative. Each chapter has a theme. Although sometimes there are references to earlier chapters, I don’t think it needs to be run sequentially. It can be thought of as a collection of essays, and can be read in any order.

Each chapter is about a different area of mathematics. Of course, there is no hope to even touch upon all the areas. These topics are what the author has chosen to show that Mathematics is accessible, fun and inspiring. Some of the topics of the chapters are so extensive that entire books of recreational math have been written about them. For example, see my previous reviews about books on topics such as the “non-Euclidean geometry” or “probability”. In spite of the limitation of condensing the material to one chapter, the author has succeeded in giving a thorough introduction to the history and ideas involved, and kept in a fun to read.

The last chapter, unconvincingly bundles non-Euclidean Geometry and Cantor’s theory of infinity together. It’s still a good chapter, but I would have preferred more detailed chapter on each. Some of the middle chapters are a breeze to read. The information about Sudoku, or the Bell Curve was brilliantly presented.

Most people who like reading books on Math will like this book as well. If you haven’t read a lot of books on Math, this is a nice place to start. Especially if you have been intimidated by high school math, you should definitely try this one, as there are many facets of Math that are just delightful and everyone deserves to be delighted by Math.

The Great Unknown

Book Review : The Great Unknown

Author : Marcus du Sautoy

My Rating : 4 out of 5 stars

The complete title of the book is “The Great Unknown: Seven Journeys to the Frontiers of Science”.

Author Marcus du Sautoy has chosen to take a “one pot meal” approach in this book and has greatly succeeded. It’s a tour of the areas of scientific knowledge that we struggle to find answers, and which have a strong possibility that the questions there may remain forever unanswered.

This is a challenging task. You can easily find full length books on each of the seven topics covered here. Condensing them to just one section of a book comes with a two pronged risk. Either it can become a shallow overview that’s too simplified, or it can become too narrow, focused only on certain aspects. To his immense credit, the author has managed that balance extremely well in first five sections. The final two sections were good too, but did not impress me as much as the previous sections.

The first section explains the recent branch of mathematics “Chaos Theory”, famous for the commonly referred, and commonly misunderstood “Butterfly Effect”. This section explains how a small gap in initial conditions of certain systems can lead to very large differences in eventual outcomes. The next section is about matter. Currently our experimentally verified understanding stops at quarks, the smallest building blocks of matter. Will we ever know if this is really the limit? There is a lot of “stuff” that we don’t know much about, like dark matter and dark energy. As you can expect the next two sections are about Quantum Physics and Universe, respectively. Quantum Physics literally puts a limit on our knowledge. At the largest scale, Black Holes and Multiverses may limit what we can know. The next section, and the last one about Physics is on “Time”. 

All those sections are well written, well explained and fun to read. The next section is first to veer directly into philosophy - Consciousness. The author prefers to look at using his mathematical lens to examine what it means to have consciousness. It’s an interesting approach, and I learned about advances in this field that of course are not covered by books on physics. Still, I felt this section wasn’t as deep as previous sections. The last section, at least to me, should have been the most exciting. It tackles the limits of mathematics, using Godel’s theorems and Cantor’s theorems about infinity. Godel’s theorems are simple to state, but trying to understand them is dizzying. Their importance for axiomatic systems (such as Mathematics) is monumental. I don’t think this section does justice to the beauty and creativity involved in these theorems. I learned something new about the theory of infinity (specifically the continuum) and it felt great.

Each section has a very personal touch. The author is not shy in admitting his preferences, biases and his struggles to understand many of these concepts. Each section also has dialogues with one or more prominent intellectual forces of that field. All this makes the book easier to read.

It’s a long book, and needs some investment of time from the reader. I think it’s worth it. You don’t have to read it in one go, and can take a pause between sections. It’s a nice tour of many prominent fields of knowledge where we are trying hard to push the limits of knowability. It’s especially useful to those who read only a few books on science if at all, because a lot is covered in one single book. So take your time, and read this one.

The Improbability Principle

Book Review : The Improbability Principle

Author : David Hand

My Rating : 5 out of 5 stars

The complete title of the book is “The Improbability Principle: Why Coincidences, Miracles, and Rare Events Happen Every Day”.

Who hasn’t experienced minor coincidences? Of course, everyone has. Even when it comes to rare events, most of us would say that we have experienced at least one such event. Are these just purely random occurrences? Many believe that they are not, and in their view, some divine power is at work. Some believe in miracles. Perhaps many more believe in supernatural abilities of certain individuals - whether it’s telepathy or seeing future or something similar. Can there be a rational explanation for all this, without invoking any argument about some divinity?

In this book published by Scientific American, the renowned statistician David Hand has provided a lucid explanation based on probability theory. He has given the theme a very catchy name, “The Improbability Principle”. With it, he asserts the paradoxical statement, “Rare events happen every day”. Wait a minute. If it’s rare, then it cannot happen every day, right?

Well, what’s rare from one individual’s point of view, is not really all that rare in a very large sample size. That’s the crux of the matter. There are other interesting aspects, and the author introduces much more rigor in his argument. The improbability principle, as per his definition, has many strands. He names them, “the law of inevitability”, “the law of truly large numbers”, “the law of selection”, “the law of the probability lever” and “the law of near enough”. Many readers would be intuitively familiar with the first two strands. I was. The formalization of other three strands was very interesting to me. Especially, “the law of near enough” which says that events that are sufficiently similar may be regarded as identical, and that can give rise to many apparent coincidences. 

All these strands are neatly arranged into individual chapters and explained using real life situations. This makes the book an easy read. There is as little mathematics as possible, and the author tries hard to make sure even those who are not mathematically inclined understand the argument well. The downside of this is, some material feels repetitive. 

The examples range a wide spectrum of topics, from gambling, accidents, psychics, science,  evolution and religion. The last two topics were most interesting to me and I wish those chapters were more extensive. In his argument, which I completely agree with, human intuition evolved to help us survive, and for that very reason it understands certainty better than uncertainty. That makes us want to believe in religion, and divine intervention.

That also raises an interesting question in my mind. Will anyone ever change their opinion by reading such books? I guess not. I was already in agreement with most of what the author is arguing, so it’s very easy for me to appreciate the strength of his arguments. If someone is already convinced that miracles do happen, I doubt this book will reverse that opinion. Because the desire to believe is so strong, that no rational argument has any chance to work.

That aside, I highly recommend this fantastic book. It’s extremely easy to read and all readers will find it insightful, regardless of their inclinations.

The Drunkard’s Walk

Book Review : The Drunkard’s Walk

Author : Leonard Mlodinow
My Rating : 5 out of 5 stars

The complete title of the book is “The Drunkard's Walk: How Randomness Rules Our Lives”.

It’s almost a cliche to say that, we as a society are not quite good at math. But what parts of math? How does it matter if on an average we don’t really understand calculus? I say, it doesn’t matter much. I think what does matter is, we are particularly inept at handling probability, or evaluating uncertainty. The success of many lottery systems worldwide is a good indication of that. I would even argue that the entire city of Las Vegas is built upon our inability to handle probabilities correctly.

The need to handle uncertainty goes beyond gambling and betting. Author Leonard Mlodinow shows how it’s part of our everyday life. Probability assessments happen in legal arguments, medical evaluation, large scale data analysis and so on.

He gives numerous examples of how we get it wrong. Ask yourself. What is more probable? A person being vegetarian, or a person being vegetarian for ethical reasons? This example is innocuous. Other examples, alas, are not so. What is more likely? A defendant fleeing the scene of crime, or a defendant fleeing the scene of crime because of fear of being accused? Most people say second is more probable, not realizing that it is a subset of first.

He uses such examples, to explain the subtleties involved, and also to build the story of how the study of Probability became a formal branch of mathematics. As you can expect, the initial reasons were indeed related to winning at gambling. Probability is closely related to Combinatorics. Instead of using mathematical terms like factorials, he tells us the story of Pascal who came with the ‘Pascal’s Triangle’ to help with calculations.

Interesting - as in simple but subtle - examples are numerous and present throughout the book. Consider my favorite. In a family of 2 children, what is the probability that both children are girls? Yes, it’s 1 out of 4. Let’s change the question slightly. In a family of 2 children, what is the probability that both children are girls, if one of them is known to be a girl? Or this. In a family of 2 children, what is the probability that both children are girls, if one of them is known to be a girl with name Florida. Read the book to understand how such conditional probabilities are calculated.

It’s not just for solving puzzles. The author mentions a terrifying personal experience, when his blood test gave a false positive for HIV. The doctor incorrectly concluded that his chance of dying soon is 999 out of 1000. Author mentions that similar erroneous conclusions happen in many forms of testing, including doping tests for athletes. Even more seriously, such wrong logic was used to convict a British woman of murdering her own children, in 1999. Astonishingly a similar mistake had also happened in the all American trial of OJ Simpson. Mishandling probabilities can have serious consequences.

Probability is also closely related to Statistics, and Statistics is closely related to Economics and Finance. This is about large scale data analysis. How do we determine how closely the data reflects the actual probability? How do we infer probability from a series of measurements? Topics such as the Gaussian curve and standard deviation, are wonderfully explained without getting overly mathematical.

In later chapters, there is some philosophical discussion on the role of chance in our life. Similar to luck versus abilities debate. I didn’t think the author handled these intractable problems well. These discussion are way too big and subjective for a book like this. That’s not a major complaint though.

I absolutely recommend this book. The real life examples, as well as topical puzzles are interesting. The writing is smooth and funny. This is the second book by the same author that I have reviewed, the first one being Euclid’s Window. The real strength of both the books, is how lucidly Leonard Mlodinow explains the complex mathematical concepts. It’s a real feat. This book, just like the previous, is immensely accessible, and will leave you educated and entertained.

Sum Of Consecutive Primes - Part 2

When I wrote the blog post on “Sum Of Consecutive Primes” I said that it was a pure D! activity. This is D!^2 :-)

One of the comments on the post suggested to do the analysis to find even more special primes. I liked the suggestion and modified my code to look for even more special primes. What kind of specialty are we talking about?

Please read the original blog post for more details. As a quick recap, we are looking for primes that can be written as sum of consecutive primes.

Obtaining primes from adding consecutive primes is just beautiful. As the analysis shows, many of these prime numbers can be written as multiple different sequences of consecutive primes. Some of these sequences are surprisingly large.

Within such primes, how about finding some more specializations, as follows.
1. The length of at least one the sequence itself is prime.
2. More specialization of the first, length of EVERY sequence is prime.
3. For a particular prime, the number of different generating sequences is also a prime.
4. Intersection of 2, and 3 : the number of sequences is prime, and length of every sequence is also prime.

In each case, we are looking for the primes below an arbitrary limit, which is 1 million for Problem 50 in Project Euler.

So here are the answers.

1. At least one sequence with prime length

The largest prime is
999983 = 34337 + 34351 + … + 34613 (29 primes)

The largest sequence is for
981391 = 71 + 73 + … + 3917 (523 primes)

The prime 442019 is noteworthy, as it has the six generating sequences, maximum for this subset. Only the first sequence is of prime length.
442019 = 419 + 421 + … + 2621 (301 primes)
442019 = 7529 + 7537 + … + 8017 (57 primes)
442019 = 13229 + 13241 + … + 13567 (33 primes)
442019 = 17569 + 17573 + … + 17807 (25 primes)
442019 = 49069 + 49081 + … + 147347 (9 primes)

2 All generating sequences are of prime length

There have to be more than 1 generating sequences to be qualified for this criterion.

The largest is
999863 = 13723 + 13729 + … + 14447 (71 primes)
999863 = 199933 + … + 200003 (5 primes)

The largest sequence in this subset is for
973691 = 61 + 67 + … + 3907 (523 primes)
Interestingly it’s the same length (523) for the largest sequence for the previous subset above.

Most prime sequences are for
999049 = 4801 + 4813 + … + 6337 (179 primes)
999049 = 7013 + 7019 + … + 8231 (131 primes)
999049 = 21019 + 21023 + … + 21493 (47 primes)
999049 = 199799 + … + 199819 (5 primes)

3. Number of generating sequence is prime

The largest is same as above 999863.

The largest sequence is for a prime that is an answer to the Project Euler : Problem 50, so I cannot give it here.

The most sequences are for
988321 = 113 + 127 + … + 3923 (515 primes)
988321 = 4673 + 4679 + .. + 6247(181 primes)
988321 = 5107 + 5113 +  … + 6577 (169 primes)
988321 = 89797 + 89809 + … + 89899 (11 primes)
988321 =  329419 + 329431 + 329471
Note that 2nd and 3rd of the above are overlapping sequences!

4. Primest of primes

Now let’s see which are the most special of these. These have ONLY a prime number ways of generating sequences, and length of each of these sequences is also prime.

The largest is 999863, same as subset 2 above.

The largest sequence in this subset is also for the same prime as for subset 2 above.
973691 = 61 + 67 + … + 3907 (523 primes)
973691 = 6841 + 6857 + …  + 8039 (131 primes)
So there are 2 sequences, each has prime number of primes.

And the most sequences are for
993367 = 13679 + 13681 + … + 14387 (71 primes)
993367 = 141863 + 141871 + … + 141941 (7 primes)
993367 = 331099 + 331127 + 331141
Now that’s one beautiful number. It’s the largest prime below 1 million that can be written in most prime number of different ways as sum of prime number of consecutive primes :-)

Project Euler : Probelm 78

The Project Euler : Problem 78 has been solved by comparatively less number of people than other problems on the same page. It is stated as

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
Find the least value of n for which p(n) is divisible by one million.

This is exactly the same as integer partitions - which is the number of ways in which a given natural number can be written as sum of smaller natural numbers. You can find the proof of the formula in this discussion.

I previously described two algorithms to calculate the integer partitions. The recursive algorithm suffers from being very slow, to the point of being useless. The iterative algorithm has acceptable speed, but its memory requirements prohibit it from being used for solving this problem.

So we need a much better way to calculate integer partitions. Fortunately, we can use some mathematics. You can check Wikipedia article on integer partitions, which mentions the following formula.

P(n) = P(n-1) + P(n-2) - P(n-5) - P(n-7) + …

There 2 things to notice.

1. The sign of each term changes based on the formula mentioned below.
2. Every term on the right hand side is of the form N-x. This x has to be a “Pentagonal Number” and is also given by the same formula below.

More concisely,

P(n) = SUM of [ (-1)^k . P (n - k(3k-1)/2) ]
for both positive and negative values of k as it goes from 1 to N.
Of course P(m) = 0, for any m less than 0.

We can use it to solve the Project Euler Problem 78 in a straight-forward way.

We start with calculating P(n) from 1 onwards up to an arbitrary number, say 1 million. To calculate P(N) at any iteration we have a nested loop that goes from N down to 1, examining only those numbers given by N-x, where x is a pentagonal number. We must consider both negative and positive values of x at every iteration and use proper sign to either add or subtract P(N-x). We will stop when we find a value of P(n) which is divisible by 1 million.

One thing to keep in mind is, the values for P(N) can get fairly large. There is no need to use anything like BigInteger, as we are only interested in the divisibility test, hence we can use the modulo arithmetic.

Here is an outline of the algorithm.

public static long GetNWithModulo1MPartitions () {

    final int MOD = 1000000 ; // divisible by 1M, from problem description
    finat int MAX = 1000000 ; // arbitrarily choosing max value for N
    int [] NumPartitions = new int [MAX] ;

    NumPartitions [0] = 1 ;
    NumPartitions [1] = 1 ;
    NumPartitions [2] = 2 ;

    for (int i = 3 ; i <= MAX ; i++ ) {
   
    long pn = 0 ;

    int sign = 0 ;
    long m1val = 0 ;
    long m2val = 0 ;

    int j ;
    for (j = 1 ; j <= i ; j++) {
        int m1 = i - (j * (3*j - 1) / 2) ; // using positive j
        int m2 = i - ((-1*j) * (3*(-1*j) - 1) / 2) ; // using negative j
        sign = (j%2 == 0) ? -1 : 1 ; // do we add or subtract ?
        // NOTE : in the following
        // if m1 or m2 is negative, the number of partitions is 0 by definition
        // We will add both, as one of them will be zero.
        m1val = (m1 < 0) ? 0 : (NumPartitions[m1] % MOD) ;
        m2val = (m2 < 0) ? 0 : (NumPartitions[m2] % MOD) ;

        pn = (pn + (sign * m1val) + (sign * m2val) ) % MOD ; // the real equation

        if ( pn < 0 ) {
            pn += MOD ; // force positive values
        } //
    }

    NumPartitions[i] = pn ;

    if ( pn == 0 ) {
        System.out.println ("Found N where P(N) is divisible by " + MOD + " and N = " + i) ;
        return ;
    }
    }

} //

That's a bit complicated. It certainly is too much for an interview question, even after giving the formula. The previous article on a recursive, as well as an iterative algorithm,  is a much better choice for a programming interview.

Euclid's Window

Book Review : Euclid’s Window
Author : Leonard Mlodinow
My Rating : 4 out of 5

The complete title of the book is “Euclid's Window: The Story of Geometry from Parallel Lines to Hyperspace”.

Geometry is a very special subject. It’s one of the oldest branches of knowledge - we started studying it to solve real life problems related to land and measurements. There is an even more important reason for calling it a special subject. That reason is Euclid, one of the most revered figures in Mathematics. He created an edifice for Geometry, whose schematic has been used to organize all mathematical knowledge.

His approach is irresistibly beautiful. At the core are the axioms, the self evident truths about the topic. Using these, and basic laws of logical reasoning, we prove simple theorems. Then we use these simple theorems to prove more complex theorems, and so on. This approach is at the foundation of modern mathematics.

Naturally, the book starts with Euclid and the Greek mathematicians. We proceed to Descartes who gave us the first main enhancement, what we now call Cartesian Geometry. If you have read many books on popular science/math, then some of the material so far will be a repetition for you. It’s still well written.

Then the author moves on to non-Euclidean geometry and the book becomes very interesting. Let me take a detour and give an idea as to what is non-Euclidean geometry.

Note that, in Euclid’s scheme, everything is built on a few trivial self-evident truths, called axioms. There is no way to prove them, but everything else is proven using them. If you change an axiom, you get a very different theory. This is not a random act. The only reason to change an axiom would be if it doesn’t feel as a self-evident truth.

Euclid’s 5th and last axiom roughly (very roughly) states that in a plane, 2 parallel lines do not meet if extended forever. It is not trivial as first 4 axioms. Compare it with the absolute simplicity of the 4th axiom which states that “all right angles are equal to one another”. The 5th axiom, often called as “The Parallel Postulate” has never appeared to be self-evident to mathematicians. Its history and surrounding controversy is a big topic in itself.

The Parallel Postulate reflects our intuitive idea about space. We mentally extend two parallel lines on a plain paper to infinity, and feel that they will never meet each other. But how do we know that space will indeed behave this way at astronomical distances? This is an important and interesting topic that ties mathematics with physics at a fundamental level. Author Leonard Mlodinow does a great job at explaining this in a very accessible and entertaining way. What he is telling is more a story of our understanding of space than a story of Geometry, but that’s a minor complaint against the title of the book.

The author explains how it was not easy challenging Euclid. Gauss did not publish any of his ideas because of the fear of backlash. Others were bolder, and persisted. Eventually these ideas were accepted as valid for Mathematics. But is their any real value in these competing geometries? Or is this just a mathematical curiosity? After all, given a line and a point outside that line, we really cannot draw 2 distinct lines that are in the same plane and are parallel to the original line. So why care about non-Euclidean geometry?

The answer, as we know now, came via Einstein. His work on the General Theory of Relativity proved that space is not Euclidean. You can really construct a triangle in space whose angles total to more than 180 degrees. This is one of the many seemingly bizarre, counter-intuitive ideas that have been brought to us by the 20th century. Here, the author focuses more on how our understanding of space changed with the theory of relativity, and less on other paradoxical aspects of the theory and justifiably so.

The last segment in the book is about how String Theory is changing that understanding even more radically, with its 10+ spatial dimensions. That’s another challenging task, and again I think the author did a great job.

I have to add a note on the style. Leonard Mlodinow has a peculiar sense of humor. I enjoyed his witty remarks throughout the book. He also tries to illustrate some points by creating scenes involving two brothers, most likely his sons, if I remember correctly. I was mildly annoyed by these examples. These two aspects of the book might irritate some readers.With these caveats I definitely recommend this book. This is not a mathematical textbook, it’s more a history. The reader is not expected to be a math graduate, but just a curious individual. So go for it.

Calculating Integer Partitions

This post can serve as a nice interview question. Because some problems can be deceptively simple. Knowing the formula MAY NOT be enough to write an algorithm to compute it. Allow me to explain using the example of Integer Partitions. If you want the explanation on how this formula is derived, you can read it here.

To recap, Integer Partitions of a number, are ways the number can be expressed as sum of smaller numbers. And, P(N), the number of integer partitions of a positive integer N can be expressed as

P(N) = PP(N,1) = PP(N-1, 1) + PP(N, 2)

Where PP(N,k) is the number of partitions in which the smallest addend is at least k. And

PP(N,k) = 0 if N < k
PP(N,k) = 1 if N = k
otherwise
PP(N,k) = PP(N-k,k) + PP(N,k+1)

Here is how it can serve as an interview question to test the programming skills. The “natural” recursive solution can be easily implemented as follows.

public static int recursivePP (int N, int k) {
    if ( N <= 0 ) return 0 ;
    if ( N < k ) return 0 ;
    if ( N == k ) return 1 ;
    return recursivePP(N-k, k) + recursivePP(N, k+1) ;
}

This is grossly inefficient. Because intermediate results are unnecessarily computed multiple times. Every time the recursion reaches a particular pair (a,b) it will issue another recursion and calculate it all over again. So the code is natural, but not smart. It would take forever to compute say P(100) this way. What’s needed is a solution based on dynamic programming that builds P(i) as i goes from 1 to N. To do that we need to store the table of values for P(N,k).

Consider the following code.

public static long[][] PPvalues = new long[100][100] ;

public static long iterativePP (int N) {

    if ( N <= 0 ) return 0 ;

    // init P(N,k) for N=1, k=1
    PPvalues[1][1] = 1 ;

    for (int i = 1 ; i <= N ; i++) {
       
    // mark PP(N,k) where N == k
    PPvalues[i][i] = 1 ;

    for (int j = i-1 ; j > 0 ; j--) {

        long pp1 = ((i-j) < j) ? 0 : PPvalues[i-j][j] ;
        long pp2 = (i < (j+1)) ? 0 : PPvalues[i][j+1] ;
        PPvalues[i][j] = pp1 + pp2 ;

    } //
    } //

    return PPvalues[N][1] ;
}

Now this performs incredibly faster than the recursive solution. O(N^2) is not ideal, but it’s not bad either. This answer should usually be enough for an interview question.

Unfortunately, it’s not enough for finding out the value of P(N) for large values of N. The reason is the memory complexity of the algorithm which is also O(N^2), and our computers have a very finite memory.  For example, even with 8G of RAM I could not calculate the value of P(10000) because there is simply not enough memory to allocate the table.

That was a real bummer. There is no quick and easy way to optimize this to take less memory. Using a better data structure to store only half the table, as P(N,k) = 0 for N < k, of course won’t help much, only by a factor of 2.

One possibility is to compute only a section of the table at any given time. Note that the formula requires only the current column and the previous column, to calculate the value of any cell. You can start from last 2 (rightmost) columns, and keep computing the table leftwards. So you have to store only 2 columns (current and previous), thus significantly reducing memory. That’s a good optimization. The resulting code will be too complex for an interview question though.

Fortunately, there is a better formula for coming up with an algorithm to calculate integer partitions. It is based on pentagonal numbers. But that’s a math question, not a programming question. I will explain that in another blog post.

Integer Partitions

Integer Partitioning is a standard problem that arises in many situations. If math is what you do, then perhaps you would classify this as a simple problem. For the rest of us, it's far from straightforward.

The basic problem can be stated as follows.

For any given positive integer N, in how many different ways can it be partitioned, that is, written as sum of smaller positive integers ?

Let's define the function P(N) as the number of integer partitions of N.

For example, 4 can be written in 5 different ways (partitions)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
4

So P(4) = 5.

Note that
1. Order of integers does not matter. So 1 + 4 is considered as the same partition as 4 + 1.
2. An integer can appear multiple times in a partition.

As is often the case, if you don't already know the trick, it's not easy to figure it out. For example, the first thing I tried was using induction, as in, can P(N+1) be expressed in terms of P(N)? I couldn't find any easy way to express it. Maybe there isn't a natural way.

The common trick in solving combinatorics problems is to use the principle of mutual exclusion. But how do I break the problem down to mutually exclusive smaller problems ? I couldn't find a way, so I gave up and surrendered myself to the all-knowing Wikipedia. Sure enough, the answer is there and this time the trick is to use an intermediate function.

Well that gave me the formula, but the explanation wasn't lucid enough on the Wikipedia page. So I decided to try to explain it in much simpler way.

It's a very nice trick and worth writing about.

Let's define another function - I am calling it partial partitions - PP(N,k) as the number of integer partitions, in which the smallest addend is at least k. It's important to note the language. The smallest addend doesn't have to be k, it can be more than k. In other words, no addend can be less than k.

For PP(4,2) we have 2 partitions in which every addend is equal or greater than 2
2 + 2
4
So PP(4,2) = 2.

For PP(4,3) and PP(4,4) we have just one same partition
4
So PP(4,4) = PP(4,3) = 1

Now, note that P(N) = PP(N,1). So if we can find a formula for PP(N,k), we will be able to determine P(N).

This neat trick of considering a more general problem, allows us to use the divide and conquer strategy. Now PP(N,k) can be divided into categories.

1. Where the smallest addend is exactly k. Let's call it PP(N,=k)
2. Where the smallest addend is strictly greater than k. Let's call it PP(N,>k).

It's easy to see that the second category is same as PP(N,k+1) because every addend must be strictly greater than k, so it's at least k+1.

What about the first category ? In this, every partition has to have k as an addend. There may be more than one addend equal to k. Since every partition has k, if we remove it, then we get partitions for N-k, and each of this partition satisfies the condition that no addend is less than k. This is PP(N-k,k). A diagram might help visualize this.

We must make sure that it is indeed the case that PP(N,=k) = PP(N-k,k) for all values of 1 <= k <= N for all integers N.

Consider a partition in PP(N,=k). As we have noticed already, removing the addend k, leaves us with a partition that adds up to N-k, with every addend >= k. Since we removed the same addend k, and every partition was different no two remaining partitions can be same. So we get proper set of distinct partitions. So PP(N,=k) must be a subset of PP(N-k,k).

Now let’s try from the other side. Consider PP(N-k,k). If we add the addend k to every partition, each partition will add up to N. Since we added the same term to each partition, they still remain distinct, so we have a proper set. Also, since we added the addend k to it, every partition of course has an element that's exactly k. So this PP(N-k, k) must be a subset of PP(N,=k).

Since PP(N-k,k) and PP(N,=k) are subsets of each other, they must be equal.

Combining all this together

PP(N,k) = PP(N,>k) + PP(N,=k) because of mutual exclusion
PP(N,k) = PP(N,k+1) + PP(N-k,k) as explained above

Now this is a recursive formula, so we need terminating conditions

PP(N,k) = 0 if k > N
PP(N,k) = 1 if k = N

To wrap up,

P(N) = PP(N,1) = PP(N-1, 1) + PP(N, 2)
That’s one pretty looking formula. In such recursive formulas, like partial derangement, both the terms reduce N and k to terminate the recursion. Here, one term reduces N, while other increases k. That’s got to put a smile on your face if you like recursion!

Sum of consecutive primes

When I was in college there was a term for such kind of activities - “D!” - pronounced as “D not”. which was an acronym for “Dhandaa not” - meaning someone who has nothing better to do. The following can be classified as a pure "D!" activity!

The Problem 50 in Project Euler is stated as

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?

I had no idea that consecutive primes can be added to get another prime ! That’s simply beautiful.

Once you have a prime number generator, solving problems related to prime numbers becomes easier, if not easy. The best generator is of course the Sieve Of Eratosthenes, for which you can find the code here.

Using it, you can generate primes up to the required limit, and implement a brute force algorithm. Just have a loop iterating over the list of primes, and keep adding up all the primes starting from that position. The sum is prime if it exists in our list. Note it down and how many primes were added to get it. Keep only the sum that was generated using more number of primes than the last one.

Well, what’s the fun in doing only that ? So I just added a data structure to keep track of which primes can be generated by adding a set of consecutive primes, and if there are more than one set of consecutive primes that add up to a prime, keep a track of that as well. The results are fun to analyze.

It’s not that just 2 or 3 primes can be added to get another prime, some of the primes below 1 million, can be constructed by adding over 500 consecutive primes. More, some of these can be constructed using more than one list ! Astonishing.

The number 41, mentioned in the problem, can also be written as sum of a different set of consecutive primes, 41 = 11 + 13 + 17. That’s the only 2-digit prime that can be obtained via adding more than one set of consecutive primes.

So what other primes can be written as sum of more than 1 set of consecutive primes ? To save typing, I am going to define a new function SCP for “sum of consecutive primes”.

SCP(n) = the number of sets of consecutive primes that can be added to get n.
So SCP(41) = 2

There are many 3 digit primes that have SCP number more than 1. For example

983 = 23 + 29 + … + 89 + 97 (17 primes)
983 = 47 + 53 + … + 101 + 103 (13 primes)
So SCP(983) = 2.

There are no 3 digit primes with SCP = 3. But There are 2 primes with SCP number as 4.

311 = 11 + 13 + .. + 43 + 47 (11 primes)
311 = 31 + 37 + … +  53 + 59 (7 primes)
311 = 53 + 59 + 61 + 67 + 71
311 = 101 + 103 + 107

The other prime is 863.

On the other hand, the smallest prime with SCP number 3 is 1151.

The smallest prime with SCP number 5 is 34421.

34421 = 269 + 271 + … + 701 + 709 (71 primes)
34421 = 1429 + 1433 + … + 1567 + 1571 (23 primes)
34421 = 3793 + 3797 + … + 3851 + 3853 (9 primes)
34421 = 4889 + 4903 + … + 4933 + 4937 (7 primes)
34421 = 11467 + 11471 + 11483

Below one million, the largest prime with SCP number as 5 is 988321. One of the set of consecutive primes that add up to that number is

988321 = 113 + 127 + … + 3919 + 3923
This has a whopping 515 consecutive primes !

And it’s NOT the answer to the Project Euler problem. The SCP number for the answer is just 3.

Below 1 million, there is only one prime with SCP number as 6, and that is 442019.

442019 = 419 + 421 + … + 2617 + 2621 (301 primes)
442019 = 7529 + 7537 + … + 8011 + 8017 (57 primes)
442019 = 13229 + 13241 + … + 13553 + 13567 (33 primes)
442019 = 17569 + 17573 + … + 17791 + 17807 (25 primes)
442019 = 49069 + 49081 + … + 49139 + 49157 (9 primes)
442019 = 147331 + 147341 + 147347

That’s a special number. There is no prime below 1 million with SCP = 7.

What’s the point of all this ? Not much, except that prime numbers are fascinating. If you want to know more about the mathematical research done on them, I highly recommend reading Prime Obsession. Don’t let the topic turn you away from reading it. It’s a very easy book to read, and is enormous fun. I know that’s hard to believe, but it really is, and that’s why it’s one of my all time favorite books.

UPDATE : Added some more analysis in a follow-up post.

Project Euler : Problem 49

If you want to challenge yourself at writing algorithms to solve mathematical problems, then Project Euler is a nice site for you. The problems have a wide range of difficulty. I found the problem 49 surprisingly rich in terms of strategies that can be employed to solve it.

The problem statement is :

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Unusual indeed. The numbers have to be prime and permutations of each other, and make up an arithmetic sequence.

Of course, there are many ways to solve the problem. One obvious candidate is use some sort of brute force approach. But what's the fun in doing that ? So I decided to try an efficient approach. I am sure there are many alternatives. The one I tried is as follows.

Note that there are 3 unusual properties. I used them to break the problem in 3 steps and wrote a small, efficient program for each step.

1. Generate Prime Numbers.
Obviously, if we inspect only the 4 digit prime numbers, it's going to reduce the problem space and speed up the solution. As long as generating prime numbers is not expensive. The standard textbook solution for this is to use "Sieve Of Eratosthenes", that offers a near linear algorithm to generate the prime numbers. You can find more explanation here. Using this program, we generate a list of 4-digit primes in ascending order.

2. Group the numbers that are permutations of each other
By treating the numbers as string of digits, we can compare any two numbers to check if they are permutations of each other. The brute force algorithm will have O(N^2) complexity. I wrote an algorithm with linear complexity that works especially well when the cardinality of alphabet set is not very high. You can find the algorithm here. With this step done, we have grouped together all the 4 digit primes that are permutations of each other. Since the original list of all the primes was already in sorted order, each group is also sorted in ascending order.

3. Find the arithmetic sequence
This is bit harder than the first 2 steps. Now, if you just want to examine a given sequence of numbers to decide if it is an arithmetic sequence, then that's very easy to do. But that's not what I wanted. I wanted to write an algorithm to find all the arithmetic sequences within a given sequence. Solving this more generic problem is NOT necessary to solve the Project Euler problem. Becase we are told that the sequence contains only 3 numbers. Moreover, we have already grouped the numbers based on permutations. So either the group is a desired sequence or not. That's simple to test. But if you were not given the problem specific information, then you have to find an arithmetic sequence within  a larger sequence. For example, I found a set of 11 primes that are permutations of each other. The entire set is not an arithmetic sequence. But a subset could have been. You can find the details of my solution to the generic problem here.

By connecting these steps, you can find the solution of the problem. On my MacBook Pro, it took less than one minute for my Java program to generate all the prime numbers, group them based on permutations and find the sequence.

Some interesting facts. There are 174 permutation groups within the 4 digit primes that have more than 3 members in it. For example
[3253, 5233, 5323] 
[6899, 8699, 8969, 9689] 
[2039, 2309, 2903, 3209, 9203].

The longest two have 11 primes in each !
[1237, 1327, 1723, 2137, 2371, 2713, 2731, 3217, 3271, 7213, 7321] 
[1279, 1297, 2179, 2719, 2791, 2917, 2971, 7129, 7219, 9127, 9721].

But none of these contain any sequences.

The most curious fact is not mentioned in the problem. The other prime permutaiton sequence, has exactly the same difference in it's terms, 3330 !! That means : The only 2 arithmetic sequences of 4 digit primes such that the numbers are permutations of each other, have exactly the same difference. The one was already given in the problem. The other one we have to find. Both sequences have the same difference, 3330. Really interesting.

The Project Euler guidelines suggest not to disclose the solution. It's OK to explain the strategy. Hence I have not given the solution here.

Finding Arithmetic Sequences

As a final step of solving a problem, I needed to find out arithmetic sequences within a series of numbers. I am not sure if there is a more efficient algorithm than what I wrote. This one will do the job just fine - the complexity is quite close to O(N^2), which seems fair to me.

The problem.

Given a series of integers in ascending order, we have to find all the arithmetic sequences that occur in the entire series. An arithmetic sequence is defined as a sequence of 3 or more integers in ascending order such that difference between any pair of consecutive integers is same.

For example.

In the series, 2 3 4 5 6 7 8 9, there are 5 sequences. The entire series is a sequence with difference as 1. Then there are (2 4 6 8), (3 5 7 9), (2 5 8) and (3 6 9).

A number can be part of multiple sequences, and multiple sequences can have the same difference between the consecutive integers.

This possibility of a number being in multiple sequences may make the problem seem harder. It isn't that hard.

The idea behind my solution is simple.

1. Iterate over the sorted array from the first element to the second last.
2. For each number i, iterate from the next number j to last. This gives us all the pairs [i,j].
3. For each pair, find the difference, d = j - i.
4. Keep a map with this difference d as the key, and for value - a list of all sequences that have this difference in its consecutive numbers. Note that this will be a list of sequences, as there can be more than one sequence for that difference.
5. See if the difference was already encountered, if not create a new list of sequences.
6. If there was an existing list of sequences, find the sequence in that list that has the first number i. If a sequence was found, add j to it. If not, we create a new sequence and add i and j to it. It's very important to note that for a given difference, there can be only one sequence that has the number i in it. For a sequence, we will use a set data structure.
7. At the end of all iterations, we have created an interesting data structure. At the top level is the map, that uses an the difference between consecutive integers as the key, and for value it has a list of sequences that have that difference. And each sequence is a set.
8. When using this data structure, we have to discard the sequences that have only 2 elements in it.

Let's see how this work for the sequence 2 4 5 6 8 9. The following list shows how the data structure will look after each iteration.

i = 2, j = 4. Map { 2:[(2,4)] }

i = 2, j = 5. Map { 2:[(2,4)] 3:[(2,5)] }

i = 2, j = 6. Map { 2:[(2,4)] 3:[(2,5)] 4:[(2,6)] }
...
i = 4, j = 5. Map { 1:[(4,5)] 2:[(2,4)] 3:[(2,5)] 4:[(2,6)] 6:[(2,8)] 7:[(2,9)] }

i = 4, j = 6. Map { 1:[(4,5)] 2:[(2,4,6)] 3:[(2,5)] 4:[(2,6)] 6:[(2,8)] 7:[(2,9)] }

i = 4, j = 8. Map { 1:[(4,5)] 2:[(2,4,6)] 3:[(2,5)] 4:[(2,6) (4,8)] 6:[(2,8)] 7:[(2,9)] }

Note that till these iterations, there is only one true sequence in the data structure above : 2:[(2,4,6)]. Of course more would be found in later iterations.

With this, let's look at the Java code.

/**
 *  Finds arithmetic sequences within a list of sorted numbers
 */
public static void findSequence (int[] nums)
{

    // Iterate over the array
    // Starting from first element, till second last element
    // For every element, iterate over the list again to find all pairs
    // For every pair, find the difference
    // For the difference, find the sequences
    //
    // There can be multiple arithmatic sequences for the same difference.
    // See if the lower number is already part of any sequence for that diff.
    // If yes, then add the higher number to that set.
    // Else, create a new set, add both numbers to it
    //
    // Any set that has 3 or more elements
    // is an arithmetic sequence.


    // Note the data structure.
    // Map the difference to a collection of sequences.
    // Each sequence is a SortedSet

    Map >> arith_sequences
        = new HashMap >> ();

    for (int i = 0 ; i < nums.ltheength - 1 ; i++ ) {
      for ( int j = i+1 ; j < nums.length ; j++ ) {
        // work on each pair
        long diff = nums[j] - nums[i] ;
        if ( ! arith_sequences.containsKey (diff) ) {
          // create the collection when the diff is
          // encountered for the first time
          arith_sequences.put (diff, new ArrayList>()) ;
        } //
       
        Collection> sequences_for_diff
                   = arith_sequences.get (diff) ;

        boolean found_sequence = false ;
        for (SortedSet sequence : sequences_for_diff) {
        if ( sequence.contains (nums[i]) ) {
            found_sequence = true ;
            sequence.add (nums[j]) ;
            break ;
        } //
      } //
      // if no sequence was found that contained i,
      // then create a new one
      if ( ! found_sequence ) {
        SortedSet sequence = new TreeSet () ;
        sequence.add (nums[i]) ;
        sequence.add (nums[j]) ;
        sequences_for_diff.add (sequence) ;
      } //
    } //
  } //



} //

The complexity is obviously at least O(N^2). For every pair of thse N*N pairs, we iterate to find the sequence that has the lower number in it. Intuitively, it may seem that the worst case will happen when the array contains N consecutive integers from 1 to N. Then the map will have keys for each number from 1 to N-1. But the value will have a list that contains only one sequence, and it will be found in just one iteration. For multplying the complexity, we need the list to have many sequences for the same difference. This depends on the data. Honestly, I do not know how to compute that complexity. Of course the cost of manipulating the data structure - adding a number to the sorted set should also be taken into account. Again, it's getting added only at the end - so that should be fast.

In any case, this is simple, and reasonably efficient algorithm for the job.

Generating Prime Numbers Using Sieve of Eratosthenes

Generating a prime is occasionally needed in solving coding puzzles. It's a pretty straightforward task, whether you stick with a naive brute force solution or with "Sieve of Eratosthenes". I am going to use this one later to show a solution for a more involved problem.

The "Sieve of Eratosthenes" is a very old method of generating the primes, named after an ancient Greek Mathematician who invented it. It's intuitive to understand, and efficient.

You start with number 2, and mark all numbers up to N that are divisible by 2 as non-prime, by just hopping forward 2 places, till you reach N. Then you start with 3, and mark every third number as non-prime. Next number 4 is already marked as non-prime, so ignore it. Then start with 5, and mark every 5th number as non-prime. And so on.

A simple observation helps most algorithms related to checking/generating prime numbers.

For finding a factor of any number N, you only have to check using numbers that are less than the square root of N. Because if N = x * y, and x > sqrt(N), then it must be true that y < sqrt(N).

You can use this observations is 2 ways.

1. When you are considering the factors to cross out the composites, you need to consider factors only till sqrt(N).
2. When you start crossing out, you can start crossing out numbers from factor^2. Anything composite below that would be a smaller multiple of factor, and would have been crossed out.

Here is the Java code :

// consider all numbers as prime to begin with

// init array of N flags to false

boolean is_non_prime[] = new boolean [N+1] ;

// NOTE : first index is 0

is_non_prime [0] = is_non_prime [1] = true ;
// 0 and 1 are not considered primes

for (int factor = 2 ; factor*factor <= N ; factor ++) {

    // no need to find composites of a non-prime number

    if ( is_non_prime[factor] )

        continue ;

    for ( int composite = factor * factor ;
              composite <= N ; composite += factor ) {

        is_non_prime [composite] = true ;

    } //

} //

After this, the array is_non_prime[k] = false for any number K that is prime.

Of course, this needs memory of N bits for storing the flags, which is not an issue in most applications.

Finding the computational complexity is a bit tricky. There are 2 loops, but the complexity is not O(N^2). The outer loop is executed K times, where K=sqrt(N). The inner loop executed only for primes, which is significantly less than K for large values of K.

Note that for factor = 2, there are N/2 operations because N/2 numbers will be crossed out. Then for factor = 3, there will be N/3 operations. Then N/5 operations and so on. So

Total operations = N/2 + N/3 + N/5 + N/7 + N/11 + N/13 + ...
  = N * ( 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + ... )

The term in the parenthesis is "prime harmonic series" . It has been shown to have the upper bound of ln ln (N). Where ln is the natural logarithm, and yes, it's a double logarithm : log of log of N.

This means the complexity of our algorithm is O (N * ln ln N ).

The double logarithm make the second term quite small than N. That makes the computation complexity of "Sieve of Eratosthenes" almost linear, which is quite a feat.