13
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Look at $(n+1)^2-n^2$ $\endgroup$
    – deinst
    Feb 6, 2012 at 21:41
  • $\begingroup$ @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). $\endgroup$ Feb 6, 2012 at 21:50
  • $\begingroup$ @deinst: Thanks for reply. That doesn't help me really though, I don't understand the general idea behind the problem or your hint. $\endgroup$ Feb 6, 2012 at 21:51
  • $\begingroup$ 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). $\endgroup$
    – davin
    Feb 6, 2012 at 21:52
  • 4
    $\begingroup$ I have removed several off-topic comments. @Artes, you should be much more respectful and constructive in the future. $\endgroup$ Feb 7, 2012 at 2:03

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Nitpick: $10^{k+12}$ not $10^k+12$. Nice answer. $\endgroup$ Feb 6, 2012 at 21:58
  • 1
    $\begingroup$ @Matthew Damn nitpicky tex parser. $\endgroup$
    – deinst
    Feb 6, 2012 at 22:01
  • $\begingroup$ 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? $\endgroup$ Feb 6, 2012 at 22:14
  • $\begingroup$ @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. $\endgroup$
    – deinst
    Feb 6, 2012 at 22:24
  • $\begingroup$ 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. $\endgroup$ Feb 6, 2012 at 22:38
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

$$ 44846418141586293^2 = 2011201220130000177943626365481849 $$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .