patternjavaMajor

Sums of perfect powers

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

perfectpowerssums

Problem

import java.util.ArrayList;

public class SumsOfPerfectPowers {

    ArrayList numList = new ArrayList(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));

    }

}

Is this piece of code well-coded?

Are there any bad habits here?

What can be improved?

Solution

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

-
Access modifiers of numList and result should be private:

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

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

private List numList = new ArrayList(5000001);

-
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++) { ... }

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

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

-
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 perfectPowers = new ArrayList();

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

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

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

-
The empty static block is unnecessary:

static {
}

Code Snippets

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

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

private static final int MAX = 5000000;

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

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

Context

StackExchange Code Review Q#15060, answer score: 36

Revisions (0)

No revisions yet.