Number theoryDifficulty 5.2AIME, harderProve itUnited States
Problem: A positive integer n is picante if n! ends in the same number of zeroes whether written in base 7 or in base 8. How many of the numbers 1,2,…,2004 are picante?
Solution
Solution: The number of zeroes in base 7 is the total number of factors of 7 in 1⋅2⋯n, which is ⌊7n⌋+⌊72n⌋+⌊73n⌋+⋯. The number of zeroes in base 8 is ⌊a⌋, where a=(⌊2n⌋+⌊22n⌋+⌊23n⌋+⋯)/3 is one-third the number of factors of 2 in the product n!. Now ⌊2kn⌋/3≥⌊7kn⌋ for all k, since (n/2k)/3≥n/7k. But n can only be picante if the two sums differ by at most 2/3, so in particular this requires (⌊n/22⌋)/3≤⌊n/72⌋+2/3⇔⌊n/4⌋≤3⌊n/49⌋+2. This cannot happen for n≥12; checking the remaining few cases by hand, we find n=1,2,3,7 are picante, for a total of 4 values.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.