Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By richard1234

Math Help - How many elements of S can be written as the sum of three integer squares?

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    How many elements of S can be written as the sum of three integer squares?

    Let S be the set of all positive integers n not exceeding 1 000 000 such that n \equiv 4 \pmod{8}, that is, S = \{4,12,20,28,\ldots,999996\}.

    How many of the elements of S can be written as the sum of the three integer squares?


    A theorem says that n can be written as sum of three integer squares iff n \ne 4^k (8m + 7) for non-negative integers k,m.

    So n = 8x - 4 can be written as sum of three integer squares iff n = 8x - 4 \ne 4^k (8m + 7), or in another word when 8x - 4 = 4^k (8m + 7) with variable x has no integer solution.

    x = 4^km + \frac{4^k \timex 7}{8} - \frac{1}{2} is not an integer when k > 1, and is an integer when k = 0,1.

    Work out how many n CANNOT be written as sum of three integer squares.

    When k = 0, n = 8m + 7 \equiv 7 \pmod{8} are not in S.
    When k = 1, n = 4(8m + 7) = 32m + 28 \equiv 4 \pmod{8} are in S.

    We require n = 4(8m + 7) \leq 1000000 or m \leq 31249, hence there are 31250 elements in S that cannot be written as sum of three integer squares.

    There are 124999 elements in S, hence 124999-31250 = 93749 elements can be written as sum of three integer squares.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: How many elements of S can be written as the sum of three integer squares?

    Your solution seems correct. However, S contains 125,000 elements, not 124,999 (you have to add 1 b/c you have an inclusive set). So the answer should be 93,750.
    Thanks from math2011
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: How many elements of S can be written as the sum of three integer squares?

    Thank you. You are right. S does contain 125000 elements.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,390
    Thanks
    757

    Re: How many elements of S can be written as the sum of three integer squares?

    it appears that i agree with your answer, although i do not know how you can conclude that x is an integer when k = 0. for then:

    x = m + 7/8 - 1/2 = m + 3/8, which is *not* an integer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: How many elements of S can be written as the sum of three integer squares?

    k cannot be zero (because every integer in S is congruent to 4 mod 8).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,390
    Thanks
    757

    Re: How many elements of S can be written as the sum of three integer squares?

    i am saying that when k = 0, x is not even an integer.

    look, when k = 0, 8x - 4 = 8m + 7

    8(x - m) = 11 ---> x - m is not an integer ---> x is not an integer.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: How many elements of S can be written as the sum of three integer squares?

    You guys are right. I have got the details wrong about k = 0. Thank you guys for pointing it out and explaining.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: May 28th 2012, 05:55 PM
  2. Replies: 8
    Last Post: November 27th 2011, 10:18 PM
  3. Replies: 1
    Last Post: July 13th 2010, 07:54 AM
  4. integer squares problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 1st 2010, 03:41 AM
  5. Replies: 2
    Last Post: January 9th 2010, 10:06 PM

Search Tags


/mathhelpforum @mathhelpforum