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.
So, practice mindfully. Practice doing the right things and doing things right. *— Junilu

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

- 1

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

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.

*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

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

- 1

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

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

- 1

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

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

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

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.

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

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

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

>

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

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.

- 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

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.

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.

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?

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

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.

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.

- 1

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