Maths Olympiad Prep

Library / /253 of 860

Number theory Difficulty 5.0 AIME, harder Find the answer

Find the smallest nn such that nn! ends in 290 zeroes.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Each 0 represents a factor of 10=2510=2 \cdot 5. Thus, we wish to find the smallest factorial that contains at least 290 2's and 290 5's in its prime factorization. Let this number be nn!, so the factorization of nn! contains 2 to the power pp and 5 to the power qq, where p=n2+n22+n23+ and q=n5+n52+n53+p=\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{2^{2}}\right\rfloor+\left\lfloor\frac{n}{2^{3}}\right\rfloor+\cdots \text { and } q=\left\lfloor\frac{n}{5}\right\rfloor+\left\lfloor\frac{n}{5^{2}}\right\rfloor+\left\lfloor\frac{n}{5^{3}}\right\rfloor+\cdots (this takes into account one factor for each single multiple of 2 or 5 that is n\leq n, an additional factor for each multiple of 222^{2} or 525^{2}, and so on). Naturally, pqp \geq q because 2 is smaller than 5. Thus, we want to bring qq as low to 290 as possible. If q=n5+n52+n53+q=\left\lfloor\frac{n}{5}\right\rfloor+\left\lfloor\frac{n}{5^{2}}\right\rfloor+\left\lfloor\frac{n}{5^{3}}\right\rfloor+\cdots, we form a rough geometric sequence (by taking away the floor function) whose sum is represented by 290n/511/5290 \approx \frac{n / 5}{1-1 / 5}. Hence we estimate n=1160n=1160, and this gives us q=288q=288. Adding 10 to the value of nn gives the necessary two additional factors of 5, and so the answer is 1170.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.