Vamos dividir uma treliça

8

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

Caçador Ad Hoc Garf
fonte
Você pode adicionar um exemplo com uma treliça maior que 2 × 2?
Erik the Outgolfer
@EriktheOutgolfer Adicionado.
Ad Hoc Garf Hunter

Respostas:

2

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 2 + n + V (n, n)) + 1

Demo

Arnauld
fonte
Você pode substituir a==1&&por a<2&&.
@ guest44851 Sim, este funciona. :-) Obrigado!
Arnauld
Você também pode substituir &&x+x+1por |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

Experimente online!

ovs
fonte
R=range? Isso salvaria alguns bytes?
Zachary
@ Zacharý não com dois intervalos
ovs 21/07
1

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
milhas
fonte
1

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!

J42161217
fonte
1
Isto é quase literalmente copiado da página OEIS
nmjcman101
3
A pergunta é cortesia do OEIS e esta é a resposta. Uma pergunta original teria uma resposta original
J42161217 de 20/07
3
Não discordo de você, e é por isso que não diminuí o voto, apenas prefiro a transparência.
nmjcman101
4
Eu também! Mas acho que as perguntas da OEIS são um truque fácil para obter pontos de reputação fáceis. É por isso que respondo da mesma maneira, para declarar essa situação
J42161217:
Você pode substituir ==1com o <2 TIO .
ovs 20/07/19
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
fonte