• CONTEST ALERT - Experience the power of DDR5 memory with Kingston Click for details

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
 

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.
 

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 ? :D
 
Last edited:

baiju

Ambassador of Buzz
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.
 

webgenius

Ambassador of Buzz
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 ?
 

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

Desmond

Destroy Erase Improve
Staff member
Admin
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 ?
 
Top Bottom