Doing Euler's Totient, The Fast Way!

Doing Euler's Totient, The Fast Way!

Some people do sudoku for fun. Others play games on their phone. I am a weird nerd, and so I solve dumb programming problems for fun. My big favourite is the Project Euler site, which consists of math problems that you probably will only be able to solve with a computer.

That’s not to say all of them require one, but let me tell you doing this by hand would be a labour of love at the very least.

Anyway it’s fun math problems. Confuses the heck out of people when I tell them that that’s what I do to chill out, but it’s how it be. Go read this blog if you’re still confused.

Wait what did this have to do with Euler’s Totient?

Oh right. Sorry got distracted. Now in keeping with respecting the game, I’m not going to give you the answer to whichever question or questions this is in reference to. But, if you are looking for a faster way to say, generate a bunch of answers to Euler’s Totient quickly, this will save you time and even teach you a thing (which is mostly what we want to do anyway and is in keeping with the spirit of the game)

So what is Euler’s Totient?

Well, Euler’s Totient — also known as Euler’s phi, or $\phi$ function — is a neat little function that when given a number returns the number of numbers less than that number that are relatively prime to that number. Relatively prime means that they share no prime factors, or that the greatest common denominator between the two numbers is $1$. Why is this function useful? Encryption, mostly. Actually no there are a bunch of cool uses to this function, but one of it’s neatest factors is that it is inherently multiplicative $\phi(xy) = \phi(x)\phi(y)$, and that it is very useful when dealing with modulo math. If you go read the Wikipedia entry you can quickly end up in a rabbit hole about the fundamentals of RSA cryptography.

The Easy And Stupid Way

Right so, if you are me and have been introduced to Euler’s Totient via the challenges in the project, you’ll have gone “Ah! Well that’s easy then. For any value, count all the numbers that have a GCD with the value of $1$!”.

This is a terrible idea.

See it does have simplicity to it, but it also is not computationally simple. To find a GCD, you need about $O(\log(n))$ steps, where $n$ is the value of the number. You then need to do this $n$ times for each number lesser than $n$ to produce the totient. So what you end up with is a really quickly hacked out function that runs in $O(n \log(n))$ time.

Taking this further, if you’re doing this with a bunch of numbers, you’re going to have $O(nk \log(k))$ time, where $k$ is influenced by the value of the numbers you are calculating the totient for, and $n$ is how many numbers you’re calculating the totient for. If $k$ is of a similar order to $n$, you end up really close to $O(n^2 \log(n))$. This is not a good complexity if you want to… idk… do anything else today.

The good news is, this is not the method they wanted you to use, nor is it the best method. There’s actually a dope as hell shortcut Euler figured out back in the day that makes this easy.

Enter Euler’s Product Formula

The key to this whole magic problem is in fact the fact that we said relatively prime, or coprime. See for a number to be relatively prime to another, it’s gotta share no factors with the other guy. All factors can be written as a series of distinct primes – If you are divisible by $8$, you’re divisible by $2$ – which means that all numbers not coprime must share a prime factor with the original number!

How the heck does this help us?

Right well, one way of counting something is to count how many of it there is. The other is to find the maximum possible number and subtract all the things we know aren’t it. Most of the time this is a terrible idea because upper bounds are often very large, but here it’s only ever $n$!

Combining these two thoughts leads us to a powerful approach to solving this: Find the distinct prime factors of whichever number we’re calculating the totient for, $n$, and then remove all numbers that are less than $n$ that share that factor.

This can actually be calculated hilarously fast. One of Euler’s neat observations was that numbers divisible by a factor happen a predictible amount over a number line. For any set of sequentially increasing numbers from $i$ to $j$, half of them will be divisible by $2$. A third of them will be divisible by $3$. A fifth of them will be divisible by $5$. Better still, as factors are multiplicative, a third of numbers not divisible by $5$ are divisible by $3$. This means we can effectively sieve our number set by multiplication, which is waaaay faster than doing slow checks!

This leads us to the awesome formula:

$\phi(n) = n\prod_{p|n}(1-\frac1p)$

where $p$ are the distinct prime factors of $n$.

This is Euler’s Product Formula, and has a delightful complexity value of only $O(\sqrt{n})$.

Let’s Do An Example!

Say we choose a number, $30$, and decide we want to calculate $\phi$. If we loop through all numbers less than $30$ and find all of the ones with a GCD of $1$ we will end up with the list:

$1, 7, 11, 13, 17, 19, 23, 29$

Which of course is exactly $8$ numbers. Note that the largest one is $29$, which means there’s no cheats here, you have to go through all the numbers. If $n$ were a hundred billion, you’re doing around about a hundred billion GCD checks. Goodbye your afternoon.

Now let’s do it the smart way. First off, we have to find all distinct prime factors of $30$. To find all factors we need to test prime numbers up to $\sqrt{30}$. It turns out that $\sqrt{30}$ is just a tad over $5$, so we need all primes between $1$ and $5$. These are:

$2, 3, 5$

And whaddya know, they are all factors of $30$. We have now concluded the factorising portion of this calculation – which is absolutely bananas when you compare it to the above – and can now move on to exactly three multiplication steps:

Step 1: $30 \times (1 - \frac{1}{2}) = 15$

Step 2: $15 \times (1 - \frac{1}{3}) = 10$

Step 3: $10 \times (1 - \frac{1}{5}) = 8$

The answer, of course, is $8$.

W h a t

The hardest part of Euler’s Product Formula is knowing the prime factors. This is piss easy compared to the GCD checks because you can pre-calculate every prime via sieve (or Miller-Rabin, another sick-ass formula I’ll have to do a runthrough for some time) ahead of time, and then just limit the prime list to primes less than $\sqrt{n}$. This means at scale, you can absolutely obliterate the calculation of $\phi$ at speed.

I love dumb complexity math, and I really love algorithms that manage to score big-O values better than $O(n)$. Euler’s Product Formula does that, which makes it pretty freaking cool.

Anyway, hope you learnt a thing, and uh if you’re out doing problems on Project Euler I hope this let you solve a couple :)