# 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

4
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

## 3 Answers

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.

-

1
Nitpick: $10^{k+12}$ not $10^k+12$. Nice answer. – Matthew Daws Feb 6 '12 at 21:58

1
@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

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$.

-

$$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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 48, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9525993466377258, "perplexity_flag": "head"}