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

9

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

ϕ(p1e1 p2e2 pkek)=(e1+1)(e2+1)(ek+1)

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

ϕ(m)=n
(e1+1)(e2+1)(ek+1)=n

Teraz musimy wybrać , aby było minimalne. Wybory dla są trywialne - są tylko liczbami pierwszymi w porządku rosnącym.eiipieip

Jednak moja pierwsza myśl o wyborze ei 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=53
15=(4+1)(2+1)
m=2432=144

Ale to jest niepoprawne dla n=16 :

16=2222
16=(1+1)(1+1)(1+1)(1+1)
m=21315171=210

Prawidłowa odpowiedź to:

16=(3+1)(1+1)(1+1)
m=233151=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:71>222

1552=(96+1)(1+1)(1+1)(1+1)(1+1)
m=296315171111>296335171

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

22315171111131171191231291311

23325171111131171191231291

25335171111131171191231

Jednak optymalnym rozwiązaniem jest:

27335271111131171191
orlp
źródło
@orlp: Moja sugestia brzmiała: naprawić (powiedzmy ) i naprawić (powiedzmy ). Następnie próbujesz zminimalizować , z zastrzeżeniem . Pracując ze stałą liczbą (liczb pierwszych), możesz zignorować komplikacje związane z tym, czy określona liczba pierwsza powinna pojawić się w globalnym minimum. Znajdź minimum dla każdego , a następnie weź min z nich. n24m2k1log(2)+k2log(3)k1k2=24mm
Steve D

Odpowiedzi:

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

T(n,1)=2n1T(2m,m)=p1p2pm

Mamy też powtarzalność:

T(n,m)=mind|n[T(nd,m1)pmd1]

Wreszcie ilość, której szukasz, to

min1ilog(n)T(n,i)

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))
Steve D.
źródło
Komentarze, do których się odnosisz, wydają się niestety usunięte, ale z pewnością jest to optymalne (w sensie obliczenia najmniejszej możliwej liczby całkowitej z dokładnie współczynnikami). Czy jest to optymalność złożoności czasu, której nie jesteś pewien? Nie znam ścisłego ograniczenia liczby dzielników liczby całkowitej , ale nawet przy bardzo pesymistycznej granicy twoim algorytmem jest tylko , co powinno być wystarczająco szybkie dla w dziesiątkach tysięcy! (BTW: nnO(n)O(n2logn)n
Pisałem
@j_random_hacker: Tak, nie jestem pewien, co się stało z tymi komentarzami: było ich wiele i już ich nie ma! Rzeczywiście mówiłem o złożoności czasu; Właściwie myślę, że prawdopodobnie jest bliżej , ale liczba dzielników jest trudną funkcją. Oczywiście powyższy kod można z pewnością lepiej zoptymalizować: nie uwzględnia na przykład duplikatów. O(nlogn)powerset
Steve D
Sądzę, że łatwiej jest to efektywnie wdrożyć za pomocą programowania dynamicznego: gist.github.com/orlp/0fbb7784782712bc7c411aa58a188143 Nawiasem mówiąc, naprawdę nie podoba mi się logarytmiczna sztuczka - ograniczona precyzja zmiennoprzecinkowa w pewnym momencie coś psuje . Biorąc to pod uwagę, nie sądzę, że jest to rzeczywiście szybsze niż generowanie wszystkich multiplikatywnych partycji. W rzeczywistości uważam, że właśnie to robi w przebraniu!
orlp
Po dokładniejszym przeczytaniu komentarza @ orlp i twojego kodu, uważam, że dla złożoności czasu (i praktycznej wydajności) ważne jest, aby zmienić for factor_list in powerset(factors)na coś, co generuje każdy odrębny dzielnik ndokładnie raz. W ten sposób, na przykład, , jeśli weźmiesz pod uwagę rozwiązania zawierające dokładnie pierwsze liczby pierwsze jako ich odrębne czynniki pierwsze, wykonasz tylko nierekurencyjną pracę zamiast , który jest wykładniczy w . n=2k3k2kO(k2)O((2kk))k
j_random_hacker
1
@orlp: Przepraszam, źle zrozumiałem termin „multiplikatywne partycje”. Dzięki za kod Python. Aby zobaczyć, dlaczego algorytm Steve'a D nie jest równoległy do ​​tego kodu, zastanów się multiplicative_partitions(24), która tworzy (między innymi) partycje [4, 3, 2]i [6, 2, 2]która (po odwróceniu kolejności w celu nadania najmniejszemu współczynnikowi pierwszemu najwyższego wykładnika) odpowiada rozwiązaniom i . Algorytm Steve'a D nigdy nie rozważy drugiego rozwiązania, ponieważ już ustalił, że rozwiązanie . 2332512531512332=72<2531=96
j_random_hacker
-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.2a·3b·5c...

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 .27·323·3323·3·52·3·5·723·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 .2pq12p1·3q1

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ż .2ab12ab1>2a1·xb12323<2·7

gnasher729
źródło
3
Wybacz mi, ale to wcale nie odpowiada na moje pytanie, po prostu podsumowuje to, co znalazłem w moim pytaniu. Tytuł jest taki: tytuł, a nie samo pytanie. Wydaje mi się, że przeczytałeś tytuł tylko przed odpowiedzią. Prawdziwe pytanie znajduje się na dole mojego tekstu pytania.
lub
Odpowiedzi na to udzielił ostatni akapit.
gnasher729,
@ gnasher729 To jest daleko od bycia odpowiedź na pytanie „skutecznie obliczyć”, lub nawet o „optymalnej strategii łączenia”
yo”