Possible Duplicates:
nth ugly number
Find the Kth least number for expression (2^x)*(3^y)*(5^z)
I'm wondering how to solve this problem in a fast and elegant way:
We define "ugly" every number n which can be written in the form: 2^x * 3^y * 5^z;, where x,y and z are natural numbers. Find the 1500th ugly number.
E.g. the first "ugly" numbers are:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
I've tried to solve this problem using brute-force, in this way:
import itertools as it
def is_ugly(n):
'''Return `True` if *n* is an ugly number.'''
if n == 1:
return True
while not n % 2:
n //= 2
while not n % 3:
n //= 3
while not n % 5:
n //= 5
return n == 1
def nth_ugly(n):
'''Return the nth ugly number.'''
num = 0
for i in it.count(1):
if is_ugly(i):
num += 1
if num == n:
return i
But it takes quite a lot of time, and I'd like to find a faster and better solution.
I know the prime factors of ugly numbers, but I can't think of a way to generate these numbers following the correct order.
I think there must be a way to generate these numbers without having to check all the numbers. The problem is that it seems like exponents of the prime factors are distributed quite randomly.
Look at this table:
n |number| x | y | z |
------------------------
1 | 1 | 0 | 0 | 0 |
------------------------
2 | 2 | 1 | 0 | 0 |
------------------------
3 | 3 | 0 | 1 | 0 |
------------------------
4 | 4 | 2 | 0 | 0 |
------------------------
5 | 5 | 0 | 0 | 1 |
------------------------
6 | 6 | 1 | 1 | 0 |
------------------------
7 | 8 | 3 | 0 | 0 |
------------------------
8 | 9 | 0 | 2 | 0 |
------------------------
9 | 10 | 1 | 0 | 1 |
------------------------
10 | 12 | 2 | 1 | 0 |
------------------------
11 | 15 | 0 | 1 | 1 |
------------------------
12 | 16 | 4 | 0 | 0 |
------------------------
13 | 18 | 1 | 2 | 0 |
------------------------
14 | 20 | 2 | 0 | 1 |
------------------------
15 | 24 | 3 | 1 | 0 |
------------------------
As you can see x,y and z values don't seem to follow any rule.
Can someone of you find any solution to this problem?
I'm thinking of trying to divide the problem in different parts. Since the problem is determined by the randomness of exponents, I could try to generate independently the powers of 2s,3s,5s and then the numbers of the form 2^x*3^y,2^x*5^z etc. And finally put them together, but I don't know if this will solve my issue.
Here is a complete solution. O(n) complexity, it generates every number once and in order.
# http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
n = 15
bases = [2, 3, 5]
nums = [1] * n
candidates_indexes = [0 for _ in bases]
candidates = [base for base in bases]
for i in range(1, n):
nextn = min(candidates)
nums[i] = nextn
for index, val in enumerate(candidates):
if val == nextn:
candidates_indexes[index] += 1
candidates[index] = bases[index] * nums[candidates_indexes[index]]
print(nums)