# sum of four squares of an integer



## reddychandra (Sep 22, 2012)

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 (Sep 22, 2012)

The four integers may be same or need to different ?


----------



## icebags (Sep 22, 2012)

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 (Sep 23, 2012)

Yeah really weird program.

@icebags
didn't really get you.


----------



## Desmond (Sep 23, 2012)

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


----------



## icebags (Sep 23, 2012)

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

~~~~~

z = input value;


```
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.



DeSmOnD dAvId said:


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



all integers, r u kidding ?


----------



## dashing.sujay (Sep 23, 2012)

DeSmOnD dAvId said:


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



Yes, because 0 is also included in integers.


----------



## baiju (Sep 23, 2012)

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 (Sep 23, 2012)

First we need proper information about the problem.


----------



## mastercool8695 (Sep 23, 2012)

really wierd.
but found these :
*www.google.co.in/url?sa=t&rct=j&q=...qIDQAQ&usg=AFQjCNHMehqOidwVcx8aD6G5_EgdIhnMCA

*www.google.co.in/url?sa=t&rct=j&q=...qIDQAQ&usg=AFQjCNHpNb4oqXoeVsW9FVfnDe9vIU9jug

more here : *www.google.co.in/webhp?sourceid=ch...on.2,or.r_gc.r_pw.r_cp.r_qf.&biw=1024&bih=653

hope this helps for those who dont believe this to be true


----------



## sharang.d (Sep 23, 2012)

Java:

Sum of squares
Sum of squares


----------



## webgenius (Sep 24, 2012)

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 (Sep 24, 2012)

mastercool8695 said:


> really wierd.
> but found these :
> *www.google.co.in/url?sa=t&rct=j&q=...qIDQAQ&usg=AFQjCNHMehqOidwVcx8aD6G5_EgdIhnMCA
> 
> ...



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 (Sep 24, 2012)

webgenius said:


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



And how ?


----------



## vickybat (Sep 24, 2012)

^^ 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:


```
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".


----------



## Desmond (Sep 25, 2012)

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 :


```
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 :


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


----------



## vickybat (Sep 25, 2012)

^^ Code isn't getting compiled. What algorithm you've used?


----------



## Desmond (Sep 25, 2012)

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.


----------



## vickybat (Sep 25, 2012)

^^ Have you added keyboard input? How are you giving input?

I'm getting the following error:


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

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


----------



## icebags (Sep 25, 2012)

DeSmOnD dAvId said:


> What error are you getting?
> 
> Compiling fine on my machine.
> 
> ...



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 ?


----------



## vickybat (Sep 25, 2012)

^^ Did you check that algorithm i posted given by that guy? I think that's a good solution coz it finds multiple possibilities.


----------



## sharang.d (Sep 25, 2012)

DeSmOnD dAvId said:


> 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?



36^2 + 34^2 + 2^2 + 0^2 = 2456

No one read my links 


> Java:
> 
> Sum of squares
> Sum of squares source


----------



## Desmond (Sep 25, 2012)

vickybat said:


> ^^ Have you added keyboard input? How are you giving input?
> 
> I'm getting the following error:
> 
> ...



Sorry, it takes input as an argument.


----------



## icebags (Sep 25, 2012)

vickybat said:


> ^^ Did you check that algorithm i posted given by that guy? I think that's a good solution coz it finds multiple possibilities.



now i checked.
the guy takes that assumption, but didn't explain why this logic must work. anyways, thanks for the link.

if u want this way, try this ::

```
z = input val;

i1 = floor(sqrt(z));                        --> like floor of sqrt(10) is 3
i2 = floor( Sqrt(z - i1^2) );
i3 = floor( Sqrt(z - i1^2 - i2^2) );
i4 =  Sqrt(z - i1^2 - i2^2 - i3^2 ) ;
```
now, as per that logic, its should be : z = i1^2 + i2^2 + i3^2 + i4^2.

hopefully i didn't make mistake.




sharang.d said:


> 36^2 + 34^2 + 2^2 + 0^2 = 2456
> 
> No one read my links



big huge program and i am bad at mathematics. (it kinda ruined my HS result). sorry man. .


----------



## vickybat (Sep 26, 2012)

^^ Will try out ur logic mate. 

This works i guess. Algorithm isn't mine and i found it over web.

Check it out guys:


```
[B]public class lagrange{
	public static void sum_of_squares(int n){
	int t1, t2, t;
   
       for (int i = (int) Math.sqrt(n / 4); i * i <= n; i++) {
       
               t1 = n - i * i;
     
       for (int j = (int) Math.sqrt(t1 / 3); j <= i && j * j <= t1; j++) {
            
               t2 = t1 - j * j;
            
       for (int k = (int) Math.sqrt(t2 / 2); k <= j && k * k <= t2; k++) {
               
                t = (int) Math.sqrt(t2 - k * k);
                
           if (t <= k && t * t == t2 - k * k) {
                    System.out.println("(" + i + "^2) + (" + j + "^2) + ("+ k + "^2) + ("+ t +"^2)");
                }
            }
        }
    }
}
            
        
        public static void main (String [] args){
        	sum_of_squares(29);
        
        }
    }
[/B]
```

Pass any  arguements into the sum_of_squares method. It also gives multiple possibilities. Numbers like 23 won't work coz it requires 5 terms
i.e 4^2 + 2^2+ 1^2+ 1^2+ 1^2

Algorithm for that is different. Interestingly, all counter variables used, yield the answer.


----------

