A while back I was looking at the different maximum values that the different integer data types (uint8, short, int, long, etc) have throughout a couple languages I’ve been using and noticed that none of them ended in zero. I wondered why that was but then relatively quickly realized that it is because integer data types in computers are made up of bytes and bits.

An 8-bit (1-byte) integer has a max value of , a 16-bit (2-byte) integer has a max value of, etc. In fact since any integer in a computer is made of bits it will have a maximum value of . The prime factorization of an n-bit integer is in the notation, it is n 2s all multiplied together. Like so:

In order for something to end in a zero it must be a multiple of 10, and the prime factorization of 10 is 5 * 2, and the prime factorization of will never contain a 5. Case closed. That was fun.

That got me thinking about figuring out how many zeroes are at the end of a number if all you have is the prime factorization. Using my basic arithmetic skills I found out that:

• 
• 
• 
• 

It appears (although isn’t proof) that the lowest quantity between twos and fives dictates how many zeroes are at the end of a number when you’re looking at its prime factorization. I tried this with many more combinations and it worked with every one of them.

So what can we do with this information?

A factorial is a number written as where for any value , . For example and . The Wikipedia page for factorials shows that . That’s a big number, over a googol. You can see the whole thing here on WolframAlpha.

So what if we want to know how many zeroes are at the end of ? Or ? Calculating directly then counting the zeroes at the end of it seems unlikely, or at least not easy, since a number like that wont fit into a standard computer int data type. This is where the prime factorization comes in, we can get the prime factorization of all numbers that go into .

And since the associative property of multiplication tells us that parenthesis don’t matter (in this case), all we have to do is count the quantity of twos and fives in the prime factorization of and see which is lower.

This can be quite time consuming for large values of though because we will have to get the prime factorization of every number between 1 and . We need a program to do that for us.

Leading up to this point we’ve already discovered most of the requirements for the program, it must:

1. Iterate from 1 to .
2. Get the prime factorizations of each of those numbers.
3. Put the prime factorizations of all of those numbers into a list.
4. Once all the prime factorizations for all numbers between 1 and have been found, it needs to go through the list and count how many twos and fives are in the list.

I chose C# to do this project for no other reason than I had been working with it quite a bit lately. The start of the program is pretty boiler plate, read a number and pass it into the method that will do the fun stuff. It doesn’t check if the input is valid or anything like that, that’s too much work for something like this.

        static void Main(string[] args)
        {
            int n = 0;
            Console.Write("Enter a number n, or -1 to quit: ");
            string str = Console.ReadLine();
            n = int.Parse(str); //convert string to int
            while(n >= 0)
            {                
                CountZeroesAtEndOfFactorial(n);
                Console.Write("Enter a number n, or -1 to quit: ");
                str = Console.ReadLine();
                n = int.Parse(str); 
            }            
        }

The CountZeroesAtEndOfFactorial() method counts the number of zeroes at the end of the number by finding which quantity is lower, twos or fives:

        private static void CountZeroesAtEndOfFactorial(int number)
        {
            List<int> factors = GetPrimeFactorizationOfFactorial(number);
            int twos = 0, fives = 0;
            foreach (int num in factors)
            {
                if (num == 2)
                    twos = twos + 1;
                if (num == 5)
                    fives = fives + 1;
            }

            //get the smaller quantity
            int zeroCount = (twos < fives) ? twos : fives; 

            Console.WriteLine("{0}! has {1} zeroes at the end", 
                number, zeroCount);
        }

The list of numbers that the CountZeroesAtEndOfFactorial() method uses comes from the method GetPrimeFactorizationOfFactorial(). This is the method that iterates through every number between 1 and , gets the factors in its prime factorization, and puts them into a list.

        private static List<int> GetPrimeFactorizationOfFactorial(int num)
        {
            List<int> list = new List<int>();
            if (num < 2)
            {
                list.Add(num);
                return list;
            }

            for (int i = 2; i <= num; i++)
                list.AddRange(GetPrimeFactorization(i));

            return list;
        }

There’s still the matter of getting the prime factorization for any given number though. That’s accomplished with the method GetPrimeFactorization(). This method is based on the fact that if a given number, , is not prime, then there exists some combination of numbers, and , such that . From there we know that (or , it doesn’t really matter which). The important part here is that has a remainder of zero. All modern programming languages that I’ve used have an operator that gives you the remainder of an integer division operation, the modulus operator, %.

So we’re looking for a number, , that gives us a remainder 0, or in math terms we want . We could try dividing by every number between 1 and , but at some point our efforts will not be necessary. This point is the square root of . Since we’re dealing with integers however, we’ll stop when the square of the number we’re testing is greater than .

private static List<int> GetPrimeFactorization(int num)
        {
            List<int> list = new List<int>();

            if (IsPrime(num))
            {
                list.Add(num);
                return list;
            }

            int i = 2;
            while (i * i <= num)
            {
                if (num % i == 0)
                {
                    int result = num / i;

                    if (IsPrime(result))
                        list.Add(result);
                    else
                        list.AddRange(GetPrimeFactorization(result));

                    if (IsPrime(i))
                        list.Add(i);
                    else
                        list.AddRange(GetPrimeFactorization(i));

                    return list;
                }
                i++;
            }
            return list;
        }

So this method has two possibilities when finding the prime factorization for a number .

1) is prime, its prime factorization is itself, just return that value, easy.

2) is not prime. So there is some number such that with a remainder of zero. In this case and are factors of , not necessarily the prime factorization of . Since there exists the possibility that there are two more numbers such that or .

As this image illustrates, the tree of prime factorization can be many layers deep:

This means that we need to get the factorizations of the numbers and , and the factorizations of their factorizations, and so on, until all we have are prime numbers. This is done through recursion and why GetPrimeFactorization() calls itself in places.

The last piece of the puzzle is the IsPrime() method.

        private static bool IsPrime(int num)
        {
            if (num == 1)
                return false;
            if (num == 2)
                return true;

            int i = 2;
            while (i * i <= num)
            {
                if (num % i == 0)
                    return false;

                i++;
            }
            return true;
        }

This method is quite similar to the GetPrimeFactorization() method, but instead of finding the prime factorization of a number it returns false if it finds a number, , such that .

It runs fairly fast too. I changed the main method a bit to do multiple runs in one session and timed them, here is a screenshot of the results:

Less than one second to calculate the number of zeroes at the end of isn’t bad, considering that in its full form it has over five million digits.

Some final thoughts:

1. This program will only work with values of that will fit into a 32-bit integer.
2. The quantity of zeroes at the end of seems to be roughly a quarter of the value of . What’s up with that?
3. There’s definitely room for optimization on this project, maybe some other time.

The program is pretty short, so I’ve just uploaded it to a Gist on GitHub.