Programming | bytes and stuff

In my last post I talked about finding the number of zeroes at the end of $n!$ , and I said that there was room for improvement. I thought about it a little bit and found a couple things to speed it up.

The first has to do with the relationship between the quantity of fives and the quantity of twos. The lower quantity in the prime factorization of $n!$ is how many zeroes it will have at the end. If I would have thought a little more about it though I would have seen that counting the twos is pointless in this situation.

Even the prime factorization of $10 = 5 \cdot 2$ has the information in there: there will always be more twos than fives. Counting from 1 to 10:

Multiples of 2: 2, 4, 6, 8, 10
Multiples of 5: 5, 10

This means that all we really need to keep track of is the quantity of fives in the prime factorization of $n!$ . Which leads to the second optimization: we only need to get the prime factorization of multiples of five.

Continue reading Factorial Zeroes 2 →

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 $2^8 = 256$ , a 16-bit (2-byte) integer has a max value of $2^{16} = 65536$ , etc. In fact since any integer in a computer is made of bits it will have a maximum value of $2^n$ . The prime factorization of an n-bit integer is in the notation, it is n 2s all multiplied together. Like so: $2^8 = 8 \cdot 8 \cdot 8 \cdot 8 \cdot 8 \cdot 8 \cdot 8 \cdot 8$

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 $2^n$ 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:

$2 \cdot 5 = 10$
$2 \cdot 2 \cdot 5 = 20$
$2 \cdot 5 \cdot 5 = 50$
$2 \cdot 2 \cdot 5 \cdot 5 = 10 \cdot 10 = 100$

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 $n!$ where for any value $n$ , $n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$ . For example $3! = 1 \cdot 2 \cdot 3$ and $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$ . The Wikipedia page for factorials shows that $70! = 1.197857167 \times 10^{100}$ . That’s a big number, over a googol. You can see the whole thing here on WolframAlpha.

Continue reading Factorizeroes! →

bytes and stuff

Category Archives: Programming

Factorial Zeroes 2

Factorizeroes!

Doing all things