Perfect Square in 987654321...

Find the smallest positive integer N N such that N 2 N^2 starts with 987654321.

Note : If you use a calculator for this problem, it can be solved in under a minute. There is no need to do extensive trial and error. You could push a maximum of 100 buttons (inclusive of each digit).


The answer is 3142696806.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Calvin Lin Staff
Apr 16, 2016

First, let's consider what it means for N 2 N^2 to have starting digits of 987654321. This simply means that

987654321 × 1 0 n N 2 < 987654322 × 1 0 n 987654321 \times 10^n \leq N^2 < 987654322 \times 10^n

While it's tempting to immediately take square roots, we don't really know how to deal with 1 0 n 2 10^ \frac{n}{2} when n n is odd. Instead, we consider the cases when n n is odd / even. This gives us:

n odd: 99380.7990006118 × 1 0 k N < 99380.7990509233 × 1 0 k n \text{ odd: } 99380.7990006118 \ldots \times 10^k \leq N < 99380.7990509233 \ldots \times 10^k n even: 31426.9680529319 × 1 0 k N < 31426.968068418 × 1 0 k n \text{ even: } 31426.9680529319 \ldots \times 10^k \leq N < 31426.968068418\ldots \times 10^k

Now, we substitute increasing values of k k till we find the smallest integer N N that satisfies the inequality.

In the odd case:
When k = 0 , k = 0, we get 99480.7990006118 N < 99380.7990509233 99480.7990006118\ldots \leq N < 99380.7990509233 \ldots , which has no integer solution.
When k = 1 , k = 1, we get 994807.990006118 N < 993807.990509233 994807.990006118\ldots \leq N < 993807.990509233 \ldots , which has no integer solution.
When k = 2 , k = 2, we get 9948079.90006118 N < 9938079.90509233 9948079.90006118\ldots \leq N < 9938079.90509233 \ldots , which has no integer solution.
When k = 3 , k = 3, we get 99480799.0006118 N < 99380799.0509233 99480799.0006118\ldots \leq N < 99380799.0509233 \ldots , which has no integer solution.
When k = 4 , k = 4, we get 994807990.006118 N < 993807990.509233 994807990.006118\ldots \leq N < 993807990.509233 \ldots , which has no integer solution.
When k = 5 , k =5, we get 9948079900.06118 N < 9938079905.09233 9948079900.06118\ldots \leq N < 9938079905.09233 \ldots , which has several integer solutions, the smallest of which is 9938079901.


In the even case:
(do the same as above)
the smallest integer N N will be 3142696806. This is the answer.

Okay, this was more fun that the simpler one for 2016.

Michael Mendrin - 5 years, 2 months ago

Log in to reply

And apparently a lot harder too. Just goes to show how the right interpretation of the underlying mathematics can make a seemingly difficult problem really obvious.

Calvin Lin Staff - 5 years, 2 months ago

Log in to reply

Thank you so much sir

Anirudh Chandramouli - 5 years, 1 month ago

tq 4 the solution, sir it was clear and explanatory

Madhav Rockzz - 5 years, 1 month ago

The good thing about this is the answer is not always odd or even. I think there may be some generalization for determining whether n is odd/even.

Aditya Kumar - 5 years, 1 month ago

Log in to reply

I'm pretty sure that 3142696806 is always odd or even.

Shawn Franchi - 3 years, 5 months ago

For people who have never looked into number theory, where do 10^(n/2), 99380.799..., and 31426.968... come from?

Shawn Franchi - 3 years, 5 months ago

Log in to reply

It's not "number theory" stuff per se.

It's just evaluating 987654321 × 1 0 n \sqrt{ 987654321\times 10^n} , which depends on whether n n is odd or even.

When n n is even, we get 31426.968 1 0 n / 2 \approx 31426.968 \ldots 10^{n/2} .
When n n is odd, we get 99380.799 1 0 ( n 1 ) / 2 \approx 99380.799 \ldots 10^{ (n-1)/2 } .

Calvin Lin Staff - 3 years, 5 months ago

i used calculator. the funny thing is i got this answer 3142696806. i wanted to check if this works i squared it. the calculator was not showing the first 9 digits.

Srikanth Tupurani - 2 years, 11 months ago

Log in to reply

Part of using a calculator is knowing it's limitations, and how one can work around it.

One approach is to use a better calculator

Calvin Lin Staff - 2 years, 11 months ago

You miss a decimal point in the line " n odd . . . n \text{ odd}... ".

Tran Quoc Dat - 5 years, 1 month ago

Log in to reply

Edited thanks.

Calvin Lin Staff - 5 years, 1 month ago

I didnt get the last part could you explain what do you mean with as we vary k?

Mr Yovan - 5 years, 1 month ago

Log in to reply

We want an integer N N that satisfies the conditions. When k = 1 k=1 , is there such an integer? How about k = 2 , 3 , 4 , k = 2, 3, 4, \ldots ? What is the smallest value of N N that would result?

Calvin Lin Staff - 5 years, 1 month ago

@Andrew Tawfeek

n odd: 99380.7990006118 × 1 0 k N < 99380.7990509233 × 1 0 k n \text{ odd: } 99380.7990006118 \ldots \times 10^k \leq N < 99380.7990509233 \ldots \times 10^k

  1. What is the smallest value of n = 2 k + 1 n = 2k+1 that will allow us to find an integer N N that satisfies the above inequality?
  2. How can we determine it?
  3. What is this value of N N ?
  4. For n = 21 n = 21 , How many integers N N will there be such that N 2 N^2 starts with 987654321?

Calvin Lin Staff - 5 years, 1 month ago
Rafael Perea
Apr 20, 2016

There are only two options, since we can split 987654321 T 987654321\overline T in two different ways: 98'76'54'32'10'00'...'00 or 9'87'65'43'21'00'...'00.

(Fortunately, since there are three attempts to get the answer, but only two to choose from; we may do one and submit. If the former case fails, the latter will give the answer. If its do or die, do all cases first.)

In order to get the square root, consider a b c 2 = ( A + B + C + ) 2 = A 2 + 2 A B + B 2 + 2 A C + 2 B C + C 2 + \overline{abc\ldots}^2 = (A+B+C+\ldots)^2= A^2 + 2AB + B^2 + 2AC + 2BC + C^2 + \ldots where A = a × 1 0 k , B = b × 1 0 k 1 , C = c × 1 0 k 2 , A = a \times 10^k,\; B = b \times 10^{k-1},\; C = c\times 10^{k-2}, \ldots for some k N k \in \mathbb N .

Thus, N 2 = a b c 2 = ( A 2 ) + ( 2 A + B ) B + ( 2 ( A + B ) + C ) C + N^2 = \overline{abc\ldots}^2 = (A^2) + (2A+B)\cdot B + (2(A+B)+C)\cdot C + \ldots .

Observe that the split we made earlier corresponds to the RHS: the first term implies A = 9 (or 3); transpose the first term, then the second implies B = 9 (or 1); transpose, the second, then the third implies C = 3 (or 4); \ldots . I'll leave the computations to you.

However the next problem would be when this seemingly infinite loop ends.

I'll demonstrate using with smaller numbers... say for 3 instead of 987654321. (I'll ignore case 30'00' \ldots )

N N 1 7
N 2 N^2 3 00
A F = A = 1 A_F= A = 1 1
N 1 = N A 2 N_1 = N - A^2 2 00
B F = 2 A + B = 27 B_F=2A + B= 27 1 89
N 2 = N 1 2 N_2 = N_1 - 2 nd 11

Here you can count the number of trailing zeros and the number of digits of the nth term factor. Observe that 1 7 2 < N 2 < 1 8 2 = N 2 + B F + B + 1 N 2 = 300 + 27 + 7 + 1 11 = 324 17^2<N^2<18^2 = N^2 + B_F +B+1 - N_2 = 300 +27 + 7 + 1 - 11 = 324 . The leading digit 3 is unaffected, therefore we can stop with a new N 2 = 324 N^2 = 324 and N = 18 N = 18 .

Back to the question above, a similar scenario appears (latter case) when N 2 > 9876543210000000000 N^2 > 9876543210000000000 , and therefore, N = 3142696806 N = 3142696806 .

Nice approach​. What is the order complexity of your algorithm to find a perfect square that starts with the digits N N ?

Calvin Lin Staff - 5 years, 1 month ago
Arjen Vreugdenhil
Apr 20, 2016

Without calculator:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
        9|87|65|43|21|  |  |  |  |  | ==> 3142696806
3 x 3 = 9            |
       ---           |
          87         |
 61 x 1 = 61         |
         ----        |
          26 65      |
624 x 4 = 24 96      |
         -------     |
           1 69 43   |
6282 x 2 = 1 25 64   |
          ---------  |
             43 79 21|
62846 x 6 =  37 70 76|
            ---------+
              6 08 45|00
 628529 x 9 = 5 65 67|61
             --------+---
                42 77|39 00
  6285386 x 6 = 37 71|23 16
               ------+------
                 5 06|15 84 00
  62853928 x 8 = 5 02|83 14 24
                -----+---------
                    3|32 69 76 00
    628539360 x 0 =  |          0
                  ---+------------
                    3|32 69 76 00 00
   6285393606 x 6 = 3|77 12 36 16 36
                   --+---------------
                    -|44 42 60 16 36 ...

In the same way I checked 98|76|54|32|1 | because of the slight possibility that it would reduce the "remainders" to less than 1 more quickly.

Since the given number has nine digits, we need at least ten zeros after it so that when the asked number is squared, all the digits of the given number retain their original positions. Thus extracting the square root of 9876543210000000000, we get 3142696805.29319, the integer next to which is 3142696806

That claim is not true.

For example, if we wanted to find the smallest integer whose digits started with 100000000, we do not need "at least 10 zeros".

Calvin Lin Staff - 2 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...