algorithm to find nth ugly number

[svlsr2000]

Can any one give me best algorithm to find nth ugly number.

[svlsr2000]

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

the 4th ugliest number is 4, 7th is 8 and so on.

[AdrianH]

[font=Times New Roman]Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence [/font]

[font=Times New Roman]1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... [/font]

[font=Times New Roman]shows the first 11 ugly numbers. By convention, 1 is included. [/font]

the 4th ugliest number is 4, 7th is 8 and so on.

First, the tags used here are not a full set of the HTML tags, so font will not work.

Second, we are not here to do your homework for you. If you want help, suggest your algorithm or if you have code you are having problems with, post the relevant code along with the problem you are having. For more information see Posting Guidelines for more information.


Adrian

[svlsr2000]

Second, we are not here to do your homework for you. If you want help, suggest your algorithm or if you have code you are having problems with, post the relevant code along with the problem you are having. For more information see Posting Guidelines for more information.


Adrian

Its not a home work question, i am too old to do homework. :)

I am just reading about some problems and trying to come out with the best solution.

The algorithm i found for this iteratively finds all the n ugly numbers from 1 to n. Hence have higher complexity.
Is there any algorithm which could find nth ugly number without finding the nth ugly number without finding (n-1)th ugly number.

[Ganon11]

Well, you could have a program that would generate X number of ugly numbers into an array. Then, when the user asks for the nth ugly number, you just retrieve array[n-1] and spit that value out.

Ahh, but this still requires you to find the n-1th ugly number...hmmm...

[AdrianH]

Its not a home work question, i am too old to do homework.

You are never too old to do homework. I've seen 80 year olds in university classes. :) Who knows, maybe one of them was you. :p ;) :D


Adrian

[AdrianH]

Well, you could have a program that would generate X number of ugly numbers into an array. Then, when the user asks for the nth ugly number, you just retrieve array[n-1] and spit that value out.

Ahh, but this still requires you to find the n-1th ugly number...hmmm...

Looks like you are on the right track. Unfortunately, I don't think that there is any O(1) algorithm to calculate it. It would have to be iterative, based on the previous values.

Staring numbers:
2, 3, 5

Next number set:
2 * {2, 3, 5}
+ 3 * {3, 5}
+ 5 * {5}
= { 2*2, 2*3, 2*5, 3*3, 3*5, 5*5 }

...and so on (use combinatorics to get the correct values to multiply).

As you get new numbers, use an appropriate sort algorithm (merge sort is a possibility) to insert them in to the list.

It’s not pretty, but it should work fairly efficiently.


Adrian

[desouky82]

could you send me the script if you have it in c

[DeMan]

By the replies above, it sounds as though the method you are using (which requires you to find all the ugly numbers up to n) is probably about as good as it gets .

The problem with working out the nth without working out the (n-1)th is that at every iteration of the method suggested above, you can introduce new numbers (almost) anywhere, consider:

we know that there are 3 ugly "base" numbers - 2, 3, 5
taking a combination of any 2 of these we know we have a further 6 options (4, 6, 10, 9, 15, 25) (of which 4 is added to the middle of the list - and one is out of order even using this simple algorithm) giving 2,3,4,5,6,9,10,15,25). The next iteration, gives 8, 12, 20, 18, 30, 50, 30, 27, 45, 75, 50, 125 {i think} and it starts to become clear that we can be inserting elements almost anywhere. There is a lower limit but you can only know this lower limit by showing that each number before either is definitely or couldn't possibly be an ugly number.

Thus you cannot say that x is the nth ugly number without knowing what the (n-1)th is

[lalsheyal]

Declare an array for ugly numbers.
Initialize the first ugly number to be 1 and 3 array index variables to point to the first element of the ugly number array.
Fill up the ugly number array : The next ugly number will be the multiplication of the existing ugly numbers with 2, 3 or 5. The existing ugly numbers are multiplied by 2, 3 and 5. In each cases choose the product of the multiplication that is the next greater integer number of the
already found biggest ugly number. The next ugly number will be the minimum of these three numbers.
Repeat the above until the desired indexed ugly number is found.

For code http://www.algoqueue.com/algoqueue/d...th-ugly-number

[manageknowledge]

Use recursion,
if you know n-1th ugly number, find out the composition
and then increase one composition at a time and whichever is nearest would be nth ugly number.