Sums of Square Integers Puzzle

Date: 07/01/2002 at 20:38:24
From: Janette
Subject: "problem of the week" problem


I have this problem of the week that no one gets in school and I was 
wondering if you could help me. Here's the problem:

How many numbers from 1-100 can be expressed as the sum of the squares 
of two positive integers?

A girl in school told me that this was a college problem. Please 
help me!!

Thank you,
Janette M. Casarrubias

Date: 07/02/2002 at 02:32:19
From: Doctor Ian
Subject: Re: "problem of the week" problem


Hi Janette,

This is one of those problems that seems harder than it actually 
is.  For one thing, it seems as though you'd have to check all 
the numbers from 1 to 100!  And for each one, you'd have to try 
all the different ways that it could be the sum of two squares.  
That sounds like an awful lot of work. 

And if you approached it that way, it _would_ be a lot of work.  
But you can approach it from a different direction.  

Consider that 10^2 is 100, and 

  100 = 10^2 + 0^2

Since 0^2 isn't the square of a positive integer, we know that 
all of the integers being squared have to be between 0 and 9.  
Does that make sense?  So we can make a little table:

        1^2   2^2   3^2   4^2  

  1^2     2     5    10    17
  
  2^2     5     8    13    20

  3^2    10    13    18    25

  4^2    17    20    25    32

I've stopped at 4^2, but if you continue up to 9^2, you'll find 
all the possibilities.  

Note that the table is symmetric, because addition is 
commutative.  So you really only have to fill in half of it, 
i.e., 

        1^2   2^2   3^2   4^2

  1^2     2     5    10    17
  
  2^2           8    13    20

  3^2                18    25

  4^2                      32

Can you take it from here? 

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