# sum of four squares of an integer

#### reddychandra

##### Right off the assembly line
i am stuck with the c/c++ program to express an positive integer as the sum of squares of 4 integers plizzzzzzzzzzz help
if 78 is entered as input,................... the
output should come out as 6^2+5^2+4^2+1^2=78

#### dashing.sujay

##### Moving
Staff member
The four integers may be same or need to different ?

#### icebags

##### Technomancer
omg, who asks ppl to write these weird programs...... ? :O

here, try this ..... do 4 loops starting from 1 upto say square root of the input, for every value of outer root, run the inner loop between the same range.

#### gameranand

##### Living to Play
Yeah really weird program.

@icebags
didn't really get you.

#### Desmond

##### Destroy Erase Improve
Staff member
Is it possible to express all integers as sum of squares of four integers?

#### icebags

##### Technomancer
may be this should work ? sorry i forgot C .....

~~~~~

z = input value;

Code:
``````for i in 0..sqrt(z) loop
for j in 0..sqrt(z) loop
for k in 0..sqrt(z) loop
for l in 0..sqrt(z) loop
if i*i + j*j + k*k + l*l = z Then
print (i,j,k,l);
exit subroutine;
ElsIf  i*i + j*j + k*k + l*l > z Then
Exit loop;
Else
l = l+1;
End if;
End loop;
k = k + 1;
end loop;
j = j + 1;
end loop;
i = i + 1;
end loop;
print ('it doesnt work buddy. :-)');``````

edit: modified a bit. starting from 0 seems better.

Is it possible to express all integers as sum of squares of four integers?

all integers, r u kidding ?

Last edited:

#### dashing.sujay

##### Moving
Staff member
Is it possible to express all integers as sum of squares of four integers?

Yes, because 0 is also included in integers.

#### baiju

How that helps? Agreed you can express 4 as 2^2+0^2+0^2+0^2 but how will you express '3' as the sum of squares of four integers? Can we use the same number more than one time like 4 = 1^2 + 1^2 + 1^2 + 1^2 ?

The smallest number will be 1^2 + 2^2 + 3^2 + 4 ^2 = 30 unless the same number can be repeated.

#### gameranand

##### Living to Play
First we need proper information about the problem.

#### webgenius

You'll need 4 loops for looping through the numbers from 1 to square root of N. No other go.

Seriously, it is a very stupid question. Instead of asking to write a program for this, the focus should be more on trying to reduce the complexity.

#### icebags

##### Technomancer

thanks for those feedback, many gifted ppl in past few centuries have really done some great jobs with mathematics.

anyways, where is opee ?

#### dashing.sujay

##### Moving
Staff member
Instead of asking to write a program for this, the focus should be more on trying to reduce the complexity.

And how ?

#### vickybat

##### I am the night...I am...
^^ Working on that. Will post soon.

Brute force algorithm is the key for solving lagrange's four square problem. Lets see how it goes.

Not able to implement what i found. The following seems to be the optimized version but looks vague:

Code:
``````nr = square_root(N);
S = {0, 1, 2^2, 3^2, 4^2,.... nr^2};
for (a = nr; a >= nr/2; a--)
{
r = N - S[a];
// it is now a 3SUM problem
for(b = a; b >= 0; b--)
{
r1 = r - S[b];
if (r1 < 0)
continue;

if (r1 > N/2) // because (a^2 + b^2) >= (c^2 + d^2)
break;

for (c = 0, d = b; c <= d;)
{
sum = S[c] + S[d];
if (sum == r1)
{
print a, b, c, d;
c++; d--;
}
else if (sum < r1)
c++;
else
d--;
}
}
}``````

source

Having a bit of trouble replicating that into java. Check out the algorithm explained by a guy called "nebffa".

Last edited:

#### Desmond

##### Destroy Erase Improve
Staff member
Is four integers a constraint? 'Cause I've come across some test cases where the numbers are getting represented by more than four integers for ex. 2456.

Or, is there any constraint on the number to be represented?

EDIT:
This is the best I could come up with :

Code:
``````class sum{
public static int prod(int num){
int i=0,n;
/* if(num==0)
return 0; */
while(true){
if((i*i)>num){
i--;
n=i*i;
break;
}
i++;
}
//System.out.print(" "+n);
//return prod(num-n);
return n;
}
public static void main(String[] args){
int num=Integer.parseInt(args[0]);
System.out.println(num + " = ");
for(int count=0;count<4;count++){
int n=prod(num);
int sqroot=(int)Math.sqrt(n);
System.out.println(sqroot +" * "+ sqroot +" = " + n);
if(n==1)
continue;
num=num-n;
}

//System.out.println(num + " " + n);
}
}``````

I've tried to make it recursive, but stopped to keep it simple (The commented parts were for recursion). This code works perfectly for most test cases (Ex. 1234), but gives extra integers for some test cases (Ex. 2456).

This is what I get for 78 :

Code:
``````78 =
8 * 8 = 64
3 * 3 = 9
2 * 2 = 4
1 * 1 = 1``````

Last edited:

#### vickybat

##### I am the night...I am...
^^ Code isn't getting compiled. What algorithm you've used?

#### Desmond

##### Destroy Erase Improve
Staff member
What error are you getting?

Compiling fine on my machine.

My logic is to find the largest squared integer (say A), closest to the integer in question (say N). Then get the difference N = N - A and repeat the same to obtain B and so forth.

I think there might be some flaw in the logic. Will have to think a little more deeply.

Last edited:

#### vickybat

##### I am the night...I am...
^^ Have you added keyboard input? How are you giving input?

I'm getting the following error:

Code:
``````Exception in thread "main" java.lang.Error: Unresolved compilation problem:
n cannot be resolved to a variable

at sum.main(sum.java:32)``````

#### icebags

##### Technomancer
What error are you getting?

Compiling fine on my machine.

My logic is to find the largest squared integer (say A), closest to the integer in question (say N). Then get the difference N = N - A and repeat the same to obtain B and so forth.

I think there might be some flaw in the logic. Will have to think a little more deeply.

is that ok logic ? because if you take largest squared number in the first hand, then will it be possible to break the rest portion in sum of square of 3 numbers ?