WP2: A math problem meant for primary school kids

Recently, a friend of mine asked for my help to solve and explain a math problem as she’s required to teach it to primary school kids. I was like, “Sure thing.” So, she sent me this:

Problem 2

Let X be a number such that

$\displaystyle X=(1\times 2\times 3\times \cdots \times 2008\times 2009) + (2010 + 2011 + \cdots + 2019)$

Find the sum of the last 500 digits of X.

And I was like

Before we start discussing, again, attempt the problem yourself first if you wish. After all, it’s (ostensibly) a primary school math problem. How hard can it be?

Analysis

Notational convenience

First, the expression for X consists of two parts. For simplicity, let’s denote

$\displaystyle Y=1\times 2\times 3\times \cdots \times 2008\times 2009\\\\ Z=2010 + 2011 + \cdots + 2019$

so that X = Y + Z.

Evaluating Y, which is a product of two thousand and nine integers, is an order of magnitude harder than evaluating Z, which is just a sum of twenty integers. Naturally, we’d expect that most of our work is going to focus on part Y.

Next, part Y can be rewritten in a more compact manner using the factorial notation, n! (the exclamation mark is the notation), where n is a positive integer. In general,

$\displaystyle n!=n\times (n-1)\times (n-2)\times \cdots \times 3\times 2\times 1$

By the way, when a mathematical expression deserves a special notation, you know it’s gonna be important. This is especially true for n! , which appears in topics like counting and calculus.

Anyway, using the factorial notation, we can express Y succinctly as

$\displaystyle Y=2009!$

Investigating Y

So what can we say about the number Y? My first claim is that Y is a humungous number. Just to give you an idea, let’s determine the number of digits Y has (in the usual base-10 system). To do that, we calculate the logarithm of Y to base 10:

$\displaystyle \log_{10} (2009!)\approx 5765.24$

A number with over five thousand digits, that’s how huge Y is! Therefore, it’s not very sensible to actually evaluate Y in full (unless you have a powerful calculator, but hey, this problem is meant for primary school kids, remember?).

Now what? Direct computation is hopeless, which honestly isn’t surprising at all. From the very look of the original expression, it’s evident that the problem is not meant to be solved straightforwardly (i.e. compute Y, compute Z, add them up, add the last 500 digits of whatever the outcome is). Merely realizing this fact is already a huge step, because it will prompt us to take an alternative approach:

Pattern recognition

Understanding n!

To analyse the structural properties of n! , let’s compute some examples. For the sake of demonstration, I am listing the first twenty factorials, even though we don’t really need that many to recognize the pattern.

$\displaystyle 1!=1\\ 2!=2\\ 3!=6\\ 4!=24\\ 5!=120\\ 6!=720\\ 7!=5\,040\\ 8!=40\,320\\ 9!=362\,880\\ 10!=3\,628\,800\\11!= 39\,916\,800\\ 12!=479\,001\,600\\ 13!=6\,227\,020\,800\\ 14!=87\,178\,291\,200\\ 15!=1\,307\,674\,368\,000\\ 16!=20\,922\,789\,888\,000\\ 17!=355\,687\,428\,096\,000\\ 18!=6\,402\,373\,705\,728\,000\\ 19!=121\,645\,100\,408\,832\,000\\ 20!=2\,432\,902\,008\,176\,640\,000$

A couple of observations can be made. First, factorial grows insanely fast! When n is only 10, n! already exceeds three million; moving ten more steps forward, 20! is a whopping nineteen-digit number.

Second, beyond certain point, the factorials are numbers that end with digit 0. Moreover, the string of 0s n! has at its back also seems to grow with n (for brevity, let’s just call it the 0-tail). Now this is promising. Could it be the case that Y = 2019! is a number that ends with an enormous number of 0s? If so, then our task of calculating the last 500 digits of X is actually much simpler than it looks as most of the summands are just going to be 0.

We have a new goal now:

To determine the length of 0-tail of Y.

And the key question to ask is this:

What contributes to the growth of 0-tail?

The “back”-story of the 0s

Since we are using base-10 number system, it’s natural to expect that the 0-tail grows every time we multiply by 10, or by any multiples of 10 in general. For example, going back to the list of factorials, we see that 10! has one more 0 than 9! because

$\displaystyle 10!=10\times 9!$

By the same token, 20! has one more 0 than 19! because

$\displaystyle 20!=20\times 19!$

However, is it really necessary for n to be a multiple of 10 for the 0-tail to grow? Not really. Looking at the factorial list, we notice that the very first time a 0 appear at the back is when n = 5. After that, the length of 0-tail stays the same until n = 10, where it grows again. The next time it happens is when n = 15, and subsequently when n = 20. Do you notice what’s common in all these values of n? They are all multiples of 5.

The reason is that the most fundamental factor (no pun intended) contributing to the growth of 0-tail is actually not 10, but its prime factors 2 and 5.

Just a quick reminder, a prime number is an integer greater than 1 whose only factors are 1 and itself. A crucial number-theoretical result states that any integer greater than 1 is either a prime number itself or can be factorized into a product of prime numbers (in fact, this result is so fundamental that it is called the fundamental theorem of arithmetic). Simply put, prime numbers are the basic building blocks of integers in the context of factorization.

Returning to our discussion, we have the prime factorization 10 = 2 × 5. Since each factor 10 of an integer k is encoded into a digit 0 of the 0-tail, each digit 0 is tied to a pair of prime factors 2 and 5 of k. Let’s look at some examples to demonstrate this fact.

$\displaystyle \begin{aligned} &(1)\qquad 13\,000\,000&=2^6\times 5^6\times 13 \\\\ &(2)\qquad 1\,625\,000&=2^3\times 5^6\times 13 \\\\ &(3)\qquad 520\,000&=2^6\times 5^4\times 13 \end{aligned}$

In Example (1), we have six copies of both factors 2 and 5, meaning we can make six copies of 10 in total, which is why the length of its 0-tail is 6.

However, Example (2) has unequal numbers of factors 2 and 5. In this case, the number of copies of 10 is governed by the “limiting” factor 2 instead of 5, in the same way how in chemistry the amount of product is governed by the amount of limiting reactant instead of the excess reactant. Hence, only three copies of 10 can be made, and so the length of 0-tail is only 3. Similar things can be said about Example (3), except this time the limiting factor is 5.

Let’s try to apply that to the astronomical Y we are after. We know that Y is expressed as

$\displaystyle Y=2009\times 2008\times\cdots\times 3\times 2\times 1$

which is not in the form of prime factorization, but that’s not too big of an issue because of two reasons:

We have complete information about the factors of Y in the original expression above – they are just all the integers from 1 to 2009;
The prime factors 2 and 5 must come from some of the aforementioned factors. More precisely, each of the prime factors of Y must also be a factor of some number from 1 to 2009 (see Remark 8.1).

Combining these two facts, we will need to investigate the multiples of 2 and 5 between 1 and 2009 inclusive. Well actually, since the multiples of 2 appear more frequently (meaning there will be an excess supply of prime factor 2), it suffices to study the multiples of 5.

Finally, after the lengthy analysis, we can start solving!

Solution

Step 1: Multiples of 5

Calculating the multiples of an integer is essentially a division problem. In our case, we just have to find the quotient of 2009/5, or equivalently, use the floor function to evaluate $\lfloor {2009/5} \rfloor$ . Either way, we have

$\displaystyle \frac{2009}{5}=401\text{ remainder }4$

which shows that there are 401 multiples of 5 between 1 and 2009, meaning we can extract 401 copies of prime factor 5 from them. Therefore, the length of 0-tail of Y is at least 401.

Wait, why do I say at least? Did we undercount?

Here’s the thing: Although the length of 0-tail is equal to the number of prime factor 5, some multiples of 5 can supply more than one copy of factor 5. For instance, all multiples of 25 (i.e. 5²) can supply at least two copies of factor 5. Similarly, the multiples of 125 (i.e. 5³) and 625 (i.e. 5⁴) can supply at least three and four copies, respectively.

Let’s take them into account.

Step 2: Multiples of 25

We perform similar calculation to determine the number of multiples of 25 below 2009.

$\displaystyle \frac{2009}{25}=80\text{ remainder }9$

There are 80 of them, each contributing a second copy of factor 5 (the first copy has been counted in Step 1), meaning the length of 0-tail of Y is at least 401 + 80 = 481.

Step 3: Multiples of 125

Again, we calculate the following.

$\displaystyle \frac{2009}{125}=16\text{ remainder }9$

So, 16 extra copies of 5 give us 16 more 0’s at the back, making the length of 0-tail at least 481 + 16 = 497.

Step 4: Multiples of 625

You already know what do right?

$\displaystyle \frac{2009}{625}=3\text{ remainder }134$

Before we proceed, let me just say that this is the final multiples to consider as 5⁵ = 3125 already exceeds 2009. Thus, we have the final three 0s to add, making the length of 0-digit exactly equal 497 + 3 = 500.

Phew! After all these analysis and steps, we arrive at the conclusion that Y = 2019! is a number with exactly five hundred zeros at the back! If you find this a cathartic experience, then good for you! That’s a great reward of exercising your brain to solve a problem… oh wait, we haven’t solved the problem, have we?

Step 5: Evaluating Z

The problem requires us to find the sum of last 500 digits of X where

$\displaystyle X=Y+Z$

Since the last 500 digits of Y are all 0, the problem simplifies to finding the sum of all the digits of Z. There are different ways of calculating that, and whichever method you use, you should effortlessly get

$\displaystyle Z=2010+2011+\cdots+2018+2019=20145$

Therefore, the sum of the last 500 digits of X equals the sum of all the digits of Z which is

$\displaystyle 2+0+1+4+5=12$

Conclusion

Now that we have solved the problem, some of you might ask “Is this problem really primary school level?” On the one hand, the actual computations only involved addition, multiplication, and division; on the other hand, the thought process that went into our analysis entailed more than just three-line logic, not to mention some hidden subtlety.

Since this question has no easy answer, I am going to pull a Dodge no Jutsu and make some other comments. First, the idea of pattern recognition is indeed an invaluable skill and should be taught as early as possible. Second, in order to optimize learning, the problems we give to our students should be reasonably challenging. We ought to view struggling more wholesomely as a necessary process to learn, not as something to avoid at all cost.

Having said that, whether or not the difficulty of this problem is suitable for kids is debatable. I choose not to comment on this as I do not know what it’s originally intended for. Nevertheless, I think the overall direction is well and good. The key thing of course is how a teacher could make the most of this problem to educate the young minds and cultivate good qualities like perseverance.

All right, this article is long enough, but I am just going to make it a tad bit longer by putting a remark below. Until then, stay acute, stay safe. See you!

Remark 8.1

Near the end of our analysis, we argued that if a prime number p is a factor of a product of integers, say m × n, then p must be a factor of m or n (or both). For example, 3 is a factor of 2 × 9, and we see that 3 is also a factor of 9.

It is important to realize that this is not true in general if p is not a prime. For example, 6 is a factor of 2 × 9, but 6 is neither a factor of 2 nor 9.

This special property of prime numbers is called the prime property in higher level algebra, and any object that behaves like this is called a prime element. In the usual realm of integers, the prime numbers are the prime elements.

But this is a bit of an unfortunate situation, because prime numbers are not traditionally defined this way. Colloquially, a prime number is a number that cannot be further broken down into two “smaller” numbers. This property is called the irreducible property in higher level algebra, and any object that possesses this property is called an irreducible element.

In general, the prime elements and irreducible elements are not always the same. Fortunately, in certain well-behaved arena (e.g. the realm of integers), they are no different. This is why we don’t bother to rename prime numbers to “irreducible numbers” (even if the latter makes perfect sense) since they enjoy both the properties.

Well, I guess you can say that mathematicians aren’t really good at naming things.