aspose file tools*
The moose likes Beginning Java and the fly likes Practical Number? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Practical Number?" Watch "Practical Number?" New topic
Author

Practical Number?

ashwin vis
Greenhorn

Joined: Sep 29, 2009
Posts: 17
Hello i am stuck with the problem of finding the practical numbers between to integers..
for example if the two integers are 1 and 12 then the practical numbers are 1,2,3,4,6... I am confused with the definition of a practical number anyhow this is the code i came up with but i am not getting the answer

i get 1,3,6,10,16,28... I know this is wrong but i read practical number is the sum of distinct divisors.. so any help with the algorithm would be very ver thankfull...
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39834
    
  28
I had never heard of practical numbers before. So I looked in Wikipedia. Don't know whether that helps, but you need to understand your algorithm before you try programming.

Write down very simply what you plan to do.
ashwin vis
Greenhorn

Joined: Sep 29, 2009
Posts: 17
this is the logic i have been given "A positive integer m is said to be practical if every n with 1 <= n <= m is a sum of distinct divisors of m".

I know how to find the divisors. All i have to do is return out the practical numbers in an int array.
if the range is from 1 to 20.. I have to return an int array ed:{1,2,4,5,8,12,16,18,20}

How do i code the sum of divisors??? I am jus able to get the divisors.. Please help me i am breaking my head over this simple algo!!!

How do i store the vaules in an int array???
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 453

a hint for you

no odd number is a practical number . think why

now just try to find out the algorithm for even numbers.

avi sinha


SCJP 5.0 SCWCD 5.0
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39834
    
  28
ashwin vis wrote: . . . Please help me i am breaking my head over this simple algo . . .?
It isn't simple.

It isn't easy to put the numbers into an array, because putting anything into an array implies knowing how many elements there are. Remember an array has a fixed size.
You can try adding numbers to a List<Integer>, and then changing the List to an Integer[] array (which can easily be copied to an int[] array), but you still have to work out how to tell whether a number, eg 11, is a sum of different elements of the array.

I don't think this is at all easy. I suggest you try a web search for such an algorithm. If you don't succeed before 20.00 GMT tomorrow, 26th October, inform me and I shall ask (indirectly) somebody I know who is very hot on mathematics whether he knows an algorithm.

By the way: is 1 a practical number or not?
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
Hi...
I am also searching for the algorithm the find out pratical number. If you have found it, can you help me??
ashwin vis
Greenhorn

Joined: Sep 29, 2009
Posts: 17
I have done a lot of googling for an algorithm for practical numbers and i came up with just one such suggestion

for n = 1 to 10,000
{
for k = 1 to n
{
Try adding up all of the different factors of n until you get k. If it doesn't work, then exit the loop and try the next n.
}
If you've gotten this far, then print n.
}

This is the suggestion i found.. i seem to be very confused on the concept of the sum of distinct divisors.. For eg: the practical numbers between 1 and 20 are 1,2,4,6,8,12,14,16,18,20.. I find that 10 and 5 are also divisors of 20 but are not practical numbers!!! .. In my problem i have to specify the range that is for eg: from m to n. i have to specify both these m and n values and return the practical numbers in an int[] array... The level of difficulty for this problem was specified as easy!!! Thats why i am still breaking my head...
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
ashwin vis wrote:I have done a lot of googling for an algorithm for practical numbers and i came up with just one such suggestion

for n = 1 to 10,000
{
for k = 1 to n
{
Try adding up all of the different factors of n until you get k. If it doesn't work, then exit the loop and try the next n.
}
If you've gotten this far, then print n.
}

This is the suggestion i found.. i seem to be very confused on the concept of the sum of distinct divisors.. For eg: the practical numbers between 1 and 20 are 1,2,4,6,8,12,14,16,18,20.. I find that 10 and 5 are also divisors of 20 but are not practical numbers!!! .. In my problem i have to specify the range that is for eg: from m to n. i have to specify both these m and n values and return the practical numbers in an int[] array... The level of difficulty for this problem was specified as easy!!! Thats why i am still breaking my head...


I think you are confused with the concept of Practical Numbers. A number n is called Practical, if we can get all numbers smaller than n i. e. 1 to n-1 by adding the factors of n.
For example, 10 is not a practical number because factors of 10 are 1, 2, 5. But we can not get numbers 1 to 9 by adding these factors.
ashwin vis
Greenhorn

Joined: Sep 29, 2009
Posts: 17
Thanks for the help... But then it means i have to check for every number whether its practical or not??? If thats the case how do i do.. Like find the divisors of each "n"and then see whether its sum is less than "n-1"???
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
ashwin vis wrote:Thanks for the help... But then it means i have to check for every number whether its practical or not??? If thats the case how do i do.. Like find the divisors of each "n"and then see whether its sum is less than "n-1"???


Yes.... You have to check for every number. But after finding divisors of n, you have to check whether each number smaller than n can be got by adding any of these divisors.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39834
    
  28
Does that mean not using the divisors twice?

You need to get an algorithm. I have a reputation for walking round with pencils and a large eraser. That is the hardware you need. Write down on paper exactly what you are going to do. You will need something much more detailed, and much simpler, than what you have written so far. When you get down to really short words, you have got somewhere.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18907
    
    8

Well, the algorithm is pretty simple. Assuming we're talking about the same thing Wikipedia was talking about. Here's all you have to do:

a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n


So to see if n is a practical number, all you have to do is (1) list all the divisors of n (2) for each k between 1 and n-1, find out if k is a sum of one or more different divisors from that list.
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 453

Paul Clapham wrote:Well, the algorithm is pretty simple. Assuming we're talking about the same thing Wikipedia was talking about. Here's all you have to do:

a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n


So to see if n is a practical number, all you have to do is (1) list all the divisors of n (2) for each k between 1 and n-1, find out if k is a sum of one or more different divisors from that list.


isn't it tough to find out if k is the sum of one more different divisors.
i think we will have to calculate the sum of members like creating combinations .
taken 1 at a time ------> comparing with each divisor
taken 2 at a time ------> sum of all possible combinations of two divisors
.
.
.
taken n at a time .................

i think its gonna be tough. is there any other way ??

avi sinha
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
Paul Clapham wrote:Well, the algorithm is pretty simple. Assuming we're talking about the same thing Wikipedia was talking about. Here's all you have to do:

a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n


So to see if n is a practical number, all you have to do is (1) list all the divisors of n (2) for each k between 1 and n-1, find out if k is a sum of one or more different divisors from that list.


Performing first task is very easy. But working on 2nd one is quite cumbersome. I m not getting the logic to write the code for this. Can someone help me with this??
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
I got the algorithm to find out whether a number is practical or not. It's given on the link below at page no 11:

http://kevingong.com/Math/EgyptianFractions.pdf
ashwin vis
Greenhorn

Joined: Sep 29, 2009
Posts: 17
Great find Surabhi... Looking at it .. Will see if i can make out anything from the algorithm.... I want to collect the divisors of n in an array how do i do that???
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18907
    
    8

ashwin vis wrote:Great find Surabhi... Looking at it .. Will see if i can make out anything from the algorithm.... I want to collect the divisors of n in an array how do i do that???

Come on... for i=1 to n-1, if i is a divisor of n then add it to the list. That's how.

Of course it helps to use a list rather than an array, this makes things a lot less cumbersome. Otherwise you have to guess how many divisors there could be, then deal with an array which was probably too big.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39834
    
  28
You would need a List to collect the divisors; you will only find an array useful when you can predict how many elements it will have beforehand.
You can of course turn a List into an array easily.
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
ashwin vis wrote:Great find Surabhi... Looking at it .. Will see if i can make out anything from the algorithm.... I want to collect the divisors of n in an array how do i do that???


In fact, you don't need to run the loop till n-1, just run it till n/2. Beyond n/2 you will not find any divisor.
ashwin vis
Greenhorn

Joined: Sep 29, 2009
Posts: 17


I am now getting the divisors in array but how do i code (summation of divisor[i]>=(divisor[i+1]-1))( this was condition for practical numbers as referenced from the link posted http://kevingong.com/Math/EgyptianFractions.pdf)
How to use the ArrayList for such an comparision?? I have been stuck with this one for 2 days now!!!
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 453

i have heard about a function in matlab called nchoosek which calculates the combinations taken n at a time.
if we can get the idea behind the function then we can get what we are looking for .

Matlab Link to nchoosesek

i am looking for it.
avi sinha
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
ashwin vis wrote:

I am now getting the divisors in array but how do i code (summation of divisor[i]>=(divisor[i+1]-1))( this was condition for practical numbers as referenced from the link posted http://kevingong.com/Math/EgyptianFractions.pdf)
How to use the ArrayList for such an comparision?? I have been stuck with this one for 2 days now!!!



You can write something like this...

Boolean practical = FALSE;
for(i=1; i< no_of_factors - 1; i++)
{
sum_of_factors = 0;
for(j = 0; j < i; j++)
{
sum_of_factors = sum_of_factors + factor[j];
}

if(sum_of_factors >= factor[i] - 1;
{
practical = TRUE;
}
else
{
practical = FALSE;
break;
}
}

if(practical == TRUE)
{
this number is practical
}
avi sinha
Ranch Hand

Joined: Mar 15, 2009
Posts: 453

i didn't get the logic behind it . can you please explain it.

avi sinha
Surabhi Gupta
Greenhorn

Joined: Oct 26, 2009
Posts: 8
avi sinha wrote:i didn't get the logic behind it . can you please explain it.

avi sinha


I have posted a link in a older post. There is the algo to find the practical number. If you have a look at that link, you would understand my code. It's a different method to find the practical number.
ashwin vis
Greenhorn

Joined: Sep 29, 2009
Posts: 17
I am getting your logic Surabhi but i have an array list of div and if i have to compare it then i have to convert it into an int[] array.. How do i do that??..
i tried this one


Iam getting Array out of bounds error.. Have i done it in the right way first of all???.. How do i get the array of divisors from the ArrayList as an int[] array???
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39834
    
  28
If you are using a List you ought to learn about Lists, which requires a trip to the Java™ Tutorials; look under "interfaces" and "implementations". Also look at the List API documentation, and the links to implementing classes.

Actually, what you have is a Set, because the divisors are all distinct.
Suggest a different approach, but one requiring lots of memory.
  • Make a Set<Integer> of divisors.
  • Work out how to get its powerset, which means all the different possible subsets. Beware. The powerset of a set size n contains 2^n members.
  • Create a total object, which takes a Set<Integer> as a parameter, and calculates the total of the members of the set.
  • Put the total objects into an array or list, and sort the list, from smallest total to largest total.
  • Count how many you have
  • Look for gaps in the sequence. Remember there will be duplicates (eg 1+2+3, 2+4)

  • Remember a number > 2^n where n = number of possible divisors is definitely not a practical number.
    Debabrata Patnaik
    Greenhorn

    Joined: Oct 27, 2009
    Posts: 5
    [deleted. CR]


    if you think you can do
    then only you can do!!!
    Debabrata Patnaik
    Greenhorn

    Joined: Oct 27, 2009
    Posts: 5
    [Deleted as hi-jack of original thread]
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39834
        
      28
    Welcome to JavaRanch

    That is a new question, which would divert one's attention from the original poster's question. You ought to have opened a new thread. It is very discourteous to the original poster, so I shall be obliged to pull rank and return ownership and content of this thread to the original poster.
    Mearaj Ahmad
    Greenhorn

    Joined: Oct 28, 2009
    Posts: 3
    here is the java code..

    [deleted]

    use this function to check if the numbers are practical or not in a range.. this shd help.. i guess so..
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39834
        
      28
    Welcome to the Ranch

    Please note what it says when you log on to "beginning Java".
    We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.
    I am afraid simply providing that sort of answer does not help at all. It deprives the poster of the opportunity to learn, and if he uses it for assessed work, may earn a mark of 0 for the entire assessment if the original is found here. Please don't be annoyed, but I shall have to pull rank and remove the solution.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39834
        
      28
    I have had second thoughts; I shall replace the code I deleted earlier.But that's only because I tried the code and got incorrect results with it. It confidently told me 4 is a practical number.

    I don't know why you are getting the bits about "surl". Sorry.
    Steve Luke
    Bartender

    Joined: Jan 28, 2003
    Posts: 4181
        
      21

    Campbell Ritchie wrote:I have had second thoughts; I shall replace the code I deleted earlier.
    ...
    But that's only because I tried the code and got incorrect results with it. It confidently told me 4 is a practical number.


    But 4 is a practical number, so it would be right telling you that.

    Divisors of 4 = 1,2,4
    1 = 1
    2 = 2
    3 = 1 + 2

    Steve
    Mearaj Ahmad
    Greenhorn

    Joined: Oct 28, 2009
    Posts: 3
    Campbell Ritchie wrote:I have had second thoughts; I shall replace the code I deleted earlier.But that's only because I tried the code and got incorrect results with it. It confidently told me 4 is a practical number.

    I don't know why you are getting the bits about "surl". Sorry.



    i guess 4 is practical.. (3=2+1,2,1) well i m sorry for my part.. i am a programmer.. i expect people to understand the algo by code. like i do..
    Mearaj Ahmad
    Greenhorn

    Joined: Oct 28, 2009
    Posts: 3
    In this prog i am finding the factors, then subtracting the numbers less than that with eachj factors, if the result is positive ,subtract the next factor and if its negative .. add the next factor,
    then check the end result. if its 0 then its practical.. else not..

    peace..
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39834
        
      28
    Divisors of 4 are 1 and 2. There is no way to add 1 and 2 to make 4. It says above that if all n where 1<= n and n <= m and n is the sum of distinct factors of m, then m is a practical number. So you ought to be able to add 1 and 2 to make 4. You can't. So, I am afraid, your algorithm doesn't give correct results.

    12 is described above as a practical number. Factors of 12 are 1 2 3 4 6. 1 + 2 + 3 + 6 = 12.

    Ashwin Vis, who gave you this assignment? It is by no means easy. What sort of course are you doing? And would you like me to ask my friend for help?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39834
        
      28
    We have two different definitions of practical numbers, one with ≤ in, and one with < in. But the definition Ashwin Vis was given has ≤ in. If you use < then 4 is indeed a practical number; if you use ≤ then 4 isn't. I don't know about you lot, but I am getting confused by this thread. I think I shall have to seek outside help.
    ashwin vis
    Greenhorn

    Joined: Sep 29, 2009
    Posts: 17
    Guys thanks a lot for all the code... i am still stuck.. Well this is an problem solving and alogorithm learning course which we have been offered in our college.. .. Well some of the people i have asked say this is a fairly simple problem !!! and have asked me to code by myself!!! I am still wondering about this one.....
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39834
        
      28
    Well, I have made a big mistake. What are the factors of 4? 1, 2.
    What are the factors of 12? 1, 2, 3, 4, 6.








    All wrong
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39834
        
      28
    Yes, I was mistaken. The results of my mistake were that I thought there is a difference between the definition with < in an the definition with ≤ in.


    What are the factors of 4 really?

    Answer: 1 2 4

    That makes a big difference to 4, for example: 1 = 1, 2 = 2, 1 + 2 = 3 and 4 = 4.

    I went to see James, our local mathematical whizz-kid and we concluded:
  • There is a set of possible divisors for any natural number
  • The possible sums are the sums of the members of the powerset of that set.
  • You can set up a set of all divisors of a number, or store them in a sequence.
  • The number of sets in a powerset is 2^n where n is the cardinality of the original set
  • If the number of divisors is small, the powerset will be small. For example, the set of divisors for 11 is {1, 11} so its powerset can have at most 4 members. Since 4 < 11 that can't be a practical number.

  • Let's create a set of number D (for divisors) which are divisors of a number x.

    D = {i | x ∈ ℕ ∧ i ∈ ℕ ∧ x mod i = 0}
    Let's create another set T for totals where the members are the sums of the members of the powerset of D, using the Σ(S) notation to mean "sum of all the members of the set S", or Σii ∈ S.
    T = {j | S ∈ ℙ(D) ∧ j = Σ(S)}
    Now a practical number can be defined as
    aa ∈ ℕ ∧ xaa ∈ T

    Remember that the empty set is a member of ℙ(D), so 0 ∈ T is always true, and ℕ only includes numbers ≥ 0.

    I am more used to shifts and bitwise operations than you, so I would try:

  • For any natural number available on the computer, x,
  • Create a sequence (List) of integers, and 1 into it.
  • Every number has 1 as a divisor.
  • Iterate from 2 to x / 2 inclusive.
  • If that number is an exact divisor of x, add it to the list. Position doesn't matter.
  • Test the size of the list n such that if 2^n < x - 1 you don't have a practical number.
  • We only count up to x - 1 because x is a divisor of itself.
  • If we had 5 divisors, we shall have 6 elements in the sequence at present, so its powerset (ignoring 0) will have 2^5 = 32 members.
  • The first divisor found is at position 0, the second at position 1, etc.
  • Create a set for your results
  • Two nested loops.
  • The outer loop from 1 to < 2^n where n is the number of divisors in the list.
  • Inner loop from 0 to < n.
  • Set sum = 0
  • If outer loop variable bitwise-and (1 left-shift inner loop variable) != 0, then (1 left-shift inner loop variable) gives the index in the sequence to retrieve the number from the sequence, and add it to the sum.
  • End inner loop
  • If the sum is >0 and < x, put it in the set. Remember sets automatically discard duplicates.
  • End outer loop.
  • Put x in the set.
  • If you have a practical number, the cardinality (number of elements) in the set will be equal to x.

    Note you do have to check that the total isn't greater than x: look at 12: 1 + 2 + 3 + 4 + 6 = 16.


    So who said there was anything simple about this ?

    You may find other algorithms simpler.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Practical Number?