Prove that integer $n$ exists such that $n^2$ begins with $201120122013$.

I've found a few different formulations of the problem where the given digits are different, so my guess is that it actually works for any array of integers. But I don't know how to solve it, nor where to start. I'm not that good in number theory.

-
Look at $(n+1)^2-n^2$ –  deinst Feb 6 '12 at 21:41
@daniel: According to online calculator, $448464^2=201119959296$. Besides, the problem is to prove that such integer exists, not to find it (I guess it's enormous). –  Lazar Ljubenović Feb 6 '12 at 21:50
@deinst: Thanks for reply. That doesn't help me really though, I don't understand the general idea behind the problem or your hint. –  Lazar Ljubenović Feb 6 '12 at 21:51
Hint: can you see why for a large enough tail, there will be a square in the range: [201120122013000...0, 201120122013999...9]? Think about making the tail very large, and then the range of numbers is large; think what guarantees that you'll be able to trap a square in that range (based on deinst's comment). –  davin Feb 6 '12 at 21:52
I have removed several off-topic comments. @Artes, you should be much more respectful and constructive in the future. –  Zev Chonoles Feb 7 '12 at 2:03

Consider $y = 10^k\sqrt{201120122013}$ then $\lceil y\rceil^2 < (y+1)^2 = 10^{2k} 201120122013 + 2y + 1$. Now $2y+1<10^{k+12}$ so if $k>12$ the leading digits of $\lceil y\rceil^2$ are 201120122013.

-
Nitpick: $10^{k+12}$ not $10^k+12$. Nice answer. –  Matthew Daws Feb 6 '12 at 21:58
@Matthew Damn nitpicky tex parser. –  deinst Feb 6 '12 at 22:01
I understand the basic concept behind the ceiling function, but I'm still inexperienced with it. Why is $2y+1<10^{k+12}$ and how does that yield your following statement? –  Lazar Ljubenović Feb 6 '12 at 22:14
@lazar Because $2*\sqrt{201120122013} < 10^12$. I actually could have made it much smaller. If $k>12$ then $2k>k+12$ and $10^{2k}>10^{k+12}$ so $\lceil y\rceil^2$ has the correct leading digits. This is of course overkill as other answers have shown. –  deinst Feb 6 '12 at 22:24
Now I understand everything. Even though it's overkill, it still proves that such integer exists (and even that there are infinite such integers). This is the kind of answer I was looking for, simple yet elegant. Thanks a lot. –  Lazar Ljubenović Feb 6 '12 at 22:38

$$44846418141586293^2 = 2011201220130000177943626365481849$$

-
I crawled decimal expansions for square roots. –  ncmathsadist Feb 6 '12 at 21:55
$n = 448464181416$ also works and seems to be the smallest such integer. I only found it based on your answer, however. –  JavaMan Feb 6 '12 at 22:01
there are two lines to crawl. The first one works. You can also crawl 1418168.2622770825 –  ncmathsadist Feb 6 '12 at 22:04
141816826227708255**2 = 20112012201300000008048309395145025 –  ncmathsadist Feb 6 '12 at 22:06
Cool. $n = 141816826228$ works also and is again the smallest such number I can find. –  JavaMan Feb 6 '12 at 22:09

You're right that there's a general procedure for this - it's based on approximations of the square root. Suppose we have a number $n^2$ of length $d$ digits - in other words, $10^{d-1}\leq n^2 \leq 10^d$. Then saying that the first $12$ digits of $n^2$ are $201120122013$ is the same as saying that the first $12$ digits (after the decimal point) of $n^2/10^d$ are $0.201120122013$; or in other words, that $0.201120122013 \leq n^2/10^d \le 0.201120122013+10^{-12}$.

Now, let $t = \sqrt{0.201120122013} = .44846418141586\ldots$ and consider the numbers $t_i = \lceil10^i\cdot t\rceil$ - these correspond to taking longer and longer 'overestimates' of the digits of $t$; for instance, $t_1 = 5, t_2 = 45, t_3 = 449,\ldots$ Then we know that $0\leq t_i-10^i\cdot t\lt 1$ (by the definition of the ceiling function), so we know that $0\leq t_i^2-10^{2i}\cdot t^2 = (t_i-10^i\cdot t)\cdot (t_i+10^i\cdot t) \lt t_i+10^i\cdot t \lt 2(10^i\cdot t+1)$; since $t$ is less than $1$ then the last value is certainly less than $2\cdot 10^i$. But we can divide this by $10^{2i}$ to get $t^2\leq t_i^2/10^{2i}\lt t^2+ 2\cdot10^{-i}$ - or in other words, $0.201120122013 \leq t_i^2/10^{2i} \le 0.201120122013+2\cdot10^{-i}$ - and all we have to do to get this to match up with our original inequality is to take an $i$ such that $2\cdot 10^{-i}$ is even less than $10^{-12}$ - for instance, $i=13$ will do. This gives us an answer that $t_{13} = 4484641814159$ squares to $t_{13}^2=20112012201303326692877281$.

-