Happy New Year!
Let’s kick the new year off with a competition level math problem.
We need to evaluate the sum of the floor of 5 to the power n over 7 where n takes on all
the integers from 0 to - you guessed it - 2022.
Pause the video and give the problem a try to see if you can solve this tricky sum!
Let’s first see what would happen if we got rid of the floor function.
We would have this sum – which is actually a fairly straightforward homework problem.
We would first pull the 1/7 in front of the sum since it’s a constant.
Then we would just apply the geometric series formula.
For a finite geometric series the formula is this, where a1 would be the first term,
which is 1, r would be the common ratio, in this case 5, and n would be the number of
terms, 2023 since we’re starting at 0, not 1.
Substituting those values into the formula we get the following.
Now just simplify the numerator.
Then multiply the numerator and denominator by negative 1.
And multiply the denominators and we get this nice expression.
It’s obviously not the answer, but it does serve two purposes.
First, it gives a hint as to the form that we’re looking for, and second, it gives
us an upper bound so if we get something larger, we know we made a mistake.
But that pesky floor function is what makes this a competition problem and not a homework
problem.
The floor function, also called the greatest integer function, simply extracts the integer
part of x.
In slightly more sophisticated math parlance, we can write that as floor x equals the maximum
value of m, where m is an element of the set of integers denoted by Z, such that m is less
than or equal to x.
Let’s expand a bit to see the effect of the floor term by term.
The first term is the floor of 1/7.
Since 1/7 has no integer part, its floor is 0.
The second term is the floor of 5/7, which also has has no integer part, so its floor
is also 0.
The third term is the floor of 25/7.
Since 25/7 is 3 and 4/7, its floor is 3.
So the sum of the first three terms would be 3.
But obviously we can’t keep evaluating like this 2020 more times, term by term.
We need a trick and a pattern to help us out.
So what’s the trick?
The trick is to rewrite each term in a slightly different way.
Let’s start with the floor of 1/7.
It’s the same as 1/7 minus 1/7.
The floor of 5/7 is also just 5/7 minus 5/7.
And for the floor of 25/7, it’s the same as 25/7 minus 4/7.
In other words, we’re just mimicking the floor function by removing the fractional
part.
Now that we got the hang of this new way to write each term without the floor symbol,
let’s evaluate some more terms to see if a pattern emerges.
We already know the first three terms, so let’s write them once again.
The fourth term is the floor of 5 cubed over 7, which leaves a remainder of 6 when divided
by 7.
So I can replace that term with 5 cubed over 7 minus 6/7.
Next term is the floor of 5 to the 4th over 7.
That’s 625 over 7 which leaves a remainder of 2.
So we’ll write that as 5 to the 4th over 7 minus 2/7.
Next term is the floor of 5 to the 5th over 7.
That’s 3125 over 7 which leaves a remainder of 3.
So we’ll write that as 5 to the 5th over 7 minus 3/7.
And now it looks like we’re in some hot water.
I don’t see any pattern emerging, and to make matters worse, these calculations are
about to get out of control.
The floor of 5 to the 6th divided by 7?
Since it’s a competition problem, calculators are not allowed.
So how on earth do we do this efficiently?
Have no fear!
A famous Frenchman is going to come to the rescue.
Can you guess who it is?
It’s Pierre de Fermat!
And he has something to tell us: Bonjour mes amis.
Avez-vous des difficultés en mathématiques?
Yes, Pierre, we are having some trouble here.
Do you have a handy tool to help us out?
Indeed he does.
And it’s Fermat’s Little Theorem.
This little number theory gem is perfect for keeping track of remainders with large exponents.
It states that any number a raised to some prime p is congruent to that same number a
when divided by p.
The only problem is the exponent here is 6, which is not prime.
But if we divide both sides of Fermat’s little Theorem by a, we get this.
And that’s exactly what we need.
Since 6 is one less than 7, which is prime, and since we’re dividing by 7, the theorem
tells us on the spot, with literally no calculation involved, that the remainder is 1.
So, using our little trick, we now can rewrite this term without the floor function.
And here are the first 7 terms, fully written out without the floor.
Did you notice that the 7th term we just found cycles back to subtracting 1/7, which we started
with?
Maybe we also have our pattern.
Could the fractional parts loop in cycles of 6 in the sequence 1/7, 5/7, 4/7, 6/7, 2/7,
3/7 and back to 1/7?
To see if this is true, we need one more modular arithmetic formula.
It simply states that the modulus of a product is the product of the moduli.
Let’s apply this formula to see if the pattern holds true, starting with 5 to the 7th over
7.
Using our rules of exponents, 5 to the 7th mod 7 can be written as 5 to the 6th times
5 to the first mod 7.
And now using the formula above, that’s equivalent to 5 to the 6 mod 7 times 5 to
the first mod 7.
We just calculated 5 to the 6 mod 7, which is 1, and 5 mod 7 is just 5.
So 1 times 5 is 5 and that maintains the pattern perfectly!
And now, I’m going to leave it to you as an exercise to show that the next 4 terms
continue the pattern as shown on the left.
So now we’re ready to finish off this problem.
The sum looks like this.
And now let’s pull out 1/7 from each term.
The top sum should look familiar.
That’s exactly what we calculated when we removed the floor function.
We determined that to be 5 to the 2023 minus 1 over 28.
And the bottom sum is easy.
Those 6 digits, which add up to 21, will repeat 337 times to get us to 2022, which means there
will be a final one left over to get us to the 2023rd term.
Now just simplify a bit.
And combining the two fractions so they have a common denominator of 28 we get our final
result.
And there’s our answer!
Congratulations if you got this correct!
Let me know in the comments below if you got the answer and how you got it.
And be sure to subscribe for a new video every week featuring puzzles, problems, applications,
and explorations.
Thanks for watching and happy new year!