Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Sum of two squares problem
Replies: 3   Last Post: Jul 27, 2010 7:44 PM

 Messages: [ Previous | Next ]
 sales@kt-algorithms.com Posts: 78 Registered: 1/29/05
Re: Sum of two squares problem
Posted: Jul 27, 2010 9:36 AM

On Jul 27, 2:50 pm, Gerry <ge...@math.mq.edu.au> wrote:
> On Jul 27, 9:36 pm, Knud Thomsen <sa...@kt-algorithms.com> wrote:
>
>
>

> > For the sum of two squares function (1):
>
> >   r2(c) = number of integer pairs (x,y) for which x^2 + y^2 = c
>
> > consider the special arguments c' defined by:
>
> >   r2(c') > sup{r2(d): d < c'}
>
> > A table of c' and r2(c') starts like this:
>
> > -------------------------------------------------------------------
> >                 c'    r2(c')   Factors of r2(c')
> > -------------------------------------------------------------------
> >                  1       4     1
> >                  5       8     5
> >                 25      12     5^2
> >                 65      16     5 13
> >                325      24     5^2 13
> >               1105      32     5 13 17
> >               4225      36     5^2 13^2
> > -------------------------------------------------------------------

>
> <snip!>
>
>
>

> > The entries annotated with '?' are tentative, as for the alleged c'
> > only r2(c') and r2(c'-1) were calculated. The preceding entries,
> > however, are based on exhaustive searches.

>
> > It seems like c' can be factored into primes congruent to 1 modulo 4,
> > reminding one of Fermat's theorem on sums of two squares and the
> > Brahmagupta?Fibonacci identity.

>
> > Any comments on the apparent regularity for c'>=5525: each time c'
> > doubles, the next prime congruent to 1 modulo 4 is added as a factor?

>
> > Best regards,
> > Knud Thomsen
> > Geologist, Denmark

>
> > References
> > 1. Mathworld Sum of Squares Function
> >    http://mathworld.wolfram.com/SumofSquaresFunction.html

>
> The column you have labeled Factors of r2(c') is, of course,
> actually factorization of c'. On the other hand, when you
> write of c' doubling, you actually mean r2(c') doubling.
>
> Anyway, it is well-known and not terribly deep that if p
> is prime, 1 mod 4, and not a factor of m, then r2(pm) = 2 r2(m).
>
> Anyway anyway, have a look athttp://www.research.att.com/~njas/sequences/A071383
> --
> GM

Many thanks, Gerry, for the references, something for me to dig into.
Too bad I forgot to look up that c' integer sequence myself ..
Do you happen to have an (online) reference to a proof of the 'r2(pm)
= 2 r2(m)' relation at hand?
I mean, it may not be deep, but it isn't obvious to this layman ;-).

Knud

Date Subject Author
7/27/10 sales@kt-algorithms.com
7/27/10 gerry@math.mq.edu.au
7/27/10 sales@kt-algorithms.com
7/27/10 Gerry Myerson