Le théorème des nombres polygonaux de Fermat stipule que chaque entier positif peut être exprimé comme la somme d'au plus -gonaux. Cela signifie que chaque entier positif peut être exprimé comme la somme d'un maximum de trois nombres triangulaires, quatre nombres carrés, cinq nombres pentagonaux, etc. Votre tâche consiste à prendre un entier positif et un entier , et à générer -entiers régionaux qui totalisent .$n$ $n$$x$$s \ge 3$$s$$x$

Le ème entier régional, où et , peut être défini de deux manières. Le non-math-y voie est que la ième nombre -gonal peut être réalisé sous la forme d' un polygone régulier à côtés, chacune de longueur . Par exemple, pour (nombres triangulaires):$n$$s$$n \ge 1$$s \ge 3$$n$$s$$s$$n$$s = 3$

Voir ici pour des exemples avec un plus grand .$s$

La définition mathématique est en utilisant la formule pour , qui donne le ème -nombre régional:$P(n, s)$$n$$s$

qui est donné dans la page Wikipedia ici .

Contribution

Deux entiers positifs, et , avec la condition . Vous pouvez entrer ces nombres entiers dans la représentation la plus naturelle de votre langue (décimal, unaire, chiffres d'église, nombres à virgule flottante à valeur entière, etc.).$s$$x$$s \ge 3$

Production

Une liste de nombres entiers, , d'une longueur maximale de , où la somme de est égale à et tous les entiers de sont nombres entiers -gonal. Encore une fois, les entiers peuvent être sortis dans la représentation naturelle de votre langue, avec n'importe quel séparateur distinct et cohérent (donc des caractères non décimaux pour la sortie décimale, un caractère différent de celui utilisé pour la sortie unaire, etc.)$L$$s$$L$$x$$L$$s$

Règles

• Les entrées ou sorties ne dépasseront jamais la limite entière pour votre langue
• $L$ ne doit pas être commandé
• En cas de sorties multiples possibles, tout ou partie est acceptable
• C'est le code-golf donc le code le plus court en octets gagne

Cas de test

   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 octets

Nous calculons le produit cartésien des $n$ premiers nombres s-gonaux, puis trouvons la première entrée qui résume à $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

Essayez-le en ligne!

JavaScript (ES6),  83  80 octets

Une recherche récursive rapide qui maximise le plus petit terme de la sortie.

Prend l'entrée comme (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])

Essayez-le en ligne!

Formule

Il s'avère plus court d'utiliser une formule basée sur 0 pour calculer les nombres $s$ -gonaux dans JS, c'est-à-dire pour commencer avec $n=0$ et pour calculer $P(n+1,s)$ :

qui peut être écrit en 14 octets:

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

Commenté

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 octets

Réponse de Jelly du port de Jonathan Allan .

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

Essayez-le en ligne!

Haskell , 55 octets

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

Essayez-le en ligne!

Produit toutes les solutions possibles. Définit les nombres s-gonaux comme la somme cumulée de la progression arithmétique

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

Gelée , 17 octets

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

Un lien dyadique (très très inefficace) acceptant sà gauche et xà droite qui donne la réponse la plus courte possible sous forme de liste d'entiers (triés par ordre croissant).

Essayez-le en ligne! - pas grand chose à essayer pour des valeurs beaucoup plus élevées!

Comment?

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]

Rubis , 79 octets

$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}}

Essayez-le en ligne!

Python 3 , 105 octets

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

Essayez-le en ligne!

Réponse JavaScript de Port of Arnauld , alors assurez-vous de lui donner un vote positif!

Rétine , 111 octets

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

Essayez-le en ligne! Le lien inclut des cas de test. Prend entrée dans l'ordre s n. Explication:

\d+
*

Convertissez en unaire.

~(`

Après avoir traité les étapes restantes, traitez-les comme un programme Retina et exécutez-les sur la même entrée.

$
$"

Dupliquez la ligne.

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

Remplacez la première copie par une expression régulière qui saute le premier nombre et correspond ensuite aux s snombres -gonal. Les nombres eux-mêmes sont capturés dans des groupes de capture impairs et les groupes de capture pairs sont utilisés pour garantir que tous les nombres sont s-gonaux.

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

Remplacez la deuxième copie par une liste séparée par des espaces des groupes de capture impairs.

Par exemple, le code généré pour une entrée de 5 17est le suivant:

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

APL (NARS), 149 caractères, 298 octets

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}

sinon trouver des solutions "0 = ≢b" que retourner pour (ns) entrée, n fois 1; sinon il retournerait la somme des nombres s qui a moins d'addend ...

tester:

  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

Le problème de cela: il ne trouve pas de solution a un certain nombre de répétition dans la somme ...

C ++ (clang) , 198 octets

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

Essayez-le en ligne!

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