# Let's divide a lattice

Let's say we have a n × n lattice; we can then divide the lattice into two sections by drawing a line through the lattice. Everything to one side of the line is in one set and everything else in another.

How many ways can we divide the lattice in the manner?

For example lets take a 2 × 2 lattice:

. .
. .


We can make 2 partitions dividing the lattice in half like so:

× ×    × o
o o    × o


We can also partition off each of the corners:

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


Lastly we can put all of the points in one partition by missing the lattice entirely:

× ×
× ×


This makes for a total of 7 partitions. Note that the following partition is not valid because it cannot be made with a single straight line.

× o
o ×


Here is a 3 × 3 lattice

. . .
. . .
. . .


There are 4 purely horizontal or vertical partitions

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


There are 4 corner partitions

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


There are 4 larger corner partitions

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


There are 8 partitions of partial corners

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


There are 8 knights move partitions

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


And there is one whole partition

× × ×
× × ×
× × ×


That makes for 29 partitions in total.

Given a number n as input, output the number of partitions that can be made in this fashion of an n × n lattice.

This is a question so answers will be scored in bytes, with less bytes being better.

## Test Cases

Here are the first 34 courtesy of the 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

• Can you please add an example with a lattice larger than 2×2? Jul 20, 2017 at 18:06
• @EriktheOutgolfer Added. Jul 20, 2017 at 18:16

## JavaScript (ES6), 113 111 bytes

Saved 2 bytes thanks to guest44851

0-indexed.

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


Based on the formula mentioned on OEIS:

Let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)(n+1-j)
a(n+1) = 2(n2 + 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));
}

• You can replace a==1&& with a<2&&.
– user72349
Jul 20, 2017 at 18:01
• @guest44851 Yes, this one works. :-) Thanks! Jul 20, 2017 at 18:05
• You can also replace &&x+x+1 with |x+x+1.
– user72349
Jul 20, 2017 at 18:06

# 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


Try it online!

• R=range? Would that save some bytes? Jul 20, 2017 at 22:51
• @Zacharý not with two ranges
– ovs
Jul 21, 2017 at 4:47

# Jelly, 14 bytes

ạþFgþFỊS_²H‘


Try it online!

## Explanation

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


courtesy of the OEIS (just like the question)

-1 byte from @ovs

Try it online!

• This is almost verbatim copied from the OEIS page Jul 20, 2017 at 17:31
• The question is courtesy of the OEIS and so is this answer. An original question would have an original answer Jul 20, 2017 at 17:35
• I don't disagree with you, which is why I didn't downvote, I just prefer transparency. Jul 20, 2017 at 17:39
• Me too! But I think that OEIS-questions is an easy trick to get easy reputation points. That's why I answer in the same way, to state this situation Jul 20, 2017 at 17:43
• You can replace ==1 with <2 TIO.
– ovs
Jul 20, 2017 at 18:41

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