O teorema dos números poligonais de Fermat afirma que todo número inteiro positivo pode ser expresso como a soma de no máximo $n$ $n$ números na diagonal. Isso significa que todo número inteiro positivo pode ser expresso como a soma de até três números de triângulos, quatro números quadrados, cinco números pentagonais etc. Sua tarefa é pegar um número inteiro positivo $x$ , e um número inteiro $s \ge 3$ , e gerar os números $s$ inteiros -gonal que somam $x$ .

O $n$ -simo $s$ -gonal inteiro, onde $n \ge 1$ e $s \ge 3$ , pode ser definida em uma de duas maneiras. A forma não-matemática y é que o $n$ ° $s$ série -gonal pode ser construído como um polígono regular com $s$ lados, cada uma de comprimento $n$ . Por exemplo, para $s = 3$ (números triangulares):

Veja aqui exemplos com um maior $s$ .

A definição matemática-y é, utilizando a fórmula para $P(n, s)$ , que produz o $n$ -simo $s$ número -gonal:

que é fornecido na página da Wikipedia aqui .

Entrada

Dois inteiros positivos, $s$ e $x$ , com a condição $s \ge 3$ . Você pode inserir esses números inteiros na representação mais natural do seu idioma (decimal, unário, numerais da Igreja, números de ponto flutuante com valor inteiro etc.).

Saída

Uma lista de números inteiros, $L$ , com um comprimento máximo de $s$ , em que a soma de $L$ é igual a $x$ e todos os números inteiros em $L$ são números inteiros $s$ -gonais. Novamente, os números inteiros podem ser emitidos na representação natural em seu idioma, com qualquer separador consistente e distinto (portanto caracteres não decimais para saída decimal, um caractere diferente daquele usado para saída unária etc.)

Regras

• As entradas ou saídas nunca excederão o limite inteiro para o seu idioma
• $L$ não precisa ser encomendado
• No caso de múltiplas saídas possíveis, qualquer uma ou todas são aceitáveis
• Isso é código-golfe, então o código mais curto em bytes vence

Casos de teste

   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 bytes

Computamos o produto cartesiano do primeiro $n$ números -sonais e, em seguida, encontramos a primeira entrada que soma $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

Experimente online!

JavaScript (ES6),  83  80 bytes

Uma pesquisa recursiva rápida que maximiza o menor termo da saída.

Toma entrada como (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])

Experimente online!

Fórmula

É mais curto usar uma fórmula baseada em 0 para calcular os números $s$ diagonal em JS, ou seja, começar com $n=0$ e calcular $P(n+1,s)$ :

que pode ser escrito em 14 bytes:

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

Comentado

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 bytes

Resposta da geléia do porto de Jonathan Allan .

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

Experimente online!

Haskell , 55 bytes

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

Experimente online!

Produz todas as soluções possíveis. Define os números s-gonais como a soma cumulativa da progressão aritmética

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

Gelatina , 17 bytes

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

Um link diádico (muito, muito ineficiente), que aceita sà esquerda e xà direita, que produz a resposta mais curta possível como uma lista de números inteiros (classificados em ordem crescente).

Experimente online! - não faz muito sentido tentar por valores muito mais altos!

Quão?

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]

Ruby , 79 bytes

Calcula o primeiro $n$ $s$-gonal e zero, obtém o produto cartesiano de si mesmo $s$vezes e encontra a primeira entrada que corresponde. Casos de teste posteriores ficam sem memória no TIO, mas teoricamente funcionam.

$\frac{n^2(s-2)-n(s-4)}{2}$ é reorganizado em $\frac{n(ns-2n-s+4)}{2}$ porque salva bytes em Ruby.

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

Experimente online!

Python 3 , 105 bytes

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

Experimente online!

Resposta JavaScript do Port of Arnauld , certifique-se de vomitá-lo!

Retina , 111 bytes

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

Experimente online! O link inclui casos de teste. Recebe entrada na ordem s n. Explicação:

\d+
*

Converta para unário.

~(`

Depois de processar os estágios restantes, trate-os como um programa Retina e execute-os na mesma entrada.

$
$"

Duplique a linha.

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

Substitua a primeira cópia por uma expressão regular que pule o primeiro número e depois corresponda s saos números -gonal. Os números em si são capturados em grupos de captura ímpares e os grupos de captura par são usados ​​para garantir que todos os números sejam s-gonal.

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

Substitua a segunda cópia por uma lista separada por espaços dos grupos de captura ímpares.

Como exemplo, o código gerado para uma entrada de 5 17é o seguinte:

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

APL (NARS), 149 caracteres, 298 bytes

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}

se não encontrar soluções "0 = ≢b" do que retornar para a entrada (ns), n vezes 1; caso contrário, retornaria a soma dos números s com menos adenda ...

teste:

  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

O problema disso: Não encontra solução que tenha algum número repetido na soma ...

C ++ (clang) , 198 bytes

#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;}

Experimente 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