Fermats polygonaler Zahlensatz

24

Der polygonale Zahlensatz von Fermat besagt, dass jede positive ganze Zahl als die Summe von höchstens -gonalen Zahlen ausgedrückt werden kann. Dies bedeutet, dass jede positive ganze Zahl als Summe von bis zu drei Dreieckszahlen, vier Quadratzahlen, fünf Fünfeckzahlen usw. ausgedrückt werden kann. Ihre Aufgabe ist es, eine positive ganze Zahl und eine ganze Zahl und die auszugeben -gonale ganze Zahlen, die sich zu summieren .n nxs3sx

Die - te -gonal ganze Zahl, wobei und , können in ein paar Arten definiert werden. Der nicht-mathematische Weg ist, dass die te eckige Zahl als reguläres Polygon mit Seiten mit jeweils der Länge n konstruiert werden kann . Zum Beispiel für s = 3 (Dreieckszahlen):nsn1s3nssns=3

Dreiecke

Sehen Sie hier für Beispiele mit einem größeren s .

Die Mathematik-y - Definition wird durch die Formel für die Verwendung von P(n,s) , die die Ausbeuten n -te s -gonal Nummer:

P(n,s)=n2(s2)n(s4)2

Das ist in der Wikipedia-Seite hier angegeben .

Eingang

Zwei positive ganze Zahlen s und x mit der Bedingung s3 . Sie können diese Ganzzahlen in der natürlichsten Darstellung in Ihrer Sprache eingeben (Dezimal-, Unär-, Kirchenzahlen, Gleitkommazahlen mit ganzzahligen Werten usw.).

Ausgabe

Eine Liste von ganzen Zahlen, L , mit einer maximalen Länge von s , wobei die Summe von L gleich ist , x und alle ganzen Zahlen in L sind s -gonal ganze Zahlen sind . Auch hier können die Ganzzahlen in der natürlichen Darstellung in Ihrer Sprache mit einem eindeutigen, konsistenten Trennzeichen ausgegeben werden (also Nicht-Dezimalzeichen für die Dezimalausgabe, ein Zeichen, das sich von dem für die unäre Ausgabe usw. unterscheidet).

Regeln

  • Die Ein- oder Ausgänge überschreiten niemals die Ganzzahlgrenze für Ihre Sprache
  • L muss nicht bestellt werden
  • Bei mehreren möglichen Ausgaben sind einige oder alle akzeptabel
  • Das ist also gewinnt der kürzeste Code in Bytes

Testfälle

   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
Caird Coinheringaahing
quelle
Sandbox Post
Caird Coinheringaahing
Kann die Ausgabe eine Auffüllung von Null aufweisen? Wenn wir zum Beispiel in Betracht ziehen, x=17, s=5könnten wir 5,12,0,0,0statt nur ausgeben 5,12?
7.
@flawr Solange die Länge des Arrays nicht überschreitet , auch mit Polsterung, ist das in Ordnungs
Caird Coinheringaahing
Sind Wiederholungen zulässig oder sollte ich Qmeiner Einreichung eine hinzufügen ?
Jonathan Allan
@ JonathanAllan Wiederholte Ausgaben sind vollkommen in Ordnung (wenn mehrere Lösungen
ausgegeben

Antworten:

6

Haskell , 78 80 77 Bytes

Wir berechnen das kartesische Produkt der ersten n s-gonal Zahlen und finden dann den ersten Eintrag , dass Summen 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

Probieren Sie es online!

fehlerhaft
quelle
6

JavaScript (ES6),  83-80  Byte

Eine schnelle rekursive Suche, die den kleinsten Ausdruck der Ausgabe maximiert.

Übernimmt die Eingabe als (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])

Probieren Sie es online!

Formel

sn=0P(n+1,s)

P(n+1,s)=((n+1)2(s-2)-(n+1)(s-4))/2=(n2(s-2)+ns+2)/2=-(n+1)((n-1)-ns/2)

Das kann in 14 Bytes geschrieben werden:

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

Kommentiert

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
Arnauld
quelle
@AZTECCO Ich kann versuchen, es später zu beheben. Vorerst entfernt.
Arnauld
Vielen Dank. Auf es warten!
AZTECCO
4

Haskell , 55 Bytes

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

Probieren Sie es online!

Gibt alle möglichen Lösungen aus. Definiert die s-gonalen Zahlen als die kumulative Summe des arithmetischen Fortschritts

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

Gelee , 17 Bytes

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

Eine (sehr sehr ineffiziente) dyadische Linkannahme slinks und xrechts, die die kürzestmögliche Antwort als Liste von Ganzzahlen liefert (aufsteigend sortiert).

Probieren Sie es online! - nicht viel Sinn, es für viel höhere Werte zu versuchen!

Wie?

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]
Jonathan Allan
quelle
@AZTECCO Das ist vollkommen in Ordnung, bei TIO tritt dort eine Zeitüberschreitung von 60 Sekunden auf (ich bin mir ziemlich sicher, dass sogar eine weitaus geringere Eingangszahl als die Zeitüberschreitung auftritt). Wie ich in meiner Antwort hervorhob, ist dies "sehr, sehr ineffizient" und es gibt "nicht viel Sinn, es für viel höhere Werte zu versuchen!". Denken Sie daran, dass der für eine Code-Golf-Lösung angegebene Code nur mit unendlichen Ressourcen ausgeführt werden muss.
Jonathan Allan
ok ich habe mit s = 3 und n = 5 getestet und es hat 12 sekunden gedauert !! Ich mag diese ineffiziente Lösung und ich vertraue Ihnen, auch wenn es fast unmöglich ist, sie zu testen :) Danke!
AZTECCO
1
xs
3

Ruby , 79 Bytes

n ss

n2(s-2)-n(s-4)2n(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}}

Probieren Sie es online!

Wert Tinte
quelle
2

Netzhaut , 111 Bytes

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

Probieren Sie es online! Link enthält Testfälle. Übernimmt die Eingabe in der Reihenfolge s n. Erläuterung:

\d+
*

In Unary konvertieren.

~(`

Behandeln Sie die verbleibenden Phasen nach der Verarbeitung wie ein Retina-Programm und führen Sie sie an derselben Eingabe aus.

$
$"

Dupliziere die Linie.

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

Ersetzen Sie die erste Kopie durch einen regulären Ausdruck, der die erste Zahl überspringt und dann mit s s-gonalen Zahlen übereinstimmt. Die Zahlen selbst werden in ungeraden Erfassungsgruppen erfasst und die geraden Erfassungsgruppen werden verwendet, um sicherzustellen, dass alle Zahlen s-gonal sind.

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

Ersetzen Sie die zweite Kopie durch eine durch Leerzeichen getrennte Liste der ungeraden Erfassungsgruppen.

Der generierte Code für eine Eingabe von 5 17lautet beispielsweise wie folgt:

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

APL (NARS), 149 Zeichen, 298 Byte

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}

falls nicht, Lösungen "0 = ≢b" finden, dann n mal 1 für (ns) -Eingabe zurückgeben; sonst würde es die Summe von s Zahlen zurückgeben, die weniger addend hat ...

Prüfung:

  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

Das Problem dabei: Es gibt keine Lösung, einige Zahlen wiederholen sich in der Summe ...

RosLuP
quelle
0

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

Probieren Sie es 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
AZTECCO
quelle