Problem. Write positive integer n as a sum of at most 4 squares. Mathematicians can prove that a positive integer can be written as the sum of at most 4 squares. That is, if n is a positive integer, then there exists non negative integers a b c d so that n = a + b + c + d. As examples 79 = 7 + 5 + 2 + 1 301 = 16 + 6 + 3 and 301 = 17 + 2 + 2 + 2 2019 = 44 + 9 + 1 + 1 2020 = 44 + 8 + 4 + 2 The problem is to design software to find an algorithm for representing a particular positive integer n as the sum of at most 4 positive integers. For a particular positive integer n, the algorithm must find at most 4 positive integers a, b, c, d with n = a + b + c + d. If n is a perfect square, then n equals its square root squared and I'm done. After some thought, I decide I need a function called the integer square root. The integer square root of a positive integer n abbreviated isqrt( n ) is the largest positive integer whose square is less than or equal to n. It equals the integer part of the square root of n. For example, isqrt( 12 ) is 3 since sqrt( 12 ) = 3.464 and isqrt( 301 ) = 17 since sqrt( 301 ) is 17.349. If n is not a perfect square, then n may be the sum of 2 squares. That is, n is the sum a + b for some positive integer a between 1 and the integer square root of n. Here I will use a greedy approach. Set a to isqrt( n ) and b = n - a. If b is a perfect square, then Im done. If not decrement a by one, reset b and test if b is a perfect square. Continue while b is not a perfect square and a is greater than 0. For n = 12, a = isqrt( 12 ) = 3 and b = 12 - 3 = 3, not a square. Decrement a to 2. Reset b to 12 - 2 = 8, not a square. Decrement a to 1. Reset b to 12 1 = 11, not a square. Decrement a to 0. So 12 is not a sum of 2 squares. For n = 301 I will test whether n is a sum of 2 square with a table. n a = isqrt( n ) b = n - a 301 17 301 17 = 12 16 301 16 = 45 15 301 15 = 76 14 301 14 = 105 13 301 13 = 132 12 301 12 = 157 1 301 1 = 300 An exhaustive search indicates 301 is not a sum of 2 squares. If n is not a perfect square and not the sum of 2 squares, then n may be the sum of 3 squares. That is, set a to isqrt( n ) and then test whether b = n - a is a sum of two squares using the algorithm in the previous case. If b is not the sum of 2 squares, decrement a, reset b and test if b is the sum of 2 squares. Continue while b is not the sum of 2 squares and a is greater than 0. So I need a function for the case of testing whether n is the sum of 2 squares. I will call the function sum2Squares(). Its parameters are n and an array of size 2 with initial values of zeros. Its return type is void. If n is the sum of 2 squares. Ill put the squares in the array parameter. If n is not the sum of 2 squares, the the array stays the same with 2 zeros. The pseudo code for algorithm I used in the construction of the table for n = 301 follows. Initialize a to isqrt( n ) and b to n a. while a > 0 and b is not a square Decrement a. Reset b to n a if a > 0 Set the array parameter to a and isqrt( b ) The header for this function is void find2Squares( int n, int [ ] values ) I will use another function for testing whether n is the sum of 3 squares. It will use the function find2Squares. Its algorithm is similar to the one for 2 squares but instead of testing is b is a square, it tests whether b is the sum of 2 squares. That is, Initialize a to isqrt( n ) and b to n a. Call find2Squares( b, values ) while a > 0 and values[ 0 ] == 0 Decrement a. Reset b to n a Call find2Squares( b, values ) if a > 0 Set the array parameter to a, values[ 0 ] and values[ 1 ] The header for this function is void find3Squares( int n, int [ ] values ) If n is not the sum of 3 squares, I repeat a similar argument for the last time with a function find4Squares(). Initialize a to isqrt( n ) and b to n a. Call find3Squares( b, values ) while a > 0 and values[ 0 ] == 0 Decrement a. Reset b to n a Call find3Squares( b, values ) if a > 0 Set the array parameter to a, values[ 0 ], values[ 1 ] and values[ 2 ] The header for this function is void find4Squares( int n, int [ ] values ) I will simulate find4Squares() for n = 301 and values = { 0, 0, 0, 0 } using a table. n a b 301 17 301 17 = 12 find3Squares( 12, values ) 12 has isqrt( 12 ) of 3 with b = 12 3 = 3 find2Squares( 3, values ) fails. 16 301 16 = 45 find3Squares( 45, values ) 45 has isqrt( 45 ) of 6 with b = 45 6 = 9 find2Squares( 9, values ) returns with values of { 3, 0 } Then find3Squares( 45, values ) returns with values of { isqrt( 45 ) = 6, 3, 0 } So find4Squares( 301, values ) returns with values of { 16, 6, 3, 0 } My functions appear to work. Try n equal to a small 4 digit number, 1015. n a b 1015 31 1015 31 = 54 find3Squares( 54, values ) 54 has isqrt( 54 ) of 7 with b = 54 7 = 5 find2Squares( 5, values ) returns with values of { 2, 1 }. Then find3Squares( 54, values ) returns with values of { 7, 2, 1 } So find4Squares( 1015, values ) returns with values of { 31, 7, 2, 1 } One more simulation for n = 1017 follows. n a b 1017 31 1017 31 = 56 find3Squares( 56, values ) 56 has isqrt( 56 ) of 7 with b = 56 7 = 7 find2Squares( 7, values ) fails. Reset a to 6, b to 56 6 = 20 find2Squares( 20, values ) returns with values of { 4, 2 }. find3Squares( 56, values ) returns with values of { 6, 4, 2 } find4Squares( 1017, values ) returns with values of { 31, 6, 4, 2 } The translation of the pseudo code to C code for each of these functions is straightforward. /* Return the integer square root of a positive integer n, the largest integer whose square n. */ int isqrt( n ) { return ( int )sqrt( n ); } To use the sqrt() function requires an include for the math library. The following statement must appear near the start of the program. #include C does not have a boolean type, but it has a bool library with values of true and false. To test whether a positive integer is a perfect square uses the following function. /* Decide if n is a perfect square. */ bool isSquare( int n ) { int rootN = isqrt( n ); return ( n == rootN * rootN ); } I need the statement #include near the start of the program. The translation to C for the function find2Squares() looks like Java code. /* Find, if possible, at most 2 non negative integers in the array squares for which the sum of the squares of its entries equals n. If not possible, squares[ 0 ] will be zero. */ void find2Squares( int n, int squares [ ] ) { int a = isqrt( n ); if ( isSquare( n ) ) squares[ 0 ] = a; else { int b = n - a * a; while ( ( a > 0 ) && ( ! isSquare( b ) ) ) { a--; b = n - a * a; } if ( isSquare( b ) ) { squares[ 0 ] = isqrt( b ); squares[ 1 ] = a; } } } A similar translation applies for find3Squares() and find4Squares(). /* Find, if possible, at most 3 non negative integers in the array squares for which the sum of the squares of its entries equals n. If not possible squares[ 0 ] will be zero. */ void find3Squares( int n, int squares [ ] ) { find2Squares( n, squares ); if ( squares[ 0 ] == 0 ) { int a = isqrt( n ), b = n - a * a; while ( ( a > 0 ) && ( squares[ 0 ] == 0 ) ) { find2Squares( b, squares ); if ( squares[ 0 ] > 0 ) squares[ 2 ] = a; else { a--; b = n - a * a; } } } } /* Find at most 4 non negative integers in the array squares for which the sum of the squares of its entries equals n. */ void find4Squares( int n, int squares [ ] ) { find3Squares( n, squares ); if ( squares[ 0 ] == 0 ) { int a = isqrt( n ), b = n - a * a; while ( ( a > 0 ) && ( squares[ 0 ] == 0 ) ) { find3Squares( b, squares ); if ( squares[ 0 ] > 0 ) squares[ 3 ] = a; else { a--; b = n - a * a; } } } } I decide to test find4Squares() with a for loop in the main() function after asking the client for low and high values of the for loop. That is, Declare int variables low and high. Print the message Enter low and high values for four squares problem. Use scanf() function to get low and high. for ( int i = low; i <= high; i++ ) Declare an integer array called values initialized to four zeros. Call find4Squares( i, values ) Print i and values with a void function printSquares() and parameters I and values. C uses the function scanf() to obtain the value of a variable from the keyboard. The statement scanf( %d, &low ) assigns the integer the client enters to the int variable low. Notice the use of the address operator & before the variable low. To get low and high from the keyboard requires scanf( %d %d, &low, &high ) The function printSquares() prints i and the nonzero items in the array values. I must use a while loop to print the non zero items in values. /* Print n and the non zero items of the values array. */ void printSquares( int n, int values [ ] ) Print n. Declare an integer i intialized to 0. while values[ i ] > 0 Print values[ i ] Increment i. Print the new line character. Ill provide you with the actual C code in a separate file and with the commands needed to compile and run the code. The purpose of this note was to illustrate what I expect from you when I ask you to write a design for an assignment and to introduce you to the C language. The syntax of C is very similar to the syntax of Java. In fact the designer for the Java language decided to use its syntax to entice C programmers to switch to Java. One key difference is that C has no class (but C++ does). Another key difference is that C has something called struct (for structure) and pointers. I'll treat structs and pointers later in the course. Now heres your first assignment

Design Assignment 0 : Design software to verify a statement about positive integers. The overall objective of your first design assignment is to improve your ability to solve problems. In particular, you will design functions that use either a for loop or a while loop to verify the following statement about positive integers: A positive integer greater than 2 can be written as a sum of two positive integers k and m such that 2k + m is prime. As examples, 2 = 1 + 1, 3 = 2 + 1, 4 = 1 + 3, 20 = 5 + 15, 50 = 11 + 39, 112 = 1 + 111, 666 = 7 + 659, 1000000 = 7 + 999993 You must design an algorithm to express a positive integer greater than 1 as a sum k + m where 2k + m is a prime number. A brute force algorithm that uses a while loop is acceptable. A design uses paragraphs that explain the steps you need to solve the problem. I will read pseudo code only if explanation in English precedes it. Once you have an algorithm you must provide a simulation with a table for your algorithm with one or two representative small positive integers. You must also design another function to count the number of different ways to express a particular positive integer as a sum k + m where 2k + m is prime. As examples, the count for 10 is 3 since 10 = 1 + 9 = 5 + 5 = 7 + 3, the count for 20 is 2 since 20 = 5 + 15 = 9 + 11 and the count for 112 is 8 since 112 = 1 + 111 = 5 + 107 = 7 + 105 = 13 + 99 = 23 + 89 = 25 + 87 = 41 + 71 = 47 + 65 For the function that performs the count, I must warn you that the computation of 2 k + m will overflow for k > 30 for integer type and for k > 62 for long type. Your design must indicate the calls to each of these functions. It must also indicate what you will do to test each function somewhat rigorously.