Nehmen wir an, wir haben ein n × n- Gitter. Wir können das Gitter dann in zwei Abschnitte unterteilen, indem wir eine Linie durch das Gitter ziehen. Alles auf einer Seite der Linie befindet sich in einem Satz und alles andere in einem anderen.

Auf wie viele Arten können wir das Gitter auf diese Weise teilen?

Nehmen wir zum Beispiel ein 2 × 2- Gitter:

. .
. .

Wir können 2 Partitionen erstellen, die das Gitter wie folgt in zwei Hälften teilen:

× ×    × o
o o    × o

Wir können auch jede der Ecken abtrennen:

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

Zuletzt können wir alle Punkte in einer Partition zusammenfassen, indem wir das Gitter vollständig verfehlen:

× ×
× ×

Dies ergibt insgesamt 7 Partitionen. Beachten Sie, dass die folgende Partition nicht gültig ist, da sie nicht mit einer einzelnen geraden Linie erstellt werden kann.

× o
o ×

Hier ist ein 3 × 3- Gitter

. . .
. . .
. . .

Es gibt 4 rein horizontale oder vertikale Trennwände

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

Es gibt 4 Eckpartitionen

× 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

Es gibt 4 größere Eckwände

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

Es gibt 8 Partitionen von Teilecken

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

Es gibt 8 Ritter, die Trennwände bewegen

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

Und es gibt eine ganze Partition

× × ×
× × ×
× × ×

Das ergibt insgesamt 29 Partitionen.

Aufgabe

Geben Sie bei einer gegebenen Zahl n als Eingabe die Anzahl der Partitionen aus, die auf diese Weise aus einem n × n- Gitter hergestellt werden können.

Dies ist eine Code-Golf- Frage, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

Hier sind die ersten 34 mit freundlicher Genehmigung der 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

JavaScript (ES6), 113 111 Byte

2 Gäste dank gast44851 gespeichert

0-indiziert.

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

Basierend auf der auf OEIS genannten Formel:

Sei V (m, n) = Summe_ {i = 1..m, j = 1..n, gcd (i, j) = 1} (m + 1-i) (n + 1-j)
a (n +1) = 2 (n ² + n + V (n, n)) + 1

Demo

let f =

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

for(n = 0; n < 50; n++) {
  console.log('f(' + n + ') = ' + f(n));
}

Python 2 , 116 Bytes

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

Probieren Sie es online aus!

Gelee , 14 Bytes

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

Probieren Sie es online aus!

Erläuterung

ạþ`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

Mathematica, 59 Bytes

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

Mit freundlicher Genehmigung des OEIS (genau wie die Frage)

-1 Byte von @ovs

Probieren Sie es online aus!

Python 2, 90 Bytes

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)