- Post Reply Bookmark Topic Watch Topic
- New Topic

programming forums
Java
Mobile
Certification
Databases
Caching
Books
Engineering
Micro Controllers
OS
Languages
Paradigms
IDEs
Build Tools
Frameworks
Application Servers
Open Source
This Site
Careers
Other
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Liutauras Vilda
- Campbell Ritchie
- Tim Cooke
- Bear Bibeault
- Devaka Cooray

Sheriffs:

- Jeanne Boyarsky
- Knute Snortum
- Junilu Lacar

Saloon Keepers:

- Tim Moores
- Ganesh Patekar
- Stephan van Hulst
- Pete Letkeman
- Carey Brown

Bartenders:

- Tim Holloway
- Ron McLeod
- Vijitha Kumara

posted 1 year ago

i am having a problem writing a program that will return the number with most divisors in 10000. that is; a number between 0 and 10000 that has the most numbers of divisors.

anyone to help, please.

anyone to help, please.

posted 1 year ago

What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

posted 1 year ago

- 1

The first step is to figure out how to do this by hand. Writing the actual java code is the easy part. The hard part is writing out the steps you would take if you had to do this using pencil and paper. And then re-writing those steps such that a 10yr old child could follow them

You want to break this down into methods that each do one simple thing, and do it well. If you can't give a method a simple name that clearly explains exactly what it does, it's probably doing too much. For example, I'd consider writing a method named:

public int divisorCount(int number)

So this method would take an int, and would return an int that is tee number of divisors the input number has.

Now, this method may need to call several other methods...i've not though through that part yet. But once I wrote this method, and tested it on a bunch of inputs, I could easily call it on the numbers 1-10000 (or really, anything). Then it's not to hard to keep track of which number returns the most divisors.

You want to break this down into methods that each do one simple thing, and do it well. If you can't give a method a simple name that clearly explains exactly what it does, it's probably doing too much. For example, I'd consider writing a method named:

public int divisorCount(int number)

So this method would take an int, and would return an int that is tee number of divisors the input number has.

Now, this method may need to call several other methods...i've not though through that part yet. But once I wrote this method, and tested it on a bunch of inputs, I could easily call it on the numbers 1-10000 (or really, anything). Then it's not to hard to keep track of which number returns the most divisors.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

posted 1 year ago

sure i understand the concepts , i have tried many things but nothing seems to work, and as am still a beginner , all i need was just an idea, not the answer.

Junilu Lacar wrote:What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

sure i understand the concepts , i have tried many things but nothing seems to work, and as am still a beginner , all i need was just an idea, not the answer.

posted 1 year ago

When I read the title, the first idea that popped into my head was to perform prime factorization on the integer under test. The number of divisors is then the number of combinations of prime factors with repetition, *I think*. I don't know if that's mathematically correct, but it's an avenue you can explore.

https://en.wikipedia.org/wiki/Prime_factor

https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition

https://en.wikipedia.org/wiki/Prime_factor

https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Stephan van Hulst

Saloon Keeper

Posts: 9254

177

posted 1 year ago

- 1

Let's see... The prime factorization of `90` is `[2,3,3,5]`. This means that the divisors of `90` are:

I was mistaken. It's not the number of combinations with repetition, but it might still give you some insight in how to approach this problem.

I was mistaken. It's not the number of combinations with repetition, but it might still give you some insight in how to approach this problem.

Stephan van Hulst

Saloon Keeper

Posts: 9254

177

posted 1 year ago

- 1

A simple heuristic for determining the integer with the most divisors would be to simply count the number of factors in the prime factorization, but it's not completely accurate if the factorization contains many duplicates:

This implies that the best heuristic is`h(x,y) = f(x) - g(y)`, where `x` is the number of prime factors, and `y` is the number of duplicate prime factors. `f(x)` and `g(y)` are for you to determine.

Value | Prime factorization | Divisors |
---|---|---|

30 | [2,3,5] | 1, 2, 3, 5, 6, 10, 15, 30 |

81 | [3,3,3,3] | 1, 3, 9, 27, 81 |

This implies that the best heuristic is

posted 1 year ago

Pretty interesting study. IMHO, mathematically, I think you did *all* the heavy lifting for the OP. Have some cows.

Henry

Stephan van Hulst wrote:

This implies that the best heuristic ish(x,y) = f(x) - g(y), wherexis the number of prime factors, andyis the number of duplicate prime factors.f(x)andg(y)are for you to determine.

Pretty interesting study. IMHO, mathematically, I think you did *all* the heavy lifting for the OP. Have some cows.

Henry

posted 1 year ago

Can you post your latest attempt? And UseCodeTags (that's a link).

adebari olalekan wrote:

Junilu Lacar wrote:What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

sure i understand the concepts , i have tried many things but nothing seems to work, and as am still a beginner , all i need was just an idea, not the answer.

Can you post your latest attempt? And UseCodeTags (that's a link).

All things are lawful, but not all things are profitable.

posted 1 year ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

of course, brute force also works. for a given number, try dividing it by every number up to it's sqaure root and see if it goes evenly. For every number OTHER than the square root, you get two divisors.

posted 1 year ago

If I understand the condition right, this task is similar to the one when you find the minimum or maximum number in the array. First, you set as a targetNumber first number from the array. Then goes the loop. Inside the loop, you take each number and calculate its divisors. Compare the number of divisors of the current number with the number of divisors of the previous number. And so on.

Are you asking more for a design of this class, or rather for an algorithm itself?

Are you asking more for a design of this class, or rather for an algorithm itself?

posted 1 year ago

this is what i have tried , i try to create a method that will recieve a parametre and evaluate on the parametre and then store it in an array; then am planning on just looking for the greatest numbers in the array

but i stopped halfway because i realized it wont work.

i know it doesnt work, and it does not even compile, it returns::

>

Knute Snortum wrote:

adebari olalekan wrote:

Junilu Lacar wrote:What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

sure i understand the concepts , i have tried many things but nothing seems to work, and as am still a beginner , all i need was just an idea, not the answer.

Can you post your latest attempt? And UseCodeTags (that's a link).

this is what i have tried , i try to create a method that will recieve a parametre and evaluate on the parametre and then store it in an array; then am planning on just looking for the greatest numbers in the array

but i stopped halfway because i realized it wont work.

i know it doesnt work, and it does not even compile, it returns::

>

posted 1 year ago

Your code, declares a store array size, of zero elements. So, later, when you try to get the second element, as index one, you get an array out of bounds condition.... since, obviously, an array for zero elements, doesn't have a second element.

Anyway, as already mentioned, the solution is more about math, than about Java code. Do you understand the math? Or are you attempting to just brute force through the problem? For the latter, it can take a lot of time...

I highly recommend that you take a step back, and take a look at the mathematical discussion, that has already taken place in this topic.

Henry

adebari olalekan wrote:

i know it doesnt work, and it does not even compile, it returns::

Your code, declares a store array size, of zero elements. So, later, when you try to get the second element, as index one, you get an array out of bounds condition.... since, obviously, an array for zero elements, doesn't have a second element.

Anyway, as already mentioned, the solution is more about math, than about Java code. Do you understand the math? Or are you attempting to just brute force through the problem? For the latter, it can take a lot of time...

I highly recommend that you take a step back, and take a look at the mathematical discussion, that has already taken place in this topic.

Henry

posted 1 year ago

yea, the math has been the problem; and that is why i didnt post my trials earlier. i discovered it is about maths , but i cant seem to wrap around the mathematical concept that could solve the problem. i know if i can get it mathematically , then it will be easy to implement into java code.

Henry Wong wrote:

adebari olalekan wrote:

i know it doesnt work, and it does not even compile, it returns::

Your code, declares a store array size, of zero elements. So, later, when you try to get the second element, as index one, you get an array out of bounds condition.

Anyway, as already mentioned, the solution is more about math, than about Java code. Do you understand the math? Or are you attempting to just brute force through the problem? For the latter, it can take a lot of time...

Henry

yea, the math has been the problem; and that is why i didnt post my trials earlier. i discovered it is about maths , but i cant seem to wrap around the mathematical concept that could solve the problem. i know if i can get it mathematically , then it will be easy to implement into java code.

posted 1 year ago

Take a look at Stephan's posts. His analysis pretty much explains, in my opinion, the majority of the math. If you have any questions regarding it, then feel free to follow up the discussion in this topic.

Henry

- 1

adebari olalekan wrote:

yea, the math has been the problem; and that is why i didnt post my trials earlier. i discovered it is about maths , but i cant seem to wrap around the mathematical concept that could solve the problem. i know if i can get it mathematically , then it will be easy to implement into java code.

Take a look at Stephan's posts. His analysis pretty much explains, in my opinion, the majority of the math. If you have any questions regarding it, then feel free to follow up the discussion in this topic.

Henry

posted 1 year ago

However, if you have the prime factorization of a number there is a very simple rule which yields the number of divisors of that number. As you already saw, the power of each prime in the factorization plays a key role.

Stephan van Hulst wrote:I was mistaken. It's not the number of combinations with repetition, but it might still give you some insight in how to approach this problem.

However, if you have the prime factorization of a number there is a very simple rule which yields the number of divisors of that number. As you already saw, the power of each prime in the factorization plays a key role.

posted 1 year ago

I must say that the formula for the number of divisors, given the prime factorization, is not simple at all (well, it is not rocket science too).

For instance, say we have a factorization with two primes, each of multiplicity 2. We have then 9 divisors. If we have a factorization, again of two primes, with multiplicity 3 and 1 respectively, then we have 8 divisors.

In both cases we have 4 primes, giving us 2^4 subsets, in principle giving us 16 divisors.

In the (2, 2) case, we seem to subtract 8 divisors to get the actual number of divisors, in the (3, 1) case we seem to subtract 7 divisors to get the number of divisors.

What very simple formula are we then talking about?

I could not remember a formula that gave me the unique number of subsets of a set, given that duplicate elements might be present. So I derived this simple scheme:

Suppose we have a set with N equal elements a. Then we can form N unique subsets. For instance, say we have this set: [2, 2, 2], then the unique subsets are [2], [2, 2] and [2, 2, 2]. 3 in total.

Now suppose that we add M b's to this set. How many uniques subsets do we get then? First of all, the M b's give us M new subsets ([b], [b, b], et cetera). Then, for each of the N existing subsets (with only a's), we can add M subsets with only b's (for instance: [a, a] and [b] give me a new subset [a, a, b]).

The new total is therefore: N (the existing number) + M (from the added b's) + N * M (to each of the N subsets with a we add M subsetswith b's).

What has all this to do with the assignment? Well, if we have the set [a, a, b], then you may read that as the set [3, 3, 5], where the prime 3 has multiplicity 2 and 5 has multiplicity 1.

According to the above, the number 45 has two primes 3 and one prime 5. The formula gives us:

for the prime 3: 2 unique subsets.

adding 5: 1 new subset ([5]) + 2 existing subsets + 2 * 1 = 5.

So, we have 5 divisors. But hang on: 45 has 6 divisors: 1, 3, 5, 9, 15, 45! Indeed, in the derived formula we left '1' out of the picture. It is not a prime (therefore we neglected it), but it is a divisor.

To our formuls: M + N + M*N, we must add 1 to get the correct number.

If we look at Stephans examples, we have:

30 = [2, 3, 5]. The derivation gives us:

for the 2: 1 subset

including the 3: 1 + 1 + 1 * 1 = 3

including the 5: 3 + 1 + 1 * 3 = 7.

Adding 1 to the outcome, we get 8 divisors.

81 = [3, 3, 3, 3]

for the 3 we get: 4 subsets.

adding 1 we get 5 divisors.

Now, this is the simplest I could come up with. I will think about the 'very simple rule' for deriving the number of divisors. Maybe I have forgotten, or have been overlooking, something quite simple.

Edit: wasn't this a Project Euler assignment? If so, I must have solved it, but how? I'll have a look and if I find something really clever, I will report.

For instance, say we have a factorization with two primes, each of multiplicity 2. We have then 9 divisors. If we have a factorization, again of two primes, with multiplicity 3 and 1 respectively, then we have 8 divisors.

In both cases we have 4 primes, giving us 2^4 subsets, in principle giving us 16 divisors.

In the (2, 2) case, we seem to subtract 8 divisors to get the actual number of divisors, in the (3, 1) case we seem to subtract 7 divisors to get the number of divisors.

What very simple formula are we then talking about?

I could not remember a formula that gave me the unique number of subsets of a set, given that duplicate elements might be present. So I derived this simple scheme:

Suppose we have a set with N equal elements a. Then we can form N unique subsets. For instance, say we have this set: [2, 2, 2], then the unique subsets are [2], [2, 2] and [2, 2, 2]. 3 in total.

Now suppose that we add M b's to this set. How many uniques subsets do we get then? First of all, the M b's give us M new subsets ([b], [b, b], et cetera). Then, for each of the N existing subsets (with only a's), we can add M subsets with only b's (for instance: [a, a] and [b] give me a new subset [a, a, b]).

The new total is therefore: N (the existing number) + M (from the added b's) + N * M (to each of the N subsets with a we add M subsetswith b's).

What has all this to do with the assignment? Well, if we have the set [a, a, b], then you may read that as the set [3, 3, 5], where the prime 3 has multiplicity 2 and 5 has multiplicity 1.

According to the above, the number 45 has two primes 3 and one prime 5. The formula gives us:

for the prime 3: 2 unique subsets.

adding 5: 1 new subset ([5]) + 2 existing subsets + 2 * 1 = 5.

So, we have 5 divisors. But hang on: 45 has 6 divisors: 1, 3, 5, 9, 15, 45! Indeed, in the derived formula we left '1' out of the picture. It is not a prime (therefore we neglected it), but it is a divisor.

To our formuls: M + N + M*N, we must add 1 to get the correct number.

If we look at Stephans examples, we have:

30 = [2, 3, 5]. The derivation gives us:

for the 2: 1 subset

including the 3: 1 + 1 + 1 * 1 = 3

including the 5: 3 + 1 + 1 * 3 = 7.

Adding 1 to the outcome, we get 8 divisors.

81 = [3, 3, 3, 3]

for the 3 we get: 4 subsets.

adding 1 we get 5 divisors.

Now, this is the simplest I could come up with. I will think about the 'very simple rule' for deriving the number of divisors. Maybe I have forgotten, or have been overlooking, something quite simple.

Edit: wasn't this a Project Euler assignment? If so, I must have solved it, but how? I'll have a look and if I find something really clever, I will report.

Stephan van Hulst

Saloon Keeper

Posts: 9254

177

posted 1 year ago

It really is quite simple though. Look at the formula you would need if your number can be factored as a power of a single prime. Now see if you can extend that formula to cases with distinct prime factors.

posted 1 year ago

What simple formula? If the prime factorization is p1^a1 * p2^a2 * ... * pn^an then the number of divisors is (a1+1) * (a2+1) * ... * (an+1).

Stephan van Hulst

Saloon Keeper

Posts: 9254

177

posted 1 year ago

I think that's pretty simple :P

Anyway, Adebari Olalekan, if you've followed the discussion so far, you have seen that you need to perform prime factorization. Here's a quick outline on how to do that:

Create a class that represents the prime factorization. It must hold the number of factors per prime number. I suggest using a`Map<Integer, Integer>` internally.

Write an algorithm to perform the factorization. Divide the number by primes, starting with 2 and going up, until the remainder is 1. Each time you can divide the number, add the prime divisor to the factorization.

To do this, you need to be able to generate prime numbers. This is the first challenge you should start with. Do you know how the Sieve of Erastosthenes works?

Anyway, Adebari Olalekan, if you've followed the discussion so far, you have seen that you need to perform prime factorization. Here's a quick outline on how to do that:

Create a class that represents the prime factorization. It must hold the number of factors per prime number. I suggest using a

Write an algorithm to perform the factorization. Divide the number by primes, starting with 2 and going up, until the remainder is 1. Each time you can divide the number, add the prime divisor to the factorization.

To do this, you need to be able to generate prime numbers. This is the first challenge you should start with. Do you know how the Sieve of Erastosthenes works?

posted 1 year ago

Honestly ... I am actually starting to lean towards a brute force solution...

First, the mathematics route is definitely the more elegant route. Second, the mathematics route is most likely the quicker route in terms of running time. And third, in my opinion, the mathematics solution is definitely the most interesting solution. If I had to do it, I can see myself spending time to do this on paper first, working on the math.

On the other hand, for reasonable small numbers, it is debatable if brute forcing the solution is slower (in running time). Also, the code necessary to figure out the primes is very similar code to figure out the divisors. Granted, going to primes may be "quicker" as there are less of them, but then, permutations/combinations will need to be done to get to the divisors. It is debatable if figuring out the primes and then calculating the number of divisors, is quicker than figuring out the divisors.

The pragmatic side of me is thinking that brute force isn't all that bad...

Henry

Honestly ... I am actually starting to lean towards a brute force solution...

First, the mathematics route is definitely the more elegant route. Second, the mathematics route is most likely the quicker route in terms of running time. And third, in my opinion, the mathematics solution is definitely the most interesting solution. If I had to do it, I can see myself spending time to do this on paper first, working on the math.

On the other hand, for reasonable small numbers, it is debatable if brute forcing the solution is slower (in running time). Also, the code necessary to figure out the primes is very similar code to figure out the divisors. Granted, going to primes may be "quicker" as there are less of them, but then, permutations/combinations will need to be done to get to the divisors. It is debatable if figuring out the primes and then calculating the number of divisors, is quicker than figuring out the divisors.

The pragmatic side of me is thinking that brute force isn't all that bad...

Henry

posted 1 year ago

I also tend to brute force for this task as it is significantly easier to implement, but would tend to brute force the prime factors instead of the divisors.

The advantage of brute forcing prime factors is that it has significantly better performance in the best case:

When brute forcing the factors the border to iterate to is reduced with each found prime factor (-> has to iterate to max(second largest factor of x, sqrt(largest factor of x))), whereas brute forcing divisors has to always iterate to sqrt(x). (Of course brute force cannot compare with e.g. pollard-rho for products of larger prime factors such as 9223371994482243049 (on my pc ~10 seconds (skipping multiples of 2 and 3) vs <.01 seconds), but should be sufficient for the required range.)

And as Henry already stated, the code to find prime factors is quite similar to the code required to find divisors. (There is no need to sieve/generate prime numbers, trial division is sufficient to find prime factors (preferable with a small wheel to skip multiples of 2 or 2 and 3 etc., which makes brute forcing prime factors always faster than brute forcing divisors as the latter cannot skip values).)

Alternatively one could try to turn the whole process around and generate the number with the most factors by maximizing the value of (a1+1) * (a2+1) * ... * (an+1) for the specific range without actually calculating the number of divisors for each number in the range.

The advantage of brute forcing prime factors is that it has significantly better performance in the best case:

When brute forcing the factors the border to iterate to is reduced with each found prime factor (-> has to iterate to max(second largest factor of x, sqrt(largest factor of x))), whereas brute forcing divisors has to always iterate to sqrt(x). (Of course brute force cannot compare with e.g. pollard-rho for products of larger prime factors such as 9223371994482243049 (on my pc ~10 seconds (skipping multiples of 2 and 3) vs <.01 seconds), but should be sufficient for the required range.)

And as Henry already stated, the code to find prime factors is quite similar to the code required to find divisors. (There is no need to sieve/generate prime numbers, trial division is sufficient to find prime factors (preferable with a small wheel to skip multiples of 2 or 2 and 3 etc., which makes brute forcing prime factors always faster than brute forcing divisors as the latter cannot skip values).)

Alternatively one could try to turn the whole process around and generate the number with the most factors by maximizing the value of (a1+1) * (a2+1) * ... * (an+1) for the specific range without actually calculating the number of divisors for each number in the range.

posted 1 year ago

no, i dont know how the sieve works but i will check online.

Stephan van Hulst wrote:I think that's pretty simple :P

Anyway, Adebari Olalekan, if you've followed the discussion so far, you have seen that you need to perform prime factorization. Here's a quick outline on how to do that:

Create a class that represents the prime factorization. It must hold the number of factors per prime number. I suggest using aMap<Integer, Integer>internally.

Write an algorithm to perform the factorization. Divide the number by primes, starting with 2 and going up, until the remainder is 1. Each time you can divide the number, add the prime divisor to the factorization.

To do this, you need to be able to generate prime numbers. This is the first challenge you should start with. Do you know how the Sieve of Erastosthenes works?

no, i dont know how the sieve works but i will check online.

Piet Souris

Rancher

Posts: 2835

96

posted 1 year ago

- 1

It was indeed a very simple formula, one that immediately comes to mind if you cannot remember it or have never seen it before.

But here you do not need complex prime factorization. As is clear from my subsets analogy, you get the most divisors when you have as many unique primes as possible (given N elements, the maximum number of subsets is 2^N, which you get when all elements are unique). Since N <= 10_000, the maximum prime number to take into account is 13. Now, you get as many primes as possible if you keep them as small and as unique as possible. A simple spreadsheet and some tries are sufficient for this.

But here you do not need complex prime factorization. As is clear from my subsets analogy, you get the most divisors when you have as many unique primes as possible (given N elements, the maximum number of subsets is 2^N, which you get when all elements are unique). Since N <= 10_000, the maximum prime number to take into account is 13. Now, you get as many primes as possible if you keep them as small and as unique as possible. A simple spreadsheet and some tries are sufficient for this.

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!