pythonmathprimesfactorizationhamming-numbers# how to generate numbers given their prime factors, but with unknown exponents?

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

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

Solution

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

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?