math - python 如何生成给定因子的数字,但指数未知?

  显示原文与译文双语对照的内容
57 4

可能重复的重复项:
第n 个丑陋的数字。
查找表达式( 2 ^x ) * ( 3 ^y ) * ( 5 ^z ) 1的最小数。

我想知道如何以一种快速而优雅的方式解决这个问题:

我们定义"ugly"每个数字 n,可以用以下形式编写:2 ^x * 3 ^y * 5 ^z,它的中x,y 和z 是自然数。查找 1500th 个难看的数字。

E.g 第一个"ugly"编号是:

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

我试图用蛮力来解决这个问题,以这种方式:

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

但这需要很多时间,我想找一个更快更好的解决方案。

我知道最好的数字因素,但我不能想出一种方法来按照正确的顺序生成这些数字。

我认为必须有一种方法来生成这些数字,而不必检查所有数字。问题是,它的指数指数似乎分布得相当随机。

请看这张表格:

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

你可以看到,x,y 和z 值似乎没有遵循任何规则。

你们谁能找到解决这个问题的方法?

我想把问题分成不同的部分。problem的随机性,i,5s,5s,5s,5s,finally,finally,finally,finally,finally,finally,generate,generate,generate,generate,generate,generate,generate,generate,generate等。

时间:原作者:0个回答

142 3

这是一个完整的解决方案。O(n) 复杂性,它按顺序生成每一个数字。

# 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)
原作者:
...