Sums of perfect powers

Question

import java.util.ArrayList;

public class SumsOfPerfectPowers {

    ArrayList<Long> numList = new ArrayList<Long>(5000001);
    // status of whether a number is power number
    boolean[] result = new boolean[5000001];

    public SumsOfPerfectPowers() {
        numList.add((long) 0);
        numList.add((long) 1);
        for (int i = 2; i <= 2237; i++) {
            int j = 2;
            double value;
            while ((value = Math.pow(i, j)) <= 5000000) {
                numList.add((long) value);
                j++;
            }
        }

        int len = numList.size();
//      System.out.println(len);
        int value;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                value = (int) (numList.get(i) + numList.get(j));
                if (value <= 5000001) {
                    result[value] = true;
                }
            }
        }


    }

    static {
    }

    public int howMany(int a, int b) {
        int sum = 0;
        for(int i=a;i<=b;i++) {
            if(result[i]) {
                sum ++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        SumsOfPerfectPowers test = new SumsOfPerfectPowers();

        System.out.println(test.howMany(0, 1));
        System.out.println(test.howMany(5, 6));
        System.out.println(test.howMany(25, 30));
        System.out.println(test.howMany(103, 103));
        System.out.println(test.howMany(1, 100000));

    }

}

1. Is this piece of code well-coded?
2. Are there any bad habits here?
3. What can be improved?

Answer 1

1. (long) 0 scructures should be written as 0L.

2. Access modifiers of numList and result should be private:

   private ArrayList<Long> numList = new ArrayList<Long>(5000001);
   // status of whether a number is power number
   private boolean[] result = new boolean[5000001];
   

3. ArrayList<...> reference types should be simply List<...>. See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces

   private List<Long> numList = new ArrayList<Long>(5000001);
   

4. 5000000 is a magic number. Using named constants instead of numbers would make the code more readable and less fragile. If you have to modify it's value it's easy to forget to do it everywhere. 2237 is also a magic number and a computed value. I'd create a MAX constant:

   private static final int MAX = 5000000;
   

   and use it everywhere, for example:

   private boolean[] result = new boolean[MAX + 1];
   

   then change 2237 to the following:

   final int maxSquare = (int) Math.ceil(Math.sqrt(MAX));
   for (int i = 2; i <= maxSquare; i++) { ... }
   

5. numList only used in the constructor, so it could be a local variable there instead of a field. Try to minimize the scope of variables. See Effective Java, Second Edition, Item 45: Minimize the scope of local variables.

6. Actually, I'd rename numList to perfectPowers since it stores perfect powers. I'd make the code more readable and easier to maintain.

7. You set the initial capacity of the list to 5000000 while it contains only about 2500 elements. It's a huge memory wasting. I'd use the default constructor of the ArrayList which use less memory.

   final List<Long> perfectPowers = new ArrayList<Long>();
   

8. Math.pow uses floating point numbers which are not always precise. For small numbers it's correct, but for big numbers it not:

   final long a = 97761243;
   final long aa = a * a;
   System.out.println("long            " + aa);
   System.out.println("Math.pow        " + ((long) Math.pow(a, 2)));
   System.out.println("BigInteger.pow: " + BigInteger.valueOf(a).pow(2).longValue());
   

   It prints:

   long            9557260632905049
   Math.pow        9557260632905048
   BigInteger.pow: 9557260632905049
   

   So, I'd change the while loop to the following:

   long value;
   while ((value = BigInteger.valueOf(i).pow(j).longValue()) <= MAX) {
       perfectPowers.add(value);
       j++;
   }
   

9. Some additional changes on the same loop would result the following:

   while (true) {
       final long value = BigInteger.valueOf(i).pow(j).longValue();
       if (value > MAX) {
           break;
       }
       perfectPowers.add(value);
       j++;
   }
   

   It does the same but I think it's easier to read.

10. In the first for loop I'd rename i to base and j to exponent, and the parameters of the howMany method to lowerBound and upperBound.

11. The empty static block is unnecessary:

    static {
    }
    

Answer 2

In addition to the other answers' points which don't need reiterating,

In almost all cases, a boolean[] can be replaced with a BitSet. It takes a significant (and deterministic) amount of space, and provides you with logical operations that, if you tried to do manually on a boolean[] you likely introduce subtle bugs into at worst, and would reinvent the wheel at best. :-)

Answer 3

A couple of comments:

1. Generally, it is recommended to declare variables as interface types for extensibility and implementation-neutral as much as possible. You would realize this when writing large programs. Based on this, numList would be of type List or Collection.
2. Instead of typecasting to (long), you can simply suffix the values with 'L' to make them long.
3. It is recommended to declare the member variables as private. The default scope is package private.
4. Didn't understand the purpose of empty static block!

Answer 4

That's how I would write it:

import java.util.ArrayList;
import java.util.List;

public class SumsOfPerfectPowers {

    private final static int SIZE = 5000001;
    private final boolean[] result = new boolean[SIZE];

    public SumsOfPerfectPowers() {
        List<Long> numList = fillNumList();
        fillResults(numList);
    }

    private List<Long> fillNumList() {
        List<Long> numList = new ArrayList<Long>(SIZE);
        numList.add(0L);
        numList.add(1L);
        int limit = 1 + (int) Math.sqrt(SIZE);
        for (int i = 2; i <= limit; i++) {
            for(long j = 2, value = i*i; value < SIZE; j++, value = (long) Math.pow(i, j)) {
                numList.add(value);
            }
        }
        return numList;
    }

    private void fillResults(List<Long> numList) {
        int len = numList.size();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int value = (int) (numList.get(i) + numList.get(j));
                if (value < SIZE) {
                    result[value] = true;
                }
            }
        }
    }

    public int howMany(int a, int b) {
        int sum = 0;
        for(int i=a; i<=b; i++) {
            sum += result[i] ? 1 : 0;
        }
        return sum;
    }

    //...
}

• usually members should be private (there are exceptions, e.g. for final members it might be OK to make them public)
• don't use magic numbers, give them a name. Or let the client provide them (maybe have a sensible default)
• prefer for loops, note that you can have multiple init and step parts. Generally, try to limit the scope of your variables
• the "assign then compare" pattern in while is not kewl
• try to make your methods smaller
• prefer interfaces over concrete classes (e.g. List)
• don't hold unnecessary data in your objects. For such a long list even uncle Bob would avoid it

Answer 5

Constructor

• Magic numbers: You have unexplained constants all over the place: 5000001, 2237, 5000000. The limit should be defined just once, preferably as a parameter to the constructor.
• Use of long: Array indices can only be int, not long (JLS Sec 10.4). Therefore, the largest limit you can support is Integer.MAX_VALUE. If that's the case, then numList should also store Integers, not Longs. However, I would still recommend the use of long to store your intermediate sums and products to protect against overflow.

• Use of floating point: Floating point calculations should never be used in proofs of integer arithmetic.

  

  I would start your constructor like this:

  public SumsOfPerfectPowers(int limit) {
      this.limit = limit;
  
      SortedSet<Integer> perfectPowers = new TreeSet<Integer>();
      perfectPowers.add(0);
      perfectPowers.add(1);
      for (int base = 2; base * base < limit; base++) {
          for (long n = base * base; n < limit; n *= base) {
              // n is long to guard against overflow.
              // Casting n to int is safe because n < limit, which is an int.
              perfectPowers.add((int)n);
          }
      }
      // List traversal is faster than tree traversal
      this.perfectPowers = new ArrayList<Integer>(perfectPowers);
  
      // etc.
  }
  

• Commutativity: Since a + b = b + a, you can cut your inner loop in half, on average, when building result. If the list of perfect powers is sorted, like I have done so above, then more short-circuiting is possible.

  this.sumOf2 = new boolean[limit];
  for (int i = 0; i < this.perfectPowers.size(); i++) {
      for (int j = 0; j <= i; j++) {
          int n = this.perfectPowers.get(i) + this.perfectPowers.get(j);
          if (0 < n && n < limit) {
              sumOf2[n] = true;
          } else {
              break;
          }
      }
  }
  

howMany()

• Naming: It wasn't immediately obvious to me what the purpose of howMany() was until I read the code. I suggest renaming howMany() to countInInterval().

• Inclusive-inclusive vs. inclusive-exclusive bounds: Inclusive-exclusive bounds are a very common pattern, especially in languages whose arrays are indexed from 0. For-loop conditions usually check for i < n, not i <= n. For more examples, consider also:

  • std::vector::end in C++
  • String.substring(beginIndex, endIndex) in Java
  • range(start, stop) in Python

  Therefore, I would consider it reasonable for this function to take as parameters an inclusive lower bound and and exclusive upper bound.

With a bit of variable renaming thrown in…

public int countInInterval(int lbIncl, int ubExcl) {
    int count = 0;
    for (int i = lbIncl; i < ubExcl; i++) {
        if (this.sumOf2[i]) {
            count++;
        }
    }
    return count;
}