8
\$\begingroup\$

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.

Task

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

\$\endgroup\$
2
  • \$\begingroup\$ Can you please add an example with a lattice larger than 2×2? \$\endgroup\$ – Erik the Outgolfer Jul 20 '17 at 18:06
  • \$\begingroup\$ @EriktheOutgolfer Added. \$\endgroup\$ – Wheat Wizard Jul 20 '17 at 18:16
2
\$\begingroup\$

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));
}

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ R=range? Would that save some bytes? \$\endgroup\$ – Adalynn Jul 20 '17 at 22:51
  • \$\begingroup\$ @Zacharý not with two ranges \$\endgroup\$ – ovs Jul 21 '17 at 4:47
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ This is almost verbatim copied from the OEIS page \$\endgroup\$ – nmjcman101 Jul 20 '17 at 17:31
  • 3
    \$\begingroup\$ The question is courtesy of the OEIS and so is this answer. An original question would have an original answer \$\endgroup\$ – ZaMoC Jul 20 '17 at 17:35
  • 3
    \$\begingroup\$ I don't disagree with you, which is why I didn't downvote, I just prefer transparency. \$\endgroup\$ – nmjcman101 Jul 20 '17 at 17:39
  • 4
    \$\begingroup\$ 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 \$\endgroup\$ – ZaMoC Jul 20 '17 at 17:43
  • \$\begingroup\$ You can replace ==1 with <2 TIO. \$\endgroup\$ – ovs Jul 20 '17 at 18:41
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.