A positive integer n is said to be good if there exists a perfect square whose sum of digits in base 10 is equal to n. For instance, 13 is good because (7^2)=49 and 4+9=13. How many good numbers are among 1, 2, 3, …, 2007?
I have started to make a list of all square numbers and adding their digits in an excel file. ... Until now, I have got good numbers as 1, 4, 7, 9, 10, 13, 16, 19. But, this method takes very long. ... Is there a shorter and smarter way to solve this problem.
On
HINT
Squares modulo $9$ are $0,1,4,0,7,7,0,4,1$ and $0,1,4,7,9$ are realised. But are there any gaps in these residue classes?
If we could find square numbers in sequence with a pattern with same initial and final digits, and constant middle digits we might would be able to show this.
For example $$34^2=1156, 334^2=111556, 3334^2=11115556$$ or $$43^2=1849, 433^3= 187489, 4333^2=18774889$$
The first of these gives difference $6$ in the sum of digits and deals with $13,19,25 \dots$. The second has difference $15$ and does some of the rest.
Can you find examples which fill all the gaps?
Further hint - I think there is a straightforward way to do this, which doesn't require so much trial, but is based on the same idea.
$91^2=8281, 991^2=982081 \dots 92^2=8464, 992^2=984064 \dots$
On
Let $a=\sum_{k=0}^{n-1} a_k 10^k$ where $a_k \in [0,9]$, and let $f(a) = \sum_{k=0}^{n-1} a_k$. Then we have:
$$ a^2 = \sum_{k,l=0}^{n-1} a_k a_l 10^{(k+l)} = a_0^210^0 + (a_1a_0 + a_0 a_1)10^1 + \dots + \left(\sum_{k=0}^{n-1} a_{n-1-k}a_k\right)10^{n-1} + \left(\sum_{k=1}^{n-1} a_{n-1-k}a_k\right)10^n + \dots + a_{n-1}^2 10^{2n-2}, $$
so $f(a^2) = \sum_{l=0}^{n-1}\sum_{k=0}^la_{l-k}a_k + \sum_{l=0}^{n-1}\sum_{k=l+1}^{n-1}a_{n-1-k}a_k$.
Hope this helps!
On
Hint: ( Continuation of your method)
I find this method of observing patterns very interesting. So I will continue with same.
Write out first few good numbers like $$1,4,7,9,10,13,16,18,19,22,25,....$$
Now write down the differences between consecutive terms like $$3,3,2,1,3,3,2,1,3,3,...$$
Did you notice the pattern of differences. It repeats like $3,3,2,1$ and again and again.
So with simple algebra you must have your answer as $$223*4=892$$
Edit:
In general from $1$ to $9n$ ($n\in N$) there are $4n$ good numbers.
On
Method 2:
(I think this one is quite similar to the method used by Mark Bennet. And one note that I am not coping his answer, just giving a slightly intuitional form of his method)
We need the sum of the digits of a perfect square. Now just remind yourself that the divisibility of 9 exactly deal with the sum of digits of a number.
You may write any perfect square in the forms of $9m$, or $9m+1$ , or $9m+4$ or $9m+7$, for some $m\in W$
Now the sum of digits of any perfect square also follow the rule. And hence your answer must be the number of numbers from 1 to 2007 of the forms $9m$, or $9m+1$ , or $9m+4$ or $9m+7$.
On
By far the answer given by Manthanein as "Method 2" seems to me the most enlightening. It allows you to list and count Good Numbers till any arbitrary upper bond you choose.
For further insight, references and Maths papers on these good numbers, you may visit the On-line Encyclopaedia of Integer Sequences at https://oeis.org/ You may search for the sequence starting with: 1,4,9,7,7,9,13,10,9,1,4,9,16,16,9,13,19,9,10,4,9, . . . known as sequence A004159 'Sum of digits of n^2'.
On
Expanding (on Excel) the table at the end of this answer, I check that there are in fact exactly 892 good numbers from 1 to 2007 included.
(Exactly the 4/9 of 2007 given by Marc Bennet)
While we are at it, an interesting recursive algorithm can be based on these “good numbers”. Given any Integer n, the sum of the digits of n^2 is the “good number" of n. The relation is surjective (many Integers can have the same good number)
For example:
2713^2 = 7360369,
7+3+6+0+3+6+9 = 34,
34 is the good number of 2713.
We can recursively calculate the good number of 34,
34^2 = 1156,
1+1+5+6 = 13,
13 is the good number of 34,
We carry on
13^2 = 169
1+6+9 = 16
16 is the good number of 13
and so on.
So doing we see Integers connected into 3 convergent trees, respectively converging towards three “attractors” which are 1, 9, and the couple 13-16. See graph of the 3 converging trees here
COMPLEMENTARY NOTE
Given an Integer n we know that the sum of its digits S(n) is congruent to n modulo 9
n ≡ S(n) (modulo 9)
(n and S(n) have the same remainder when divided by 9)
So any Integer can be written as n = 9k + r
and its square n^2 = (9k + r)^2
or (81k^2 + 18kr + r^2) or (9k’ + r^2)
The table r 1 2 3 4 5 6 7 8
r^2 1 4 9 16 25 36 49 64
r^2 mod 9 1 4 0 7 7 0 4 1
shows that good numbers can only be of the form
9k, 9k + 1, 9k + 4, 9k + 7
The first few are given below:
9k, 9k + 1, 9k + 4, 9k + 7
k=0 0 1 4 7
k=1 9 10 13 16
k=2 18 19 22 25
k=3 27 28 31 34
k=4 36 37 40 43
To be formal about this note that for $r$ large enough and $s$ a single decimal digit $$ (10^r-s)^2 = 10^{2r}-2s \cdot 10^r+r^2 = 9\cdot(10^{2r-1}+10^{2r-2}+\dots 10^{r+3})+(100-2s)\cdot10^r+s^2$$
So we begin with a string of $9$s which is $r-3$ long followed by two digits which are fixed (and may be zero or $9$), then a string of zeros followed by either one or two digits of $s^2$. Every time you increase $r$ by one, the digit sum increases by the addition of a single leading $9$.
Take $s=1$ to see what happens
$9^2=81$
$99^2=9801$
$999^2=998001$
This deals with $9,18, 27\dots$
With $s=2$
$8^2=64$
$98^2=9604$
$998^2=996004$
Which deals with $10,19,28\dots$
With $s=3$
$7^2=49$
$97^2=9409$
$997^2=994009$
Which deals with $13,22,31\dots$
$s=4$ deals with multiples of $9$ again.
$s=5$ gives
$5^2=25$
$95^2=9025$
$995^2=990025$
And this deals with $7,16,25\dots$
With the addition of a few early cases which these miss, you can show that you hit every positive element of every class of quadratic residue modulo $9$