Vamos a dividir un enrejado

8

Digamos que tenemos una red n × n ; entonces podemos dividir la red en dos secciones dibujando una línea a través de la red. Todo a un lado de la línea está en un conjunto y todo lo demás en otro.

¿De cuántas maneras podemos dividir la red de la manera?

Por ejemplo, tomemos una red 2 × 2 :

. .
. .

Podemos hacer 2 particiones dividiendo la red por la mitad así:

× ×    × o
o o    × o

También podemos dividir cada una de las esquinas:

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

Por último, podemos poner todos los puntos en una partición al perder la red por completo:

× ×
× ×

Esto hace un total de 7 particiones. Tenga en cuenta que la siguiente partición no es válida porque no se puede hacer con una sola línea recta.

× o
o ×

Aquí hay una red 3 × 3

. . .
. . .
. . .

Hay 4 particiones puramente horizontales o verticales

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

Hay 4 particiones de esquina

× 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

Hay 4 particiones de esquina más grandes

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

Hay 8 particiones de esquinas parciales

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

Hay 8 divisiones de movimiento de caballeros

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

Y hay una partición completa

× × ×
× × ×
× × ×

Eso hace 29 particiones en total.

Tarea

Dado un número n como entrada, genera el número de particiones que se pueden hacer de esta manera de una red n × n .

Esta es una pregunta de , por lo que las respuestas se puntuarán en bytes, con menos bytes mejor.

Casos de prueba

Aquí están los primeros 34 cortesía de la 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
fuente
¿Puede agregar un ejemplo con una red más grande que 2 × 2?
Erik the Outgolfer
@EriktheOutgolfer Añadido.
Ad Hoc Garf Hunter

Respuestas:

2

JavaScript (ES6), 113 111 bytes

Guardado 2 bytes gracias a guest44851

0 indexado.

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

Basado en la fórmula mencionada en OEIS:

Sea V (m, n) = Suma_ {i = 1..m, j = 1..n, mcd (i, j) = 1} (m + 1-i) (n + 1-j)
a (n +1) = 2 (n 2 + n + V (n, n)) + 1

Manifestación

Arnauld
fuente
Se puede reemplazar a==1&&con a<2&&.
@ guest44851 Sí, este funciona. :-) ¡Gracias!
Arnauld
También puede reemplazar &&x+x+1con |x+x+1.
1

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

Pruébalo en línea!

ovs
fuente
R=range? ¿Eso ahorraría algunos bytes?
Zacharý
@ Zacharý no con dos rangos
2017
1

Jalea , 14 bytes

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

Pruébalo en línea!

Explicación

ạþ`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
millas
fuente
1

Mathematica, 59 bytes

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

cortesía de la OEIS (al igual que la pregunta)

-1 byte de @ovs

Pruébalo en línea!

J42161217
fuente
1
Esto es casi literalmente copiado de la página OEIS
nmjcman101
3
La pregunta es cortesía de la OEIS y también lo es esta respuesta. Una pregunta original tendría una respuesta original
J42161217
3
No estoy en desacuerdo con ustedes, por eso no voté en contra, simplemente prefiero la transparencia.
nmjcman101
44
¡Yo también! Pero creo que las preguntas OEIS son un truco fácil para obtener puntos de reputación fáciles. Es por eso que respondo de la misma manera, para indicar esta situación
J42161217
Se puede reemplazar ==1con <2 TIO .
ovs
0

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