sum of four squares of an integer

R

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

The four integers may be same or need to different ?

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.

Yeah really weird program.

@icebags
didn't really get you.

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

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.

DeSmOnD dAvId said:
Is it possible to express all integers as sum of squares of four integers?

all integers, r u kidding ?

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.

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.

First we need proper information about the problem.

M

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

Java:

Sum of squares
Sum of squares

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.

mastercool8695 said:
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

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

anyways, where is opee ?

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

And how ?

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

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:

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

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.

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

DeSmOnD dAvId said:
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 ?

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

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

vickybat said:
^^ 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)

Sorry, it takes input as an argument.

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

Code:

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.

.

^^ Will try out ur logic mate.

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

Check it out guys:

Code:

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