1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This should probably be a comment, but there is oeis.org/A049415 $\endgroup$
    – Jim M
    Commented Jan 26, 2022 at 6:34

3 Answers 3

3
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Ah, thank you! I knew I was missing something. $\endgroup$ Commented Mar 18, 2016 at 13:02
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I get a different result for $t_{16}$ using the other formula. I get $68377224$ instead of $68377223$ $\endgroup$ Commented Jul 1, 2019 at 14:00
  • $\begingroup$ 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. $\endgroup$ Commented Jul 1, 2019 at 14:01
  • $\begingroup$ 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;' $\endgroup$ Commented Jul 1, 2019 at 14:03
0
$\begingroup$

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.

$\endgroup$
1

You must log in to answer this question.

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