Wydajne obliczanie najmniejszej liczby całkowitej za pomocą n dzielników

Aby rozwiązać ten problem, po raz pierwszy to zauważyłem

$$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$

Gdzie to liczba (niekoniecznie pierwsza) dzielników . Jeśli jest najmniejszą liczbą całkowitą taką, że , to$\phi(m)$$m$$m$$\phi(m) = n$

$$\phi(m) = n$$ $$(e_1 + 1)(e_2 + 1)\cdots(e_k +1) = n$$

Teraz musimy wybrać , aby było minimalne. Wybory dla są trywialne - są tylko liczbami pierwszymi w porządku rosnącym.$e_i$$\prod_{i} p_i^{e_i}$$p$

Jednak moja pierwsza myśl o wyborze $e_i$ była nieprawidłowa. Pomyślałem, że możesz po prostu uwzględnić $n$ , posortować czynniki w porządku malejącym i odjąć 1. W większości przypadków działa to dobrze, np. Najmniejsza liczba całkowita z dzielnikami $n = 15$ to:

$$15 = 5 \cdot 3$$ $$15 = (4 + 1)(2 + 1)$$ $$m = 2^4 3^2 = 144$$

Ale to jest niepoprawne dla $n = 16$ :

$$16 = 2 \cdot 2\cdot 2 \cdot 2$$ $$16 = (1 + 1)(1 + 1)(1 + 1)(1 + 1)$$ $$m = 2^1 3^1 5^1 7^1 = 210$$

Prawidłowa odpowiedź to:

$$16 = (3 + 1)(1 + 1)(1 + 1)$$ $$m = 2^3 3^1 5^1 = 120$$

Jest więc jasne, że czasami musimy połączyć czynniki. W tym przypadku, ponieważ . Ale nie widzę dokładnie czystej i bezpośredniej strategii łączenia. Na przykład, można by pomyśleć, że zawsze musimy połączyć się z siłą , ale to nie jest prawda:$7^1 > 2^2$$2$

$$1552 = (96 + 1)(1 + 1)(1 + 1)(1 + 1)(1 + 1)$$ $$m = 2^{96} 3^1 5^1 7^1 11^1 > 2^{96} 3^3 5^1 7^1$$

Nie mogę od razu wymyślić przykładu, ale mój instynkt mówi, że niektóre zachłanne podejścia mogą zawieść, jeśli najpierw połączą złe moce.

Czy istnieje prosta optymalna strategia połączenia tych uprawnień, aby uzyskać prawidłową odpowiedź?

---

Uzupełnienie. Chciwy algorytm, który sprawdza każde możliwe scalenie i wykonuje najlepszy na zasadzie scalania po scaleniu, kończy się niepowodzeniem dla . Seria połączeń jeden po drugim to:$n = 3072$

$$2^2 3^1 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1 31^1$$

$$2^3 3^2 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1$$

$$2^5 3^3 5^1 7^1 11^1 13^1 17^1 19^1 23^1$$

Jednak optymalnym rozwiązaniem jest:

$$2^7 3^3 5^2 7^1 11^1 13^1 17^1 19^1$$

Oto rozwiązanie oparte na moich komentarzach powyżej. Nie twierdzę, że jest to optymalne.

Chodzi o to, aby rozważyć , które definiujemy jako „najmniejszą dodatnią liczbę całkowitą o dokładnie dzielnikach i różnych czynnikach pierwszych”. Dokonujemy łatwych obserwacji:$T(n,m)$$n$$m$

$$\begin{align} T(n, 1) &= 2^{n-1}\\ T(2^m, m) &= p_1p_2\cdots p_m \end{align}$$

Mamy też powtarzalność:

$$\begin{equation} T(n,m) = \min_{d|n} [T\left(\frac{n}{d}, m-1\right)\cdot p_m^{d-1}] \end{equation}$$

Wreszcie ilość, której szukasz, to

$$\begin{equation} \min_{1\le i\le\lceil\log(n)\rceil} T(n, i) \end{equation}$$

W tym celu oto kod Python, który zgadza się ze wszystkimi liczbami, które podałeś powyżej. Zauważ, że współdziałanie z logarytmami powoduje, że liczby są mniejsze: rzeczywista liczba całkowita, której szukasz, to round(2**smallest(n)).

import functools
import itertools
import math

# All primes less than 100.
PRIMES = [
  2, 3, 5, 7, 11,
  13, 17, 19, 23, 29,
  31, 37, 41, 43, 47,
  53, 59, 61, 67, 71,
  73, 79, 83, 89, 97,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
  max_factors = math.ceil(math.log2(n))
  min_so_far = float('Infinity')
  factors = factorize(n)
  memo = {}
  for i in range(1, max_factors+1):
    t = T(n,i, factors, memo)
    if 0.0 < t < min_so_far:
      min_so_far = t
  return min_so_far

def T(n, m, factors=None, memo=None):
  if memo is None:
    memo = {}
  if n < 2 or m < 1:
    return 0
  elif m == 1:
    # Everything on the smallest prime.
    return (n-1) * LOG_PRIMES[0]
  elif n < 2**m:
    return 0
  elif n == 2**m:
    # Product of first m primes, in log.
    return sum(LOG_PRIMES[:m])
  elif (n,m) in memo:
    return memo[(n,m)]

  if factors is None:
    factors = factorize(n)
  if len(factors) < m:
    return 0

  smallest = float('Infinity')  
  for factor_list in powerset(factors):
    divisor = product(factor_list)
    first = T(divisor, m-1, factor_list, memo)
    # No such product.
    if first < 1.0:
      continue
    second = (n/divisor - 1) * LOG_PRIMES[m-1]
    total = first + second
    if total < smallest:
      smallest = total

  memo[(n,m)] = smallest
  return smallest

def product(nums):
  return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
  prime_factors = []
  for p in PRIMES:
    while n%p == 0:
      n //= p
      prime_factors.append(p)
    if n == 1:
      break
  return prime_factors

def powerset(lst):
  # No empty set.
  return itertools.chain.from_iterable(itertools.combinations(lst, r) 
                                       for r in range(1, len(lst)+1))

Możliwymi kandydatami na „najmniejszą liczbę całkowitą z n dzielnikami” są liczby całkowite w postaci gdzie a ≥ b ≥ c ... i (a + 1) (b + 1) (c + 1) ... = n.$2^a·3^b·5^c...$

Musisz więc znaleźć wszystkie sposoby wyrażenia n jako iloczyn liczb całkowitych ≥ 2 w kolejności rosnącej oraz obliczyć i sprawdzić odpowiednich kandydatów. Na przykład, gdy n = 16, 16 = 8 · 2 = 4 · 4 = 4 · 2 · 2 = 2 · 2 · 2 · 2, więc możliwości to , , , , a najmniejsza to .$2^7·3$$2^3·3^3$$2^3·3·5$$2·3·5·7$$2^3·3·5 = 120$

Jeśli n jest iloczynem dwóch liczb pierwszych p · q, p ≥ q, jedynymi kandydatami są i , a ta ostatnia jest zawsze mniejsza .$2^{pq-1}$$2^{p-1}·3^{q-1}$

Można zorientować się, niektóre stanu, który nie jest czynnikiem , na przykład, poprzez sprawdzenie, czy dla niektórych liczba pierwsza x to nie jest czynnik. W przykładzie n = 16 występuje czynnik ponieważ .$2^{ab-1}$$2^{ab-1} > 2^{a-1}·x^{b-1}$$2^3$$2^3 < 2·7$