 My Math Forum Writing Natural numbers as the sum of 4 squares
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 March 21st, 2017, 03:01 AM #1 Math Team   Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 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  March 21st, 2017, 07:46 AM #2 Senior Member   Joined: Sep 2015 From: USA Posts: 2,364 Thanks: 1270 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 March 22nd, 2017, 02:40 AM #3 Math Team   Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 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.  March 27th, 2017, 09:28 AM #4 Member   Joined: Jan 2016 From: Athens, OH Posts: 92 Thanks: 47 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 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; 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; 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; 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 March 27th, 2017, 10:15 AM   #5
Senior Member

Joined: Nov 2010
From: Berkeley, CA

Posts: 174
Thanks: 35

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. Tags natural, numbers, squares, sum, writing Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Nienna426 Number Theory 4 April 27th, 2015 04:27 PM bigli Number Theory 1 November 1st, 2013 12:14 AM Eureka Number Theory 4 November 3rd, 2012 03:51 AM jinjouk Number Theory 12 June 3rd, 2008 06:11 AM Daniel Number Theory 1 October 22nd, 2007 05:08 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      