# Sums of perfect powers

``````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() {
for (int i = 2; i <= 2237; i++) {
int j = 2;
double value;
while ((value = Math.pow(i, j)) <= 5000000) {
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?
-

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) {
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;
}
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 {
}
``````
-
+1 very complete look around problems –  cl-r Aug 27 '12 at 8:12
Registered just to give you an upvote. –  user1477388 Aug 27 '12 at 14:19
@user1477388: Thanks :-) –  palacsint Aug 27 '12 at 15:16

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

-
lol, will BitSet be more efficient than boolean arrarys? –  hugemeow Aug 26 '12 at 15:53

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!
-
About 1, it's a constructor. –  Esko Luontola Aug 25 '12 at 22:34
Ah! My bad! I copied the body of the class for review. Updated by comments. –  Vikdor Aug 26 '12 at 2:59

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);
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)) {
}
}
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
-

### 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 `Integer`s, not `Long`s. 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>();
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.
}
}
// 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++) {
long n = this.perfectPowers.get(i) + this.perfectPowers.get(j);
if (n < limit) {
sumOf2[(int)n] = true;
} else {
break;
}
}
}
``````

### `howMany()`

• Naming: It wasn't immediately obvious to me what its purpose 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:

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;
}
``````
-