We notice the following: If there exists some $N$ such that $2\cdot 10^{N+1}\!\!\!\not|(\overline{a_{N}\cdots a_{1}a_{0}})^{2}+999$, then $\forall n\geq N$ $v_{10}((\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999)\leq N+1$. The same holds for $(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999$. Now we have the following two cases... Case 1. There exists some $N$ such that $2\cdot 10^{N+1}\!\!\!\not|(\overline{a_{N}\cdots a_{1}a_{0}})^{2}+999$ Let $f(n)=\frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999}$. If $v_{10}((\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999)$ can be arbitrarily big, then $v_{10}(f(n))$ can be arbitrarily big. But for $n\geq M$, $f(n)<100$, so contradiction. Therefore there exists some $K$ such that $2\cdot 10^{K+1}\!\!\!\not|(\overline{b_{K}\cdots b_{1}b_{0}})^{2}+999$. Let $\max\lbrace{N,K\rbrace}=T$. We notice that for $n\geq T+1$, $v_{10}((\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999)=v_{10}((\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999)$, and the same for $(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999$. Let $\lim_{n\rightarrow \infty}v_{10}((\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999)=X$, $\lim_{n\rightarrow \infty}v_{10}((\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999)=Y$. Of course $X\leq Y$ must hold. For $n>\max\lbrace{T,X+2,Y+2,M\rbrace}$ $$f(n+1)=\frac{(\overline{b_{n+1}\cdots b_{1}b_{0}})^{2}+999}{(\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999}=10^{Y-X}\cdot \frac{10^{2n+2-Y}b_{n+1}^{2}+2\cdot 10^{n+1-Y}b_{n+1}\cdot \overline{b_{n}\cdots b_{1}b_{0}}+\frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{10^{Y}}}{10^{2n+2-X}b_{n+1}^{2}+2\cdot 10^{n+1-X}b_{n+1}\cdot \overline{a_{n}\cdots a_{1}a_{0}}+\frac{(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999}{10^{X}}}$$Comparing with $f(n)=10^{Y-X}\cdot\frac{\frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{10^{Y}}}{\frac{(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999}{10^{X}}}$, we see that $\frac{f(n+1)}{10^{Y-X}}\equiv \frac{f(n)}{10^{Y-X}} \pmod {1000}$. But for $n\geq M$, $f(n)< 100$, so we get $f(n+1)=f(n)$. This means $f(n)$ becomes constant eventually. Let this constant $c$. Some tedious calculationsUsing some properties related to proportionality, we see that $c=\frac{\overline{b_{n+1}\cdots b_{1}b_{0}}+\overline{b_{n}\cdots b_{1}b_{0}}}{\overline{a_{n+1}\cdots a_{1}a_{0}}+\overline{a_{n}\cdots a_{1}a_{0}}}$ for big $n$. Using the same property again, we see that $c=\frac{10b_{n+1}+b_{n}}{10a_{n+1}+a_{n}}$ for big $n$. If $ca_{n}\neq b_{n}$, $b_{n+1}>ca_{n+1}$, so $b_{n+1}\not\equiv ca_{n+1} \pmod{10}$, which contradicts $c=\frac{10b_{n+2}+b_{n+1}}{10a_{n+2}+a_{n+1}}$. Therefore $c=\frac{b_{n}}{a_{n}}$ for all big $n$, so $c=\lim_{n\rightarrow \infty}f(n)=c^{2}$. This means $c=1$. Therefore $c=1$, and $a_{n}=b_{n}$ must hold for all $n\geq 0$. Case 2. For all $N\geq 0$, $2\cdot 10^{N+1}|(\overline{a_{N}\cdots a_{1}a_{0}})^{2}+999$ We can easily see that for $N\geq 0$, $2\cdot 10^{N+1}|(\overline{b_{N}\cdots b_{1}b_{0}})^{2}+999$ must also hold. Since $a_{0}^{2}+999|b_{0}^{2}+999$ and $(\overline{a_{1}a_{0}})^{2}+999|(\overline{b_{1}b_{0}})^{2}+999$, we get $a_{0}=b_{0}$, $a_{1}=b_{1}$. Now we prove the following claim. Claim. After $a_{0},a_{1},\cdots,a_{n}$ satisfying the assumption of Case 2 for $N=0,1,\cdots,n$ has been decided, there exists a unique $a_{n+1}$ satisfying the assumption of Case 2 for $N=n+1$. Proof of ClaimLet $(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999=2\cdot 10^{n+1}\cdot l$. Then $(\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999=10^{2n+2}a_{n+1}^{2}+2\cdot 10^{n+1}a_{n+1}\cdot\overline{a_{n}\cdots a_{1}a_{0}}+2\cdot 10^{n+1}\cdot l$. Since $2\cdot 10^{n+2}|10^{2n+2}$, $2\cdot 10^{n+2}|(\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999 \Leftrightarrow 10|a_{n+1}\cdot\overline{a_{n}\cdots a_{1}a_{0}}+l$ Since $\overline{a_{n}\cdots a_{1}a_{0}}$ is coprime with $10$, there exists a unique $a_{n+1}$ among $\{0,1,2,\cdots ,9\}$ such that $10|a_{n+1}\cdot\overline{a_{n}\cdots a_{1}a_{0}}+l$. By the claim, we see that the value of $a_{0}$ totally determines the sequence $\{a_{n}\}_{n\geq 0}$ for Case 2. The same holds for $\{a_{n}\}_{n\geq 0}$, so since $a_{0}=b_{0}$, we get that $a_{n}=b_{n}$ for all $n\geq 0$. Therefore in both cases, $a_{n}=b_{n}$ for $n\geq 0$. $\blacksquare$

WLOG let's assume that $M > 10^{10^{10^{10}}}$. For each $n$, let $c_n = \frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{(\overline{a_n \cdots a_1a_0})^2+999}.$ From the condition of the problem that $a_n, b_n \neq 0$ for $n \ge M$, we know for $n \ge M$ that $c_n \in \{1, 2, \cdots, 100\}.$ If there were infinitely many $n \in \mathbb{N}$ with $c_n = 1$, then we'd have $\overline{b_{n}\cdots b_{1}b_{0}} = \overline{a_n \cdots a_1a_0}$ for infinitely many $n \in \mathbb{N}$, and hence we'd be done. Otherwise, assume for contradiction that only finitely many $n \in \mathbb{N}$ satisfied $c_n = 1$, suppose that $M$ is such that all $n$ with $c_n = 1$ are less than $M$. Note that since $M$ is big ($>10^{10^{10^{10}}}$), we know that $c_n$ is not a perfect square for $n \ge M.$ Call $n \ge M$ $k$-type if $c_n = k$. From our previous work, we know that all $n \ge M$ are of at most $90$ different types. Hence, among any $91$ consecutive integers $m, m+1, m+2, \cdots, m+90$ with $m \ge 10^{2M}$, we know that two are of the same type, say $m+a$ and $m+b$ are both $k-$type for $k \in \{1, 2, \cdots, 100\}$ not a perfect square, where $a < b$. For convenience, we will let $B_1 = \overline{b_{m+a}\cdots b_{1}b_{0}}, B_2 = \overline{b_{m_b}\cdots b_{1}b_{0}}, A_1 = \overline{a_{m+a} \cdots a_1a_0}, A_2 = \overline{a_{m+b} \cdots a_1a_0}$. Now, let $\{(x_1, y_1), (x_2, y_2), \cdots, (x_t, y_t)\}$ be the pairs of positive integers which satisfy $x_i < 10^{10^{10}}$ and $\frac{x_i^2-1}{y_i^2} = k.$ It's then well-known that there exists $1 \le v \le t$ with: $$A_2 = A_1x_v + B_1ky_v, B_2 = A_1y_v + B_1x_v.$$Hence, we have that: $$A_1(x_v - 1) + B_1ky_v \equiv A_1y_v + B_1(x_v-1) \equiv 0$$modulo $10^{m+a+1}.$ Therefore, we have that: $$10^{m+a+1} \mid y_v(A_1(x_v - 1) + B_1ky_v) - (x_v-1)(A_1y_v + B_1(x_v-1)) = B_1(ky_v^2 - x_v^2 + 2x_v - 1) = 2x_vB_1.$$Since $v_{5} (x_v) < 2 \cdot 10^{10^{10}} < M-1, v_2 (x_v) < 5 \cdot 10^{10^{10}} < M-1$, we must have that $10^{M+1} | B_1.$ However, this implies that $b_M = 0$, contradicting the conditions of the problem. $\square$

Define $A_n =\left( \overline{a_na_{n-1}\dots a_1a_0 }\right) $ and $B_n =\left( \overline{b_nb_{n-1}\dots b_1b_0 }\right) $. Set $K_n= \frac {B_n^2+999}{A_n^2+999}$. First note that we have : $$A_n\equiv A_{n-1} \pmod {10^n} \quad B_n\equiv B_{n-1} \pmod {10^n} $$$$B_n^2+999=K_n(A_n^2+999) \quad B_{n-1}^2+999=K_{n-1}(A_{n-1}^2+999)$$ This gives $K_n (A_n^2+999) \equiv K_{n-1}^2(A_n^2+999) \pmod {10^n}$ Claim : We have that one of the following cases holds : $10^n \mid A_{n-1}^2+999$ for all $n\ge 1$. $K_n$ is eventually constant Proof : Assume that there is a $N$ such that there is some prime $p\in \{2,5\}$ such that $p^N \nmid A_{N-1}^2+999$. Note that because of the congruence $A_n\equiv A_{N-1} \pmod {p^N}$ we have that for all $n\ge N-1$, $\nu_p(A_n^2+999)<N$. Conisder $d_n = \operatorname {gcd}(10^n,A_{n-1}^2+999)$. We have $d_n \mid \frac {10^n}{p^n}\cdot p^N$, so we have the congruence: $$K_n =K_{n-1} \pmod {\tfrac {10^n}{d_n}} \implies K_n =K_{n-1} \pmod {p^{n-N}}$$ Note that we have a dumb size bound on $K_n$ : $$K_n =\frac { B_n^2+999}{A_n^2+999} < \frac {10^{2n+2}+999}{10^{2n}+999} <100$$ So take $p^{n-N} >100$ and the claim is proven. $\square$ Case 1 : Assume $10^{n+1} \mid A_n^2+999 \mid B_n^2+999$ for all $n \ge 0$ We actually prove that this divisibility can be improved. We claim $2\cdot 10^n \mid A_{n-1}^2+999$ for all $n\ge 1$. We have : $$A_n^2+999 = (10^na_n+A_{n-1})^2+999 \equiv A_n^2+999 = 2\cdot 10^na_n + A_{n-1}^2+999 \pmod {2\cdot 10^{n}}$$ So we have $2\cdot 10^n \mid 10^{n+1} \mid A_n^2+999$, so $2\cdot 10^n \mid A_{n-1}^2+999$. We prove $a_n=b_n$ for all $n \ge 0$ with induction on $n$. Check $n=0,1$ by direct calculation. Now assume $a_k=b_k$ for all $k<n$. We only care about $A_{n-1}=B_{n-1}$. We have : $$ A_n^2+999 = 2\cdot 10^na_nA_{n-1}+A_{n-1}^2+999 \equiv 0 \pmod {2\cdot 10^{n+1}} \iff a_nA_{n-1} + \frac {A_{n-1}^2+999}{2\cdot 10^n} \equiv 0 \pmod {10}$$ Similarly we have: $$b_nB_{n-1} + \frac {B_{n-1}^2+999}{2\cdot 10^n} \equiv 0 \pmod {10}$$ This gives $a_n \equiv b_n \pmod {10}$. Since $a_n,b_n<10$, we get $a_n=b_n$ and we are done by induction. $\blacksquare$ Remark on strengthening divisibility conditionThe obvious way to try induction doesnt work because we are missing out on a extra 2 ! With the weak condition, we can only conclude $a_n \equiv b_n \pmod 5$, which isnt sufficient. So this gives the idea of strengthening the divisibility which fortunately isnt too hard to prove. Case 2 : $K_n$ is eventually constant. NT flavoured arguements dont really work here, so we try glorified size, i.e analysis type arguements So we have that for all $n>N$ $B_n^2+999=K(A_n^2+999)$. First note that for all large $n$, we have that $\frac {B_n^2}{A_n^2} \approx \frac {B_n^2+999}{A_n^2+999} =K$. In other words $\lim_{n\rightarrow \infty} \frac {B_n}{A_n} = \sqrt K$. Define $C_n = \frac {B_n}{A_n}-\sqrt K$, so that $\lim_{n\rightarrow \infty} C_n=0$. Next using the equalities : $$B_n^2+999 = K(A_n^2+999) \quad B_{n-1}^2+999 = K(A_{n-1}^2+999)$$$$B_n=10^nb_n+B_{n-1} \quad A_n=10^na_n+A_{n-1}$$ We have the following equality (after some manipulation) : $$ \frac {10^n}{A_{n-1}}(b_n^2-Ka_n^2) =2(Ka_n- b_n \frac {B_{n-1}}{A_{n-1}})$$$$\iff \frac {10^n}{A_{n-1}}(b_n^2-Ka_n^2) =2(Ka_n- b_n (C_{n-1}+ \sqrt K))$$$$\iff \frac {10^n}{A_{n-1}}(b_n^2-Ka_n^2) = -2\sqrt K(b_n-\sqrt K a_n)-2b_nC_{n-1}$$$$\iff (b_n-\sqrt Ka_n) \left( \frac {10^n}{A_{n-1}}(b_n+ \sqrt Ka_n)+2\sqrt K \right) = -2b_nC_{n-1}$$ Call the above equation as $\spadesuit$. Take $n\rightarrow \infty$ in $\spadesuit$. Since $b_n$ takes finitely many values, RHS goes to $0$. Since the second factor of LHS is always positive, (in particular it's always $\geq 2\sqrt K$), we have $\lim_{n\rightarrow \infty} b_n-\sqrt Ka_n =0$. Note that $b_n-\sqrt Ka_n$ takes only finitely many values, so there exists a $L$ such that for all $n>L$, we have $b_n=\sqrt K a_n$. Plugging in $n>L$ in the equation $\spadesuit$. This gives $C_{n-1}=0$, so we have $\frac {B_n}{A_n} = \sqrt K$ for all large $n$. Plugging into the equation $B_n^2+999=K(A_n^2+999)$, we get $K=1$. In other words, $A_n=B_n$ holds for all large $n$. By definition of $A_n,B_n$, we conclude that $a_n=b_n$ for all $n\ge 0$ and we are done. $\blacksquare$

Define $A_n =\left( \overline{a_na_{n-1}\dots a_1a_0 }\right) $ and $B_n =\left( \overline{b_nb_{n-1}\dots b_1b_0 }\right) $. Let $u_n=A_n/10^n,v_n=B_n/10^n$. Let $k_n=\sqrt{\frac{B_n^2+999}{A_n^2+999}}$.$K_n$ has only finitely many possible values. Assume for contradiction that $K_n \neq 1$ for some $n$,then it holds for any positive integer $n$.It is also easy to draw a contradiction if $K_n \in Z$. We prove that there exists a finite set $S$,such that for all $\epsilon>0$,there exists an integer $N$ such that for all $n>N$,there exists $t \in S,|u_n-t|<\epsilon$ (and a similar argument for $v_n$) In fact,we have $$\frac{b_{n+1}+v_n}{a_{n+1}+u_n}\to K_{n+1},\frac{v_n}{u_n}\to K_n$$Clearly $\frac{b_{n+1}}{a_{n+1}}\neq K_n$(which is not a rational number),the system of equations has a unique solution. The above claim indicates that there exists an $L$ such that we can uniquely determine $a_{n-L}$ from $a_n,a_{n-1},\cdots,a_{n-L+1}$.This easily yields that $a_n$ is eventually periodic,and so is $b_n$.However,this indicates that $\frac{B_n}{A_n}$ converges to a rational number,a contradiction.