Teorema bilangan poligon Fermat

24

Teorema bilangan poligon Fermat menyatakan bahwa setiap bilangan bulat positif dapat dinyatakan sebagai jumlah paling banyak -gonal. Ini berarti bahwa setiap bilangan bulat positif dapat dinyatakan sebagai jumlah hingga tiga angka segitiga, empat angka persegi, lima angka pentagonal, dll. Tugas Anda adalah mengambil bilangan bulat positif , dan bilangan bulat , dan untuk menghasilkan - bilangan bulat global yang berjumlah .n nxs≥3sx

The th bilangan bulat -gonal, di mana dan , dapat didefinisikan dalam beberapa cara. Cara non-matematika-y adalah bahwa th jumlah -gonal dapat dibangun sebagai poligon dengan sisi, masing-masing panjang . Misalnya, untuk (angka segitiga):nsn≥1s≥3nssns=3

segitiga

Lihat di sini untuk contoh dengan huruf lebih besar .s

Definisi matematika-y adalah dengan menggunakan rumus untuk , yang menghasilkan ke- ke- :P(n,s)ns

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

yang diberikan di halaman Wikipedia di sini .

Memasukkan

Dua bilangan bulat positif, s dan x , dengan kondisi s≥3 . Anda dapat memasukkan bilangan bulat ini dalam representasi paling alami dalam bahasa Anda (angka desimal, angka unaris, angka angka mengambang bilangan bulat, dll.).

Keluaran

Daftar bilangan bulat, L. , dengan panjang maksimum s , di mana jumlah L. sama dengan dan semua bilangan bulat di adalah bilangan bulat -gonal. Sekali lagi, bilangan bulat dapat ditampilkan dalam representasi alami dalam bahasa Anda, dengan pemisah yang berbeda dan konsisten (jadi karakter non-desimal untuk output desimal, karakter yang berbeda dari yang digunakan untuk output unary, dll.)xL.s

Aturan

  • Input atau output tidak akan pernah melebihi batas integer untuk bahasa Anda
  • L. tidak harus dipesan
  • Dalam hal beberapa kemungkinan keluaran, salah satu atau semua dapat diterima
  • Ini adalah kode-golf sehingga kode terpendek dalam byte menang

Uji kasus

   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
code-golf math sequence number-theory caird coinheringaahing
sumber
Posting Sandbox
caird coinheringaahing
Dapatkah output memiliki beberapa bantalan nol? Sebagai contoh jika kita mempertimbangkan x=17, s=5dapatkah kita menghasilkan 5,12,0,0,0bukan hanya 5,12?
flawr
@ flawr Selama panjang array tidak melebihi , bahkan dengan padding, tidak apa-apas
caird coinheringaahing
Apakah pengulangan diizinkan atau haruskah saya menambahkan Qke kiriman saya?
Jonathan Allan
@JonathanAllan Output berulang baik-baik saja (jika menghasilkan beberapa solusi)
caird coinheringaahing

Jawaban:

6

Haskell , 78 80 77 byte

Kami menghitung produk Cartesian dari pertama n nomor-Gonal s, dan kemudian menemukan entri pertama yang jumlah ke 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

Cobalah online!

cacat
sumber
6

JavaScript (ES6),  83  80 byte

Pencarian rekursif cepat yang memaksimalkan istilah terkecil dari output.

Mengambil input sebagai (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])

Cobalah online!

Rumus

Ternyata menjadi lebih pendek untuk menggunakan rumus berbasis 0 untuk menghitung angka s -gonal di JS, yaitu mulai dengan n=0 dan untuk menghitung 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)

yang dapat ditulis dalam 14 byte:

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

Berkomentar

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
sumber
@AZTECCO Saya mungkin mencoba memperbaikinya nanti. Dihapus untuk saat ini.
Arnauld
Terima kasih. Menunggu itu!
AZTECCO
4

Haskell , 55 byte

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

Cobalah online!

Keluarkan semua solusi yang mungkin. Mendefinisikan angka s-gonal sebagai jumlah kumulatif dari perkembangan aritmatika

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

Jelly , 17 byte

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

Tautan diad (sangat sangat tidak efisien) menerima sdi sebelah kiri dan xdi sebelah kanan yang menghasilkan jawaban sesingkat mungkin sebagai daftar bilangan bulat (diurutkan naik).

Cobalah online! - tidak banyak gunanya mencobanya untuk nilai yang jauh lebih tinggi!

Bagaimana?

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
sumber
@AZTECCO Tidak apa-apa, kali ini keluar pada TIO di sana pada 60 detik (saya cukup yakin nomor input yang jauh lebih kecil daripada yang akan waktu habis). Seperti yang saya tunjukkan dalam jawaban saya, ini "sangat sangat tidak efisien" dan bahwa "tidak banyak gunanya mencobanya untuk nilai yang jauh lebih tinggi!". Ingat, kode yang diberikan untuk solusi kode-golf hanya perlu pekerjaan yang diberikan sumber daya tak terbatas.
Jonathan Allan
ok saya diuji dengan s = 3 dan n = 5 dan butuh 12 detik !! Saya suka solusi yang tidak efisien ini dan saya akan mempercayai Anda, bahkan jika hampir tidak mungkin untuk mengujinya :) terima kasih!
AZTECCO
1
⁸xs
3

Ruby , 79 byte

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

Cobalah online!

Nilai Tinta
sumber
2

Retina , 111 byte

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

Cobalah online! Tautan termasuk kasus uji. Mengambil input dalam urutan s n. Penjelasan:

\d+
*

Konversikan ke unary.

~(`

Setelah memproses tahapan yang tersisa, perlakukan sebagai program Retina dan jalankan pada input yang sama.

$
$"

Gandakan garis.

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

Ganti salinan pertama dengan ekspresi reguler yang melompati angka pertama dan kemudian cocok dengan s sangka -gonal. Angka-angka itu sendiri ditangkap dalam kelompok penangkap aneh dan kelompok penangkap genap digunakan untuk memastikan bahwa semua angka-angka tersebut adalah s-gonal.

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

Ganti salinan kedua dengan daftar yang dipisahkan oleh ruang dari kelompok-kelompok tangkapan aneh.

Sebagai contoh, kode yang dihasilkan untuk input 5 17adalah sebagai berikut:

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

APL (NARS), 149 karakter, 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}

jika tidak menemukan solusi "0 = ≢b" daripada pengembalian untuk input (ns), n kali 1; selain itu akan mengembalikan jumlah angka yang memiliki sedikit penambahan ...

uji:

  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

Masalahnya: Ini tidak menemukan beberapa solusi memiliki beberapa angka yang diulang ...

RosLuP
sumber
0

C ++ (dentang) , 198 byte

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

Cobalah 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
sumber