как генерировать числа с учетом их простейших коэффициентов, но с неизвестными экспонентами? [дублировать]

На этот вопрос уже есть ответы:

Закрыто 8 лет назад.

Возможные дубликаты:
n-е некрасивое число
Найти K-е наименьшее число для выражения (2^x)*(3^y)*(5^z)

Интересно, как быстро и элегантно решить эту проблему:

Мы определяем "некрасивое" каждое число n, которое может быть записано в форме: 2^x * 3^y * 5^z; где x,y и z - натуральные числа. Найдите 1500-е некрасивое число.

Например, первые "уродливые" числа:

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, похоже, не следуют никакому правилу.

Может ли кто-нибудь из вас найти какое-нибудь решение этой проблемы?

Я подумываю о том, чтобы попытаться разделить задачу на разные части. Так как задача определяется случайностью экспонентов, то я мог бы попробовать самостоятельно сгенерировать силы 2s,3s,5s, а затем числа вида 2^x*3^y,2^x*5^z и т.д. И, наконец, сложить их вместе, но я не знаю, решит ли это мою проблему.

задан Cœur 29 July 2017 в 15:49

0 ответов

Другие вопросы по тегам:

python math primes factorization hamming-numbers

как генерировать числа с учетом их простейших коэффициентов, но с неизвестными экспонентами? [дублировать]

0 ответов

Похожие вопросы: