# powerful numbers program in java

Hi,

http://www.solveerrors.com/forums/count-find-powerful-numbers-202468.asp

I wonder what are these powerful numbers

1, 4, 8, 9, 16, 25, 27, 32, 36, ...

What is the logic to get them. I was not clear. Please advise.
LVL 7
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
1 is 1^0, one to the power zero (or 1^1 or 1^2 or 1^3 or ...)
4 is 2^2, two to the power two
8 is 2^3, two to the power three
9 is 3^2, three to the power two
16 is 2^4 (or 4^2), two to the power four (or four to the power 2)
25 is 5^2
27 is 3^3
32 is 2^5
36 is 6^2
...
Commented:
So a Powerful Number is a non-negative integer (that's a mathematical integer, not a Java one, which will be limited to Integer.MAX_VALUE), which, if it can be divided by any prime number (obviously smaller than it), and *also* divided by the square of that prime number, is classed as Powerful.

So get your code for finding prime numbers (eventually from your other question here on EE), and use it to test some number of your choice for divisibility by that prime AND the square of that prime, which if true will show it is one of these. Isn't that about it, ozo?
Commented:
That's one way to do it, but you don't actually need code for finding prime numbers if you notice that for any non-prime that divides your number, it would also be divisible by a smaller number that is prime
Information Technology SpecialistCommented:
It's been quite a while but, as I recall, a powerful number is one that can be expressed as an integer to the power of 2, an integer to the power of 3, or an integer to the power of 2 times an integer to the power of 3. Looking at the powerful numbers between 1 and 300, you can see how they all can be expressed with that criteria. However, I don't recall how they relate to prime numbers.

1      1^2 (or 1^3)
4      2^2
8      2^3
9      9^2
16      4^2
25      5^2
27      3^3
32      2^2*2^3
36      6^2
49      7^2
64      8^2
72      2^3*3^2
81      9^2
100      10^2
108      2^2*3^3
121      11^2
125      5^3
128      4^2*2^3
144      12^2
169      13^2
196      14^2
200      5^2*2^3
216      6^3
225      15^2
243      3^2*3^3
256      16^2
288      6^2*2^3
289      17^2

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
>>it would also be divisible by a smaller number that is prime<< . . . how does one establish the primeness of that? Are you saying you need to cache a list of primes somewhere?
Author Commented:
integer to the power of 2, an integer to the power of 3, or an integer to the power of 2 times an integer to the power of 3.

i think i have not got this clearly.

How we got these numbers

1      1^2 (or 1^3)
4      2^2
8      2^3
9      9^2
16      4^2
25      5^2
27      3^3
32      2^2*2^3
36      6^2
49      7^2
64      8^2
72      2^3*3^2
81      9^2
100      10^2
108      2^2*3^3
121      11^2
125      5^3
128      4^2*2^3
144      12^2
169      13^2
196      14^2
200      5^2*2^3
216      6^3
225      15^2
243      3^2*3^3
256      16^2
288      6^2*2^3
289      17^2

i understand prime number program and how to get prime number from other my EE post.

What is the extension of logic i have to do the power numbers?

I still not clear on what is power number?

1 is 1^0, one to the power zero (or 1^1 or 1^2 or 1^3 or ...)
4 is 2^2, two to the power two
8 is 2^3, two to the power three
9 is 3^2, three to the power two
16 is 2^4 (or 4^2), two to the power four (or four to the power 2)
25 is 5^2
27 is 3^3
32 is 2^5
36 is 6^2
why we do not have 3^4 which is 81? in this series
why we do not have 5^3 which is 125? in this series
Information Technology SpecialistCommented:
>>why we do not have 3^4 which is 81? in this series<< because it's not a number to the power of 2 or 3
>>why we do not have 5^3 which is 125? in this series<< because that series only got the first 9 numbers. If you look at the series I posted 5^3 is included
Information Technology SpecialistCommented:
I said this originally >> a powerful number is one that can be expressed as an integer to the power of 2, an integer to the power of 3, or an integer to the power of 2 times an integer to the power of 3.<< but, as it slowly comes back to me, all powerful numbers can be expressed as an integer to the power of 2 times an integer to the power of 3 and are divisible by a prime number and that number times itself, so
1 = 1^2*1^3 and its prime number relationship is that it's divisible by 1 (a prime number) and divisible by 1*1.
4 = 2^2*1^3 (divisible by the prime number 2 and by 2*2)
8 = 1^2*2^3 (divisible by the prime number 2 and by 2*2)
9 = 1^2*3*3 (divisible by the prime number 3 and by 3*3)
...
36 = 6^2*1^3 (divisible by the prime number 3 and by 3*3)
...
72 = 3^2*2^3 (divisible by the prime number 3 and by 3*3)
....
100 - 10^2*1^3 (divisible by the prime number 5 and by 5*5)
etc.
Author Commented:
or an integer to the power of 2 times an integer to the power of 3
this one is not clear. Can you advise wih example

a powerful number is one that can be expressed as an integer to the power of 2, an integer to the power of 3

i think according to above explanation i think below are clear (integer to the power of 2, integer to the power of 3)

if integer is 1 then
1(1^2)
1(1^3)

similarly if integer is 2

4 (2^2)
8 (2^3)

similarly if integer is 3
9(3^2)
27(3^3)

similarly if integer is 4
16(4^2)
64(4^3)
Information Technology SpecialistCommented:
If you look at the link rrz provided you will see the statement (paraphrased) "All powerful numbers can be expressed as a-squared b_cubed."
Commented:
As awking has pointed out, you don't have to worry about primes to compute the powerful numbers. Here is code to demonstrate that fact. It prints the powerful numbers up to 1000
``````import java.util.*;
public class Powerful{
public static void main(String args[]){
TreeSet<Integer> set = new TreeSet<Integer>();
for(int a = 1; a <= 31; a++){
for(int b = 1; b <= 10; b++){
set.add(a * a * b * b * b);
}
}
Iterator<Integer> iter = pSet.iterator();
while(iter.hasNext())System.out.print(iter.next() + " ");
}
}
``````
Author Commented:
powerful numbers are exactly those that can be written a2b3, where a and b are positive integers. Here are the powerful numbers up to 1000:

a2b3?
Author Commented:
``````       for(int a = 1; a <= 31; a++){
for(int b = 1; b <= 10; b++){
``````

why we choose 31 for a and 10 for b?
Author Commented:
``````	set.add(a * a * b * b * b);
``````

what is meaning of above line?
what is headSet and why it is set to 1000?

i got output as below
1 4 8 9 16 25 27 32 36 49 64 72 81 100 108 121 125 128 144 169 196 200 216 225 243 256 288 289 324 343 361 392 400 432 441 484 500 512 529 576 625 648 675 676 729 784 800 841 864 900 961 968 972 1000
Information Technology SpecialistCommented:
>>why we choose 31 for a and 10 for b? <<
Because the powerful number must take the for of a^2*b^3 and since we were only trying to find powerful numbers from 1 to 1000, square of a can not be greater than 1000, meaning the largest square we could have would be 31^2 (961 since 32^2 = 1024) and the largest cube we could have would be 10^3 (1000).
Information Technology SpecialistCommented:
>>what is headSet and why it is set to 1000?<<
the headset method, with the Boolean parameter true, returns a view of the portion of the sorted set whose elements are less than or equal to 1000, since that is all we were trying to find. Note without the Boolean parameter set to true, it would return a set that was strictly less than 1000 so you could have just used set.headSet(1001).
Author Commented:
36      6^2
49      7^2
64      8^2

how these fit in our logic of a2b3?

should i think like below to see it as a2b3?
36       6^2* 1^3
49      7^2*1^3
64      8^2*1^3
Author Commented:
do the integer neds to be less that some number and we go in incremetal order for a and b?
Information Technology SpecialistCommented:
I'm not sure of the meaning of your question. There are an infinite number of powerful numbers, which is why the examples restricted the upper limit to 1000.
Commented:
I used TreeSet in my code to automatically sort and throw out duplicates.
The headSet  method grabs only the values up to 1000.  That is necessary because the sequence is missing values above that value. The nested for loops find 31*10 values, but  only calculate the square numbers to 31*31  and the cubic numbers to 10*10*10.
The output matches the value given at
http://primes.utm.edu/glossary/xpage/PowerfulNumber.html
Author Commented:
p=a2b3 ie
p=a*a*b*b*b
(p is powerful number. a and b are integers)

what is relation between p,a,b. p should be greater than a, b or can be equal or less)

Information Technology SpecialistCommented:
Except for 1 (as a powerful number expressed as 1^2*1^3), the powerful number will always be greater than a and b. Think about it, since the smallest expression in the form of a^2*b^3 is 2^2*1^3 which equals 4 and 4 is greater than both 1 and 2.
Commented:
I  must admit that the definition of a powerful number confuses me too.  I don't know if the following  link helps either.
http://math.stackexchange.com/questions/240692/square-full-powerful-numbers
But, aren't we focused on code here?

By the way, you should learn to use the question mark. It would make your questions easier to understand.
Consider the following line that you posted above here.
what is relation between p,a,b. p should be greater than a, b or can be equal or less)
Proper punctuation would make it easier to read.
What is relation between p,a,b?  p should be greater than a, b or can be equal or less?
At the top, you posted
What is the logic to get them. I was not clear. Please advise.
What is the logic to get them?  It was not clear. Please advise.
Look at
http://grammar.ccc.commnet.edu/grammar/marks/question.htm
http://ell.stackexchange.com/
English is my only language, but I don't get it right all the time either.
Author Commented:
Except for 1 (as a powerful number expressed as 1^2*1^3), the powerful number will always be greater than a and b. Think about it, since the smallest expression in the form of a^2*b^3 is 2^2*1^3 which equals 4 and 4 is greater than both 1 and 2.

is there is any relation between a, b?
or  a, b can be any random numbers to derive p using formulae a2b3?
Commented:
a and b can be arbitrary positive integers, and the resulting p=a^2*b^3 will be powerful, but for a given powerful p, there would be a limited number of choices for a and b
Author Commented:
but for a given powerful p, there would be a limited number of choices for a and b

what are choices of a, b with reference to p?

why we do not have a2b3 for all below p.

1      1^2 (or 1^3)
4      2^2
8      2^3
9      9^2
16      4^2
25      5^2
27      3^3
32      2^2*2^3
36      6^2
49      7^2
64      8^2
72      2^3*3^2
81      9^2
100      10^2
108      2^2*3^3
121      11^2
125      5^3
128      4^2*2^3
144      12^2
169      13^2
196      14^2
200      5^2*2^3

how they choose a,b for given p?

say for p(200) how they choose 5 as a and 2 as b?

also for p(196) what is 14 is it is a or b? if it is a then why b is not there? does it mean a2b3 is not valid formulale all the time ? ( p can be a2 also?)
Commented:
for 200 = 2*2*2*5*5, there is only one way to express it as a^2*b^3
for 64 = 2*2*2*2*2*2,  it can be expressed as 1^2*4^3 or as 8^2*1^3
for 14^2 = 14^2*1^3,  a is the number under the 2, b is the number under the 3
Information Technology SpecialistCommented:
>>how they choose a,b for given p?<<
For any given p, it MUST be able to be expressed as a^2*b^3, so a is always squared and b is always cubed.

>> say for p(200) how they choose 5 as a and 2 as b? <<
Here are all of the factors of 200 (i.e. evenly divided into 200)
1,2,4,5,8,10,20,25,40,50,100,200
How many are squares? Answer: 4 ==> 1 (1^2), 4 (2^2), 25 (5^2), 100 (10^2)
How many are cubes? Answer: 2 ==> 1 (1^3), 8 (2^3)
Multiplying every square times every cube
1*1 != 200
4*1 != 200
25*1 != 200
100*1 != 200
1*8 != 200
4*8 != 200
25*8 = 200
100*8 != 200
The only values that produce 200 are 5^2*2^3 (5 squared X 2 cubed)
so 5 is and 2 is b

>> also for p(196) what is 14 is it is a or b? if it is a then why b is not there? does it mean a2b3 is not valid formulale all the time ? ( p can be a2 also?) <<
For a powerful number of 196, since it MUST be expressed a a^2*b^3, becomes 14^2*1^3, so 14 is the a and 1 is the b. Since 1 to any power is always 1, a powerful number that can be totally derived from a square (e.g.196)will always be expressed as the square root of the powerful number squared times 1 cubed. Conversely, a powerful number that can be totally derived from a cube (e.g.8) will always be expressed as 1 squared times the cube root of the powerful number cubed.
Information Technology SpecialistCommented:
Also, don't get hung up on whether it's a or b, it's simply that every powerful number is the product of an integer squared times and integer cubed, which is also equivalent to an integer cubed times and integer squared. You could express the powerful number as x^3*y^2 as well. It's just that a has been used in these examples as the integer that gets squared and b as the integer that gets cubed.
Author Commented:

Here are all of the factors of 200 (i.e. evenly divided into 200)
1,2,4,5,8,10,20,25,40,50,100,200
How many are squares? Answer: 4 ==> 1 (1^2), 4 (2^2), 25 (5^2), 100 (10^2)
How many are cubes? Answer: 2 ==> 1 (1^3), 8 (2^3)
Multiplying every square times every cube
1*1 != 200
4*1 != 200
25*1 != 200
100*1 != 200
1*8 != 200
4*8 != 200
25*8 = 200
100*8 != 200
The only values that produce 200 are 5^2*2^3 (5 squared X 2 cubed)
so 5 is and 2 is b

i see a  and b are factors of p which can be expressed as a2b3
Author Commented:
i see all a2 and b3 also holds good since 1^3 and 1^2 fills rest to make a2b3
Author Commented:
Because the powerful number must take the for of a^2*b^3 and since we were only trying to find powerful numbers from 1 to 1000, square of a can not be greater than 1000, meaning the largest square we could have would be 31^2 (961 since 32^2 = 1024) and the largest cube we could have would be 10^3 (1000).
now i understand above statement.

i also removed boolean and it worked same as before.

import java.util.*;
public class Powerful{
public static void main(String args[]){
TreeSet<Integer> set = new TreeSet<Integer>();
for(int a = 1; a <= 31; a++){
for(int b = 1; b <= 10; b++){
set.add(a * a * b * b * b);
}
}
Iterator<Integer> iter = pSet.iterator();
while(iter.hasNext())System.out.print(iter.next() + " ");
}
}
Author Commented:
when we use with boolean? when we use without boolean? please advise
Commented:
if you take the prime factorization of a number prime0^power0 * .... * primen ^ powern,
any integer power >=2 can be expressed as power = 2*i+3*j for integer i,j >= 0
so when power >=2,  prime^power = (prime^i)^2 * (prime^j)^3
so when all the powers are >=2, the entire number can be expressed as
(prime0^i0 * ... * primen^in)^2 * (prime0^j0 * ... * primen^jn)^3
so you can use (prime0^i0 * ... * primen^in) for a and (prime0^j0 * ... * primen^jn) for b
Commented:
the boolean tells whether to include the end point