My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
  • 1 Post By romsek
  • 1 Post By johng40
  • 1 Post By Petek
Reply
 
LinkBack Thread Tools Display Modes
March 21st, 2017, 03:01 AM   #1
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,260
Thanks: 198

Writing Natural numbers as the sum of 4 squares

Greetings MMF members and guests.

It is a well known result that every Natural number can be written as the sum of $4$ squares. $3$ squares are not enough. (For example , $7$ cannot be written as the sum of $3$ squares)

Euler did work on the problem and then Lagrange provided a proof based in part on Euler's work.

Some Natural numbers can be written as the sum of $4$ squares in more than one way.

For example $1$ :

$35 = 5^2 + 3^2 + 1^2 + 0^2$

$35 = 4^2 + 3^2 + 3^2 + 1^2$

Note that repetition of squares is allowed and the square of zero is allowed.

Example $2$

$36 = 6^2 + 0^2 + 0^2 + 0^2$

$36 = 5^2 + 3^2 + 1^2 + 1^2$

$36 = 4^2 + 4^2 + 2^2 + 0^2$

$36 = 3^2 + 3^2 + 3^2 + 3^2$


My question is purely recreational in nature ... Is there a way to look at a number , use some algorithm and quickly be able to determine in how many different ways it can be written as the sum of $4$ squares without having to test all possible combinations?

P.S. I hope that one of you computer programmer wizards can print a list of the number of ways the first $200$ natural numbers can be written as the sum of $4$ squares.

Thank you for your attention
agentredlum is offline  
 
March 21st, 2017, 07:46 AM   #2
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: CA

Posts: 1,238
Thanks: 637

Rabin and Shallit's 1986 paper, "Randomized Algorithms in Number Theory" (Comm. in Pure and Applied Math v.39(supplement):S239-S256)

details an algorithm for this. I don't have the article in hand but from the few comments about it I read it's not a trivial algorithm.
Thanks from agentredlum
romsek is offline  
March 22nd, 2017, 02:40 AM   #3
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,260
Thanks: 198

I looked it up and found some commentary on MathStackExchange but was not able to determine if the algorithm counts the number of different ways a Natural number can be written as the sum of 4 squares. The algorithm gives a way to write a Natural number as the sum of 4 squares , that's true.

agentredlum is offline  
March 27th, 2017, 09:28 AM   #4
Member
 
Joined: Jan 2016
From: Athens, OH

Posts: 44
Thanks: 26

I had fun writing a program (in Java) that calculates the number of ways a positive integer can be written as a sum of 4 squares. Here's the output of one run of the program, as you requested for all integers from 1 to 200:

This program calculates the number of ways a positive integer can be written a a sum of 4 squares.
Enter a positive integer n:
200
Enter option 1 or 2:
1. Display all ways for the range 1 to 200
2. Display all ways (if < 100) for the one value 200
1
For 200:
minimum ways:1 maximum ways:14
min at:128 max at:198
average number of ways:5.035
1:1 2:1 3:1 4:2 5:1 6:1 7:1 8:1
9:2 10:2 11:1 12:2 13:2 14:1 15:1 16:2
17:2 18:3 19:2 20:2 21:2 22:2 23:1 24:1
25:3 26:3 27:3 28:3 29:2 30:2 31:2 32:1
33:3 34:4 35:2 36:4 37:3 38:3 39:2 40:2
41:3 42:4 43:3 44:2 45:4 46:2 47:2 48:2
49:4 50:5 51:3 52:5 53:3 54:5 55:3 56:1
57:4 58:5 59:3 60:3 61:4 62:3 63:4 64:2
65:4 66:6 67:4 68:4 69:4 70:5 71:2 72:3
73:5 74:5 75:5 76:5 77:4 78:4 79:3 80:2
81:6 82:7 83:4 84:5 85:5 86:5 87:4 88:2
89:5 90:9 91:5 92:3 93:5 94:4 95:3 96:1
97:6 98:7 99:6 100:7 101:5 102:7 103:5 104:3
105:6 106:7 107:4 108:7 109:5 110:6 111:5 112:3
113:5 114:8 115:6 116:4 117:8 118:7 119:4 120:2
121:6 122:8 123:6 124:6 125:7 126:8 127:5 128:1
129:7 130:10 131:5 132:7 133:7 134:7 135:7 136:4
137:6 138:10 139:6 140:5 141:6 142:5 143:5 144:4
145:8 146:9 147:8 148:8 149:6 150:11 151:5 152:3
153:10 154:10 155:6 156:6 157:8 158:6 159:6 160:2
161:7 162:13 163:7 164:6 165:8 166:9 167:5 168:4
169:8 170:11 171:10 172:8 173:7 174:9 175:8 176:2
177:8 178:12 179:6 180:10 181:8 182:10 183:7 184:2
185:9 186:11 187:9 188:6 189:11 190:8 191:5 192:2
193:8 194:11 195:10 196:10 197:7 198:14 199:7 200:5

Enter 0 to quit, 1 for another run:
0

If you are a programmer, you can easily run the Java program on your own computer. Otherwise, you can get one of your programmer friends to help you. Here's the program (you need to put the 3 public classes in different files):

Code:
package multiset4squares;

import java.util.Scanner;

public class Multiset4squares {
   public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
      int n1 = 100;
      int choice;
      Multisets b = new Multisets(n1, 4);
      NasFourSquares c = new NasFourSquares(n1);
      System.out.print("This program calculates the number of ways a positive");
      System.out.println(" integer can be written a a sum of 4 squares.");
      while (true) {
         System.out.println("Enter a positive integer n:");
         n1 = scan.nextInt();
         if (n1 < 1) {
            System.out.println("n must be a positive integer.");
            continue;
         }
         System.out.println("Enter option 1 or 2:");
         System.out.println("1. Display all ways for the range 1 to " + n1);
         System.out.println("2. Display all ways (if < 100) for the one value " + n1);
         choice = scan.nextInt();
         if (choice == 1) {
            if (n1 > 1000) {
               System.out.println("Range must be at most 1..1000");
            } else {
               b.reset(n1);
               b.generateRec(0, 0, 4);
               b.display(true);
            }
         } else if (choice == 2) {
            if (n1 > 100000) {
               System.out.println("Single n must be at most 100,000");
            } else {
               c.reset(n1);
               c.generate(n1, 4);
               c.display(c.count <= 50);
            }
         } else {
            System.out.println("Enter the integer choice 1 or 2.");
         }
         System.out.println("Enter 0 to quit, 1 for another run:");
         int again = scan.nextInt();
         if (again == 0) {
            break;
         }
      }
   }
}
Code:
package multiset4squares;

public class Multisets {
/* This class represents multisets of cardinality k (4) with values from
 * 0..n-1.  Here n is floor(sqrt(n1))+1
 * Method generate recursively computes all such multisets,
 * the multi set is stored in k component array m and then processed.
 * For a given multiset m, set sum = sum of m[i]^2, 0>=i<=k-1.  If sum
 * <= n1, s[sum] is incremented.  So at conclusion s[i] is the number
 * of ways i can be written as the sum of 4 squares.
 */
   int n1, n, k;
   int[] m;
   int[] s;
   
   Multisets(int n1, int k1) {
      k = k1;
      m = new int[k];
      reset(n1);
   }

   void reset(int n1) {
      this.n1 = n1;
      n = (int) Math.floor(Math.sqrt(n1))+1;
      s = new int[n1+1];
   }
   
   void processMultiset() {
      int i;
      int sum=0;
      for (i=0;i<k;i++) {
         sum+=m[i]*m[i];
      }
      if (sum<=n1) {
         s[sum]++;
      }
   }
/* The initial call is generateRec(0,0,4).  For a given generated multiset
 * m, if i = sum of squares of components of m <= n1, the component s[i]
 * is incremented.  The generation of the multisets is in lexicographic
 * order.  There should be a way to shorten the generation since any 
 * i > sum is just ignored; however I don't see how to modify the
 * algorithm.
 */
   void generateRec(int mIndex, int startN, int r) {
      int i, j, l;
      if (r == 0) {
         processMultiset();
         return;
      }
      for (i = startN; i < n; i++) {
         for (l = 0; l < r; l++) {
            m[mIndex + l] = i;
         }
         for (j = r; j > 0; j--) {
            generateRec(mIndex + j, i + 1, r - j);
         }
      }
   }
   
/* AFTER generation, this method outputs the results
 * 
 */
   void display(boolean all) {
      int i;
      int min, max, minI = 0, maxI = 0, sum =0;
      min = max = s[0];
      for (i = 1; i <= n1; i++) {
         sum += s[i];
         if (s[i] <= min) {
            min = s[i];
            minI = i;
         } else if (s[i] > max) {
            max = s[i];
            maxI = i;
         }
      }
      System.out.println("For "+n1+":");
      System.out.println("minimum ways:" + min + " maximum ways:" + max);
      System.out.println("min at:" + minI + " max at:" + maxI);
      double ave = (double) sum / n1;
      System.out.println("average number of ways:" + ave);
      if (all) {
         for (i = 1; i <= n1; i++) {
            System.out.print(i + ":" + s[i] + " ");
            if (i%8==0) {
               System.out.println();
            }
         }
         System.out.println();
      }
  }
}
Code:
package multiset4squares;

class MultiNode {
   int[] s;
   MultiNode next;

   MultiNode(int[] m) {
      s = new int[4];
      int i;
      for (i = 0; i < 4; i++) {
         s[i] = m[i];
      }
      sort(s);
      next = null;
   }
   
   void sort(int[] a) {
      int i, j, v;
      for (i = 1; i < 4; i++) {
         v = a[i];
         for (j = i - 1; j >= 0 && v < a[j]; j--) {
            a[j + 1] = a[j];
         }
         a[j + 1] = v;
      }
   }

   boolean isEqual(int[] m) {
      int i, j;
      for (i = 0; i < 4; i++) {
         if (m[i]!=s[i]) {
            return(false);
         }
      }
      return (true);
   }
}

public class NasFourSquares {
/* For a single value n, this class generates all ways that n can be
 * represented as the sum of 4 squares.
 */
   int n;
   int[] m;
   MultiNode header;
   int count=0;

   NasFourSquares(int n) {
      this.n = n;
      m = new int[4];
      header=new MultiNode(m);
   }
   
   void reset(int n) {
      this.n = n;
      header.next = null;
      count = 0;
   }

   void processM() {
      int i, sum = 0;
      for (i=0;i<4;i++) {
         header.s[i]=m[i];
      }
      header.sort(header.s);
      MultiNode q = header.next;
      while (q != null) {
         if (q.isEqual(header.s)) {
            return;
         }
         q = q.next;
      }
      count++;
      q = new MultiNode(m);
      q.next = header.next;
      header.next = q;
   }
/* Recursively generate the number of ways n can be written as
 * the sum of r squares.  The recursive generation produces duplicate
 * multisets to do this, so a linked list of multisets is maintained that
 * ensures only 1 multiset is "saved".  Again, there should be an easier
 * way to avoid duplicates, but I don't see how.
 */
   void generate(int n, int r) {
      int i, k, j, sq;
      if (r == 0) {
         return;
      }
      k = (int) Math.sqrt(n);
      for (i = k; i >= 1; i--) {
         sq = i * i;
         m[4 - r] = i;
         if (sq == n) {
            for (j = 4 - r + 1; j < 4; j++) {
               m[j] = 0;
            }
            processM();
         } else {
            generate(n - sq, r - 1);
         }
      }
   }
   
   void display(boolean all) {
      System.out.println("For " + n + " there are " + count + " ways:");
      if (all) {
         int i;
         MultiNode p = header.next;
         while (p != null) {
            for (i = 0; i < 4; i++) {
               System.out.print(p.s[i] + " ");
            }
            System.out.println(n);
            p = p.next;
         }
      }
   }
}
Thanks from agentredlum
johng40 is offline  
March 27th, 2017, 10:15 AM   #5
Senior Member
 
Joined: Nov 2010
From: Berkeley, CA

Posts: 170
Thanks: 27

Math Focus: Elementary Number Theory, Algebraic NT, Analytic NT
See Theorem 386 in Hardy and Wright's An Introduction to the Theory of Numbers:

Quote:
The number of representations of a positive integer n as the sum of four squares, representations which differ only in order or sign being counted as distinct, is 8 times the sum of the divisors of n which are not multiples of 4.
Thanks from agentredlum
Petek is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
natural, numbers, squares, sum, writing



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odd numbers that can be represented in only one/two ways as difference of squares Nienna426 Number Theory 4 April 27th, 2015 04:27 PM
Perfect squares between two numbers bigli Number Theory 1 November 1st, 2013 12:14 AM
The paradox between prime numbers and natural numbers. Eureka Number Theory 4 November 3rd, 2012 03:51 AM
natural numbers from sets....not very natural jinjouk Number Theory 12 June 3rd, 2008 06:11 AM
N-digit numbers and their squares Daniel Number Theory 1 October 22nd, 2007 05:08 PM





Copyright © 2017 My Math Forum. All rights reserved.