Произведение простых множителей числа, меньшего этого числа

Прежде всего, прошу прощения за заголовок, я не знал, как выразить свою проблему словами. Ну, вот оно:

Для целого числа a больше 1 пусть F будет отсортированным списком простых множителей числа a. Мне нужно найти все кортежи c (заполненные целыми числами), такие, что длина каждого кортежа равна размеру F и (F[0] ** c[0]) * (F[1] ** c[1]) * (...) < a. Добавлю, что пишу на Python.

Пример:

a = 60
F = [2,3,5]

# expected result:

C = {(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 2, 0),
(0, 2, 1), (0, 3, 0), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1),
(1, 2, 0), (1, 3, 0), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 2, 0), (3, 0, 0),
(3, 0, 1), (3, 1, 0), (4, 0, 0), (4, 1, 0), (5, 0, 0)}

Я сгенерировал этот результат, используя itertools.product(), а именно:

m = math.floor(round(math.log(a, min(F)), 12))
for i in itertools.product(range(m + 1), repeat=len(F)):
    if math.prod([F[j] ** i[j] for j in range(len(F))]) < a: print(i)

Я думаю, что это работает, но это неэффективно. Например число 5 встречается только в одном кортеже, но проверено много раз! Есть ли способ сделать это быстрее? Я бы использовал несколько циклов while (с операторами break), но поскольку я не знаю, какова длина F, я не думаю, что это возможно.


python prime-factoring number-theory
person Michał Dobranowski    schedule 20.12.2020    source источник
comment
Привет Михал! Чтобы я понял проблему, которую вы хотите решить: вы пытаетесь получить все делители a? У вас есть разложение a на простые множители? Является ли c[i] показателем степени множителя F[i] в текущем делителе a?   -  person smed    schedule 20.12.2020
comment
К сожалению, я не пытаюсь получить все делители a. Например, последний кортеж - (5,0,0) эквивалентен 2^5 * 3^0 * 5^0 = 32 * 1 * 1 = 32, что не является делителем 60, но меньше 60 и набором простых множителей 32 — это подмножество простых делителей числа 60. И у меня есть хорошая функция для простой факторизации a.   -  person Michał Dobranowski    schedule 20.12.2020
comment
Таким образом, для фактора f из a максимальный показатель степени будет n таким, что f**n<=a<f**(n+1) ?   -  person smed    schedule 20.12.2020
comment
Одно исправление: f**n<a<=f**(n+1). И тогда f - максимальный показатель, но он не будет работать во всех случаях, например. для f = 2 максимальный показатель степени равен 5, но 2^5 * 3^1 * 5^0 > 60 (поэтому кортеж (5,1,0) не включен в мой ожидаемый результат.   -  person Michał Dobranowski    schedule 20.12.2020

Ответы (4)


arrow_upward
1
arrow_downward

Вы основываете все свои range лимиты только на min(F). Давайте настроим каждый на log(a, factor), чтобы уменьшить количество случаев:

from math import ceil, log, prod
from itertools import product

a = 60
F = [2, 3, 5]

ranges = [range(0, ceil(log(a, factor))) for factor in F]

C = []

for powers in product(*ranges):
    if prod(F[i] ** power for i, power in enumerate(powers)) < a:
        C.append(powers)

print(C)

По моим меркам, ваш код генерирует 216 тестовых случаев, чтобы получить 25 результатов, но приведенный выше код генерирует только 1/3 этих тестовых случаев.

person cdlane    schedule 21.12.2020

arrow_upward
0
arrow_downward

Вы можете перебрать все допустимые кортежи с помощью генератора, например:

def exponent_tuples(prime_factors, limit):
    def next_tuple(t):
        n = math.prod(f ** tt for f, tt in zip(prime_factors, t))
        for idx, (f, tt) in enumerate(zip(prime_factors, t)):
            n *= f
            if n < limit:
                return (0,) * idx + (tt + 1,) + t[idx + 1 :]
            n //= f**(tt+1)
        return None

    t = (0,) * len(prime_factors)
    while t is not None:
        yield t
        t = next_tuple(t)


for t in exponent_tuples([2, 3, 5], 60):
    print(t)

Идея здесь состоит в том, чтобы в основном увеличивать записи кортежа, такие как цифры числа, и иметь соответствующую цифру, которая сбрасывается до нуля и переносит 1 всякий раз, когда вы достигаете определенного предела.

Я почти уверен, что это делает именно то, что вы хотите, за исключением, возможно, порядка, в котором он дает кортежи (можно настроить, изменив функцию next_tuple)

РЕДАКТИРОВАТЬ: немного упростил код

person Cereal    schedule 20.12.2020

arrow_upward
0
arrow_downward

Почти готовое предложение будет звучать так (исполнение снаряда)

>>> max_exponents(42,[2,3,7])
[5, 3, 1]
>>> #pick 2
>>> max_exponents(42//2**2,[3,7])
[2, 1]
>>> #pick 1
>>> max_exponents(42//(2**2*3**1),[7])
[0]

Я почти закончил. Это будет адаптироваться к любому количеству факторов!

person smed    schedule 23.12.2020

arrow_upward
-1
arrow_downward

Каким-то образом ваше предложение сводится к этому (более читабельная форма?)

import math as m 
import pprint

a = 60
prime_factors = [2,3,5]

exponents =list(map(lambda x:m.floor(m.log(a,x)),prime_factors))
rez = []
for i in range(exponents[0]+1):
    for j in range(exponents[1]+1):
        for k in range(exponents[2]+1):
            if 2**i*3**j*5**k <= a:
                rez.append((i,j,k))
pprint.pprint(rez)

и вы хотели бы знать, есть ли способ сделать это быстрее (с меньшим количеством тестов). Итак, мы больше не на стороне реализации, а больше на стороне концепции (алгоритма)?

Например, после того, как был выбран первый показатель степени c[0], следующие должны быть выбраны среди одного, подходящего в a//(2**c[a]), как предложил другой ответчик, я думаю

person smed    schedule 20.12.2020
comment
Ну да. Я хотел бы найти более эффективный алгоритм (если он есть). - person Michał Dobranowski; 20.12.2020
comment
Ваше решение - это то, чего я пытаюсь избежать. У вас есть три цикла for, и нет гарантии, что len(prime_factors) тоже будет 3. - person Michał Dobranowski; 21.12.2020
comment
Я понимаю, что мое предложение было не решением, а уточнением. С этого момента мы можем попытаться настроить его, чтобы сделать лучше - person smed; 21.12.2020