# Number of N-digit Perfect Squares

I was working on a programming problem to find all 10-digit perfect squares when I started wondering if I could figure out how many perfects squares have exactly N-digits. I believe that I am close to finding a formula, but I am still off by one in some cases.

Current formula where $n$ is the number of digits:

$\lfloor\sqrt{10^n-1}\rfloor - \lfloor\sqrt{10^{n-1}}\rfloor$

How I got here:

1. Range of possible 10-digit numbers is from $10^9$ to $10^{10}-1$
2. 10-digit perfect squares should fall into the range of $\sqrt{10^9}$ to $\sqrt{10^{10}-1}$

Results of program for $n = 1,2,3,4,5$:

DIGITS=1, ACTUAL_COUNT=3,   COMPUTED_COUNT=2
DIGITS=2, ACTUAL_COUNT=6,   COMPUTED_COUNT=6
DIGITS=3, ACTUAL_COUNT=22,  COMPUTED_COUNT=21
DIGITS=4, ACTUAL_COUNT=68,  COMPUTED_COUNT=68
DIGITS=5, ACTUAL_COUNT=217, COMPUTED_COUNT=216


Program:

#!/usr/bin/perl

use strict;
use warnings;

sub all_n_digit_perfect_squares {
my ($n) = @_; my$count = 0;
my $MIN = int( sqrt( 10**($n-1) ) );
my $MAX = int( sqrt( (10**$n)-1 ) );
foreach my $i ($MIN .. $MAX ) { if ( ($i * $i) >= 10**($n-1) ) {
$count++; } } print "DIGITS=$n"
. ", ACTUAL_COUNT=$count" . ", COMPUTED_COUNT=" . ($MAX-$MIN), "\n"; return; } all_n_digit_perfect_squares($_) for (1..5);


If you think about it, you should have a formula that says the number of squares is f (n) - f (n-1) for some function f, so that every perfect square is counted exactly once if you calculate the squares from 10^1 to 10^2, from 10^2 to 10^3 and so on.

In your formula, the squares 100, 10,000, 1,000,000 and so on are not counted at all. For example, for 3 digit numbers the squares are from 10^2 to 31^2, that's 22 numbers. You calculate 31 - 10 = 21. Change your formula to

$\lfloor\sqrt{10^n-1}\rfloor - \lfloor\sqrt{10^{n-1}-1}\rfloor$

• Ah, thank you! I knew I was missing something. – Hunter McMillen Mar 18 '16 at 13:02

I'm interested in the question that you're asking. I've been thinking about this for the last few days and couldn't find anything online about this subject. If you have anything references, I would appreciate it. Here is what I have so far and sorry if the formatting is off, this is my first post.

$$\text{Let}\; \mathbb{N} \;\text{be the set of Natural numbers} \; = \{1,2,3,4,..,N\},$$ Then there exists a set $$\mathbb{S}$$, such that for $$s\in\mathbb{S}\; ;\; s_i = \{10^{i-1},...,(10^i-1)\} \;, \text{for} \; i = 1,2,3,...,M.$$ Example : $$s_1 = \{1,2,3,...,9\}\; ; \;\;\; i=1 = 1\;\text{digit}$$ $$s_2 = \{10,11,12,...,99\}\; ; \;\; i=2 = 2\;\text{digits}$$ $$s_3 = \{100,101,102,...,999\}\; ; \;\; i=3 = 3\;\text{digits}$$ $$...$$ $$s_i = \{10^{i-1},...,(10^i - 1)\} ; \;\; i\; \text{digits}$$

Within each set $$s_i$$, there exists a set $$\mathbb{A}$$ such that for all members of $$\mathbb{A}$$, call it $$a_p$$, when squared are still a member of $$s_i$$: $$a\in\mathbb{A}\; ; \;\; a = \{ a_1,a_2,...,a_k \}$$ $$(a_p)^2 \in s_i ,\; \text{for}\; p = 1\; \text{to}\; k$$

Example : $$s_1 = \{1,2,3,...,9\}\; ; \;\;\; a_1 = \{1,2,3\}$$ $$s_2 = \{10,11,12,...,99\}\; ; \;\; a_2 = \{ a_1 , 4, 5,6,...,9\} = \{1,2,3 , 4, 5,6,...,9\}$$

I'm going to start omit the previous sets before the current $$i^{th}$$ set we're looking at. So it'll look like this:

$$s_2 = \{10,11,12,...,99\}\; ; \;\; a_2 = \{4, 5,6,...,9\},$$

but also know that all previous sets before the current $$i^{th}$$ can included, but is not unique to the $$i^{th}$$ digits.

I'm going to list a few in the long version, just as an example. $$s_3 = \{100,101,102,...,999\}\; ; \;\; a_3 = \{10,11,12,...,31 \}$$ $$s_4 = \{1000,1002,1003,...,9999\}\; ; \;\; a_4 = \{32,33,34,...,99 \}$$ $$s_5 = \{10000,...,99999\}\; ; \;\; a_5 = \{100,...,316 \}$$ $$s_6 = \{100000,...,999999\}\; ; \;\; a_6 = \{317,...,999 \}$$ $$s_7 = \{1000000,...,9999999\}\; ; \;\; a_7 = \{1000,...,3162 \}$$

Now we can write these compactly as, the first i=1,2,3 are written in the long way and i > 4 is written in the short hand version as given by $$s_i$$: $$s_1 = \{10^0,2,3,...,9\}\; ; \; a_1 = \{1,2,3\}\; ; \; t_1 = 3$$ $$s_2 = \{10^1,...,99\}\; ; \; a_2 = \{4, 5,6,...,9\}\; ; \; t_2 = 6$$
$$s_3= \{10^2,...,999\}\; ; \; a_3 = \{10^1,...,31\}\; ; \; t_3 = 22$$
$$s_4= \{10^3,...,(10^4 -1)\}\; ; \; a_4 = \{32,...,99\}\; ; \; t_4 = 68$$ $$s_5= \{10^4,...,(10^5 -1)\}\; ; \; a_5 = \{10^2,...,316\}\; ; \; t_5 = 217$$

I also introduced $$t_i$$, which is the count of the number of members of $$a_i$$, (this is exactly what you're solving for, I believe). Notice, we can get an exact solution for $$t_i$$ given by: $$t_i = (\{a_i\}_{max} - \{a_i\}_{min}) + 1$$ (I think this could be calculated using a norm)

I'm going to list out a few sequences and point out an interesting patterns.

Starting with $$i=3$$, (you could extend this to $$i=1$$ if you want),

if $$i = odd$$ : The lower bound of $$a_i$$, call this $$\{a_i\}_{min}$$ is exactly $$10^l$$, where $$l = (i-1)/2$$ ;

if $$i = even$$ : The upper bound of $$a_i$$, call this $$\{a_i\}_{max}$$ is exactly $$10^z - 1$$, where $$z = (i)/2$$ ;

I claim that for $$i=even$$, you have

$$s_{i-1} = \{10^{i-2},...,(10^{i-1}-1)\}\; ; \;\; a_{i-1} =\{10^l,...,upper\;bound_{(i-1)}\} \; ; \; t_{i-1} = ?$$ $$s_{i} = \{10^{i-1},...,(10^{i}-1)\}\; ; \;\; a_{i} =\{lower\; bound_{(i)},...,(10^z-1)\} \; ; \; t_{i} = ?.$$

I'm still working/thinking about I can get the upper bounds, lower bounds, and $$t_i$$.

Here are the first 16 digits, and their lists. I also have done this out until 34 digits, took my computer a good few hours to compute by brute force. I am almost done with an algorithm that can do it much quicker.

Also note, that if you know the lower bounds and upper bounds, you can easily obtain $$t$$, which is the number of elements that are contained in $$\{a_i\}$$, since $$\{a_i\}$$ is ordered.

$$s_1 = \{10^0,2,3,...,9\}\; ; \; a_1 = \{1,2,3\}\; ; \; t_1 = 3$$ $$s_2 = \{10^1,...,99\}\; ; \; a_2 = \{4, 5,6,...,9\}\; ; \; t_2 = 6$$
$$s_3= \{10^2,...,999\}\; ; \; a_3 = \{10^1,...,31\}\; ; \; t_3 = 22$$
$$s_4= \{10^3,...,(10^4 -1)\}\; ; \; a_4 = \{32,...,99\}\; ; \; t_4 = 68$$ $$s_5= \{10^4,...,(10^5 -1)\}\; ; \; a_5 = \{10^2,...,316\}\; ; \; t_5 = 217$$ $$s_6= \{10^5,...,(10^6 -1)\}\; ; \; a_6 = \{317,...,999\}\; ; \; t_6 = 683$$ $$s_7= \{10^6,...,(10^7 -1)\}\; ; \; a_7 = \{10^3,...,3162\}\; ; \; t_7 = 2163$$ $$s_8= \{10^7,...,(10^8 -1)\}\; ; \; a_8 = \{3163,...,9999\}\; ; \; t_8 = 6837$$ $$s_9= \{10^8,...,(10^9 -1)\}\; ; \; a_9 = \{10^4,...,31622\}\; ; \; t_9 =21623$$ $$s_{10}= \{10^9,...,(10^{10} -1)\}\; ; \;\; a_{10} = \{31623,...,(10^5-1)\}\; ; \; t_{10} = 68377$$ $$s_{11}= \{10^{10},...,(10^{11} -1)\}\; ; \;\; a_{11} = \{10^5,...,316227\} \; ; \; t_{11} = 216228$$ $$s_{12}= \{10^{11},...,(10^{12} -1)\}\; ; \;\; a_{12} = \{316228,...,(10^6-1)\}\; ; \; t_{12} = 683772$$ $$s_{13}= \{10^{12},...,(10^{13} -1)\}\; ; \;\; a_{13} = \{10^6,...,3162277\}\; ; \; t_{13} = 2162278$$ $$s_{14}= \{10^{13},...,(10^{14} -1)\}\; ; \;\; a_{14} = \{3162278,...,(10^7-1)\} \; ; \; t_{14} = 6837722$$. $$s_{15}= \{10^{14},...,(10^{15} -1)\}\; ; \;\; a_{15} = \{10^7,...,31622776\} \; ; \; t_{15} = 21622777$$ $$s_{16}= \{10^{15},...,(10^{16} -1)\}\; ; \;\; a_{16} = \{31622777,...,(10^8-1)\} \; ; \; t_{16} = 68377223$$

• I get a different result for $t_{16}$ using the other formula. I get $68377224$ instead of $68377223$ – Hunter McMillen Jul 1 at 14:00
• As far as other research that I did into this topic, after I found a working solution I didn't explore the area much further. – Hunter McMillen Jul 1 at 14:01
• Sample code to recreate my outputs for the first 16 elements: perl -E 'sub f { my $n = shift; return int(sqrt(10**$n - 1)) - int(sqrt(10**($n-1) - 1)); } say f($_) for 1..16;' – Hunter McMillen Jul 1 at 14:03

The number of perfect squares between any two numbers a and b with a less than b is floor sqrt b - ceil sqrt a + 1. i.e. a=1000 b=2000. ceil sqrt 1000 = 32. floor sqrt 2000 = 44. So 32 33 34 35 36 37 38 39 40 41 42 43 and 44 when squared will be perfect squares between 1000 and 2000 and 44-32+1=13. If you are silly and try for the number of perfect squares between 1000 and 1001 then 31-32+1=0. between 9 and 10 then 3-3+1=1.