Season 4 Episode 1

Another classic problem in this episode; we start with a thousand lightbulbs, all of which are off, and then people start switching them on and off. We'll solve the problem and discuss some variants.

Further Reading

Prime sieve

The lightbulb switching process works a little bit like the sieve of Eratosthenes (thank you chat for reminding me what that’s called). The sieve is an algorithm for finding prime numbers. There’s an NRICH activity that gets you to calculate it here https://nrich.maths.org/7520 and an animation of it working (plus more explanation) on Brilliant here; https://brilliant.org/wiki/sieve-of-eratosthenes/

If you know how to write computer code, consider how you would write up this algorithm. If you do write this up, you could use your code to work out how many primes there are between 1 and 10,000.

Number of factors

One of my suggested extensions for the lightbulb problem asked you for the number of times each bulb changes state. We can work this out by counting the factors.

Let’s start with an example, by finding the factors of 36. In the livestream I listed the factors of 36 working from smallest to largest by thinking about whether each number in turn was a factor of 36. There’s a faster way to work systematically to find the factors which you probably learn in school; I should factorise the number $36=2^2\times 3^2$ and then work from there.

Because of that prime factorisation, any factor of 36 can only have 2s and/or 3s in its prime factorisation, and that factor can only have at most two 3s and at most two 2s. In fact, the factors are precisely the different combinations of choices of how many 2s to have and how many 3s to have; first choose how many 2s to put in the factor, and then choose how many 3s to put in the factor. Different choices give different factors, and every factor works like this. You have three choices for how many 2s to put in the factor (0 or 1 or 2) and then three choices for how many 3s to put in the factor (0 or 1 or 2), so nine combinations of choices overall, and 36 has nine factors.

In general, we might write something like
\[N=p_1^{a_1} p_2^{a_2} p_3^{a_3}\dots p_n^{a_n}.\]
for the prime factorisation of a number, where $p_1$, $p_2$, and so on are prime numbers and $a_1$, $a_2$, and so on are the powers in the prime factorisation. Then our factors use the same primes, and in the factor the power on prime $p_1$ is anything between $0$ and $a_1$ inclusive.

So the total number of choices for how to build a factor of $N$ is
\[(1+a_1)(1+a_2)\dots(1+a_n)\]
That’s a formula for the number of factors of a number in terms of its prime factorisation.

You can use this way of thinking about factors to make a nice short proof that only square numbers have an odd number of factors; complete the gaps in the argument below.

For the number of factors to be [blank], each bracket in that expression must be [blank] (because if any one of the brackets were [blank] then the product would be [blank] too), and each bracket is [blank] if each $a_i$ is [blank]. If each $a_i$ is [blank] then the original number is the square of [blank].

As an extension, if you know about geometric series then you can work out an expression for the sum of the factors of a number. Start by working this out for the sum of the factors of $p^n$ where $p$ is a prime number and $n$ is a positive whole number. Then try $pq$ and then try the general case for $N$ above, with the big general prime factorisation.

Exercise: Suppose that $2^n-1$ is prime for some whole number $n$, and write $N=2^{n-1}(2^n-1)$. Show that the sum of the factors of $N$ (including $N$) is $2N$.

Perfect numbers

If the sum of the factors of a number (including itself) gives twice the number itself, we call that a perfect number. All the perfect numbers we know are of the form above, $2^{n-1}(2^n-1)$, with $n$ chosen so that $2^n-1$ is prime. We don't know much about how to choose $n$ to achieve this, and we don’t know if there are any other perfect numbers not of that form.

In particular, we don’t know if there are any odd perfect numbers. But we do know that if there are any odd perfect numbers, they’re not multiples of 105. This has been known for quite a while, and there's an nice write-up of one proof on the Bilkent University’s website after it was used for their Math Problem of the Month September 2006.

There’s more information about odd perfect numbers at https://mathworld.wolfram.com/OddPerfectNumber.html. It’s one of those things where mathematicians have checked all the numbers up to $10^{1500}$ without finding any, but we still haven’t proved there aren’t any.

Semiprime numbers

Part of the discussion mentioned semiprime numbers in passing. What’s one of those? A semiprime number is the product of two prime numbers (which could be the same). So $15=3\times 5$ is semiprime, $4=2\times 2$ is semiprime, and $12=2\times2\times3$ is not a semiprime.

Semiprimes play a starring role in RSA cryptography https://brilliant.org/wiki/rsa-encryption/.

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.