0
$\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$
2
$\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$
  • $\begingroup$ Ah, thank you! I knew I was missing something. $\endgroup$ – Hunter McMillen Mar 18 '16 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$
  • $\begingroup$ I get a different result for $t_{16}$ using the other formula. I get $68377224$ instead of $68377223$ $\endgroup$ – Hunter McMillen Jul 1 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$ – Hunter McMillen Jul 1 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$ – Hunter McMillen Jul 1 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.