challenging problems

[jayant3001]

hi
i ve tried to solve this prob using java:
For a positive integer n, let σ2(n) be the sum of the squares of its divisors. For example,

σ2(10) = 1 + 4 + 25 + 100 = 130.
Find the sum of all n, 0 n 64,000,000 such that σ2(n) is a perfect square.

but its taking long long time to run
can anybody help??
this is my code:

import java.math.*;
import static java.lang.Math.*;
public class prob211
{
	public prob211()
	{
		BigInteger sum = BigInteger.ZERO;
		
		for(BigInteger i = BigInteger.valueOf(1);i.compareTo(BigInteger.valueOf(64000000))<0;i=i.add(BigInteger.ONE))
		{
			BigInteger x = BigInteger.ZERO;
			BigInteger sqsum = BigInteger.ZERO;
			for(BigInteger j = BigInteger.valueOf(1);j.compareTo(BigInteger.valueOf((i.divide(BigInteger.valueOf(2))).longValue()))<=0;j=j.add(BigInteger.ONE))
			{
				if((i.mod(j)).equals(BigInteger.ZERO))
				{
					sqsum = sqsum.add(j.multiply(j));
				}
			}
			sqsum=sqsum.add(i.multiply(i));
			long y =(long) sqrt(sqsum.longValue());
			for(BigInteger k= BigInteger.ONE;k.compareTo(BigInteger.valueOf(y))<=0;k=k.add(BigInteger.ONE))
			{
			  x = x.add(((k.multiply(BigInteger.valueOf(2))).subtract(BigInteger.ONE)))	;
			}
			if(x.equals(sqsum))
			{
			sum = sum.add(i);
			}
			}
		System.out.println(sum);
	} 
	public static void main(String[] args)
	{
	  new prob211();
	}
}

[Norm]

Have you tried debugging your code by adding println() statements to print out every so often to show progress?

[Eranga]

Yes debug and see, I think you are working on a Java IDE. Check about the following loop you are using.

		if((i.mod(j)).equals(BigInteger.ZERO))
		{
			sqsum = sqsum.add(j.multiply(j));
		}

it may take a long time to execute.

[Norm]

I'd rewrite the program to use int or long variables anywhere they work. All those method calls will take time.
To see where the code is eating CPU time use the -Xprof option on the java command. You only need a few 1000 loops to get an idea where the time is being spent, not 64M

[jayant3001]

i checked using println(). upto 10000 its going well but after that its taking long time

[jayant3001]

ya mod i m working on java IDE .Is there any other way to do that ?

[jayant3001]

hi norm
but number is too big to work with long or int thats why i m using BigInteger

[Norm]

Have you tried a version that uses int or long?
How long to they take?

[Norm]

What number is too big? How big? Why are all the numbers BigInteger? Do the loop control variables get that large?

What does the for loop on k compute? Does it always have to start at 1?

For tests I ran you code for 10000 loops - it took 48 secs.
I rewrote the code to use a modified version of BigInteger and changed the for(k) loop to return y*y and it took 3 secs. Both versions get the same answer:
//sum=36446 for 10000, time=48859 your code
//sum=36446 for 10000, time=3172 my version

[jayant3001]

BigInteger is needed only for variable sum.but i easy other place for easy .I think where u use long or int instead of BigInteger its does not make any difference .
k is for checking perfect square n its necessary to start from 1.
can u just tell what modified version of BigInteger u used so that it took less time ??any way main prob is for loop containing
j.

[Norm]

Instead of rewriting your code to use long, I wrote this class hoping that it would be faster than Sun's version.

   static class BigInteger {
      final static BigInteger ZERO = new BigInteger(0);
      final static BigInteger ONE = new BigInteger(1);
      final static BigInteger TWO = new BigInteger(2);
      long value;

      BigInteger() {
      }
      BigInteger(long v){
         value = v;
      }
      //-----------------------------
      long longValue(){
         return value;
      }
      static BigInteger valueOf(long ln) {
         if(ln == 0) return ZERO;
         else if(ln == 1) return ONE;
         else if(ln == 2) return TWO;
         else return new BigInteger(ln);
      }
      int compareTo(BigInteger bi) {
         return (int)(value - bi.value);
      }
      BigInteger divide(BigInteger bi) {
         return new BigInteger(value/bi.value);
      }
      BigInteger multiply(BigInteger bi) {
         return new BigInteger(value*bi.value);
      }
      BigInteger mod(BigInteger bi) {
         long mod = value % bi.value;
         return valueOf(mod);
      }
      BigInteger add(BigInteger bi) {
         return new BigInteger(value + bi.value);
      }
      BigInteger subtract(BigInteger bi) {
         return new BigInteger(value - bi.value);
      }
      public boolean equals(BigInteger bi) {
         return (value == bi.value);
      }
      public String toString() {
         return ""+value;
      }
   } // end class BigInteger

What is the size of the number that is too big for long? long is 2^64
using primitives will make your code much faster.
Also you could move some expressions outside of the loop:

         final BigInteger endJ = BigInteger.valueOf((i.divide(BigInteger.valueOf(2))).longValue()); 
 ...
BigInteger BIy = BigInteger.valueOf(y)
           ...
           k.compareTo(BIy) <= 0;

instead of computing them over and over.


I replaced the for(k) loop with y*y and I get the same answers as your code with the loop. And its much faster.

Have you tried the -Xprof operand to get a profile of where you code is executing? You'll need to break the constructor up into a couple of methods to see which code.

[jayant3001]

yes i did -Xprof operation but actually i m new to this so i could not understand this .can u explain it plz.

36446

Flat profile of 65.57 secs (4428 total ticks): main

  Interpreted + native   Method                        
  0.0%     1  +     0    java.math.BigInteger.subtract
  0.0%     1  +     0    Total interpreted

     Compiled + native   Method                        
 21.4%   949  +     0    java.math.MutableBigInteger.divide
 17.6%   732  +    46    java.math.BigInteger.add
 10.9%   436  +    46    java.math.BigInteger.valueOf
  7.6%   287  +    49    java.math.BigInteger.subtract
  7.4%   236  +    91    java.math.BigInteger.add
  7.1%   313  +     0    prob211.<init>
  5.0%   185  +    36    java.math.BigInteger.multiplyToLen
  4.7%   164  +    45    java.math.BigInteger.multiply
  4.1%   180  +     0    java.math.BigInteger.compareTo
  4.1%   167  +    13    java.math.BigInteger.subtract
  2.6%    47  +    66    java.math.BigInteger.divide
  2.4%    45  +    63    java.math.BigInteger.remainder
  2.1%    93  +     2    java.math.BigInteger.trustedStripLeadingZeroInts
  1.4%    64  +     0    java.math.MutableBigInteger.copyValue
  0.9%    39  +     0    java.math.MutableBigInteger.clear
  0.7%     0  +    30    java.math.BigInteger.<init>
  0.1%     3  +     0    java.math.BigInteger.mod
100.0%  3940  +   487    Total compiled


Flat profile of 6.40 secs (1 total ticks): DestroyJavaVM

  Thread-local ticks:
100.0%     1             Unknown: thread_state


Global summary of 71.99 seconds:
100.0%  4927             Received ticks
  7.1%   349             Received GC ticks
  2.5%   122             Other VM operations
  0.0%     1             Unknown code

[Norm]

21.4% 949 + 0 java.math.MutableBigInteger.divide
17.6% 732 + 46 java.math.BigInteger.add
10.9% 436 + 46 java.math.BigInteger.valueOf
7.6% 287 + 49 java.math.BigInteger.subtract

Of the 66 seconds for your program to execute, over 50% was spent in the above 4 methods.
Most of you usages of valueOf (11%) are for constants and should be final and outside of the loops.

You still have NOT stated how large the numbers are you are working with.
Using classes for the repeated computations in your code is VERY EXPENSIVE!!!

[Eranga]

ya mod i m working on java IDE .Is there any other way to do that ?

No I'm just asking. Because it's too easy to debug your code and see what happen. You can use the watch list as well.

[jayant3001]

norm
in code above i ve written that loop should be up to 64000000
and if we take a number near it and add square of its factors then certainly it will be very large

[jayant3001]

thanks for explanation .............

[Norm]

How long does it take on your computer to run your code for 64M loops?

[jayant3001]

i wait for 4 hrs but could not get answer

[jayant3001]

hi norm i ve written code using long n int but same prob here

import static java.lang.Math.*;
public class prob211a
{
	public prob211a()
	
	{
		long sum = 0L;
		for(int i = 1;i<64000000;i++)
		{
			 long sqsum = 0L;
			final int rem = i/2;
			for(int j=1;j<=rem;j++)
			{
				if(i%j==0)
				{
					sqsum += j*j; 
				}
			}
			sqsum+= i*i;
			long sqr = (long)sqrt(sqsum);
			if(sqsum == (sqr*sqr))
			{
				sum+= i;
			//	System.out.println(i);
			}
		}
		System.out.println(sum);
	}
	public static void main(String[] args)
	{
		new prob211a();
	}
}

[Eranga]

Can you explain what's your question is. Is that take a long time to get a result?