Infinitely continued string of perfect squares

Nov 2006
54
0
All the positive perfect squares 1, 4, 9, 16, 25…. are written in accordance with strictly ascending order of magnitude and without the commas, resulting in the following infinite string:

149162536496481100121144...........

Reading left to right, determine the 2010th digit in the abovementioned string.

Source: Modified and amended version of an Olympiad problem which I saw in a math periodical in 2004.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
sqrt(10) = 3.16227766...

1² to 3² have 1 digit.
4² to 9² have 2 digits.
10² to 31² have 3 digits.
32² to 99² have 4 digits.
100² to 316² have 5 digits.
317² to 999² have 6 digits.
1000² to 3162² have 7 digits.
 
Nov 2006
54
0
CRGreathouse said:
sqrt(10) = 3.16227766...

1² to 3² have 1 digit.
4² to 9² have 2 digits.
10² to 31² have 3 digits.
32² to 99² have 4 digits.
100² to 316² have 5 digits.
317² to 999² have 6 digits.
1000² to 3162² have 7 digits.
Ty CRG.

# 1-digit perfect squares = 3 --> 3*1 =3
# 2-digit perfect squares = 6 --> 6*2 =12
# 3-digit perfect squares = 22 --> 22*3 =66
# 4-digit perfect squares = 68 --> 68*4 =272
# 5-digit perfect squares = 217 --> 217*5 =1085
# 6-digit perfect squares = 683 --> 683*6 = 4098

It is now obvious that, Sum (i=1 to 6) (# i-digit perfect squares)*i > 2010

Now, Sum (i=1 to 5) (# i-digit perfect squares)*i = 3+12+66+272+1085= 1438

Also, (2010-1438)/6 = 95 + 2/6

Since 316+95 = 411, it follows that the required digit must be the second digit reading from the left in the base ten expansion of 412^2 = 169744.

In other words, the required 2010th digit is 6.

Is this result accurate?
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
K Sengupta said:
Is this result accurate?
Brute force checks out:
Code:
find(k)=my(d);for(n=1,k,d=digits(n^2);if(d<k,k-=d,return(Vec(Str(n^2))[k])))
find(2010) returns "6".
 
Feb 2010
199
0
this just blew my mind XD ... how did you guys do this? to begin with, how did you come up with the step sqrt(10) = 3.16227766 ...? I take it it's some predefined rule/law that i dunno about >.> ... and i see how using it you find out the range of perfect squares with a certain amount of digits, dat is just infinitely awesome XD Are there other applications to this? And is it always a sqrt(10) or is there more to it? Could you point me in the direction where could read up on this technique pls?
but then how do you know the number of perfect squares in each set? i get confused after the part where you add up the numbers to reach 2010 digits and find that it's somewhere in the vicinity of 6-digit perfect squares X.X What is this step (2010-1438)/6 = 95 + 2/6? and the one after it...
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Solarmew said:
to begin with, how did you come up with the step sqrt(10) = 3.16227766 ...? I take it it's some predefined rule/law that i dunno about >.>
I had never done that before, but it seemed to fit. :D

It's easy to see that 10^n is the first number that, when squared, has 2n+1 digits. To find the first number with 2n digits, find sqrt(10^(2n-1)) which is 10^(n-1) * sqrt(10). The integer below this is the last with 2n-1 digits; the integer above this is the first with 2n digits.

Solarmew said:
And is it always a sqrt(10) or is there more to it?
It's sqrt(10) because we're looking at the number of base-10 digits. If you wanted to do this in base 8, you'd use sqrt(8).

Solarmew said:
Could you point me in the direction where could read up on this technique pls?
Well, considering that I've never read about it before, I'd say this thread is the only place I can suggest.

Solarmew said:
but then how do you know the number of perfect squares in each set?
I wrote that
100² to 316² have 5 digits.
since 100 = sqrt(10000) and floor(sqrt(100000)). It's easy to count the number of members: 316 - 100 + 1 = 217 (the +1 is because it includes its endpoints).

Solarmew said:
i get confused after the part where you add up the numbers to reach 2010 digits and find that it's somewhere in the vicinity of 6-digit perfect squares X.X What is this step (2010-1438)/6 = 95 + 2/6? and the one after it...
K Sengupta might be able to answer this better than I.

The squares from 1^2 to 316^2 have 1438 digits, so you have 2010-1438 = 572 digits left. 95 * 6 = 570, so the first 95 6-digit squares use up 570 of the 572 digits. You then need the 2nd digit of the 96th 6-digit square, (316+96)^2.
 
Feb 2010
199
0
omg this is way beyond me X.x ... but thank you anyways, this is very informative, i just gotta try to figure it out a lil bit more >.<
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Solarmew said:
omg this is way beyond me X.x ... but thank you anyways, this is very informative, i just gotta try to figure it out a lil bit more >.<
Can you figure out what the smallest and largest natural numbers are that, when squared, have exactly 10 decimal digits?