Probabilistic PIE

Commenters Sylvain B., xpil, and Christian Luca all gave correct answers to the challenge from my previous post. If the probability that someone likes X is p, then the probability they don’t like X is (1-p). Therefore the probability that someone doesn’t like anchovies and doesn’t like books is (1-a)(1-b). (If liking anchovies and books are independent, then not liking those things is also independent.) Likewise, the probability that someone doesn’t like all three is (1-a)(1-b)(1-c).

The reason I asked the question, however, is to see the pattern that emerges if we multiply out these expressions, which commenter Buddha Buck explained.

1 - a - b + ab

1 - a - b - c + ab + ac + bc - abc

1 - a - b - c - d + ab + ac + ad + bc + bd + cd - abc - abd - acd - bcd + abcd

The first line is the result of multiplying out (1-a)(1-b); the second is (1-a)(1-b)(1-c); and the last is of course (1-a)(1-b)(1-c)(1-d). After expanding everything as much as possible, we get one term for the product of every possible combination of the probabilities, with a positive sign for an even number of probabilities, and negative for an odd number.

Do you see why this happens? Each term in the result arises from choosing one of the two possible terms from each parenthesized expression. Taking (1-a)(1-b)(1-c) as a specific example, we get bc if we choose 1 from (1-a), and -b from (1-b), and -c from (1-c), yielding 1 \cdot (-b) \cdot (-c) = bc.

And now for a set of follow-up questions. Suppose that P is the set of all people in our population, A is the set of people who like anchovies, and B is the set of people who like books. Suppose we also know how many people like both anchovies and books, that is, we know |A \cap B|. (The notation |S| denotes the size of a set S, and \cap denotes the intersection of two sets, that is, the set of elements the two sets have in common.)

  • How many people like neither anchovies nor books?

  • Now suppose C is the set of people who like carpets. Suppose we also know the sizes of the sets A \cap C, B \cap C, and A \cap B \cap C. How many people like none of the things?

  • And so on?

Posted in pattern, probability, solutions | Tagged , | 7 Comments

A probabilty puzzle

Suppose that we have surveyed a certain population of people, and have determined the following probabilities:

  • The probability that a person likes anchovies is a.
  • The probability that a person likes to read books is b.
  • The probability that a person likes carpets is c.

Suppose we also know that these probabilities are all independent, that is, they do not influence each other at all. Wether a person likes anchovies has nothing to do with whether they like to read or whether they like carpets, and so on. When probabilities are independent, it makes sense to multiply them: for example, the probability that someone likes both anchovies and carpets is the product ac.

  • What is the probability that a randomly chosen person likes neither anchovies nor books?

  • What is the probability that a randomly chosen person likes none of these three things?

  • Can you generalize? What if we had four, five, or more independent probabilities for things people might like; what would be the probability that a random person didn’t like any of the things?

Posted in challenges, probability | Tagged , | 9 Comments

Computing the Euler totient function, part 4: totient of prime powers

I’ve been on a bit of a hiatus as I’ve been travelling with my family for the past month. So here’s a recap.

Our story so far

  • Recall that the Euler totient function, \varphi(n), counts how many numbers from 1 to n are relatively prime to (that is, share no prime factors in common with) n.

  • My current goal is to show that if we know the prime factorization of n, we can calculate \varphi(n) much more quickly than just by counting.

  • This rests on the fact that \varphi is multiplicative, that is, \varphi(mn) = \varphi(m)\varphi(n) whenever m and n are relatively prime. In particular this means we can break down \varphi based on a number’s prime factorization: \varphi(p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}) = \varphi(p_1^{k_1})  \varphi(p_2^{k_2}) \dots \varphi(p_n^{k_n}).

  • First I displayed some visualizations that give us some intuition for why this is true. Then in another post I presented a formal proof based on that intuition.

  • So the only thing left is to figure out how to compute \varphi(p^k). That’s what we’ll do today! Then we’ll see the whole method of computing \varphi in action.

Totient of prime powers

As a warmup, what is \varphi(p) when p is prime? Since p is prime, by definition it has no prime factors other than itself, and no smaller number can share a prime factor with it. Hence every number from 1 to p-1 is relatively prime to p, and \varphi(p) = p-1.

How about \varphi(p^2)? Here’s an example with p=5. The blue squares are the numbers relatively prime to 5^2 = 25—the ones we want to count—and the white squares are the ones which share a prime factor with 25.

In general, the only numbers that share a prime factor with p^2 are numbers that are divisible by p. In the example above, there are five white squares; in general, counting p^2 itself, there are exactly p of these numbers: p, 2p, 3p, 4p, \dots, (p-1)p, p^2. So all of the numbers from 1 to p^2 are relatively prime to p^2 except for those p multiples of p, for a total of p^2 - p. Put another way, exactly one out of every p numbers is divisible by p, so each consecutive group of p numbers yields p-1 which are relatively prime to p. There are p such groups up to p^2, so the total is p(p-1) = p^2 - p. In the example with p=5, you can verify that there are 5^2 - 5 = 5 \cdot (5-1) = 20 blue squares.

Finally, what about bigger powers, \varphi(p^k)? Well, once again, the only numbers which share any common factor with p^k are exactly the multiples of p. There’s one multiple of p (and p-1 non-multiples of p) in every group of p numbers. How many such groups are there up to p^k? There are p^{k-1} of them. Hence \varphi(p^k) = p^{k-1}(p-1).

Putting it all together

A previous post contained an example that required computing \varphi(151389); now we can see how to do it. First, we factor the number as 151389 = 3^5 \cdot 7 \cdot 89. Then, using the fact that \varphi is multiplicative, we can break it down into three separate applications of \varphi:

\varphi(3^5 \cdot 7 \cdot 89) = \varphi(3^5) \cdot \varphi(7) \cdot  \varphi(89).

Finally, we can evaluate \varphi for each of these prime powers:

  • \varphi(3^5) = 3^4 \cdot (3-1) = 81 \cdot 2 = 162
  • \varphi(7) = 6
  • \varphi(89) = 88

Hence \varphi(151389) = 162 \cdot 6 \cdot 88 = 85536. For this relatively small number we can actually double-check this result using a computer to count the answer by brute force:

>>> length [n | n <- [1 .. 151389], gcd n 151389 == 1]
85536

Math works!

Posted in arithmetic, computation, counting | Tagged , , | Leave a comment

Computing the Euler totient function, part 3: proving phi is multiplicative

We are trying to show that the Euler totient function \varphi(n), which counts how many numbers from 1 to n share no common factors with n, is multiplicative, that is, \varphi(mn) = \varphi(m) \varphi(n) whenever m and n share no common factors. In my previous post, we looked at some illustrations, for example:

The dark blue squares are those counted by \varphi(mn), and the light blue rows and columns are those counted by \varphi(m) and \varphi(n). We noted what these pictures are telling us: because we know from the Chinese Remainder Theorem that the numbers x from 0 to mn-1 correspond exactly to pairs of numbers (x \bmod m, x \bmod n), showing that \varphi is multiplicative really comes down to showing the following fact:

x is relatively prime to mn if and only if x\bmod m is relatively prime to m and x \bmod n is relatively prime to n.

In other words, the dark blue cells show up precisely at the intersections of light blue rows and columns. Let’s prove this!

First, if x shares no common factors with the product mn, then it can’t possibly share any common factors with m or n individually. This is because any divisor of m is also a divisor of mn, and likewise for n; so if x did share any common factor with, say, m, then it would automatically be a common factor with mn. The converse is also true: if x shares no common factors with m and also shares no common factors with n, then it can’t share any common factors with mn. That is,

(A) x is relatively prime to mn if and only if x is relatively prime to m and xn is relatively prime to n.

For the second piece of the puzzle, note that by definition, x \bmod m = x - qm for some integer q. That is, x \bmod m is what is left over after we subtract some number of copies of m from x. If x shares a common factor d with m, then so does x \bmod m = x - qm, since we could factor d out of both x and qm. Likewise, if we add qm to both sides to get x = qm + x \bmod m, we can see that if x \bmod m shares a common factor d with m, then so does x—since once again we could factor d out of both qm and x \bmod m. Thus we have shown that

x shares a common factor with m if and only if x \bmod m shares a common factor with m,

or, taking the contrapositive of this statement,

(B) x is relatively prime to m if and only if x \bmod m is relatively prime to m.

Now let’s put the puzzle pieces together:

\begin{array}{c}x \text{ is relatively prime to } mn \\[1.2em] \text{if and only if (by (A))} \\[1.2em] x \text{ is relatively prime to } m \text{ \textbf{and} } x \text{ is relatively prime to } n \\[1.2em] \text{if and only if (by (B), twice)} \\[1.2em] x \bmod m \text{ is relatively prime to } m \text{ \textbf{and} } x \bmod n \text{ is relatively prime to } n \end{array}

which is exactly what we set out to prove.

The Chinese Remainder Theorem tells us that when m and n are relatively prime, there is a 1-1 matchup between the numbers 0 \leq x < mn and the pairs of numbers (a,b) such that 0 \leq a < m and 0 \leq b < n. But we now know we can make an even finer distinction: 0 \leq x < mn which are relatively prime to mn are in 1-1 correspondence with pairs (a,b) where a is relatively prime to m and b is relatively prime to n. Hence, \varphi(mn) = \varphi(m)\varphi(n).

Posted in arithmetic, computation, counting | Tagged , , , | 1 Comment

Computing the Euler totient function, part 2: seeing phi is multiplicative

In my last post, I claimed that \varphi(mn) = \varphi(m) \varphi(n) whenever m and n are relatively prime. (Recall that \varphi(n) counts how many numbers from 1 to n share no factors in common with n.)

Let’s get some intuition for this by looking at some m \times n Chinese remainder theorem grids and highlighting the numbers which are relatively prime to mn. So, for example, the first grid below is 3 \times 5; I’ve filled it in with consecutive numbers from 0 to 14 along the diagonal, and highlighted all the numbers that share no common factors with 15. (I’ve also labelled the rows and columns with smaller numbers counting from 0.) Below that I’ve also chosen to show similar 3 \times 8, 5 \times 6, and 8 \times 9 grids.

And here’s a slightly bigger example (14 \times 15):

There are some striking patterns here. The placement of the highlighted cells is clearly not random: they are precisely confined to certain rows and columns. (Incidentally, this is exactly what I was trying to show in my last post without words, though I think the colors may have been somewhat distracting.) Which rows and columns are they? Let’s have a look. Below I’ve drawn the 8 \times 9 grid again, this time highlighting the rows and columns where cells relatively prime to 72 occur:

Notice that the highlighted rows (1, 3, 5, 7) are exactly the numbers relatively prime to 8, and the highlighted columns (1, 2, 4, 5, 7, 8) are the ones relatively prime to 9. The number of dark blue intersection points is just the number of highlighted rows times the number of highlighted columns: there are four highlighted rows and six highlighted columns, making a total of 24 dark blue squares. That is, \varphi(72) = \varphi(8) \varphi(9).

You can check that this is true for the other examples I showed above as well. So can we turn this into a conjecture? Remember that when we label an m \times n grid with consecutive numbers along the diagonal, the number x ends up at the grid coordinates (x \mod m, x \mod n) (see this post). We’re guessing that cells containing numbers relatively prime to mn end up precisely where the row number is relatively prime to m and the column number is relatively prime to n, so we can translate this into the more formal statement

x is relatively prime to mn if and only if x\bmod m is relatively prime to m and x \bmod n is relatively prime to n

We’ll prove this next time!

Posted in arithmetic, computation, counting | Tagged , , | 2 Comments

Computing the Euler totient function, part 1

Recall that Euler’s totient function \varphi(n) counts how many of the integers from 1 to n are relatively prime to n, that is, share no factors in common with n. For example, \varphi(12) = 4, since only 1, 5, 7, and 11 share no factors with 12; on the other hand \varphi(13) = 12, since every number from 1 to 12 shares no common factors with 13. We’ve encountered this function many times before, but I’ve never actually talked about how to compute it!

Of course, we could just count: that is, to compute \varphi(n), list all the numbers from 1 to n, and compute the GCD of each number with n (using the Euclidean algorithm); count the ones for which the GCD is 1. This works, of course, but it is possible to compute \varphi(n) much faster than this.

The key to computing \varphi more quickly is that it is has the special property of being multiplicative: if m and n are relatively prime, then \varphi(mn) = \varphi(m) \varphi(n) (don’t take my word for it though—we’ll prove it!).

Recall that we can break any number down as a product of distinct prime powers,

n = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}.

For example, 360 = 2^3 \cdot 3^2 \cdot 5^1. Of course, any powers of two different primes are relatively prime to each other (they are only divisible by their respective primes), so if \varphi is multiplicative it means we can break down \varphi(n) like this:

\varphi(n) = \varphi(p_1^{k_1}) \varphi(p_2^{k_2}) \dots \varphi(p_n^{k_n}).

Then all we have left to do is figure out how to compute \varphi(p^k) for some power of a prime p. That is, we’ve reduced a harder problem (“how many numbers are relatively prime to an arbitrary integer n?”) to a more specific and hopefully easier one (“how many numbers are relatively prime to an integer of the form p^k for some prime number p?”). Some questions we still have to answer:

  1. How do we know that \varphi(mn) = \varphi(m) \varphi(n) when m and n are relatively prime? (Hint: look at my previous post and the one before that…)

  2. How do we find \varphi(p^k)? You might like to try figuring this out too. As a warmup, what is \varphi(p)? Then what about \varphi(p^2)? Can you generalize?

Posted in arithmetic, computation, counting | Tagged , , | 1 Comment

Post without words #26

Image | Posted on by | Tagged , , | 2 Comments