2012-02-03 10 views
7

że mają zasadniczo problem, który sprowadza się do następujących: Biorąc pod uwagę niektóre (liczba całkowita), liczba n, dla znalezienia zbioru liczb względnie pierwsze, np C = (c , C ,. .., C K), każdy w ilości mniejszej niż n, które spełniają:Maksymalny iloczyn względnie pierwsze czynniki

1) Produkt z wszystkimi C i jest maksymalne.

2) Suma wszystkich c i jest równa n.

To może być pytanie do MathOverflow, ale czy istnieje jakiś algorytm nie-brutalnej siły do ​​robienia tego?

+0

Z ciekawości, jaki jest twój pierwotny problem? – templatetypedef

+0

@templatetypedef Obliczanie elementu największego rzędu w grupie permutacji S_ {n} – Yuushi

+0

poszukaj math.stackexchange.com –

Odpowiedz

7

Poszukujesz maksymalnej maksymalnej wielokrotności dowolnej partycji n. Produkt jest znany jako funkcja Landau (patrz OEIS A000793). Można to obliczyć za pomocą programowania dynamicznego, patrz here.

+0

Ah, genialne, dziękuję. – Yuushi

Powiązane problemy