Twierdzenie liczby wielobocznej Fermata stwierdza, że każdą dodatnią liczbę całkowitą można wyrazić jako sumę co najwyżej -liczb liczbowych. Oznacza to, że każdą dodatnią liczbę całkowitą można wyrazić jako sumę maksymalnie trzech liczb trójkątów, czterech liczb kwadratowych, pięciu liczb pięciokątnych itp. Twoim zadaniem jest pobranie dodatniej liczby całkowitej i liczby całkowitej i wyprowadzenie -gonalne liczby całkowite, które sumują się do .
-tej -gonal całkowitą, gdzie i , może być zdefiniowane w kilka sposobów. Sposób niż matematyka Y jest taka, że tH liczba -gonal może być wykonana jako regularny wielokąt boków, z których każdy o długości . Na przykład dla (liczby trójkątne):
Zobacz tutaj przykłady z większymi .
Definicja Math Y jest za pomocą wzoru na , które daje w wyniku -tym liczbę -gonal:
który jest podany na stronie Wikipedii tutaj .
Wkład
Dwie dodatnie liczby całkowite, i , z warunkiem . Możesz wprowadzić te liczby całkowite w najbardziej naturalnej reprezentacji w swoim języku (dziesiętne, jednoargumentowe, liczby kościelne, liczby zmiennoprzecinkowe o wartościach całkowitych itp.).
Wydajność
Lista liczb całkowitych o maksymalnej długości , gdzie suma jest równa a wszystkie liczby całkowite w są liczbami całkowitymi -gonal. Ponownie, liczby całkowite mogą być wyprowadzane w naturalnej reprezentacji w twoim języku, z dowolnym wyraźnym, spójnym separatorem (więc znak (-y) dziesiętny dla wyjścia dziesiętnego, znak inny niż ten używany dla wyjścia jednostkowego itp.)
Zasady
- Wejścia lub wyjścia nigdy nie przekroczą limitu liczb całkowitych dla twojego języka
- nie musi być zamawiany
- W przypadku wielu możliwych wyników, wszystkie lub wszystkie są dopuszczalne
- To jest code-golf, więc wygrywa najkrótszy kod w bajtach
Przypadki testowe
x, s => L
1, s => 1
2, s => 1, 1
5, 6 => 1, 1, 1, 1, 1
17, 3 => 1, 6, 10
17, 4 => 1, 16
17, 5 => 5, 12
36, 3 => 36
43, 6 => 15, 28
879, 17 => 17, 48, 155, 231, 428
4856, 23 => 130, 448, 955, 1398, 1925
źródło
x=17, s=5
czy moglibyśmy produkować5,12,0,0,0
zamiast po prostu5,12
?Q
do mojego zgłoszenia?Odpowiedzi:
Haskell ,
78 8077 bajtówObliczamy iloczyn kartezjański pierwszychn -liczb gonalnych, a następnie znajdujemy pierwszy wpis, który sumuje się do n .
Wypróbuj online!
źródło
JavaScript (ES6),
8380 bajtówSzybkie wyszukiwanie rekurencyjne, które maksymalizuje najmniejszy termin wyniku.
Pobiera dane wejściowe jako
(s)(x)
.Wypróbuj online!
Formuła
Okazuje się, że krótsze jest użycie formuły opartej na 0 do obliczenia liczbs gonal w JS, tj. Aby rozpocząć od n = 0 i obliczyć P.( n + 1 , s ) :
które można zapisać w 14 bajtach:
Skomentował
źródło
05AB1E ,
1413 bajtówPort galaretki Jonathana Allana .
Wypróbuj online!
źródło
Haskell , 55 bajtów
Wypróbuj online!
Wyprowadza wszystkie możliwe rozwiązania. Definiuje liczby s-gonalne jako skumulowaną sumę postępu arytmetycznego
źródło
Galaretka , 17 bajtów
(Bardzo, bardzo nieefektywny) dyadyczny link akceptujący
s
po lewej ix
po prawej stronie, który daje najkrótszą możliwą odpowiedź jako listę liczb całkowitych (posortowane rosnąco).Wypróbuj online! - nie ma sensu próbować tego przy znacznie wyższych wartościach!
W jaki sposób?
źródło
⁸
Rubinowy , 79 bajtów
Wypróbuj online!
źródło
Python 3 , 105 bajtów
Wypróbuj online!
Odpowiedź JavaScript na Port of Arnauld , więc upewnij się, że go głosujesz!
źródło
Siatkówka , 111 bajtów
Wypróbuj online! Link zawiera przypadki testowe. Pobiera dane wejściowe w kolejności
s n
. Wyjaśnienie:Konwertuj na unary.
Po przetworzeniu pozostałych etapów potraktuj je jako program Retina i uruchom je na tym samym wejściu.
Powiel linię.
Zastąp pierwszą kopię wyrażeniem regularnym, które przeskakuje nad pierwszą liczbą, a następnie pasuje do
s
s
liczb -gonal. Same liczby są przechwytywane w nieparzyste grupy przechwytywania, a parzyste grupy przechwytywania są używane do zapewnienia, że wszystkie liczby sąs
-gonalne.Zastąp drugą kopię nieparzystą listą nieparzystych grup przechwytywania.
Przykładowo wygenerowany kod dla danych wejściowych
5 17
jest następujący:źródło
APL (NARS), 149 znaków, 298 bajtów
jeśli nie, znajdź rozwiązania „0 = ≢b” niż zwróć dla wejścia (ns), n razy 1; inaczej zwróci sumę liczb s, która ma mniej uzupełnienia ...
test:
Problem polegający na tym, że nie znaleziono rozwiązania ma pewną liczbę powtórzeń w sumie ...
źródło
C ++ (clang) , 198 bajtów
Wypróbuj online!
źródło