Twierdzenie liczby wielobocznej Fermata stwierdza, że ​​każdą dodatnią liczbę całkowitą można wyrazić jako sumę co najwyżej $n$ $n$ -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 $x$ i liczby całkowitej $s \ge 3$ i wyprowadzenie $s$ -gonalne liczby całkowite, które sumują się do $x$ .

$n$ -tej $s$ -gonal całkowitą, gdzie $n \ge 1$ i $s \ge 3$ , może być zdefiniowane w kilka sposobów. Sposób niż matematyka Y jest taka, że $n$ tH $s$ liczba -gonal może być wykonana jako regularny wielokąt $s$ boków, z których każdy o długości $n$ . Na przykład dla $s = 3$ (liczby trójkątne):

Zobacz tutaj przykłady z większymi $s$ .

Definicja Math Y jest za pomocą wzoru na $P(n, s)$ , które daje w wyniku $n$ -tym $s$ liczbę -gonal:

który jest podany na stronie Wikipedii tutaj .

Wkład

Dwie dodatnie liczby całkowite, $s$ i $x$ , z warunkiem $s \ge 3$ . 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 $L$ o maksymalnej długości $s$ , gdzie suma $L$ jest równa $x$ a wszystkie liczby całkowite w $L$ są liczbami całkowitymi $s$ -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
• $L$ 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

Haskell , 78 80 77 bajtów

Obliczamy iloczyn kartezjański pierwszych $n$ -liczb gonalnych, a następnie znajdujemy pierwszy wpis, który sumuje się do $n$ .

s#n=[x|x<-mapM(map(\n->s*(n^2-n)`div`2+n*(2-n)))([0..n]<$[1..s]),sum x==n]!!0

Wypróbuj online!

JavaScript (ES6),  83  80 bajtów

Szybkie wyszukiwanie rekurencyjne, które maksymalizuje najmniejszy termin wyniku.

Pobiera dane wejściowe jako (s)(x).

s=>g=(x,n=0,a=[],y=~n*(~-n-n*s/2))=>x<y?x|a[s]?0:a:g(x,n+1,a)||g(x-y,n,[...a,y])

Wypróbuj online!

Formuła

Okazuje się, że krótsze jest użycie formuły opartej na 0 do obliczenia liczb $s$ gonal w JS, tj. Aby rozpocząć od $n=0$ i obliczyć $P(n+1,s)$ :

które można zapisać w 14 bajtach:

~n*(~-n-n*s/2)

Skomentował

s =>                         // main function taking s
  g = (                      // recursive function g
    x,                       // taking x
    n = 0,                   // start with n = 0
    a = [],                  // a[] = list of s-gonal numbers
    y =                      // y = P(n + 1, s)
      ~n * (~-n - n * s / 2) //   = -(n + 1) * ((n - 1) - n * s / 2)
  ) =>                       //
    x < y ?                  // if x is less than P(n + 1, s):
      x | a[s] ?             //   if x is not equal to 0 or a[] is too long:
        0                    //     failed: return 0
      :                      //   else:
        a                    //     success: return a[]
    :                        // else:
                             //   process recursive calls:
      g(x, n + 1, a) ||      //   preferred: try to increment n
      g(x - y, n, [...a, y]) //   fallback : try to use the current s-gonal number

05AB1E , 14 13 bajtów

Port galaretki Jonathana Allana .

ÍIÝ*>.¥¹ã.ΔOQ

Wypróbuj online!

Haskell , 55 bajtów

n%s=[l|l<-mapM(\_->scanl(+)0[1,s-1..n])[1..s],sum l==n]

Wypróbuj online!

Wyprowadza wszystkie możliwe rozwiązania. Definiuje liczby s-gonalne jako skumulowaną sumę postępu arytmetycznego

1, s-2, 2*s-3, 3*s-4, ...

Galaretka , 17 bajtów

x’2;’ÄÄx⁸ŒPS⁼¥Ƈ⁹Ḣ

(Bardzo, bardzo nieefektywny) dyadyczny link akceptujący spo lewej i xpo 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?

x’2;’ÄÄx⁸ŒPS⁼¥Ƈ⁹Ḣ - Link: s, x                    e.g.  5, 17
x                 - repeat (s) (x) times                [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
 ’                - decrement (vectorises)              [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
  2;              - prepend a two                       [2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
    ’             - decrement (vectorises)              [1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
     Ä            - cumulative sums                     [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52]
      Ä           - cumulative sums                     [1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425, 477]
       x⁸         - repeat (each of those) (s) times    [1, 1, 1, 5, ..., 425, 477, 477, 477]
         ŒP       - power-set                           [[], [1], [1], ..., [1, 1], ..., [5, 22, 70], ... etc]
                      (this has 2^(x(s+1)) entries ...this example would have 2^(17(5+1)) = 2^102 = 5070602400912917605986812821504 entries!)
                      (Note: the lengths increase left to right)
              Ƈ   - filter keep if:
             ¥    -   last two links as a dyad:
           S      -     sum
            ⁼  ⁹  -     equals (x)?                     [[5,12], ... , [5,12], [1, 1, 5, 5, 5], ... , [1, 1, 5, 5, 5], [1, 1, 1, 1, 1, 12], ...]
                Ḣ - head                                [5,12]

Rubinowy , 79 bajtów

$n$ $s$$s$

$\frac{n^2(s-2)-n(s-4)}{2}$$\frac{n(ns-2n-s+4)}{2}$

->n,s{a=(0..n).map{|i|i*(i*s-2*i-s+4)/2};a.product(*[a]*~-s).find{|a|a.sum==n}}

Wypróbuj online!

Python 3 , 105 bajtów

def f(s,x,n=0,a=[]):y=~n*(~-n-n*s/2);return(x<1)*a*(len(a)<=s)if x<y else f(s,x,n+1,a)or f(s,x-y,n,a+[y])

Wypróbuj online!

Odpowiedź JavaScript na Port of Arnauld , więc upewnij się, że go głosujesz!

Siatkówka , 111 bajtów

\d+
*
~(`$
$"
0%["^_+ "|""]'$L$`\G_(?<=(?=___(_*))_+)
((_(?($.(2*$>`))$1\$.(2*$>`)))$*)
1%|' L$`\G_
$$.$.($`$>`

Wypróbuj online! Link zawiera przypadki testowe. Pobiera dane wejściowe w kolejności s n. Wyjaśnienie:

\d+
*

Konwertuj na unary.

~(`

Po przetworzeniu pozostałych etapów potraktuj je jako program Retina i uruchom je na tym samym wejściu.

$
$"

Powiel linię.

0%["^_+ "|""]'$L$`\G_(?<=(?=___(_*))_+)
((_(?($.(2*$>`))$1\$.(2*$>`)))$*)

Zastąp pierwszą kopię wyrażeniem regularnym, które przeskakuje nad pierwszą liczbą, a następnie pasuje do s sliczb -gonal. Same liczby są przechwytywane w nieparzyste grupy przechwytywania, a parzyste grupy przechwytywania są używane do zapewnienia, że ​​wszystkie liczby są s-gonalne.

1%|' L$`\G_
$$.$.($`$>`

Zastąp drugą kopię nieparzystą listą nieparzystych grup przechwytywania.

Przykładowo wygenerowany kod dla danych wejściowych 5 17jest następujący:

^_+ ((_(?(2)__\2))*)((_(?(4)__\4))*)((_(?(6)__\6))*)((_(?(8)__\8))*)((_(?(10)__\10))*)$
$.1 $.3 $.5 $.7 $.9

APL (NARS), 149 znaków, 298 bajtów

r←f w;n;s;i;k
(n s)←w⋄r←⍬⋄→0×⍳s<3⋄i←1
→0×⍳n<k←2÷⍨(i×i×s-2)-i×s-4⋄r←r,k⋄i+←1⋄→2

h←{0=≢b←((v←↑⍵)=+/¨a)/a←{0=≢⍵:⊂⍬⋄m,(⊂1⌷⍵),¨m←∇1↓⍵}f⍵:v⍴1⋄k←↑⍋≢¨b⋄k⊃b}

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:

  h 1 3
1 
  h 2 8
1 1 
  h 5 6
1 1 1 1 1 
  h 17 3
1 6 10 
  h 17 4
1 16 
  h 17 5
5 12 
  h 36 3
36 
  h 43 6
15 28 
  h 879 17
17 48 155 231 428 
  h 4856 23
321 448 596 955 2536 
  +/h 4856 23
4856

Problem polegający na tym, że nie znaleziono rozwiązania ma pewną liczbę powtórzeń w sumie ...

C ++ (clang) , 198 bajtów

#import<vector>
using V=std::vector<int>;V f(int n,int s){V _{0};int z=1,a=0,b=1,i,t;for(;a<n;b+=s-2)_.push_back(a+=b),++z;V o;for(t=a=0;t-n;b=++a)for(o=V(s),t=i=0;b;b/=z)t+=o[i++]=_[b%z];return o;}

Wypróbuj online!

V=vector<int> 
V _{0}; // initialized with one element =0 
int z=1, // vector size 
a=0,b=1,i,t;for(;a<n;b+=s-2)_.push_back(a+=b),++z;
// pushes polygons in V
V o; // vector to be returned 
for(t=a=0;t-n;b=++a) // ends when t=n
// loop to generate multi-dimension indexes
// for example a=1234 z=10
// a%z->4 , a/=z , a%z-> 3 , ... 2 , 1
for(o=V(s),t=i=0;b;b/=z)// loop to extract indexes
t+=o[i++]=_[b%z]; // put the sum in t and values in o
return o