Number of N-digit Perfect Squares

Question

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);

Any advice on where I went wrong would be helpful.

Answer 1

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$