ashwin vis

Greenhorn

Posts: 17

posted 7 years ago

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

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

Marshal

Posts: 55717

163

posted 7 years ago

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.

Write down very simply what you plan to do.

ashwin vis

Greenhorn

Posts: 17

posted 7 years ago

this is the logic i have been given

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

**"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???

Campbell Ritchie

Marshal

Posts: 55717

163

posted 7 years ago

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?

It isn't simple.ashwin vis wrote: . . . Please help me i am breaking my head over this simple algo . . .?

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

Posts: 8

ashwin vis

Greenhorn

Posts: 17

posted 7 years ago

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

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

Posts: 8

posted 7 years ago

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

Posts: 17

Surabhi Gupta

Greenhorn

Posts: 8

posted 7 years ago

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.

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

Marshal

Posts: 55717

163

posted 7 years ago

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.

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.

posted 7 years ago

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:

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.

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.

posted 7 years ago

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

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

SCJP 5.0 SCWCD 5.0

Surabhi Gupta

Greenhorn

Posts: 8

posted 7 years ago

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

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

Posts: 8

posted 7 years ago

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

http://kevingong.com/Math/EgyptianFractions.pdf

ashwin vis

Greenhorn

Posts: 17

posted 7 years ago

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.

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

Marshal

Posts: 55717

163

Surabhi Gupta

Greenhorn

Posts: 8

posted 7 years ago

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

Posts: 17

posted 7 years ago

I am now getting the divisors in array but how do i code

How to use the ArrayList for such an comparision?? I have been stuck with this one for 2 days now!!!

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

posted 7 years ago

i have heard about a function in matlab called

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

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

SCJP 5.0 SCWCD 5.0

Surabhi Gupta

Greenhorn

Posts: 8

posted 7 years ago

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

}

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

}

Surabhi Gupta

Greenhorn

Posts: 8

posted 7 years ago

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.

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

Posts: 17

posted 7 years ago

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

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

Marshal

Posts: 55717

163

posted 7 years ago

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.

Actually, what you have is a Set, because the divisors are all distinct.

Suggest a different approach, but one requiring lots of memory.

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

Debabrata Patnaik

Greenhorn

Posts: 5

Debabrata Patnaik

Greenhorn

Posts: 5

posted 7 years ago

[Deleted as hi-jack of original thread]

if you think you can do

then only you can do!!!

Campbell Ritchie

Marshal

Posts: 55717

163

posted 7 years ago

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.

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

Posts: 3

posted 7 years ago

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

[deleted]

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

Campbell Ritchie

Marshal

Posts: 55717

163

posted 7 years ago

Welcome to the Ranch

Please note what it says when you log on to "beginning Java".

Please note what it says when you log on to "beginning Java".

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

Campbell Ritchie

Marshal

Posts: 55717

163

posted 7 years ago

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

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

Posts: 3

posted 7 years ago

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

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

Posts: 3

Campbell Ritchie

Marshal

Posts: 55717

163

posted 7 years ago

Divisors of 4 are 1 and 2. There is no way to add 1 and 2 to make 4. It says above that

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?

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

Marshal

Posts: 55717

163

posted 7 years ago

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

Posts: 17

posted 7 years ago

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

Marshal

Posts: 55717

163

Campbell Ritchie

Marshal

Posts: 55717

163

posted 7 years ago

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

D = {

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 Σ

T = {

Now a practical number can be defined as

∀

Remember that the empty set is a member of ℙ(D), so 0 ∈ T is always

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

For any natural number available on the computer, Create a sequence (List) of integers, and 1 into it. Every number has 1 as a divisor. Iterate from 2 to If that number is an exact divisor of Test the size of the list We only count up to 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^ Inner loop from 0 to < 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 < End outer loop. Put If you have a practical number, the cardinality (number of elements) in the set will be equal to

Note you do have to check that the total isn't greater than

So who said there was anything simple about this ?

You may find other algorithms simpler.

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:

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 Σ

*i*•*i*∈ S.T = {

*j*| S ∈ ℙ(D) ∧*j*= Σ(S)}Now a practical number can be defined as

∀

*a*•*a*∈ ℕ ∧*x*≥*a*⇒*a*∈ TRemember 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:

*x*,

*x*/ 2 inclusive.

*x*, add it to the list. Position doesn't matter.

*n*such that if 2^

*n*<

*x*- 1 you don't have a practical number.

*x*- 1 because

*x*is a divisor of itself.

*n*where

*n*is the number of divisors in the list.

*n*.

*x*, put it in the set. Remember sets automatically discard duplicates.

*x*in the set.

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