Susam Pal

Implication of implications

Susam Pal — Tue, 22 Nov 2011 14:00:00 +0000

Last night, I came across a simple propositional logic problem concerned with the validity of the following statement:

((A ⇒ B) ∧ (B ⇒ C)) ⇔ (A ⇒ C)

At first, I thought it is valid. But on drawing the truth table, I was surprised to see that it isn't valid.

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇔ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	F
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	F
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

My intuition had failed. The truth table shows that there are two cases in which the statement is false.

Case 1: (A ⇒ C) ∧ (B ⇒ C) ∧ ¬(A ⇒ B)

In this case, A implies C and B implies C, but A does not imply B. This corresponds to the third row in the truth table. It makes sense. Two things can imply a third thing but they need not imply each other. For example, rain may imply wet soil and snow may imply wet soil as well, but rain need not imply snow. Here is another example that demonstrates this.

The following two statements are true for any integer x.

4 | x ⇒ 2 | x
6 | x ⇒ 2 | x

But the following statement is false when x ≡ 4 (mod 12) or x ≡ 8 (mod 12).

4 | x ⇒ 6 | x

In other words, if an integer is a multiple of 4 or 6, then it is also a multiple of 2. But this is not equivalent to saying that if an integer is a multiple of 4, then it is also a multiple of 6. That's not even correct as we can confirm for x ∈ {4, 8, 16, 20, 28, 32, …}.

Case 2: (A ⇒ B) ∧ (A ⇒ C) ∧ ¬(B ⇒ C)

In this case, A implies B as well as C but B does not imply C. This corresponds to the sixth row in the truth table. It makes sense as well. One thing can imply two other things but those two things need not imply each other. For example, rain may imply wet soil and flooded rivers but wet soil need not imply flooded rivers. The soil could be wet due to irrigation sprinklers. Once again, here is a mathematical example to demonstrate this.

The following two statements are true for any integer x.

6 | x ⇒ 2 | x
6 | x ⇒ 3 | x

But the following statement is false when x is an odd multiple of 3.

2 | x ⇒ 3 | x

The truth table correctly tells us that saying, "If an integer is a mutliple of 6, then it is a multiple of 2 as well as 3," is not equivalent to saying, "If an integer is a multiple of 2, it is a multiple of 3 as well." That would be nonsense.

Encoding intuition correctly

My intuition incorrectly concluded that the (A ⇒ B) ∧ (B ⇒ C) ⇔ (A ⇒ C) is valid because I was not translating the given statement correctly in my mind. I was thinking that if A implies B and B implies C, of course A must also imply C. This is true but this is not what the given statement represents. The given statement means something more than this. In addition to what I thought, it also means that if A does not imply B or B does not imply C, then A does not imply C as well. This however doesn't happen. The truth table shows that even though A does not imply B or B does not imply C, it is possible that A implies C.

As far as my intuition is concerned, the following would be the right way to represent what I was thinking.

((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)

Indeed, this statement is valid as can be seen from the truth table below.

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

AUTH CRAM-MD5

Susam Pal — Mon, 07 Nov 2011 20:27:56 +0000

I was playing with a few SMTP authentication mechanisms while setting up my SMTP server. I found CRAM-MD5 authentication mechanism particularly interesting as it is a challenge-response authentication mechanism and involves HMAC-MD5. Let me first show a complete session with an SMTP server before coming to CRAM-MD5. Note that I am not using TLS or SSL in the sessions displayed below so that the SMTP traffic can be seen as plaintext. In practice, any email program should be configured to use TLS or SSL while having a session with an SMTP server. In the following session, I have selected the PLAIN authentication mechanism.

susam@nifty:~$ telnet susam.in 25
Trying 106.187.41.241...
Connected to susam.in.
Escape character is '^]'.
220 tesseract.susam.in ESMTP Exim 4.72 Mon, 07 Nov 2011 20:27:56 +0530
EHLO nifty.localdomain
250-tesseract.susam.in Hello nifty.localdomain [122.167.80.194]
250-SIZE 52428800
250-PIPELINING
250-AUTH PLAIN LOGIN CRAM-MD5
250-STARTTLS
250 HELP
AUTH PLAIN AGFsaWNlAHdvbmRlcmxhbmQ=
235 Authentication succeeded
MAIL FROM:<alice@susam.in>
250 OK
RCPT TO:<example.recipient@gmail.com>
250 Accepted
DATA
354 Enter message, ending with "." on a line by itself
Date: Mon, 07 Nov 2011 20:28:00 +0530
From: Alice <alice@susam.in>
To: Example Recipient <example.recipient@gmail.com>
Subject: Test email 

This is a test email.
.
250 OK id=1RNQef-0004e7-7s
QUIT
221 tesseract.susam.in closing connection
Connection closed by foreign host.

In the AUTH PLAIN line I have sent the base64 encoding of the string \0alice\0wonderland. \0 indicates a null character, alice is the sender's user name and wonderland is the sender's password. If an eavesdropper intercepts this network traffic, he can easily find the user's password by simply decoding the base64 response sent by the client. This is also susceptible to replay attacks as the eavesdropper can use the AUTH PLAIN line containing the base64 encoded credentials to log into the server in future. This is why it is very important to secure the connection with TLS or SSL while having a session with the SMTP server.

Now, let me quickly show only the relevant lines for an authentication using the LOGIN mechanism.

AUTH LOGIN
334 VXNlcm5hbWU6
YWxpY2U=
334 UGFzc3dvcmQ6
d29uZGVybGFuZA==
235 Authentication succeeded

What is happening here becomes clear by decoding the base64 encoded messages. The following statements in Python 2.7.2 decode these messages.

>>> 'VXNlcm5hbWU6'.decode('base64')
'Username:'
>>> 'YWxpY2U='.decode('base64')
'alice'
>>> 'UGFzc3dvcmQ6'.decode('base64')
'Password:'
>>> 'd29uZGVybGFuZA=='.decode('base64')
'wonderland'

If the session isn't encrypted, LOGIN authentication mechanism is susceptible to the same problems that PLAIN authentication mechanism is susceptible to. Now, let me describe the CRAM-MD5 authentication mechanism. When the client selects the CRAM-MD5 authentication mechanism, the server sends a base64 encoded challenge as shown below.

AUTH CRAM-MD5
334 PDE3ODkzLjEzMjA2NzkxMjNAdGVzc2VyYWN0LnN1c2FtLmluPg==

An HMAC is calculated for this challenge with the password as the key and MD5 as the hash function. A string is formed by concatenating the user name, a space and the hex representation of the HMAC. The base64 encoding of this string is sent as the response by the client. The following statements I tried in Python 2.7.2 show how a response can be formed for the above challenge.

>>> 'PDE3ODkzLjEzMjA2NzkxMjNAdGVzc2VyYWN0LnN1c2FtLmluPg=='.decode('base64')
'<17893.1320679123@tesseract.susam.in>'
>>> import hmac, hashlib
>>> hmac.new('wonderland', '<17893.1320679123@tesseract.susam.in>', hashlib.md5).hexdigest()
'64b2a43c1f6ed6806a980914e23e75f0'
>>> 'alice 64b2a43c1f6ed6806a980914e23e75f0'.encode('base64')
'YWxpY2UgNjRiMmE0M2MxZjZlZDY4MDZhOTgwOTE0ZTIzZTc1ZjA=\n'

Of course, this can be written as a small function:

import hmac, hashlib
def cram_md5_response(username, password, base64challenge):
    return (username + ' ' +
            hmac.new(password,
                     base64challenge.decode('base64'),
                     hashlib.md5).hexdigest()).encode('base64')

The following snippet shows the SMTP server accepting the client-response.

AUTH CRAM-MD5
334 PDE3ODkzLjEzMjA2NzkxMjNAdGVzc2VyYWN0LnN1c2FtLmluPg==
YWxpY2UgNjRiMmE0M2MxZjZlZDY4MDZhOTgwOTE0ZTIzZTc1ZjA=
235 Authentication succeeded

CRAM-MD5 authentication mechanism is relatively more secure than the other two mechanisms even if the connection is not secured because the password can not be retrieved by decoding the base64 encoded client-response. The password is used as the key to calculate the HMAC but the password is not present anywhere in the response. It prevents replay attacks too because the server sends an unpredictable challenge for every authentication. The client-response computed for a certain challenge is invalid for further authentications which will involve different unpredictable challenges.

Here is a list of hyperlinks for further reading:

RFC 4954: SMTP Service Extension for Authentication
RFC 4616: The PLAIN Simple Authentication and Security Layer (SASL) Mechanism
RFC 2195: IMAP/POP AUTHorize Extension for Simple Challenge/Response
RFC 2104: HMAC: Keyed-Hashing for Message Authentication

When worse is better

Susam Pal — Sat, 29 Oct 2011 02:00:00 +0000

Let me begin this post with a puzzle.

Alex and Bob worked as financial advisers for the same company. They drew equal salaries from the company. They behaved well at the office. Both worked on similar assignments. Each assignment required a yes-no decision. The company used the decisions made by them to make profits.

After the recession hit the company very badly, they have to fire one of them. Both Alex and Bob worked on almost the same number of assignments in the last ten years. Alex has been consistently taking about 80% decisions correctly every year. Bob, on the other hand, has been taking only about 5% correct decisions every year.

The company has decided to keep Bob and fire Alex. Why?

If you want to solve this puzzle yourself, you might want to stop here and think for a while. There are spoilers ahead.

Before giving away the solution to this puzzle, let me discuss something else.

Shannon's noisy channel coding theorem guarantees that in a binary symmetric channel with an error rate p, it is possible to transmit digital data with arbitrarily small probability of error up to a transmission rate of:

1 + p log₂ p + (1 − p) log₂ (1 − p)

We'll call this the optimal transmission rate. The error rate p is the probability that the channel will corrupt a bit from 1 to 0 or vice versa. The transmission rate is the ratio of the number of data bits to the total number of bits used to represent them. If we employ error-correcting codes, the transmission rate would be less than 1 because we'll need extra bits for error correction. As a result, the number of bits used to represent them would be more than the number of data bits.

For p = 0, the transmission rate is maximum. That's obvious. Loosely speaking, if the channel is error-free, we do not need extra bits for error correction. The transmission rate is poorest when p = ¹⁄₂. In this case, each bit received is completely random since the channel is just as likely to send 0 or 1 irrespective of the original bit sent by the transmitter. However, it might be surprising that as the error rate increases from 0.5 to 1, the optimal transmission rate increases. When p = 1, the optimal transmission rate is maximum again. It is easy to undersand this intuitively. At p = 1, the channel is guaranteed to corrupt each bit. So, the receiver can correct the error by inverting each bit in the received message. So, we do not need extra bits for error correction in this case as well.

Now, let me get back to the puzzle I mentioned while beginning this post.

The company decided to keep Bob because he was more useful to the company. He helped the company to take 95% correct decisions. They simply did the opposite of what Bob recommended and made huge profits in the last ten years. Alex on the other hand helped them take only 80% decisions correctly. So, he has to go. It's unfair but it's mathematically correct.

Re: Infosys, TCS, or Wipro?

Susam Pal — Fri, 28 Oct 2011 03:07:00 +0000

The 'Infosys, TCS, or Wipro?' post is doing the rounds again and some hatred as well as love is arriving on my email. That's fine. I've got pretty used to it in the last 5 months. If you try to say the truth, some people are going to call you arrogant and offensive. I would take hatred any day rather than needlessly sugarcoat things to please everybody.

So, I can understand when someone dislikes the way I have expressed the whole matter in that blog post. But I fail to understand the motivation behind any employee of these organizations trying to justify that working there is almost as good as working for a company where you can work with a team of very talented engineers. There have been plenty of arguments on the web. I'll discuss some of the points made in the arguments.

India needs IT services companies
Business problems vs. engineering problems
Business problems and engineering problems
Engineering in Adobe, Amazon, Google, etc.

Passionate people can do engineering anywhere
But everyone can not join Adobe, Amazon, Google, etc.
Infosys, TCS and Wipro have good engineers
Training
Meritocracy
Leaving Infosys, TCS, or Wipro
Solving algorithm problems vs. editing configuration

India needs IT services companies: The number one argument has been that India needs IT services companies because they make a lot of money and they are very successful. I don't understand why anyone would attack my post with this point when I have never said anything to the contrary. I agree with this point. However, in my opinion, students who have learnt their engineering well during the course, and now want to improve their engineering skills during work shouldn't work for one of these companies. They should join a start-up or a company known for hiring skilled engineers.
Business problems vs. engineering problems: The second most popular argument has been that a software company is not a place to showcase your engineering talent. They argue that it is a place to solve business problems, not engineering problems. I disagree with this very firmly. Business problems and engineering problems are not mutually exclusive. The reason why many employees of these companies feel that solving a business problem wouldn't involve an engineering problem is that they are not technically sound enough to even realize whether a particular problem needs to be solved with some concept they learnt in their engineering course. I've said this before and I'll say it again. Engineering problems are there in every software company. It needs the mind of an engineer to identify those problems and solve it correctly. Not all string parsing problems should be solved with a chain of string library functions stitched together. Some string processing and parsing work can be done more efficiently and reliably by coding a simple DFA. Not all data should be stored as records in an array. Some need to be stored as graphs. Knowing regular expressions can be dangerous if one doesn't know what kind of patterns they can not express.
Business problems & engineering problems: If you want to solve business problems and keep your customers happy, Infosys, TCS, or Wipro might be the right place for you. If you want to solve business problems, keep your customers happy and learn a great deal of engineering while doing all these, you need to find another workplace where you can work with a team of skilled engineers who you can give you constructive feedback or criticism on your work.
Engineering in Adobe, Amazon, Google, etc.: A popular myth that prevails among many is that there is no engineering to do in the Indian offices of Adobe, Amazon, Google, etc. I'll reiterate that there is engineering to do in every software company, even in Infosys, TCS and Wipro. It really depends on the people whether they want to do engineering sincerely or not. Some people would somehow develop the required software by stitching together libraries and give up or look for less-efficient workarounds when a particular task requires inventing a new engineering solution. There is another kind of people who are ready to invent new engineering solutions with all the engineering knowledge they have acquired during college and professional life. They do not hesitate to re-invent the wheel when the existing libraries do not meet the requirements of the particular problem at hand. Such engineers are more in number in start-ups like Gluster, Parallocity, SlideShare, etc. and companies like Adobe, Amazon, Google, etc. These companies also collaborate with universties to learn new techniques and concepts to solve business problems. These companies do not look for less-efficient workarounds when faced with a brick wall. They challenge themselves and do everything possible to solve a problem in the best possible way. These are the places where freshers can hope to learn a great deal of engineering from people around them.
Passionate people can do engineering anywhere: Another popular argument is that it doesn't matter where you work. One can do engineering anywhere, be it Google or Infosys. I agree with this. But then, given a place like Adobe, Amazon, or Google where you can get very good feedback on your work from talented colleagues around you and another place like Infosys, TCS, or Wipro where clueless people around you would call you great because you solved a problem and hail you as a genius, where do you think you are going to learn more and improve yourself faster?
But everyone can not join Adobe, Amazon, Google, etc.: Well, I never said that everyone should get into a reputed software product company. Not everyone wants to make a career in engineering. Some people have other goals in life. They just want a regular job. It sounds perfectly fine to me. My post was written for those who aspire to make a career in engineering. In my opinion, they should try to get into a reputed software product company or a start-up that is known to hire skilled engineers. If they aren't well prepared, the only thing one can do is to prepare well to fulfill their aspirations. Some people say that they should join Infosys, TCS and Wipro to earn a living while they are preparing and I think it's a great advice. I'll suggest considering contributing some new features or bug-fixes they would like to see in some open source project. Apache Incubator has a lot of budding projects. They can try solving problems at TopCoder, CodeChef, SPOJ, Project Euler, etc. All these things are good ways of preparing in my opinion.
Infosys, TCS and Wipro have good engineers: Many people have told me that there are good engineers in Infosys, TCS and Wipro as well. I agree. I never mentioned that 100% of the engineers in these companies don't do engineering. I mentioned that the majority of them don't do it. In fact, drawing from my personal experience, I quoted a figure that only 1 out of 200 are capable of engineering in these companies. Like most guess work, this figure could be wrong but I am pretty confident that the bigger picture I am trying to paint here isn't.
Training: Many claimed that I am wrong about the poor standard of training in Infosys, TCS, or Wipro. I must tell them that I have attended some of these training programmes. Among the many horror stories pertaining to training in these companies, I'll share only one with you to make my point. In the training assessments, the instructors set question papers containing problems with code that invokes undefined behaviour and ask you to predict its output. 'It invokes undefined behaviour' is not provided as an option you can select as the correct answer. Such training and knowledge is not only inaccurate but also very dangerous if you care about robustness and security of the software you create.
Meritocracy: A few people felt that I should have mentioned that these companies do not practice meritocracy. Anyone with sufficient number of years of experience can get a promotion in these companies. This is true. It didn't occur to me while writing that post. I was focussed on the popular myths about these companies that prevail among college students while writing the post.
Leaving Infosys, TCS, or Wipro: Some people commented that people like me just leave these companies and discourage others from joining them. They feel that we choose the easy way out. They would rather have us stay in these companies and improve them. Firstly, getting a job in a reputed company where you can get an opportunity to work on interesting engineering problems is not easy. You have to be passionate about your area of interest. You have to work and prepare yourself for it. Secondly, Infosys, TCS and Wipro were made by their founders with a particular vision of providing IT services. They have achieved what they wanted with great success. The improvements that you want to make in these companies may not be consistent with the vision of the founders.
Solving algorithm problems vs. editing configuration: This has to be the strangest argument I have come across. Someone mentioned that a person who solves algorithm problems earns no more than someone who only edits configuration files. After seeing both sides of the software industry, I find this false. Solving an algorithm problem is one thing. Solving an algorithm problem efficiently is an entirely different thing. I have seen people who can solve difficult algorithm problems efficiently earning at least twice that of an Infosys engineer. I have numerous examples for this: a friend who is solving problems to deliver the best news from the entire web to the users and another who writes algorithms for a cluster of Nvidia GPUs to do real-time analysis of network traffic to keep attackers out of the network. I have seen people solving algorithm problems in Topcoder, Codechef, etc. earning very well as software developers. One might argue that those toy problems tell you nothing about one's professional programming ability. But one has to agree that it at least tells you that someone who can solve difficult and contrived problems set by some of the most intelligent brains on the planet must be good at solving real software engineering problems which for the most part are less challenging algorithm-wise and more challenging design-wise. The toppers from these contests earn way more than someone who only edits configuration files.

To summarize, that post was meant for and only for people who have what it takes to work at a place where he can solve engineering problems. I have known many such people who were good engineers but weren't aware of the reality in companies like Infosys, TCS, or Wipro before joining them. That post was meant for these people. I devoted a couple of paragraphs in the previous post to make this clear but for some reason most people seem to have ignored them.

Solutions to 'Loopy C puzzle'

Susam Pal — Sat, 01 Oct 2011 22:46:00 +0000

In my blog post yesterday, I shared this puzzle:

Add or modify exactly one operator in the following code such that it prints exactly 6 dots.

int i;
for (i = 0; i < 6; i--)
    printf(".");

Let me first list all the possible solutions I know.

for (i = 0; i < 6; i++)
for (i = 0; i < 6; ++i)
for (i = 0; -i < 6; i--)
for (i = 0; i + 6; i--)
for (i = 0; i ^= 6; i--)

The last solution in the list is not quite obvious and needs a little analysis to understand why it works.

To generalize the problem, let us use n instead of 6. So, the loop becomes:

int i;
for (i = 0; i ^= n; i--)
    printf(".");

If we use XOR to represent bitwise exclusive OR, first i is set to i = n XOR i before we enter the loop. Since, the initial value of i is 0, this amounts to setting i = n before we enter the loop.

Thereafter, every iteration prints a dot and sets i = n XOR (i - 1). If we try to represent two such consecutive iterations as one operation, this composite operation prints two dots and sets i = n XOR {[n XOR (i - 1)] - 1} where i on the RHS is the value of i before the pair of iterations and i on the LHS is the value of i after the pair of iterations complete. … (A)

Before we proceed further, note that

k XOR 1 = k - 1 for an odd integer k. … (1)
k XOR 1 = k + 1 for an even integer k. … (2)
a XOR b is an odd integer if a and b have different parities. … (3)

I'm not presenting the proof of these results since they are very trivial. We'll use these results in the discussion below.

If n is odd, i is odd initially because i is set to n before we enter the loop. We'll show that i always remains odd and never changes for every pair of iterations.

i = n XOR {[n XOR (i - 1)] - 1}    … from (A)
  = n XOR {[n XOR (i - 1)] XOR 1}    … from (1) and (3)
  = (n XOR n) XOR [(i - 1) XOR 1]    … from associativity of XOR
  = 0 XOR [(i - 1) + 1]    … from (2) and (3)
  = i

Note that i begins as i = n. Since, i is set to n again after every two iterations, the loop never terminates.

If n is even, i is even initially because i is set to n before we enter the loop. We'll show that i always remains even and decrements by 2 for every pair of iterations.

i = n XOR {[n XOR (i - 1)] - 1}    … from (A)
  = n XOR {[n XOR (i - 1)] XOR 1}    … from (1) and (3)
  = (n XOR n) XOR [(i - 1) XOR 1]    … from associativity of XOR
  = 0 XOR [(i - 1) - 1]    … from (1) and (3)
  = i - 2

Since i begins as i = n and decrements by 2 for every two iterations, the loop terminates after n iterations thereby printing n dots.

Loopy C puzzle

Susam Pal — Sat, 01 Oct 2011 01:45:00 +0000

Let me share a very interesting C programming puzzle that I learnt from one of my colleagues.

Consider the following code-snippet written in the C programming language.

int i;
for (i = 0; i < 6; i--)
    printf(".");

This code invokes undefined behaviour. The value in variable i decrements to INT_MIN after |INT_MIN| + 1 iterations. In the next iteration, there is a negative overflow which is undefined for signed integers in C. On many implementations though, INT_MIN − 1 would result in INT_MAX which is not less than 6 and thus the loop would terminate. With such implementations, this code would print |INT_MIN| + 1 dots. With 32-bit integers, that would be 2147483649 dots. However, it could also be optimized into an endless loop by the compiler if it wants to exploit the fact that a negative overflow for signed integers is undefined. gcc in fact does optimize that to an endless loop if you compile it with the -O3 option.

Now, here is the puzzle.

Add or modify exactly one operator in the following code such that it prints exactly 6 dots.

int i;
for (i = 0; i < 6; i--)
    printf(".");

An obvious solution is:

int i;
for (i = 0; i < 6; i++)
    printf(".");

There are at least 3 other solutions. I found one of them very interesting. I'll discuss the interesting solution tomorrow. Till then, feel free to try and post your solutions below as comments.

Update: The discussion on the solution is now available at: Solutions to 'Loopy C Puzzle'.

From the Tower of Hanoi to counting bits

Susam Pal — Sun, 25 Sep 2011 12:33:00 +0000

A few weeks ago, I watched Rise of the Planet of the Apes in a movie theatre. The movie showed a genetically engineered chimpanzee trying to solve a puzzle involving 4 discs, initially stacked in decreasing size on one of three pegs. The chimpanzee was supposed to transer the entire stack to one of the other pegs, moving only one disc at a time and never moving a larger one onto a smaller one.

The problem was called the Lucas' problem in the movie. I couldn't help myself from remarking to my friend sitting next to me that the problem is actually known as the Tower of Hanoi and the minimum number of moves required to solve the problem is 2ⁿ − 1 if there are n discs involved. The math lectures were not very welcome by her in the middle of the movie.

During the intermission, she was curious to know why it was called the Lucas' problem instead of the Tower of Hanoi in the movie. I think it's probably because the puzzle was invented by the French mathematician Édouard Lucas in 1883. There is another version of this problem known as the Tower of Brahma that involves 64 discs made of pure gold and three diamond needles. According to a legend, a group of Brahmin priests are working at the problem and the world will end when the last move of the puzzle is completed. Now, even if they make one move every second, it'll take 18,446,744,073,709,551,615 seconds to complete the puzzle. That's about 584.54 billion years.

Since, the puzzle in the movie involved only 4 discs, it can be solved in 2⁴ − 1 = 15 moves as illustrated in an animated solution by André Karwath that I found in the Wikipedia article for the puzzle.

I'll not discuss the solution of this puzzle in this blog post. There are plenty of articles on the web including the Wikpedia article that describes why it takes a minimum of 2ⁿ − 1 moves to complete the puzzle. In this post, I'll talk about an interesting result I discovered while playing with this puzzle one April afternoon this year.

An interesting thing to note is that if we use T_n to denote the minimum number of moves required to solve the Tower of Hanoi problem involving n discs, then T_n when expressed in binary is the largest possible n-bit integer. For example, T₄ = 15₁₀ = 1111₂. After all, the largest n-bit integer is 2ⁿ − 1. Now, let me describe the result I came across while playing with it by asking a question.

This problem deals with arbitrary-precision integers. Some definitions:

A positive integer N is called an n-bit integer if and only if the minimum number of bits required to express the integer is n, or in other words, ⌊log₂(N)⌋ + 1 = n.
T_n represents the largest possible n-bit integer.

Some assumptions:

Let the time complexity of adding or subtracting two integers be O(1).
Let the time complexity of counting the number of 1-bits in an n-bit integer be O(n).

A positive integer n is given. What is the most efficient way, in terms of time complexity, to compute the number of 1-bits in T₁ + T₂ + … + T_n?

The naive approach would involve adding all the n integers and counting the number of 1-bits in the sum. The time required to add the n integers is O(n). The sum would require (n + 1) bits to be represented. Hence, it would take O(n) time to count the number of bits in the sum. Since the sum is (n + 1) bits long, the naive approach requires O(n) memory as well. If n is as large as 2⁶⁴, over 2 exbibytes of memory would be required to store the sum.

There is a more efficient solution.

T₁ + … + T_n
= 2^{(n + 1)} − 2 − n
= [2^{(n + 1)} − 1] − (n + 1)

Now, 2^{(n + 1)} − 1 has (n + 1) 1-bits. Subtracting (n + 1) from it is equivalent to removing one 1-bit in 2^(n + 1) − 1 for each 1-bit in (n + 1). So,

[number of 1-bits in T₁ + … + T_n] = [(n + 1)] − [number of 1-bits in (n + 1)].

So, the computation involves counting the number of 1-bits in n + 1 which takes O(log n) time and subtracting it from n + 1 which takes O(1) time. The problem is solved in O(log n) time. It occupies O(log n) memory. What required over 2 exbibytes of memory with the naive approach requires only a little over 8 bytes of memory with this approach.

Langford pairing

Susam Pal — Sat, 17 Sep 2011 12:45:00 +0000

I came across this problem more than 2 years ago when Pranave, a colleague at RSA, posted this in the internal mathematics forum.

Given a list of first n natural numbers with each natural number occurring exactly twice in the list, we need to arrange the list in a manner such that there are exactly k numbers between two k's for each k in the sequence.

For a small list, say, (1, 1, 2, 2, 3, 3, 4, 4), the answer can be obtained by trial and error: (4, 1, 3, 1, 2, 4, 3, 2).

But what if the list is very long? There is another important question: Is there a solution for every possible such list? The answer turns out to be: No. One can easily see that there is no valid arrangements for (1, 1) or (1, 1, 2, 2) that satisfy the condition specified in the problem statement.

So, we have two things to solve now.

For what values of n is the problem solvable?
If the problem is solvable for some value of n, how do we solve it?

In this blog post, I'll show how I solved it. I took some help from the computer by writing a Python program to see if I could notice any patterns. Here is the output.

n =  1 :          0 solutions (     0 s)
n =  2 :          0 solutions (     0 s)
n =  3 :          2 solutions (     0 s)
n =  4 :          2 solutions (     0 s)
n =  5 :          0 solutions (     0 s)
n =  6 :          0 solutions (     0 s)
n =  7 :         52 solutions (     0 s)
n =  8 :        300 solutions (     0 s)
n =  9 :          0 solutions (     1 s)
n = 10 :          0 solutions (     6 s)
n = 11 :      35584 solutions (    45 s)
n = 12 :     216288 solutions (   390 s)

From the output, I could form a conjecture:

There exists a permutation of (1, 1, 2, 2, …, n, n) such that for each k in the sequence (1 ≤ k ≤ n) there are k numbers between the two k's if and only if n ≡ 3 (mod 4) or n ≡ 0 (mod 4).

Let me show how I proved this conjecture.

Proof of the necessity of the condition n ≡ 3 (mod 4) or n ≡ 0 (mod 4)

Let (1, 1, 2, 2, …, n, n) be a sequence which can be rearranged such that there are k numbers between the two k's for each k in the sequence. Let us number the position of each number in this permutation as 1, 2, …, 2n.

Partition the numbers in this partition into two halves:

Partition 1: All numbers in odd numbered positions.
Partition 2: All numbers in even numbered positions.

The length of each partition is n.

Note that if k (1 ≤ k ≤ n) is even, one of the two k's is located on an odd numbered position and the other one on even numbered position.

If k is odd the two k's are both located on odd numbered positions or both located on even numbered positions. The two k's will never be split in two different partitions. It will be together in one partition.

From the above discussion it is obvious that the number of even numbers in each partition is equal. Let the number of even numbers in each partition be m. Let us assume there are p pairs of odd numbers in partition 1 and q pairs of odd numbers in partition 2. Thus, there are 2p odd numbers in partition 1 and 2q odd numbers in partition 2.

Since, the length of each partition is n, n = m + 2p = m + 2q. Hence, p = q. This implies that there must be p + q = 2p pairs of odd numbers in the two partitions, i.e. the number of positive odd numbers less than or equal to n is 2p.

In other words, the number of positive odd numbers less than or equal to n must be even. … (1)

We know that, for a positive integer n, the number of positive odd numbers less than or equal to n is ⌈n/2⌉. Let q be the quotient and r be the remainder obtained after dividing n by 4. We have four possible cases.

If n = 4q + 1, number of positive odd numbers less than or equal to n is, ⌈(4q + 1)/2⌉ = 2q + 1.
If n = 4q + 2, number of positive odd numbers less than or equal to n is, ⌈(4q + 2)/2⌉ = 2q + 1.
If n = 4q + 3, number of positive odd numbers less than or equal to n is, ⌈(4q + 3)/2⌉ = 2q + 2.
If n = 4q + 4, number of positive odd numbers less than or equal to n is, ⌈(4q + 4)/2⌉ = 2q + 2.

We can see that the number of odd numbers less than or equal to n is even if and only if n ≡ 3 (mod 4) or n ≡ 0 (mod 4). … (2)

From (1) and (2), the necessity of the condition n ≡ 3 (mod 4) or n ≡ 0 (mod 4) is proven.

Proof of the sufficiency of the condition n ≡ 3 (mod 4) or n ≡ 0 (mod 4):

If we can show that we can construct a permutation that satisfies the condition in the question for every positive integer n such that n ≡ 3 (mod 4) or n ≡ 0 (mod 4), then the proof would be complete. We have two cases to deal with:

n ≡ 3 (mod 4)
n ≡ 0 (mod 4)

When, n ≡ 3 (mod 4), let x = (n + 1) / 4. Partition the first n natural numbers in 4 sequences, p₁, p₂, p₃ and p₄ such that each sequence contains x − 1 numbers and 3 single numbers a, b and c according to the following rules. This is possible since, 4(x − 1) + 3 = 4x − 1 = n + 1 − 1 = n. The partitioning rules are as follows.

a = 2x − 1
b = 4x − 2
c = 4x − 1
p₁ = Odd numbers between 1 and a in ascending order. (1, …, 2x − 3).
p₂ = Even numbers between 1 and a in ascending order. (2, …, 2x − 2).
p₃ = Odd numbers between a and b in ascending order. (2x + 1, …, 4x − 3).
p₄ = Even numbers between a and b in ascending order. (2x, …, 4x − 4).

It can be verified that the above partitioning rules imply that the length of each partition p_i is x − 1 where 1 ≤ i ≤ 4. Also, all natural numbers less than or equal to n are present in the 4 partitions and 3 single numbers above.

Let us consider an array A of size 2n. The first index of array is 1. Now, a valid permutation can be formed with the following placement rules.

A[1] to A[x − 1] contains reversed p₄.
A[x] to A[2x − 2] contains reversed p₁.
A[2x − 1] contains b.
A[2x] to A[3x − 2] contains p₁.
A[3x − 1] contains c.
A[3x] to A[4x − 2] contains p₄.
A[4x − 1] contains a.
A[4x] to A[5x − 2] contains reversed p₃.
A[5x − 1] to A[6x − 3] contains reversed p₂.
A[6x − 2] contains b.
A[6x − 1] contains a.
A[6x] to A[7x − 2] contains p₂.
A[7x − 1] contains c.
A[7x] to A[8x − 2] contains p₃.

Note that 8x − 2 = 2n. So, the last rule can be rewritten as "A[7x] to A[2n] contains p₃".

When n ≡ 0 (mod 4), let x = n / 4. Partition the first natural numbers in 4 sequences, p₁, p₂, p₃ and p₄ such that each sequence contains x − 1 numbers and 4 single numbers a, b, c and d. The partition rules contain the 7 rules discussed above and one more rule. The additional rule is: d = 4x.

The placement are same for all cells in the array with one exception and two additional rules for the two new cells.

A[4x − 1] = d. (Exception. Modifies rule 7.)
A[8x − 1] = a.
A[8x] = d.

With these rules it can be shown that two k's have k elements in between. In other words, the difference in the array indices of the cells where two k's are present is k + 1.

a = 2x − 1. The two a's are located at A[4x − 1] and A[6x − 1]. The difference in array indices is 2x. Hence, two a's have 2x − 1 = a numbers in between. Similarly, this can be verified for b, c and d.

The two 1's are located at A[2x − 2] and A[2x]. The difference in array indices is 2. Hence, the two 1's have 1 number in between. From this it can be shown that for each k in p₁, there are k numbers in between. Take an arbitrary element m in p₁. From the construction rules, we see that, the two m's are located in A[2x − 2 − (m − 1)/2] and A[2x + (m − 1)/2]. The difference in the indices is: 2x + (m − 1)/2 − 2x + 2 + (m − 1)/2 = m + 1. Similarly, it can be shown that for any k in any parition p_i (1 ≤ i ≤ 4), there are k numbers between the two k's.

Here is an example.

n = 11
x = (11 + 1) / 4 = 3
a = 5
b = 10
c = 11
p1 = (1, 3)
p2 = (2, 4)
p3 = (7, 9)
p4 = (6, 8)

                      (a)
                      +------------+
                (c)   |            |
                +-----|------------|------+
         (b)    |     |            |      |
         +------|-----|----------+ |      |
         |      |     |          | |      |
8 6 3 1 10 1 3 11 6 8 5 9 7 4 2 10 5 2 4 11 7 9
=== ===    ===    ===   === ===      ===    ===
 |   |      |      |     |   |        |      |
 |   +------+ (p1) |     |   +--------+ (p2) |
 +-----------------+     +-------------------+
                  (p4)                      (p3

Notes

There is an entry for this problem in OEIS: http://oeis.org/A014552.
The internal symmetries in the permutation are not very obvious from the proof but the permutation simply requires us to place a, b, c, p₁, p₂ and p₃ in this order: (p₄' p₁' b p₁ c p₄ a p₃' p₂' b a p₂ c p₃) when n ≡ 3 (mod 4), where p_i' is reversed p_i (1 ≤ i ≤ 4).
For n = 3, we get x = 1. So, length of the partitions p₁, p₂, p₃ and p₄ is x − 1 = 0 each. So, rules that involve the partitions do not apply in case of n = 3.
In this proof, I have shown one set of rules to construct a valid permutation for a given n such that n ≡ 3 (mod 4) or n ≡ 0 (mod 4). But actually, I found 2 such sets of rules. The variables a, b, c and d remain same in the other rule. Only the rules for p₁, p₂, p₃, p₄ and placement rules differ.
The above two points imply that, except for n = 3, using construction rules, we can construct at least two different permutations for a given value of n such that n ≡ 3 (mod 4) or n ≡ 0 (mod 4).
It seemed like for values of n > 20, there might be over a quadrillion possible solutions. It wasn't feasible to verify this on my laptop with the program I wrote. When I discussed this with a person who was interested in this problem, he asked, "What? Don't you have a quad(rillion)-core processor?"
I worked through a Saturday night till 3:30 AM of the following Sunday morning and I could prove only the necessity of the condition n ≡ 3 (mod 4) or n ≡ 0 (mod 4). When a friend asked me about the progress, I could manage to say this, "Half of it. Need to prove a 'necessary and sufficient' condition. Proved the necessary part only but this much is sufficient for me today. The sufficient part is necessary for the proof to be complete but i think, now it has become necessary to do the sufficient part tomorrow as it is too late already."
The above point reminds me of a famous quote by George Pólya, "Mathematics consists in proving the most obvious thing in the least obvious way".
The above point reminds me of http://humor.beecy.net/misc/principia/.

The Orkut exploit

Susam Pal — Sat, 25 Jun 2011 11:03:00 +0000

I first came to know about Sunny Vaghela about one and a half years ago when I got an email from Sandip Dev of Sun Microsystems (now acquired by Oracle).

Hi Susam,

I just read the Orkut exploit on your site http://susam.in/security/advisory-2007-06-22.txt. It seems this guy, Sunny Vaghela, claims this exploit to be his own (http://sunnyvaghela.com/orkut-hacking.html). He also claims that people from Google visited him (http://www.techgoss.com/Story/227S12-Security-expert-starts-NGO-to-help-cyber-victims.aspx). Whats your take on this?

Regards,
Sandip Dev

Hi Sandeep,

In our advisory, we have documented that the session management vulnerability associated with orkut_session cookie was first reported by Net-Square Solutions Private Limited. We published an advisory in 2007 because even though the Net-Square advisory mentioned that the vulnerability is fixed, we found that it wasn't. So, we published the results of our investigation and experiments.

The link that you have sent me doesn't mention that he claims the exploit to be his own. I have not seen the Headline Today video on his work. However, if he does claim that it is his own exploit, either he has discovered the vulnerability independently and is unaware of related work that has been done before or he is using information from the advisories published by us and Net-Square, but claiming it to be his own.

Regards,
Susam Pal

Hi Susam,

He has put it under "Research" on his site and also in the interview he says he "found" this exploit. Well I have reading up about him recently and this came up. So I thought I would alert you. Thanks for the response.

Regards,
Sandip

Hi Sandip,

Thanks for the alert. I was assuming that he was talking about his work in good faith. There is a possibility, no matter however small, that he has discovered the vulnerability independently and he is not aware that we have already investigated this and published advisories on it.

However, I understand that there is also a possibility that he is violating our copyright on our work and claiming that the work is a result of his own research. I don't mind it since most websites on the web properly attribute the advisory and the investigation to me and Vipul.

Thanks for the alert however. It was interesting to see an old work in the news recently.

Regards,
Susam Pal

A couple of days ago, I found him again at attrition.org, a website that used to be the largest mirror of defaced websites.

Sunny Vaghela has found a place in attrition.org's charlatans watch list: Sunny Vaghela: Claims of Orkut Vulnerability Research. He is the third Indian to get into this list after Ankit Fadia and Sahil Khan.

URLs in C

Susam Pal — Fri, 03 Jun 2011 10:13:00 +0000

Here is a C puzzle I like to ask my friends and colleagues. It is one of those silly puzzles that may bring a smile on your face if you aren't able to figure it out immediately.

#include <stdio.h>

int main()
{
    http://blog.susam.in/2011/06/urls-in-c.html
    printf("URLs in C\n");
    return 0;
}

This code compiles and runs successfully even though the C99 standard doesn't mention anywhere that URLs are valid syntactic elements in C. How does this code work then?

Infosys, TCS, or Wipro?

Susam Pal — Sun, 15 May 2011 08:45:00 +0000

Sometimes computer science, IT or electronic and communication engineering students get placed in two or three major Indian IT companies and they find it hard to decide which one to join. "Infosys, TCS, or Wipro?" is one of the most common questions I have faced from such students. The answer is much simpler than they think it is.

"None."

This blog post is not about how these companies feed the stomachs of lakhs of people. This blog post is not about undermining the efforts of these companies. They are probably good at keeping their customers happy. This blog is not about offending the employees of these organizations. That'll be an unintentional side-effect.

This blog post is about a choice that freshers usually have to make and the information they should have before they make the choice. This blog post is about urging the freshers who want to make a career in engineering to not make a mistake that I did because I did not have the necessary information at the right time; a mistake that I could correct two years later after I realized it. This blog post is about some very unpleasant facts about these major Indian IT companies that you wouldn't know unless you have been a part of it.

ALERT: If you are not interested in making a career in engineering, lack the confidence to do so, or you are very content with working for one of these three companies for reasons that are valid to you, this post is not for you. It won't make any sense to you. Do not proceed.

Now, let me start slaying the different myths that exist about these organizations one by one and I am not going to mince words while doing this. You have been warned.

Training: People think that these organizations are good for freshers because they get a lot of training which they wouldn't get in other organizations. I must remind such people that attending training programmes is not equivalent to learning. Indeed these organizations provide a lot of training to freshers but only about 1% of the trainees actually absorb the knowledge. The 1% that do absorb the training do not stick to the organization for a long time because sooner or later they realize that they want to do some real engineering. The figure '1%' isn't merely a guess. This is my observation across various trainee-batches that have been trained in one of these organizations. Think about it. Can you learn a new programming language in just 3 days? If your answer is "no", you shouldn't join one of these organizations. If your answer is "yes", you shouldn't join one of these organizations.
Engineering: One can find engineering problems in these organizations but no trace of engineering. For those of you who work in one of these organizations and are offended by this statement, please go and open your engineering textbooks again. Try to remind yourself what you studied and what you learnt. Consider what you do now.
Engineers: The number of engineers in these organizations are very very few; perhaps only 1 in every 200 is an engineer. This is a guess, albeit not a wild one. This is why there is no engineering in these companies despite the presence of engineering problems. "But isn't the minimum qualification to get a job in one of these organizations bachelor's of engineering?", you might ask. It is. Yes, all of them have a degree in engineering or computers of some sort but only about 1 out of 200 is an engineer. The rest 199 do not understand why a bitcount of 1's complement of bitwise XOR of two variables would give you the number of similar bits in corresponding positions in both variables, why one can not create a POSIX compliant regular expression to match only strings with balanced parentheses, or how to find the shortest chain of connections between two friends in a social network. Note that I have used 'or' as the conjunction and not 'and'. They may be good software users or good "software-tailors" who can create software by stitching together many library functions but they aren't engineers.
Culture: One of the worst cultures you can find in the whole of software industry. Very few are busy trying to learn a few things mentioned in the previous paragraph. Some employees are busy figuring out ways to impress their female colleagues using the resources provided by the organization rather than learning and solving problems in better ways. Others are busy cribbing. Here is a shocking piece of information for those who have never worked for one of these organizations. One can also manage to find mud-slinging in company forums once in a while. Professionalism is at its worst here. But they convince themselves that they are professional because they speak English fluently and know how to wear a tie. Employees feel their salaries are pathetic. I feel they are overpaid. How much should a good software user earn?
Onsite: Contrary to the popular belief, the number of trips to foreign lands isn't a measure of one's technical prowess. It is mostly (but not always) a measure of how dispassionate one is about engineering and his profession, and how greedy one can be for wealth. Some of the best engineers I have met in these organizations were never eager to go onsite, never went, joined an organization where they could put their knowledge and skills to better use and then flew to a foreign land because their knowledge, skills and understanding of technology were needed there.

So, my answer to the question "Infosys, TCS, or Wipro?" is "None." That's not very helpful. Here is a more helpful one. One can consider applying for a job in an organization where he or she can get an opportunity to solve some engineering problems. One cannot learn engineering and programming merely by attending trainings. One has to learn it by doing, solving problems, observing what experienced engineers do, experimenting, screwing up a few times and reworking, talking to good engineers, etc. One can try looking for an organization where the leaders of projects are very good engineers. Start-ups are more likely to have them. Some matured ones are Gluster, Parallocity, SlideShare, etc. New start-ups come up every year. Software companies which develop famous and successful products are more likely to have them. Some good examples are Adobe, Amazon, Google, Phoenix, RSA, etc. So, how does one figure whether a certain organization is an organization of engineers or an organization of good software users?

The clue is: Interview.

Remember the questions they ask in the interview. Think about them later. Try discussing the questions with your friends who are known for solving tough engineering problems. An interview is not only an opportunity for an organization to evaluate an applicant, it is also an opportunity for the applicant to evaluate an organization.

Update: October 28, 2011: This post got way more attention than I wanted. It was discussed and debated at various places on the web. As a result, here is a follow-up post: Re: Infosys, TCS, or Wipro?

A surprise test

Susam Pal — Sun, 08 May 2011 08:46:00 +0000

I was studying in the 1st standard. Our science teacher gave us a surprise test. I tried to answer all questions correctly. After the corrected notebooks were returned, I found that the teacher had incorrectly marked one of my answers as incorrect. I was sure that I was correct. So, I showed it to the girl sitting next to me and declared innocently, "This answer is correct. But she doesn't know. She is stupid."

When she went to collect her notebook, she informed the teacher about what I had just said. The teacher was offended and asked me to stand outside the class. Our principal was passing through the corridor and she was surprised to see me standing outside. She asked what I did and I said that I called our teacher stupid. She asked me to apologize.

I didn't know how to do that. I started recollecting from Hindi movies. The villian would fall at someone's feet and cry, "Mujhe maaf kar do. Please, mujhe maaf kar do."^[*] I thought, "I can't do this. I can't fall at her feet. That would be very embarrassing. I said that she was stupid and I was right. Why should I fall at her feet?" I refused to apologize, inspite of repeated warnings and requests. I was simply not ready to fall at her feet and do the drama.

The matter escalated and I was asked to leave that place. I was taken to the reception area. I was not allowed to attend any classes. I sat there crying the whole day. Visitors came and enquired why I was crying. I explained. Before the final bell rang, a complaint was registered in my diary and my parents were asked to meet the principal next day.

The next day, my parents met the principal. Thankfully, it went well. She explained how she was impressed with my innocence and honesty. It seemed as if she had called my parents only to praise me. I grew up to be wiser and humbler. Now, I understand that falling at someone's feet is not the only way to apologize.

[*] Translated to English: "Forgive me. Please, forgive me."

From out shuffles to multiplicative order

Susam Pal — Wed, 23 Mar 2011 04:05:00 +0000

A colleague asked this problem.

A perfect riffle shuffle or bridge shuffle is when we split a deck of cards into two halves (one in each hand), and then alternately drop one card from each half till all have fallen. For the sake of this problem, let us assume that the top card will always be the top card and the bottom card will always be the bottom card after shuffling. However the rest of the cards will be deranged.

How many such riffle shuffles do we need to perform on a deck of 52 cards, in order to obtain the exact same starting order?

Such a style of shuffling is also known as out shuffle.

Let us assume that there are 2n cards where n is a positive integer. Let us number the positions of the cards as 0, 1, … 2n − 1 where position 0 is the top of the deck and position 2n − 1 is the bottom of the deck. Here is an example with 10 cards called c₀, c₁, … c₉ with positions indicated in the first column.

0. c₀                     c₀
1. c₁                     c₅
2. c₂                     c₁
3. c₃                     c₆
4. c₄ ———> Shuffling ———> c₂
5. c₅                     c₇
6. c₆                     c₃
7. c₇                     c₈
8. c₈                     c₄
9. c₉                     c₉

Let us consider a card at position k where 0 ≤ k < 2n. It is easy to see from the description of the problem that a card at position k moves to position 2k if the card belongs to the top half of the deck, otherwise it moves to 2(k − n) + 1.

2(k − n) + 1 ≡ 2k − (2n − 1) ≡ 2k (mod 2n − 1)

So, we can say that a card at position k moves to position k' ≡ 2k mod (2n − 1) after an out shuffle where 0 ≤ k' < 2n.

So, after m shuffles a card at position k moves to position k` ≡ 2^m · k (mod 2n − 1) where 0 ≤ k` < 2n. So, we are looking for the smallest positive integer m such that for all integers k, where 0 ≤ k < 2n,

2^m · k ≡ k (mod 2n − 1)

Removing k from both sides we get

2^m ≡ 1 (mod ⁽²ⁿ⁻¹⁾⁄_{gcd(k, 2n−1)})

For simplicity, let us represent ⁽²ⁿ⁻¹⁾⁄_{gcd(k, 2n−1)}) as F_nk. So, a card at position k returns to the same position after m out shuffles where m is the smallest positive integer that satisfies the congruence relation

2^m ≡ 1 (mod F_nk)

Since 2n − 1 is odd, F_nk must be odd. So, gcd(2, F_nk) = 1. The smallest positive integer m that satisfies the congruence relation above is known as the multiplicative order of 2 modulo F_nk and is denoted as ord_{F_nk}(2).

If n = 1, F_nk = 1 and 2^m ≡ 1 (mod F_nk) is true for all positive integers m. So, with two cards, an out shuffle doesn't change the positions of the cards.

If n > 2, let us consider a k which is coprime to 2n − 1 and 1 < k < 2n − 1. There exists at least one such k because φ(x) ≥ 2 for x > 2 where φ(x) is the Euler's totient of a positive integer x which is defined as the number of positive integers less than or equal to x that are coprime to x. Now, gcd(k, 2n − 1) = 1. So, now the congruence relation

2^m ≡ 1 (mod ⁽²ⁿ⁻¹⁾⁄_{gcd(k, 2n−1)})

reduces to

2^m ≡ 1 (mod 2n − 1)

So, far we understand that after ord_2n−1(2) out shuffles, any card at a position number coprime to 2n − 1 would be back to its original position. What about cards at other positions?

For a card at position k such that k is not coprime to 2n − 1, gcd(k, 2n − 1) ≠ 1. In this case the number of out shuffles required to bring the card at its original position is ord_{F_nk}2.

2^{ord_2n−1(2)} ≡ 1 (mod 2n − 1) ⇒ 2^{ord_2n−1(2)} ≡ 1 (mod F_nk) … (since F_nk | 2n − 1)

As a consequence of Lagrange's theorem, ord_{F_nk}(2) | ord_2n−1(2).

In other words, ord_2n−1(2) = c · ord_{F_nk}(2) for some positive integer c.

So, performing ord_2n−1(2) out shuffles is same as repeating ord_{F_nk}(2) out shuffles c times. Every ord_{F_nk}(2) shuffles brings back the card at position k to the same position. So, repeating it c times would leave it at the same position as well.

Hence, we conclude that ord_2n−1(2) out shuffles would restore a deck of 2n cards to its original configuration, where n is a positive integer.

For a deck of 52 cards, n = 26. So, ord₅₁(2) out shuffles would restore the deck to its original configuration.

Let us compute ord₅₁(2).

From Carmichael's theorem, 2^λ(51) ≡ 1 (mod 51), where λ(n) is the smallest positive integer m such that a^m ≡ 1 (mod n) for every positive integer a coprime to and smaller than n.

λ(51) = lcm(λ(3), λ(17)) = lcm(2, 16) = 16.

Again as a consequence of Lagrange's theorem, ord₅₁(2) | λ(51). In other words, ord₅₁(2) | 16.

Let us check all the factors of 16 and see which one is the multiplicative order of 2 modulo 51.

2² ≡ 4 (mod 51) 2⁴ ≡ 16 (mod 51) 2⁸ ≡ 256 ≡ 1 (mod 51).

∴ ord₅₁(2) = 8.

8 is the answer.

Listening to superimposed waves

Susam Pal — Thu, 03 Feb 2011 01:32:00 +0000

Let me share a little experiment I did last night. Listen to the following audio first. This plays a sine wave of 500 Hz for 2 seconds followed by another sine wave of 500.1 Hz for 2 more seconds. You can hear a tick after each second. The 500.1 Hz sine wave starts at the second tick.

Download 500Hz-500point1Hz-sequenced.mp3

Could you notice any difference in the pitch of the two tones? The difference in the frequencies is so small that you wouldn't be able to notice it by hearing.

Now, let us see what happens when we superimpose both the waves and listen to it.

Download 500Hz-500point1Hz.mp3

You would notice that the loudness decreases rapidly at about 5 seconds and then returns to full volume by 10 seconds, decreases rapidly again at 10 seconds and returns to full volume by 15 seconds and so on. In other words, the loudness decreases every 10 seconds.

Let us see why this happens from the graph of the waves. The first wave can be represented with the function f(t) = 0.4 sin (2π · 500 · t) and the second one with g(t) = 0.4 sin (2π · 500.1 · t)

At t = 0 seconds, both the waves look very similar. The crests and troughs of both the waves appear almost simultaneously. On superposition, the amplitude almost doubles. The graph of the superimposed waves is shown below. Note that the amplitude of each wave in the figure above is 0.4 while that of superimposed waves is almost 0.8 as can be seen below. In fact, it is exactly 0.8 at t = 0 seconds and then gradually decreases in the region 0 < t < 5.

The time period of the second wave is slightly shorter than the first one as the frequency of the second wave is slightly greater than the first one. So, the two waves are not identical. In fact, the second wave looks like a very slightly compressed form of the first wave. At about t = 5 seconds, the difference is obvious.

The crests and troughs of both the waves do not appear simultaneously at around t = 5 seconds. In fact, the crest of one wave and the trough of the other wave appear simultaneously. This cancels out each other on superposition and thus the resultant wave has almost no amplitude at this time.

The amplitude is exactly 0 at t = 5 seconds and it increases gradually till t = 10 seconds. At t = 10 seconds, the amplitude becomes 0.8 again and then starts decreasing till t = 15 seconds when it becomes 0 again. This cycle continues. This can be seen in the graph of the superimposed waves given below.

Let us understand this mathematically. Let us represent both the sine waves with the functions: y₁ = A sin 2πft and y₂ = A sin 2π(f + Δf)t, where A is the amplitude of the waves, and f and f + Δf are the frequency of the two waves.

So, the superimposed waves can be represented as

y₁ + y₂

= A sin 2πft + A sin 2π(f + Δf)t

= (2A cos 2π · ^Δf⁄₂ · t) sin 2π(f + ^Δf⁄₂)t

To understand this function intuitively, imagine it as a sine wave with a frequency of f + ^Δf⁄₂ and an amplitude of 2A cos 2π · ^Δf⁄₂ · t. In our case, f + ^Δf⁄₂ = 500.5 Hz. So, the superimposed waves look like a sine wave with a frequency of 500.5 Hz but with its amplitude varying with time at a frequency of ^Δf⁄₂. In other words, the amplitude oscillates between 0 and 2A every ¹⁄_Δf seconds. Since Δf = 0.1 Hz and A = 0.4 in our case, we see that the amplitude of the 500.5 Hz sine wave oscillates between 0 and 0.8 every 10 seconds.

Flowers

Susam Pal — Sat, 22 Jan 2011 23:48:00 +0000

Flowers is my third attempt at composing music. I composed, played and recorded it last year but I scribbled it down and prepared the sheet music today. Hence, this blog post today.

The links to the audio files, sheet music, etc. are provided below. The files reside in my website. In case, my website is down, the YouTube link provided below should still work.

This piece consists of 161 measures. It is approximately 3 minutes 8 seconds long.

MP3 | OGG | YouTube | Score | LilyPond

This piece of music embodies love, peace and joy. After I composed the first few notes and played it, someone told me that the notes bring an image of flowers in the mind. Most of the music emerged naturally from my mind. Some of the bass notes did not come out naturally and I decided them, quite artificially, to fill the music with a pleasant and peaceful mood. It took me a couple of days to compose this. I played and recorded this after a day of practice.

A hidden form and Fermat's Last Theorem

Susam Pal — Wed, 12 Jan 2011 10:12:00 +0000

Here is a problem I made one night for my friends who love to solve mathematical puzzles.

Find all integer solutions for the equation: y² + 3 = ^x³⁄₁₈.

You might want to stop here and think for a while if you want to solve this yourself. There are spoilers ahead.

In this problem, I have hidden a Diophantine equation of the form aⁿ + bⁿ = cⁿ. The first clue to this hidden form might be the equation with its terms rearranged.

x³ = 18y² + 54

The right hand side is 2(9y² + 3³). This is of the form 2(3a²b + b³) which is equal to (a + b)³ − (a − b)³. Now, the hidden form must be clear. So, let me write down the solution to this problem neatly.

y² + 3 = ^x³⁄₁₈
⇒ x³ = 18y² + 54
⇒ x³ = (y + 3)³ − (y − 3)³
⇒ x³ + (y − 3)³ = (y + 3)³

From Fermat's last theorem, we know that an equation of the form, aⁿ + bⁿ = cⁿ has got a trivial solution a = b = 0 and no other solutions for positive integers a, b and c when n > 2. Now, let us examine x³ + (y − 3)³ = (y + 3)³ with the help of Fermat's Last Theorem. A trivial solution in this case is ruled out because there is no value of y for which y − 3 = y + 3 = 0.

However, if we consider y − 3 = 0, or y = 3, we get an equation that is no longer of the form required by Fermat's Last Theorem.

x³ = 6³
⇒ x = 6

If we consider y + 3 = 0, or y = −3, again we get

x³ + (−6)³ = 0
⇒ x = 6.

Hence, the integral solutions to the equation are:

x = 6
y = ±3

Squaring numbers with 5 at ends

Susam Pal — Tue, 21 Dec 2010 05:03:00 +0000

In this post, I'll discuss some simple tricks I use to square numbers that begin or end with the digit 5. Let me illustrate each trick with two examples for 2-digit numbers. Later, in this post, I'll generalize the trick for n-digit numbers where n ≥ 2 after explaining why the tricks work using algebra.

Squaring a 2-digit number that ends with 5

I learnt this from a book when I was in 5th standard. For a 2-digit number that ends with 5, let us assume that the first digit is A. So, the number can be written as A5. The square is: A × (A + 1) followed by 25, i.e. the first few digits of the square is given by A × (A + 1) and the last two digits are 25. Let us try some examples.

25² = 625. (2 × 3 = 6.) 85² = 7225. (8 × 9 = 72.)

Squaring a 2-digit number that begins with 5

After learning that trick from the book, I wondered if I could make more tricks for myself. This is the first one I could come up with. If the first digit of a 2-digit number is 5 and the second digit is A, i.e. if the number is of the form 5A, the square is given by the sum of 25 and A followed by square of A. In other words, the first two digits of the square are obtained from 25 + A and the last two digits are obtained from A². Let us try some examples.

52² = 2704. (25 + 2 = 27 and 2² = 4.) 57² = 3249. (25 + 7 = 32 and 7² = 49.)

Squaring an n-digit number that ends with 5

Let us represent all digits except the last one as A. So, the number is of the form A5 where A represents one or more digits. e.g. if the number is 115, A = 11.

So, we can say that the number of the form A5 can be algebraically expressed as 10A + 5. Now, (10A + 5)² = 100A² + 100A + 25 = 100A(A + 1) + 25. This amounts to writing A(A + 1) followed by 25.

Let us try some examples:

115² = 13225. (11 × 12 = 132.) 9995² = 99900025. (999 × 1000 = 999000.)

Squaring an n-digit number that begins with 5.

Let us represent all digits except the first one as A. So the number is of the form 5A where A represents one or more digits. e.g. if the number is 512, A = 12.

So, we can say that the number of the form 5A can be algebraically expressed as 5 × 10ⁿ + A where n is the number of digits in A, i.e. the number of digits after the first digit which is 5. Now, (5 × 10ⁿ + A)² = 25 × 10²ⁿ + 10^{n + 1}A + A². This amounts to writing 25 as the first two digits followed by A² as the last 2n digits and then adding A to it by placing it just below the second digit which is 5. Some examples follow.

502²

= 250004   (2² = 4.)
  +02      (02 placed under 5.)
---------
  252004
---------

512²

= 250144   (12² = 144.)
  +12      (12 placed under 5.)
---------
  262144
---------

Using both tricks together

5195²

= 25038025 (195² =
38025; 19 × 20 = 380.)
  +195     (195 placed under 5.)
-----------
  26988025 
-----------

Note that in the problem above, we use the second trick to square 5195 because it begins with the digit 5. However, while doing so, we need to figure the square of 195 and we use the first trick to do this.

π PM

Susam Pal — Mon, 20 Dec 2010 09:38:00 +0000

For so long, I have been wishing "Happy Pi PM" to my friends and colleagues at 3:14 PM. However, this doesn't seem to be appropriate since 3:14 PM is not really 3.14 PM. In fact, 3:14 PM is 3¹⁴⁄₆₀ PM which when expressed in decimal representation turns out to be 3.23333 PM, accurate up to 5 decimal places.

The value of π accurate up to 5 decimal places is 3.14159. Now, .14159 hour = 509.724 seconds ≈ 8 minutes and 30 seconds, or 8½ minutes.

So, π PM turns out be 3:08:30 PM or 8½ minutes past 3 PM.

Belated birthday

Susam Pal — Wed, 01 Dec 2010 05:09:00 +0000

This is a poem I wrote for a friend when I was in school. The last two lines are inspired from an Archies card.

BELATED BIRTHDAY

All days come but once in annum,
Amongst them all very special are few,
Amongst the few you love the most is one,
The day when the world got you.

You celebrate the day you're born
And want your chums to be near.
I regret that I left you lorn,
Hope you pardon me, O dear!

Shamelessly I wish you, 'A belated very happy birthday'.
Though I know, now it is very late;
But I swear, I didn't forget your birthday
I just forgot the date.

Clumsy pointers

Susam Pal — Mon, 29 Nov 2010 14:27:00 +0000

Here is a silly puzzle I solved exactly one month ago.

Without using typedef, declare a pointer to a function which has an array of 10 pointers to functions which have int * argument and return type void as argument, and returns a pointer to a function which has int * argument and return type void.

If the above problem statement is difficult to understand, here is the same problem expressed in terms of typedef.

Without using typedef, declare a pointer that is equivalent to the following declaration of x.

typedef void (*func_t)(int *);
func_t (*x)(func_t [10]);

I'll describe how I solve such problems. I start from the right end of the problem and work my way to the left most end defining each part one by one.

Let me start.

void x(int *)
A function which has int * argument and return type void.

void (*x)(int *)
Pointer to a function which has int * argument and return type void.

void (*x())(int *)
A function that returns a pointer to a function which has int * argument and return type void.

void (*x(void (*)(int *)))(int *)
A function which has a pointer to a function that has int * argument and return type void as argument, and returns a pointer to a function which has int * argument and return type void.

void (*x(void (*[10])(int *)))(int *)
A function which has an array of 10 pointers to functions that has int * argument and return type void as argument, and returns a pointer to a function which has int * argument and return type void.

void (*(*x)(void (*[10])(int *)))(int *)
A pointer to a function which has an array of 10 pointers to functions that has int * argument and return type void as argument, and returns a pointer to a function which has int * argument and return type void.

I verified the declaration with a short code.

#include <stdio.h>

/* A function which has int * argument and return type void. */
void g(int *a)
{
    printf("g(): a = %d\n", *a);
}

/* A function which has an array of 10 pointers to functions that has
 * int * argument and return type void as argument, and returns a
 * pointer to a function which has int * argument and return type void.
 */
void (*f(void (*a[10])(int *)))(int *)
{
    int i;
    for (i = 0; i < 10; i++)
        a[i](&i);
    return g;
}

int main()
{
    /* An array of 10 pointers to functions that has int * argument and
     * return type void. */
    void (*a[10])(int *) = {g, g, g, g, g, g, g, g, g, g};

    /* A pointer to the function which has an array of 10 pointers to
     * functions that has int * argument and return type void as
     * argument, and returns a pointer to a function which has int *
     * argument and return type void. */
    void (*(*x)(void (*[10])(int *)))(int *) = f;

    /* A pointer to a function that has int * argument and return type
     * void. */
    void (*y)(int *a) = x(a);

    int i = 10;
    y(&i);
    return 0;
}

Section 5.12 (Complicated Declarations) of the second edition of The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie has some good examples of complicated declarations of pointers although they are less clumsy than the one in this blog post. Let me mention a couple of interesting ones from that section.

char (*(*x())[])()
x: function returning pointer to array[] of pointer to function returning char.

char (*(*x[3])())[5]
x: array[3] of pointer to function returning pointer to array[5] of char.

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇔ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	F
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	F
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇔ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	F
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	F
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇔ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	F
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	F
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

A	B	C	A ⇒ B	B ⇒ C	A ⇒ C	(A ⇒ B) ∧ (B ⇒ C)	((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	F	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	T	F	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T