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

Write down very simply what you plan to do.

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

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?

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

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

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.

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.

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

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

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

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.

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.

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

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

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

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

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.

if you think you can do

then only you can do!!!

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.

[deleted]

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

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

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

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

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

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