Twierdzenie o liczbie wielobocznej Fermata

24

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 s3) i wyprowadzenie s -gonalne liczby całkowite, które sumują się do x .

n -tej s -gonal całkowitą, gdzie n1 i s3) , 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):

trójkąty

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:

P.(n,s)=n2)(s-2))-n(s-4)2)

który jest podany na stronie Wikipedii tutaj .

Wkład

Dwie dodatnie liczby całkowite, s i x , z warunkiem s3) . 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 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
Cairney Coheringaahing
źródło
Sandbox post
caird coinheringaahing
Czy dane wyjściowe mogą mieć wypełnienie zerowe? Na przykład, jeśli weźmiemy pod uwagę, x=17, s=5czy moglibyśmy produkować 5,12,0,0,0zamiast po prostu 5,12?
flawr
@flawr Tak długo, jak długość tablicy nie przekracza , nawet przy wypełnieniu, to w porządkus
caird coinheringaahing
Czy powtórzenia są dozwolone, czy powinienem dodać Qdo mojego zgłoszenia?
Jonathan Allan
@JonathanAllan Powtarzane dane wyjściowe są całkowicie w porządku (w przypadku wyświetlania wielu rozwiązań)
Cairney Coinheringaahing

Odpowiedzi:

6

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!

wada
źródło
6

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

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

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
Arnauld
źródło
@AZTECCO Mogę spróbować to naprawić później. Na razie usunięty.
Arnauld
Dzięki. Czekając na to!
AZTECCO
4

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, ...
xnor
źródło
3

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]
Jonathan Allan
źródło
@AZTECCO To w porządku, limit czasu na TIO wynosi 60 sekund (jestem prawie pewien, że nawet znacznie mniejszy numer wejściowy przekroczy limit czasu). Jak wskazuję w mojej odpowiedzi, jest to „bardzo bardzo nieefektywne” i że „nie ma większego sensu próbowanie przy znacznie wyższych wartościach!”. Pamiętaj, że kod podany dla rozwiązania code-golf wymaga jedynie pracy przy nieskończonych zasobach.
Jonathan Allan
ok testowałem przy s = 3 in = 5 i zajęło to 12 sekund !! Podoba mi się to nieefektywne rozwiązanie i zaufam ci, nawet jeśli przetestowanie go jest prawie niemożliwe :) dziękuję!
AZTECCO
1
xs
3

Rubinowy , 79 bajtów

n ss

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

Wartość tuszu
źródło
2

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
Neil
źródło
1

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 ...

RosLuP
źródło
0

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
AZTECCO
źródło