Mari kita membagi kisi

8

Katakanlah kita memiliki kisi n × n ; kita kemudian dapat membagi kisi menjadi dua bagian dengan menggambar garis melalui kisi. Segala sesuatu di satu sisi garis dalam satu set dan semua lainnya di sisi lain.

Berapa banyak cara kita membagi kisi dengan cara itu?

Sebagai contoh mari kita ambil 2 × 2 kisi:

. .
. .

Kita dapat membuat 2 partisi membagi kisi menjadi dua seperti:

× ×    × o
o o    × o

Kami juga dapat mempartisi masing-masing sudut:

× o    o ×    o o    o o
o o    o o    × o    o ×

Terakhir kita dapat meletakkan semua poin dalam satu partisi dengan melewatkan kisi sepenuhnya:

× ×
× ×

Ini membuat total 7 partisi. Perhatikan bahwa partisi berikut ini tidak valid karena tidak dapat dibuat dengan garis lurus tunggal.

× o
o ×

Ini adalah 3 × 3 kisi

. . .
. . .
. . .

Ada 4 partisi murni horizontal atau vertikal

× × ×    × × ×    × o o    × × o
× × ×    o o o    × o o    × × o
o o o    o o o    × o o    × × o

Ada 4 partisi sudut

× o o    o o ×    o o o    o o o    
o o o    o o o    o o o    o o o
o o o    o o o    o o ×    × o o

Ada 4 partisi sudut yang lebih besar

× × o    o × ×    o o o    o o o
× o o    o o ×    o o ×    × o o
o o o    o o o    o × ×    × × o

Ada 8 partisi sudut parsial

× × o    o × ×    o o ×    o o o    o o o    o o o    o o o    × o o
o o o    o o o    o o ×    o o ×    o o o    o o o    × o o    × o o
o o o    o o o    o o o    o o ×    o × ×    × × o    × o o    o o o

Ada 8 ksatria bergerak partisi

× × o    o × ×    × × ×    o o o    o o ×    × o o    o o o    × × ×
× o o    o o ×    o o ×    o o ×    o o ×    × o o    × o o    × o o
× o o    o o ×    o o o    × × ×    o × ×    × × o    × × ×    o o o

Dan ada satu partisi utuh

× × ×
× × ×
× × ×

Itu membuat 29 partisi secara total.

Tugas

Mengingat sejumlah n sebagai input, output jumlah partisi yang dapat dibuat dengan cara ini dari n × n kisi.

Ini adalah pertanyaan sehingga jawaban akan dinilai dalam byte, dengan lebih sedikit byte yang lebih baik.

Uji Kasus

Berikut adalah 34 izin pertama dari OEIS:

1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 361329, 407303

OEIS A114043

Ad Hoc Garf Hunter
sumber
Bisakah Anda menambahkan contoh dengan kisi yang lebih besar dari 2 × 2?
Erik the Outgolfer
@EriktheOutgolfer Ditambahkan.
Ad Hoc Garf Hunter

Jawaban:

2

JavaScript (ES6), 113 111 byte

Disimpan 2 byte berkat guest44851

Diindeks 0.

n=>[...Array(n)].map((_,i,a)=>a.map((_,j)=>x+=(g=(a,b)=>b?g(b,a%b):a<2&&(n-i-1)*(n-j))(i+1,++j)),x=n*++n)|x+x+1

Berdasarkan formula yang disebutkan pada OEIS:

Misalkan V (m, n) = Sum_ {i = 1..m, j = 1..n, gcd (i, j) = 1} (m + 1-i) (n + 1-j)
a (n +1) = 2 (n 2 + n + V (n, n)) + 1

Demo

Arnauld
sumber
Anda bisa menggantinya a==1&&dengan a<2&&.
@ guest44851 Ya, ini berhasil. :-) Terima kasih!
Arnauld
Anda juga bisa mengganti &&x+x+1dengan |x+x+1.
1

Python 2 , 116 byte

lambda n:2*(~-n*n+sum((n-i)*(n-j)*g(i,j)for i in range(1,n)for j in range(1,n)))+1
g=lambda x,y:y and g(y,x%y)or x<2

Cobalah online!

ovs
sumber
R=range? Apakah itu menghemat beberapa byte?
Zacharý
@ Zacharý tidak dengan dua rentang
Ov
1

Jelly , 14 byte

ạþ`Fgþ`FỊS_²H‘

Cobalah online!

Penjelasan

ạþ`Fgþ`FỊS_²H‘  Input: integer n
ạþ`             Form the table of absolute differences on [1, 2, ..., n]
   F            Flatten
    gþ`         Form a GCD table on that
       F        Flatten
        Ị       Test if the absolute value of each is <= 1
         S      Sum (Count the number of true's)
          _     Subtract
           ²    Square of n
            H   Halve
             ‘  Increment
mil
sumber
1

Mathematica, 59 byte

2Sum[(#-i)(#-j)Boole[i~GCD~j<2],{i,#-1},{j,#-1}]+2#^2-2#+1&

milik OEIS (seperti pertanyaannya)

-1 byte dari @ovs

Cobalah online!

J42161217
sumber
1
Ini hampir kata demi kata disalin dari halaman OEIS
nmjcman101
3
Pertanyaannya adalah milik OEIS dan begitu juga jawaban ini. Sebuah pertanyaan asli akan memiliki jawaban asli
J42161217
3
Saya tidak setuju dengan Anda, itulah sebabnya saya tidak memilih, saya hanya memilih transparansi.
nmjcman101
4
Saya juga! Tapi saya pikir pertanyaan OEIS adalah trik mudah untuk mendapatkan poin reputasi yang mudah. Itu sebabnya saya menjawab dengan cara yang sama, untuk menyatakan situasi ini
J42161217
Anda dapat mengganti ==1dengan <2 TIO .
Ov
0

Python 2, 90 byte

lambda n:4*n*n-6*n+3+4*sum((n-i)*(n-k/i)for i in range(n)for k in range(i*i)if k/i*k%i==1)
orlp
sumber