Aby rozwiązać ten problem, po raz pierwszy to zauważyłem
Gdzie to liczba (niekoniecznie pierwsza) dzielników . Jeśli jest najmniejszą liczbą całkowitą taką, że , to
Teraz musimy wybrać , aby było minimalne. Wybory dla są trywialne - są tylko liczbami pierwszymi w porządku rosnącym.
Jednak moja pierwsza myśl o wyborze była nieprawidłowa. Pomyślałem, że możesz po prostu uwzględnić , 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 to:
Ale to jest niepoprawne dla :
Prawidłowa odpowiedź to:
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:
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:
Jednak optymalnym rozwiązaniem jest:
źródło
Odpowiedzi:
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
Mamy też powtarzalność:
Wreszcie ilość, której szukasz, to
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))
.źródło
powerset
for factor_list in powerset(factors)
na coś, co generuje każdy odrębny dzielnikn
dokł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 .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 .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⋅3 23⋅33 23⋅3⋅5 2⋅3⋅5⋅7 23⋅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 .2pq−1 2p−1⋅3q−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ż .2ab−1 2ab−1>2a−1⋅xb−1 23 23<2⋅7
źródło