Finding a Six-Digit Number

Date: 05/12/2005 at 20:29:00
From: Caroline
Subject: Finding a 6-digit number

I'm thinking of a 6-digit number. The sum of the digits is 43.  And 
only two of the following three statements about the number are true: 
(1) it's a square number, (2) it's a cube number, and (3) the number 
is under 500,000.

Date: 05/13/2005 at 11:34:08
From: Doctor Vogler
Subject: Re: Finding a 6-digit number

Hi Caroline,

Thanks for writing to Dr. Math.  The important thing to know about the
sum-of-digits function is that for every positive integer n, the sum
of digits of n is congruent to n mod 9.  What does that mean?  See

  Mod, Modulus, Modular Arithmetic
  http://mathforum.org/library/drmath/view/62930.html 

for an introduction to modular arithmetic.  Essentially, it means that
if you subtract the sum of digits from n, then you will always get
something divisible by 9.  That is, if you divide n by 9, and you
divide the sum of digits by 9, you will get the same remainder.  To
see why, see the proofs in the links in

  Divisibility Rules
  http://mathforum.org/dr.math/faq/faq.divisibility.html 

for the rule for divisibility by 9.  Or search our archives at

    http://mathforum.org/library/drmath/mathgrepform.html 

for the phrase

  sum of digits

or the phrase

  casting out nines

or something similar.  

Now, what's the point of this?  Well, since your number has sum of
digits 43 (which is 7 mod 9, i.e. the remainder is 7 when you divide
by 9), it must also happen that your number is 7 mod 9.  Well, this
can't happen for a cube.

Every cube is either 0, 1, or 8 mod 9.  To see this, notice that every 
integer can be written as either 3k, 3k+1, or 3k+2 for some integer k.  
(Divide by 3; then k is the quotient and 0, 1, or 2 is the remainder.)  
Now expand

    (3k)^3 = 27k^3

  (3k+1)^3 = 27k^3 + 27k^2 + 9k + 1

  (3k+2)^3 = 27k^3 + 54k^2 + 36k + 8

and all of the terms except the 1 and 8 are divisible by 9.  So you 
can't get 7 mod 9 with a cube.

Therefore, you must be looking for a square less than 500,000.  Well,
there aren't all that many squares less than 500,000.  In fact, there
are 708 of them (from 0^2 to 707^2).  Furthermore, only the numbers
that are 4 mod 9 or 5 mod 9 will have squares that are 7 mod 9, which
means that you only need to check about 2/9'ths of those numbers. 

What's more, 43 is a pretty high sum of digits for a six-digit number
to have, especially since the first number can't be more than a 4. 
You see, 499999 only has a sum of 49, so you can only go down by 6. 
That means that any number with a 0, 1, or 2 in one of the last five
places will be too small.  And so on.  So now look at all of those
squares.  It turns out that exactly one of them has a sum of digits
that is exactly 43.  Which one?

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/