How to count powerful numbers

Question

I have ran into a rather peculiar Java coding question today, and I wish to get some clarifications.

Here is the question posed:

A powerful number is a positive integer m that for every prime number p dividing m, p*p also divides m.

        (a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors,
        which are 1 and the prime number itself, the first prime numbers are: 2, 3, 5, 7, 11, 13, ...)

        The first powerful numbers are: 1, 4, 8, 9, 16, 25, 27, 32, 36, ...

        Please implement this method to
        return the count of powerful numbers in the range [from..to] inclusively.

My question is what exactly IS a powerful number? Here is my definition:

1. A positive integer AND
2. A positive integer that is divisible by a prime number AND
3. A positive integer that is divisible by a primeValX*primeValX and also divisible by a primeValX

Am I wrong on my assertion? Because it doesn't return the right result when i apply my assertions to my code.

The supposed result should be 1, 4, 8, 9, 16

Here is the actual result I got:

i: 4 j: 2 ppdivm: 0 pdivm: 0
powerful num is: 4
i: 8 j: 2 ppdivm: 0 pdivm: 0
powerful num is: 8
i: 9 j: 3 ppdivm: 0 pdivm: 0
powerful num is: 9
i: 12 j: 2 ppdivm: 0 pdivm: 0
powerful num is: 12
i: 16 j: 2 ppdivm: 0 pdivm: 0
powerful num is: 16
total count: 5

Here are my codes:

  public static int countPowerfulNumbers(int from, int to) {
            /*
              A powerful number is a positive integer m that for every prime number p dividing m, p*p also divides m.

              (a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors,
              which are 1 and the prime number itself, the first prime numbers are: 2, 3, 5, 7, 11, 13, ...)

              The first powerful numbers are: 1, 4, 8, 9, 16, 25, 27, 32, 36, ...

              Please implement this method to
              return the count of powerful numbers in the range [from..to] inclusively.
             */
           int curCount=0;
           int curPrime;
           int[] rangePrime;
           int pdivm, ppdivm;
           for(int i=from; i<=to; i++){
               if(i<0){
                   continue;
               }


               rangePrime = primeRange(1 , i);
               for(int j=0; j<rangePrime.length-1; j++){

                   pdivm = i%rangePrime[j];
                   ppdivm = i%(rangePrime[j]*rangePrime[j]);
                   //System.out.println("ppdivm: " + ppdivm + " pdivm: " + pdivm);

                   if(pdivm == 0 && ppdivm == 0){
                       curCount++;
                       System.out.println("i: " +i + " j: " + rangePrime[j] + " ppdivm: " + ppdivm + " pdivm: " + pdivm);

                       System.out.println("powerful num is: " + i);
                   }

               }


           }

           System.out.println("total count: " + curCount);
           return curCount;
        }

       public static int[] primeRange(int from, int to){

           List<Integer> resultant = new LinkedList<Integer>();
           for(int i=from; i<=to; i++){
               if(isPrime(i)== true){
                   resultant.add(i);
               }
           }

           int[] finalResult = new int[resultant.size()];
           for(int i=0; i<resultant.size(); i++){
               finalResult[i] = resultant.get(i);

           }

           return finalResult;
       }

       public static boolean isPrime(int item){

           if(item == 0){
               return false;
           }

           if(item == 1){
               return false;
           }

           Double curInt, curDivisor, curDivi, curFloor;
           for(int i=2; i<item; i++){
               curInt = new Double(item);
               //System.out.println(curInt);
               curDivisor = new Double(i);
               //System.out.println(curDivisor);

               curDivi = curInt/curDivisor;
               //System.out.println(curDivi);

               curFloor = Math.floor(curDivi);

               if(curDivi.compareTo(curFloor) == 0){
                   return false;
               }
           }

           return true;
       }

    public static void main(String[] args){

        System.out.println(isPrime(1));

        int[] printout = primeRange(1, 10);
        for(int i=0; i<printout.length; i++){
            System.out.print(" " + printout[i] + " ");
        }
        System.out.println("");
        countPowerfulNumbers(1, 16);

        return;
    }

Thanks!

Answer 1

clarification, correction of you code, and faster method below

Your definition has errors:

2 : A positive integer that is divisible by a prime number => it is the definition of any non prime number

3 : A positive integer that is divisible by a primeValXprimeValX and also divisible by a primeValX => is equivalent of A positive integer that is divisible by a primeValXprimeValX (and it includes assertion 2)

Then your definition is "any not prime number with some prime divisor ^2 "

I took the original definition,you put:

A powerful number is a positive integer m that for every prime number p dividing m, p*p also divides m.

like this one: http://mathworld.wolfram.com/PowerfulNumber.html

Then my algorithm: check for every prime dividor X of your number, if X*X is also a dividor. If not, it is finished.

I correct your code like this

for(int i=from; i<=to; i++)
        {
       // CHANGE THERE (or <=3)
        if(i<=1)
           continue;

I put one flag:

// by default:
boolean powerfull=true;

If i is prime itself, not powerfull !

// if prime: finished !
if (isPrime(i))
    continue;

The big change is in your test:

 // RULE is: i divisor => ixi must be a dividor
 if(pdivm == 0)
       if (ppdivm != 0)
            {
             // You lose !
           System.out.println("i: " +i + " j: " + rangePrime[j] + " ppdivm: " + ppdivm + " pdivm: " + pdivm);
            powerfull=false;
            }

Then, in you main loop:

if (powerfull)
    {
    curCount++;
    System.out.println("powerful num is: " + i);
    }

SECOND METHOD, faster especially if your range is big:

as pointed in my link:

Powerful numbers are always of the form a^2b^3 for a,b>=1.

Then: make a loop from 2 to range^1/2 another embedded loop from 2 to range^1/3 and multiply

like that:

int from=4;
int to=100000;

Set<Integer> set=new TreeSet<Integer>(); // automatically sorted

// Max candidates
int maxSquarecandidate= (int) Math.sqrt(to);
int maxCubeCandidates=(int) Math.pow(to,1.0/3)+1;

for (int candidate1=1; candidate1<maxSquarecandidate;candidate1++)
    for (int candidate2=1; candidate2<maxCubeCandidates;candidate2++)
        {
        int result=candidate1*candidate1*candidate2*candidate2*candidate2;

        if ((result!=1) && (result>=from) && (result<=to)) set.add(result);
        }

System.out.println(set);

hope it helps !

Answer 2

Your definition does not match the quoted definition. Part 1 is correct. Parts 2 and (as Draco18s commented) 3 are incorrect.

Your second point is almost a duplicate of the first. The singular difference is that 1 is a positive integer, but it is not divisible by any prime numbers (1 itself is not prime, as your isPrime() function correctly returns).

Your third point starts off with a (in my opinion) awkward wording of the conditions. It seems to suggest checking if (i % (p*p)) == 0 first, and then checking (i % p) == 0, which would then be redundant and allow for missing the crucial case where (i % (p*p)) != 0 but (i % p) == 0, because the first check would cause the second to be skipped. Fortunately, your code does the checks in the correct (p, then p*p) order.

Now we come to the major error in your third point, the one that Draco18s and Frank were trying to point out. You state that a powerful number must be divisible by a primeValX*primeValX and a primeValX. The given definition states a powerful number must be divisible by primeValX*primeValX for every primeValX it is divisible by.

What's the difference? Your version requires that there is at least one primeValX*primeValX that can divide a powerful number. Thus it will exclude 1, since it is not divisible by any primes, and include numbers like 12, which is divisible by the prime 2, and 2*2.

The given version requires that for all primes that divide a powerful number, the squares of the primes also divide them. This has two implications:

1. All or every succeeds by default if there are no candidates. Thus, since there are no prime divisors to fail the test for 1, 1 is a powerful number.
2. You cannot take a shortcut and succeed as soon as you find one p and p*p that work. You have to test all prime divisors and their squares before you can know if it is a powerful number. You can fail as soon as you get one prime divisor whose square is not also a divisor.

Answer 3

Your definition is incorrect based on the Wiki article on Powerful Numbers.

It says that for each prime p dividing your number, p^2 also divides that number.

You're getting 12 as a result because your not making the restriction of ALL primes dividing the number. So 12 is divisible by 2 and 2^2=4. However, it's also divisible by 3, but not 3^2=9.