How many slices of pizza do we have?

Question

At the beginning, we had a whole piece of pizza and two people. So we cut the pizza into two slices of the same size. But at the same time, there is another guy joined us. We had to re-cut the pizza into three parts of the same size. This time we only need to cut two more times. But this was not the end yet, people were keep coming one by one. Every time we divided the pizza into equals with a minimum times of cut.$^{1}$ In the end, a total of N people came. How many slices of pizza do we have? Is there a way to figure it out quickly?

$^{1}$ The slices cannot be rearranged to get a smaller number of cuts. We cut the pizza in place, at $n$ equally-placed lines, as in the image below.

Answer 1

We may identify angles for the slices with real numbers between $0$ and $1$. At step $n$, we cut at angles $0, \frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n}$. (As clarified in the comments, the problem seems to assume this. Note that there is a more interesting question if we are allowed to rearrange the pieces, or if we are allowed to place the cuts at any arbitrary angle as long as the lines are equally spaced.)

Thus, the number of slices after $n$ people have joined is equal to the number of rational numbers in the interval $[0,1)$ with denominator at most $n$. The number with denominator exactly $k$ is $\phi(k)$, where $\phi$ is the totient function which counts how many numbers between $0$ and $k-1$ (numerators) are relatively prime to the $k$ (the denominator).

Therefore, the total number of slices after $n$ people have joined can also be expressed as $$ a_n = \sum_{k=1}^n \phi(k). $$

The sequence $a_n$ begins $2, 4, 6, 10$ as in your picture. More information on the sequence can be found in this Online Encyclopedia of Integer Sequences page.

Answer 2

First, let us consider the cuts to be the $n$-th roots of unity in the complex plane and let $\phi(n)$ be Euler's totient function. I claim that the number of cuts is $\sum_{k=1}^n\phi(k)$. To see this first we note that for some prime $p$ the only divisor is $1$ we must make $p-1$ new cuts since those roots of unity could not be cut yet or it would imply a divisor of $p$. Now for some composite $n$ as we traverse the circle by taking multiples of $e^{2\pi i/n}$ then we note that for some cut $e^{2 \pi i k/n}$ to have already been made implies that $k$ divides $n$. This means we will make a new cut when $k$ is relatively prime to $n$. Summing over these cuts for each $n$ gives us the result.