Digamos que temos uma rede n × n ; podemos então dividir a estrutura em duas seções, desenhando uma linha através da estrutura. Tudo ao lado da linha está em um conjunto e todo o resto em outro.

De quantas maneiras podemos dividir a estrutura da maneira?

Por exemplo, vamos usar uma estrutura 2 × 2 :

. .
. .

Podemos fazer duas partições dividindo a estrutura ao meio da seguinte forma:

× ×    × o
o o    × o

Também podemos particionar cada um dos cantos:

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

Por fim, podemos colocar todos os pontos em uma partição perdendo completamente a rede:

× ×
× ×

Isso totaliza 7 partições. Observe que a partição a seguir não é válida porque não pode ser feita com uma única linha reta.

× o
o ×

Aqui está uma treliça 3 × 3

. . .
. . .
. . .

Existem 4 partições puramente horizontais ou verticais

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

Existem 4 partições de canto

× 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

Existem 4 partições de canto maiores

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

Existem 8 partições de cantos parciais

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

Existem 8 cavaleiros mover partições

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

E há uma partição inteira

× × ×
× × ×
× × ×

Isso representa 29 partições no total.

Tarefa

Dado um número n como entrada, imprima o número de partições que podem ser feitas dessa maneira em uma rede n × n .

Esta é uma questão de código-golfe, para que as respostas sejam pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

Aqui estão as 34 primeiras cortesia do 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 bytes

Guardado 2 bytes graças a guest44851

Indexado a 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

Com base na fórmula mencionada no OEIS:

Seja V (m, n) = Soma {{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

Experimente online!

Gelatina , 14 bytes

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

Experimente online!

Explicação

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

cortesia do OEIS (assim como a pergunta)

-1 byte de @ovs

Experimente online!

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)