Finding the number of reduced fractions with denominator d

Part 2: Euler’s totient function

In Part 1, we left off after having optimized the GCD function which played a central role in my first brute force attempt at writing a numReducedFractions(d) function. This function is mean to find the number of reduced fractions for a given denominator. To reiterate here is what that first version of numReducedFractions(d) does:

  • set a count variable to 0
  • go through the numbers from 1 until and including the denominator
  • if the GCD of the looping number and the denominator is 1, increment count
  • return count

Optimizing the GCD function in turn optimized this function and I was able to pass the test specs for some but not all very large numbers. Still, it wasn’t good enough… so I was left with how to optimize the numReducedFractions function itself and I played with a few ideas — limit the for-loop or use recursion a la GCD? I settled on doing some more research.

That’s when I discovered Euler’s Totient Function. Not like I derived it myself — rather I found it on Wikipedia. The function counts the positive integers up to a given integer n that are coprime to that integer. Coprime means that the only integer that divides two numbers is 1. For example, 9 and 14 are NOT prime numbers, but they are coprime to each other since their GCD is 1. In other words, Euler’s totient function spits out exactly what we want! I also learned that the things we want are called ‘totatives’, hence Euler’s ‘totient’ function. Knowing this, I was left with two challenges:

1) Understand how it works.

2) Translate it into code.

How it works

Using the standard notation, Euler’s totient function is written like so:

φ(n) is the number of reduced fractions that can be generated for a given n. In case you are unfamiliar with the notation, we are multiplying n times the product of (1 -1/p) where p stands for all of the primes factors of n. Let’s try it out for 15. First of all, let’s list the primes from 1 to 15: 2, 3, 5, 7, 11, 13. Of these, only 3 and 5 divide p evenly. Next let’s take the product of (1–1/p) for each of them and multiply by 15.

And this is 8! Which is definitely correct. (Reduced fractions with a denominator of 15 are 1/15, 2/15, 4/15, 7/15, 8/15, 11/15, 13/15, 14/15.)

So why does this work?

  • First off, there are 15 total fractions that have the denominator 15. (1/15, 2/15, 3/15, 4/15, … 15/15). That’s where the initial 15 is from.
  • One third of those fractions are can be reduced: 3/15, 6/15, 9/15, 12/15, 15/15. Notice, these are all of the fractions where the numerator is divisible by 3. This comes about because 15/3 = 5 and 5/15 = 1/3. This means that 2/3 of the fractions are completely reduced. So we can multiply 15 * 2/3 to find the number of fractions that are reduced. 15 * 2/3 is 10.
  • Out of the remaining 10 fractions 5/15, and 10/15 can be reduced. Notice these are the ones where the numerator is divisible by five. 15/5 = 3 and 3/15 = 1/5. So 4/5 of our 10 fractions are reduced and we can multiply our 10 times 4/5. 10 * 4/5 = 8.

So, maybe that’s just a demonstration of the magic of the formula, without a complete explanation of why it works. If you’re interested in a deeper theoretical grounding, check out the excellent Wikipedia article.

The code

Here is the non-optimized code for the basic idea of Euler’s totient function. (I don’t feel bad about posting this since it definitely won’t pass the specs.)

So… are we back to where we started? Kind of — I’ve written another brute force algorithm that needs to be optimized. But this time we have some lessons from isPrime and GCD optimization.

The first thing that we need to realize is that finding all of the primes from 1 to square root n is pretty expensive. It instantly gives us a O(n²) since we’re looping within a loop. The following optimizations help us out:

  1. Instead we should look for prime factors within our original for-loop and we can instantly limit our initial for-loop to the square root of the number since we know that any numbers beyond that will not be prime factors.
  2. If the original number is divisible by the current number, we will update the original number to equal the quotient of the original number divided by current number as long as the quotient continues to be divisible by the current number. This is a little confusing so let’s see it with our original example: 15.
  • Right now original number = d = 15.
  • First pass of our for-loop, current num = which I have dubbed ‘p’ = 2. (One is neither prime nor composite so we can start at 2.) 15 is not evenly divisible by 2 so move on …
  • Next pass of our for-loop, p = 3. Fifteen is divisible by 3 so:
  • d = 15/3 = 5
  • Is 5 divisible by 3? Nope. Alright let’s do the next thing.

3) At this point we update the counter to be the counter minus the the quotient of the counter divide by the current number. Say what?

In our case the counter (which started at 15 — we begin with the assumption that all of the numerators would produce reduced fractions) becomes the counter minus counter/current number. So our counter is reduced down to 10 since 15/3 = 5 and 15 minus 5 is 10. This is the same thing as multiplying our counter by 2/3, since 1/3 of our fractions could be reduced. (See the logic up above if necessary!)

Then we continue on with our for-loop… We only keep checking as long as our p ≤ square-root of our original number, which is actually no longer our original number … it’s been updated! d = 5 now. Which means we are actually done with our for-loop since p now equals 4 which is larger than the square root of 5.

But 10 isn’t the right answer! We still have to reduce things a bit more. It’s actually possible for the ‘original number’ to have one prime factor greater than the square root of itself. So we check if the ‘original number’ (which had constantly been updated to be the quotient of itself and the looping number) is greater than one. If the ‘original number’ is now 1, that means that we were able to find all prime factors. If not, we update the counter to be equal to the counter minus the counter divided by the current ‘original number’. (Basically the same logic as we were doing in our for-loop). In the case of 15:

d (the original number) has been left of at 5, so the counter (now 10) = 10 minus 10/5. In other words, the counter goes from 10 to 8. This adjustment needs to happen since 5 is another prime factor of 15, so we need to get rid of another 1/5 of our possible results. 10 * 1/5 = 2. Hence 10 minus 2 =8. We made it!!!

In summary

We end up saving a lot of time by updating our ‘original number’ to the result of it divided by a one of its factors and limiting our looping to the square root of that ‘original number’. I hope that this explanation of how to write an optimized function that returns the number of reduced fractions (or totatives) for a given denominator has been helpful.

Sometimes while looking at Euler’s totient function or at this code that I’ve come up with, I feel that I still don’t fully understand it, and other times it seems to all make sense and the simplicity of it hits me as a thing of great beauty. If you’ve made it all the way here and can think of better ways of explaining things, please let me know!

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade