powerful numbers program in java

Hi,

I am following below link

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
gudii9Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

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.

ozoCommented:
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
...
krakatoaCommented:
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?
ozoCommented:
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
Determine the Perfect Price for Your IT Services

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden with our free interactive tool and use it to determine the right price for your IT services. Download your free eBook now!

awking00Information 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

Your issues matter to us.

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

Start your 7-day free trial
krakatoaCommented:
>>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?
gudii9Author 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
awking00Information 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
awking00Information 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.
gudii9Author 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)
awking00Information 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."
rrzCommented:
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);				
		    }
	    }
		SortedSet<Integer> pSet = set.headSet(1000, true);
		Iterator<Integer> iter = pSet.iterator();
        while(iter.hasNext())System.out.print(iter.next() + " ");	
	}
}

Open in new window

gudii9Author 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?
gudii9Author Commented:
       for(int a = 1; a <= 31; a++){
	        for(int b = 1; b <= 10; b++){

Open in new window


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

Open in new window


what is meaning of above line?
SortedSet<Integer> pSet = set.headSet(1000, true);
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
awking00Information 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).
awking00Information 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).
gudii9Author 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
gudii9Author Commented:
do the integer neds to be less that some number and we go in incremetal order for a and b?
awking00Information 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.
rrzCommented:
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
gudii9Author 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)

please advise
awking00Information 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.
rrzCommented:
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.
gudii9Author 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?
please advise?
ozoCommented:
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
gudii9Author 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?)
ozoCommented:
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
awking00Information 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.
awking00Information 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.
gudii9Author 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
gudii9Author Commented:
i see all a2 and b3 also holds good since 1^3 and 1^2 fills rest to make a2b3
gudii9Author 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);                        
                }
          }
            //SortedSet<Integer> pSet = set.headSet(1000, true);
        SortedSet<Integer> pSet = set.headSet(1000);
            Iterator<Integer> iter = pSet.iterator();
        while(iter.hasNext())System.out.print(iter.next() + " ");      
      }
}
gudii9Author Commented:
when we use with boolean? when we use without boolean? please advise
ozoCommented:
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
ozoCommented:
the boolean tells whether to include the end point
https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#headSet%28E,%20boolean%29
so without it 1000 was omitted
gudii9Author Commented:
i see my putput now wherer 1000 omitted

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
awking00Information Technology SpecialistCommented:
If you look at the java documentation for a TreeSet object, you will see, as I previously stated, that the headSet method takes two forms. The first one has only an element parameter and the second has an element parameter and a Boolean parameter. The first one will include a view of the portion of the set that is strictly less than the element (which is why set.headSet(1001) could have been used) and the second one will include a view of the portion of the set that is less than or equal to the element if the Boolean parameter is set to true.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.