EDIT: Could have used Euler and $2^{20}$ to avoid the middle section. @below because I did not qualify so I had time to write it up.

@above How did you get a solution so fast?

$ 2^19+20$ also works if ur nervous. i'lll add in solution soon.

This problem was proposed by me. One answer is $n = 20 + 2^{19} = 524308$. First, observe that \begin{align*} 5^n &\equiv 5^{20} \pmod{5^{20}} \\ 5^n &\equiv 5^{20} \pmod{2^{20}} \\ \end{align*}the former being immediate and the latter since $\varphi(2^{20}) = 2^{19}$. Hence $5^n \equiv 5^{20} \pmod{10^{20}}$. Moreover, we have \[ 5^{20} = \frac{1}{2^{20}} \cdot 10^{20} < \frac{1}{1000^2} \cdot 10^{20} = 10^{-6} \cdot 10^{20}. \]Thus the last $20$ digits of $5^n$ will begin with six zeros. This completes the proof.

sunny2000 wrote: $ 2^{19}+20$ also works if ur nervous. i'lll add in solution soon. Fixed!

v_Enhance wrote: This problem was proposed by me. One answer is $n = 20 + 2^{19} = 524308$. First, observe that \begin{align*} 5^n &\equiv 5^{20} \pmod{5^{20}} \\ 5^n &\equiv 5^{20} \pmod{2^{20}} \\ \end{align*}the former being immediate and the latter since $\varphi(2^{20}) = 2^{19}$. Hence $5^n \equiv 5^{20} \pmod{10^{20}}$. Moreover, we have \[ 5^{20} = \frac{1}{2^{20}} \cdot 10^{20} < \frac{1}{1000^2} \cdot 10^{20} = 10^{-6} \cdot 10^{20}. \]Thus the last $20$ digits of $5^n$ will begin with six zeros. This completes the proof. Congratulations v_Enhance on getting a problem accepted!

Wait doesn't $9*2^8+4$ work? Edit: apparently not. I used Euler's theorem so that the last digits would be 000000625 My logic: So $5^{9*2^8+4}\equiv 625 mod 5^9$ (right...) and $5^{9*2^8+4}\equiv 625 mod 2^9$ since $5^{2^8}\equiv 1 mod 2^9$

Don't think so. http://www.wolframalpha.com/input/?i=5%5E580

If you want $5^n\equiv 625 \mod 5^9$ and $n$ not equal to 4, you clearly need $n>9$. In that case, $5^9|5^n-625$, which means $5^9|625$ which is false.

Or just notice that $5^n\equiv 0 \pmod{5^9}$ for $n\ge 9$.

FlakeLCR wrote:

Exactly how I did it.

if v_Enhance said that one answer is $20+2^{19}$, is there another one?

Another answer is $n = 20 + 2^{18}$, much the same proof. I think the smallest $n$ is $n=3375$, though I don't think there was a way you could have found that during the contest.

Do you still get 7 for proving n exists without finding it?

vitriolhumor wrote: Do you still get 7 for proving n exists without finding it? Yes, though I have yet to see a solution which does this.

v_Enhance wrote: I think the smallest $n$ is $n=3375$, though I don't think there was a way you could have found that during the contest. "Say it takes $ab$ seconds to multiply an $a$-digit integer by a $b$-digit integer..."

But if we use the Fast Fourier Transform then we can do it in around $a\log a$, assuming $a$ is larger. And to compute $5^n$ we only need $c\log n$ multiplications, up to a $O(n)$ amount of digits, giving us around $n(\log n)^2$ time to compute that. It is linear time to check for zeroes. Then sum from $1$ to $n$ to bring it to about $O(n^2(\log n)^3)$ time*.

Actually, it would be interesting to change $5$ to other things (not a power of $10$) and find the minimal exponent; it obviously exists, since for every $a$ not a power of ten, there exists $n$ such that $a^n$ starts with any fixed prefix, like $10\cdots 0$. It's only $O(n^2(\log n)^3)$ time as an algorithm. However, boundedness might only be determinable by the constants in Kronecker's theorem... which is possible, true, but annoying. I'm going to see if we can show $n < 10^6$ exists with $5^n$ starting with $x000000$.

asdf334 wrote: 2^18 + 20 gang That’s what I found at first, but I made it easier by doing $2^{19}+20$ Ig it’s not that hard to show that $5^{2^{18}}\equiv 1\pmod{2^{20}}$

Can someone please PM me the strategy for these kinds of general decimal expansion problems?

*I never expected this kind of random comment would pop out of asdf, with the post having no other content...But I will leave reporting for someone else who wants to.*

Any way other than DottedCaculator’s to show that $n=3375$ works?

of course not

maybe there is

$n=2^{19}+20$ works; clearly we have $n<10^6$. We clearly have $5^n \equiv 5^{20} \pmod{5^{20}}$. Further, we have $$5^n \equiv 5^{20} \pmod{2^{20}} \iff 5^{n-20} \equiv 1 \pmod{2^{20}},$$which is true by Euler totient, so by CRT $5^n \equiv 5^{20} \pmod{10^{20}}$. Additionally, $$5^{20}\cdot 2^{20}=10^{20} \implies 5^{20}\cdot 10^6<10^{20} \implies 5^{20}<10^{14},$$so the last $20$ digits of $5^n$ begin with 6 consecutive zeroes as desired. $\blacksquare$

I claim that $n=2^{18}+20 = 262164$ works. Claim: $2^{20} \mid 5^n-5^{20}.$ Proof: By Lifting the Exponent lemma, $$\nu_2(5^{n-20} - 1) = \nu_2(5-1) + \nu_2(2^{18}) + \nu_2(5+1) - 1 = 20.$$ Now I claim that the last $20$ digits of $5^n$ is six zeros followed by the decimal representation of $5^{20}$, which solves the problem. First, note that $5^{20}$ has $\lceil{20 \cdot \log_{10}5 \rceil} = 14$ digits, so this claim amounts to showing that $5^{2^{18}+20} \equiv 5^{20} \pmod {2^{20} \cdot 5^{20}}.$ This congruence is obviously true modulo $5^{20}$ and follows modulo $2^{20}$ due to the lemma, so our value of $n$ works and is less than $10^6$.

Should’ve been swapped with JMO/1 I think. We claim $n = 2^{19} + 20$, which is clearly less than $10^6$ works. First, note that $5^n\equiv 5^{20}\pmod{5^{20}}$. Additionally, $$5^n\equiv 5^{2^{19} + 20}\equiv 5^{20}\pmod{2^{20}}.$$Hence, $5^n\equiv 5^{20}\pmod{10^{20}}$. Now, it remains to show that $5^{20}$ has at most $14$ digits, as then the last $20$ digits of $5^n$ will be $5^{20}$ preceded by $\ge 20 - 14 = 6$ zeros, which finishes. Indeed, \[ 5^{20} < 10^{14}\iff 5^6 < 2^{14}\iff 15625 < 16384,\]which is true, so we are done.

Note $2^{17}+18<10^6$. We claim that there are six consecutive zeroes in $5^{18+2^{17}}$. We claim that $$5^{18+2^{17}}\equiv 5^{18}\pmod{10^{18}}$$Clearly, $$5^{18+2^{17}}\equiv 5^{18}\pmod{5^{18}}$$So, it suffices to show $$5^{18+2^{17}}\equiv 5^{18}\pmod{2^{18}}.$$Since $\phi(2^{18})=17$, $5^{2^{17}}\equiv 1\pmod{2^{18}}$. So, $$5^{18+2^{17}}\equiv 5^{18}\pmod{2^{18}}.$$ So, $5^{18+2^{17}}-5^{18}$ has 18 zeroes at the end. We have $5^{10}<10^6$, so $5^{20}<10^{12}$, so $5^{18}<10^{11}$. So, $5^{18}$ has at most 11 digits. So, when we add $5^{18}$ to $5^{18+2^{17}}-5^{18}$, we get a number with at least 18-11=7 consecutive zeroes.

I believe this solution works, but I am rather bad at NT. Suppose that such an $n$ does exist; then, if we take $5^n \pmod {10^k}$ for some $k$, this residue must be less than $10^{k-6}$ to have six consecutive zeroes. Note that since $5^n \equiv 5^k \pmod {5^k}$, we can try to make a construction for $n$ such that $5^n \equiv 5^k \pmod {10^k}$ and $5^k < 10^{k-6}$. Notice that we should aim for $k=20$, as \[ 5^{20} = 10^{20} \div 2^{20} < 10^{20} \div 10^6 = 10^{14} \]To find the $n$ such that $5^n \equiv 5^{20} \pmod {10^{20}}$, we must also have $5^n \equiv 5^{20} \pmod {2^{20}}$, or $5^{n-20} \equiv 1 \pmod {2^{20}}$, which implies $2^{19} \mid n-20$. Notice that $n = 2^{19}+20$ satisfies this condition, thus $5^n \equiv 5^{20} \pmod {10^{20}}$, thus proving the existence.

I got 6 consecutive zeroes on USAJMO Take $n=2^{19}+20$ By Euler Totient Theorem, $5^{2^{19}}\equiv1(\mod2^{20})$ Let it be $a\cdot2^{20}+1$ Then $5^{2^{19}+20}=a\cdot10^{20}+5^{20}$. Since $5^{20}=\dfrac{10^{20}}{2^{20}}<10^{14}$, the 14th to 19th digits of $5^{2^{19}+20}$ are all zero, satisfying the conclusion. Full proof here: https://infinityintegral.substack.com/p/usajmo-2016-contest-review

$n = 2^{19} + 22$ works. To see this, notice that $5^{22}$ has $16$ digits, and notice that \begin{align*} \nu_5 \left(5^{2^{19}+22} - 5^{22}\right) &= 22 \\ \nu_2 \left(5^{2^{19} + 22} - 5^{22}\right) = \nu_2(5^2-1)+\nu_2(2^{19}) &= 22 \end{align*}Hence $5^n - 5^{22}$ has $22$ zeroes at the end of its decimal representation. The result easily follows.

This post includes some of my thought process on this. So if you were at some point some enjoyer of bashing perfect powers (like 7 yrs old me :p), you would've noticed that it's common to see powers of $5$ as the last digits of a bigger power of $5$, so it is reasonable to consider some $k,\ell$ for which $5^n \equiv 5^k \pmod{10^{\ell}}$, since we pretty much can take care of $5^{\ell}$ (and also this means we would need $k \ge \ell$ so for bounding reasons the most optimal choice is $k=\ell$) we will focus on $\pmod{2^{\ell}}$, now notice that $\phi(2^{\ell})=2^{\ell-1}$ and $\gcd(2,5)=1$. therefore $5^{2^{\ell-1}+\ell} \equiv 5^{\ell} \pmod{2^{\ell}}$ so we have that if we set $n=2^{\ell-1}+\ell$ then $5^n \equiv 5^{\ell} \pmod{10^{\ell}}$, so now we just need to make $10^{\ell}$ as distant as possible from $5^{\ell}$, which happens when $\ell$ is maximal, and since $2^{20}>10^6>2^{19}+2$ we have that $\ell=20$ is the maximal we can choose so we have $5^n=5^{20} \pmod{10^{20}}$, and since $5^{20}=\frac{10^{20}}{2^{20}}<\frac{10^{20}}{10^6}$ we have that $\pmod{10^{20}}$ the first six numbers are $000000$ thus we are done .

The problem is equivalent to finding an integer $n$ such that there exists $k \in \mathbb{Z}^+$ that satisfies the inequality $$5^n \mod 10^k < 10^{k-6}$$Starting from this expression, we have: \[ 5^n \mod 10^k = 5^k (5^{n-k} \mod 2^k) < 10^{k-6} \]\[ \Rightarrow 5^{n-k} \mod 2^k < \frac{10^{k-6}}{5^k} = \frac{2^k}{10^6} \]Setting $n = 2^{k-1} + k$, by Euler's theorem, we have: \[ 5^{n-k} \equiv 5^{2^{k-1}} \equiv 1 \pmod{2^k}. \]Setting $n = 2^{19} + 20 = 524288 + 20 = 524268 < 10^6$, we obtain: \[ 5^{n-20}\pmod{2^{20}}=1< \left( \frac{1024}{1000} \right)^2 = \frac{2^{20}}{10^6}. \]Therefore, $n = 2^{19} + 20$ works.